1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const mem = std.mem;
const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const u32HashSet = std.ArrayHashMap(u32, void, u32HashSetCtx, false);
const u32HashSetCtx = struct {
pub fn hash(self: @This(), K: u32) u32 {
_ = self;
return K;
}
pub fn eql(self: @This(), K1: u32, K2: u32, s: usize) bool {
_ = s;
_ = self;
return K1 == K2;
}
};
const Card = struct {
var cardId: u32 = 1;
id: u32,
winning: u32HashSet,
owned: u32HashSet,
};
fn parseCard(text: []const u8) !Card {
var result = Card{
.id = Card.cardId,
.winning = u32HashSet.init(allocator),
.owned = u32HashSet.init(allocator),
};
Card.cardId += 1;
var prefix = mem.splitScalar(u8, text, ':');
_ = prefix.next(); // ignore 'Card ##' prefix
const postfix = prefix.next() orelse unreachable;
var allNumbers = mem.splitScalar(u8, postfix, '|');
var winningText = mem.splitScalar(u8, allNumbers.next() orelse unreachable, ' ');
var ownedText = mem.splitScalar(u8, allNumbers.next() orelse unreachable, ' ');
// split produces some empty strings that must be ignored later
while (winningText.next()) |numText| {
const num = std.fmt.parseInt(u32, numText, 10) catch continue;
try result.winning.put(num, undefined);
}
while (ownedText.next()) |numText| {
const num = std.fmt.parseInt(u32, numText, 10) catch continue;
try result.owned.put(num, undefined);
}
return result;
}
fn matchesPerCard(cards: ArrayList(Card)) ArrayList(u64) {
var res = ArrayList(u64).init(allocator);
for (cards.items) |card| {
var n: u64 = 0;
for (card.winning.keys()) |win| {
if (card.owned.contains(win)) {
n += 1;
}
}
res.append(n) catch unreachable;
}
return res;
}
pub fn part1(cards: ArrayList(Card)) void {
var ans: u64 = 0;
const matches = matchesPerCard(cards);
defer matches.deinit();
for (matches.items) |nMatches| {
if (nMatches > 0) {
ans += std.math.pow(u64, 2, nMatches - 1);
}
}
print("{d}\n", .{ans});
}
pub fn part2(cards: ArrayList(Card)) void {
var ans: u64 = 0;
var matches = matchesPerCard(cards);
var copies = ArrayList(u64).init(allocator);
defer {
matches.deinit();
copies.deinit();
}
copies.resize(matches.items.len) catch unreachable;
@memset(copies.items, 1);
for (matches.items, copies.items, 0..) |m, c, i| {
for (i + 1..i + 1 + m) |j| {
copies.items[j] += c;
}
ans += c;
}
print("{d}\n", .{ans});
}
pub fn main() !void {
var splitLines = mem.splitScalar(u8, fin, '\n');
var cards = ArrayList(Card).init(allocator);
defer cards.deinit();
while (splitLines.next()) |line| {
const c = try parseCard(line);
try cards.append(c);
}
part1(cards);
part2(cards);
}
|
