W4P3BJJLXCXZEIOGWLTYBFEKD3NWLP2EAGN47ZXPBTHZ5KSC747QC
const std = @import("std");
const path = "../data/day04/input.txt";
const retSize = u16;
const grid_item_size = u7;
const Grid = struct {
boardMap: std.AutoHashMap(grid_item_size, Point),
row: [5]u3 = .{ 0, 0, 0, 0, 0 },
col: [5]u3 = .{ 0, 0, 0, 0, 0 },
pub fn getValue(self: @This()) retSize {
var sum: retSize = 0;
var it = self.boardMap.iterator();
while (it.next()) |item| {
if (!item.value_ptr.marked) {
sum += item.key_ptr.*;
}
}
return sum;
}
};
const Point = struct {
row: u3, // < 5
col: u3, // < 5
marked: bool = false,
};
const Bingo = struct {
numbers: std.ArrayList(grid_item_size),
boards: std.ArrayList(Grid),
};
fn first() anyerror!retSize {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var bg = try parseInput(allocator);
defer { // cleanup code
for (bg.boards.items) |_, idx| {
bg.boards.items[idx].boardMap.deinit();
}
bg.boards.deinit();
bg.numbers.deinit();
}
for (bg.numbers.items) |num| {
for (bg.boards.items) |_, idx| {
// std.debug.print("{any} {any}\n", .{ num, idx });
var curr = &bg.boards.items[idx];
const coord = curr.boardMap.get(num) orelse continue;
curr.row[coord.row] += 1;
curr.col[coord.col] += 1;
try curr.boardMap.put(num, .{ .row = coord.row, .col = coord.col, .marked = true });
// std.debug.print("{any} {any} {any}\n", .{num, curr.row, curr.col});
if ((curr.row[coord.row] == 5) or (curr.col[coord.col] == 5)) {
return num * curr.getValue();
}
}
}
unreachable;
}
fn second() anyerror!retSize {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var bg = try parseInput(allocator);
defer { // cleanup code
for (bg.boards.items) |_, idx| {
bg.boards.items[idx].boardMap.deinit();
}
bg.boards.deinit();
bg.numbers.deinit();
}
var to_remove = std.ArrayList(usize).init(allocator);
defer to_remove.deinit();
for (bg.numbers.items) |num| {
for (bg.boards.items) |_, idx| {
var curr = &bg.boards.items[idx];
const coord = curr.boardMap.get(num) orelse continue;
curr.row[coord.row] += 1;
curr.col[coord.col] += 1;
try curr.boardMap.put(num, .{ .row = coord.row, .col = coord.col, .marked = true });
if ((curr.row[coord.row] == 5) or (curr.col[coord.col] == 5)) {
if (bg.boards.items.len == 1) {
return num * curr.getValue();
} else {
try to_remove.append(idx);
}
}
}
std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));
for (to_remove.items) |idx| {
bg.boards.items[idx].boardMap.deinit();
_ = bg.boards.swapRemove(idx);
}
try to_remove.resize(0);
}
unreachable;
}
fn parseInput(allocator: std.mem.Allocator) anyerror!Bingo {
const input = @embedFile(path);
var lines = std.mem.split(u8, input, "\n");
var ret = Bingo{
.numbers = std.ArrayList(grid_item_size).init(allocator),
.boards = std.ArrayList(Grid).init(allocator),
};
var gridRow: u3 = 0;
var gridCol: u3 = 0;
var g = Grid{ .boardMap = std.AutoHashMap(grid_item_size, Point).init(allocator) };
var idx: usize = 0;
while (lines.next()) |line| : (idx += 1) {
// read in numbers
if (idx == 0) {
var nums = std.mem.tokenize(u8, line, ",");
while (nums.next()) |num| {
try ret.numbers.append(try std.fmt.parseUnsigned(grid_item_size, num, 10));
}
continue;
}
// std.debug.print("line: {any}\n", .{line});
// read in Grids
var items = std.mem.tokenize(u8, line, " ");
while (items.next()) |item| {
const value = try std.fmt.parseUnsigned(grid_item_size, item, 10);
// std.debug.print("{any} -> {any} {any}\n", .{value, gridRow, gridCol});
try g.boardMap.put(value, .{ .row = gridRow, .col = gridCol });
gridCol += 1;
}
gridCol = 0;
if (line.len != 0) gridRow += 1;
// append grid
if (gridRow == 5) {
try ret.boards.append(g);
gridRow = 0;
gridCol = 0;
// create new grid
g = Grid{ .boardMap = std.AutoHashMap(grid_item_size, Point).init(allocator) };
}
}
return ret;
}
pub fn main() anyerror!void {
var timer = try std.time.Timer.start();
_ = try first();
const f = timer.lap() / 1000;
_ = try second();
const s = timer.lap() / 1000;
std.debug.print("Day 4 \t\tfirst: {d}µs \t\tsecond: {d}µs\n", .{ f, s });
}
test "first" {
try std.testing.expectEqual(@as(retSize, 11536), try first());
}
test "second" {
try std.testing.expectEqual(@as(retSize, 1284), try second());
}
72,86,73,66,37,76,19,40,77,42,48,62,46,3,95,17,97,41,10,14,83,90,12,23,81,98,11,57,13,69,28,63,5,78,79,58,54,67,60,34,39,84,94,29,20,0,24,38,43,51,64,18,27,52,47,74,59,22,85,65,80,2,99,70,33,91,53,93,9,82,8,50,7,56,30,36,89,71,21,49,31,88,26,96,16,1,75,87,6,61,4,68,32,25,55,44,15,45,92,35
58 60 65 4 91
73 31 80 83 44
98 47 33 21 25
76 6 41 94 50
55 30 52 11 36
8 27 21 18 94
59 3 47 1 64
67 16 90 20 83
26 43 87 82 4
19 93 89 48 72
28 31 21 56 35
63 98 25 65 61
46 11 91 24 34
76 22 15 0 87
83 80 39 12 71
48 9 95 18 12
67 20 40 29 51
0 85 21 69 89
71 81 97 64 13
75 24 65 50 56
1 27 24 93 42
47 71 21 91 88
39 7 65 64 51
28 16 15 25 56
48 23 32 20 22
26 37 62 13 82
53 54 16 50 75
42 18 51 64 60
25 47 71 38 77
27 57 29 76 40
97 20 68 90 70
42 96 62 49 27
56 67 12 13 94
71 35 31 54 17
73 3 5 23 19
43 93 19 7 80
88 37 51 49 58
29 97 17 94 65
61 22 75 98 85
28 73 84 47 1
96 99 82 7 91
43 32 48 39 60
49 51 15 30 11
16 72 52 69 18
79 95 41 68 59
90 3 81 44 99
9 40 94 19 37
41 52 43 83 46
2 42 26 24 70
49 74 34 66 77
59 83 91 44 0
62 85 69 18 8
74 5 94 48 32
50 46 25 6 96
87 41 75 22 31
36 61 69 96 87
77 60 49 32 45
92 97 34 21 70
31 62 6 63 2
56 93 26 54 85
30 96 54 85 82
29 92 1 74 42
63 26 65 34 98
87 91 6 53 64
62 45 13 50 56
3 67 61 56 23
34 48 39 76 37
44 83 35 72 29
70 45 55 47 4
31 92 6 99 59
9 42 99 80 14
81 57 72 63 18
19 67 25 90 58
0 4 51 52 69
93 60 73 28 23
5 27 68 24 35
69 67 49 1 79
73 64 4 42 32
55 74 44 90 45
92 43 33 2 3
7 45 24 51 33
71 66 6 13 23
77 55 76 48 44
39 70 43 36 32
88 5 69 47 92
45 40 5 93 80
64 37 10 35 4
11 6 75 30 38
74 44 26 90 99
1 81 8 50 32
92 71 59 47 32
45 65 68 55 28
99 88 17 36 82
16 22 61 48 93
29 5 69 24 51
88 85 54 41 92
10 67 40 4 30
29 45 32 47 51
96 81 94 58 34
39 72 7 46 98
52 33 11 60 69
19 9 88 93 75
82 45 72 48 44
85 61 87 79 26
71 80 21 0 3
60 1 57 93 81
17 32 61 21 4
76 24 46 98 33
9 84 91 6 23
5 59 52 96 54
22 35 20 41 4
57 8 9 97 10
19 25 12 65 53
5 50 91 32 23
58 96 15 7 78
90 78 31 47 88
81 56 55 95 10
60 42 68 34 57
53 64 85 50 35
48 16 89 93 77
64 4 0 7 16
58 50 37 98 34
85 71 75 22 57
81 91 6 86 19
61 63 95 40 3
66 88 55 0 32
68 9 98 73 36
15 45 39 67 6
91 11 79 23 84
12 80 62 14 17
79 31 43 75 97
54 78 87 60 99
41 34 32 61 26
44 37 20 12 18
16 73 10 71 22
92 83 15 36 27
28 21 35 42 18
60 87 41 38 95
45 10 70 5 80
11 30 56 17 61
63 25 57 42 14
24 71 2 11 93
56 73 16 47 28
87 64 8 27 83
21 50 78 48 62
18 29 90 1 16
39 72 21 88 55
19 13 69 83 71
7 97 43 58 61
23 96 9 33 81
36 13 32 1 11
57 17 91 76 72
29 83 35 68 90
87 12 39 19 0
99 31 16 25 43
5 52 64 73 40
0 1 51 3 14
61 91 55 30 88
33 83 31 13 71
24 97 36 19 53
81 15 67 72 78
20 21 40 96 37
13 5 33 83 66
22 61 91 56 84
35 86 75 41 46
28 29 73 84 26
42 54 3 15 12
34 16 62 91 30
53 13 5 46 55
67 18 1 59 24
16 39 26 11 67
36 20 62 27 78
85 25 9 87 66
6 70 60 98 59
94 46 17 81 10
35 86 49 59 38
88 54 68 17 87
10 9 90 30 62
82 20 32 77 76
81 83 79 0 67
26 9 63 23 45
22 44 36 60 4
84 91 54 6 78
94 2 62 61 31
52 88 42 21 29
1 32 44 0 9
13 36 26 6 17
50 74 14 51 88
25 10 73 43 16
47 68 34 2 81
74 67 38 24 32
46 53 63 18 82
33 41 48 90 5
56 3 20 99 17
96 94 59 21 87
49 72 39 25 62
59 99 27 53 98
33 46 92 38 8
18 82 90 70 20
3 2 54 0 75
54 34 45 0 19
95 11 27 62 50
3 77 79 17 81
74 57 40 83 47
88 72 39 92 16
65 1 91 71 67
81 23 34 48 90
28 92 84 11 3
5 8 61 16 76
83 46 24 55 82
42 87 55 23 59
79 54 81 48 95
61 16 44 13 91
53 98 72 30 88
65 69 83 36 64
45 80 47 27 78
54 36 16 75 1
17 26 68 28 39
43 87 49 0 89
56 24 7 85 92
18 50 95 70 49
44 47 69 92 54
96 28 79 67 16
13 31 29 98 14
53 20 5 66 25
88 33 27 97 67
20 69 22 35 0
50 73 70 52 91
71 32 48 21 65
3 5 15 30 86
77 85 98 6 11
15 53 21 89 67
51 40 62 8 36
37 69 47 24 29
39 63 64 72 44
13 7 80 86 29
45 91 82 41 42
69 74 12 68 38
84 51 6 10 14
57 26 62 17 24
31 88 98 2 11
33 40 23 30 43
25 16 50 41 22
12 51 99 6 89
91 66 90 97 32
22 74 70 98 54
25 20 76 40 38
21 99 69 10 41
11 59 46 61 36
87 50 49 84 78
57 25 39 22 86
37 8 61 78 73
49 30 95 3 44
18 1 58 91 46
24 64 17 13 60
61 10 14 53 83
32 28 66 65 40
63 86 48 76 6
92 69 95 24 55
59 71 72 30 33
47 76 18 53 56
37 42 9 28 2
0 80 99 48 27
79 20 15 5 54
3 7 71 89 87
31 8 16 28 79
56 77 66 59 36
9 99 85 57 6
67 82 73 87 91
37 52 43 58 81
9 2 96 51 64
68 30 36 3 66
33 57 41 83 52
90 84 54 20 56
14 88 62 76 38
17 86 75 54 5
13 59 68 87 74
44 62 31 57 98
7 24 36 71 76
69 23 19 70 73
55 40 1 98 24
85 29 39 72 3
80 28 94 67 65
14 70 49 97 90
11 2 74 44 48
49 91 63 99 67
1 69 29 22 81
58 77 62 74 16
9 68 38 6 78
72 24 94 64 76
94 98 58 41 63
77 76 73 62 49
74 38 87 92 46
83 89 48 5 15
26 19 8 44 56
72 21 44 61 99
84 8 66 69 32
12 38 57 86 37
87 74 41 3 91
90 78 45 89 49
22 85 17 59 8
99 43 79 65 84
56 36 66 78 57
50 10 39 67 69
12 14 34 68 23
2 8 58 29 89
53 54 69 19 48
22 52 35 36 6
26 46 44 15 61
21 71 63 83 99
84 25 24 59 95
49 29 26 17 58
39 51 15 72 21
1 13 35 85 11
4 91 18 89 53
49 76 48 58 19
32 11 53 24 67
64 12 3 45 31
6 75 44 46 80
59 90 42 39 83
71 25 59 18 12
54 10 77 52 13
42 68 28 17 37
33 82 47 22 24
38 14 79 41 84
81 56 34 28 71
83 27 14 16 30
63 26 6 45 29
86 53 60 50 15
8 43 7 44 91
32 30 59 58 55
76 24 8 79 0
35 14 46 16 99
20 19 98 4 94
74 85 51 31 17
32 37 22 91 52
1 20 88 17 86
64 61 34 23 79
28 42 5 67 72
4 94 13 74 14
11 62 72 23 45
60 65 56 81 29
83 64 73 61 1
57 77 2 30 9
10 39 50 28 88
50 17 65 72 16
24 86 42 39 68
20 84 27 98 12
57 41 1 63 32
94 22 38 81 18
45 51 38 88 94
21 24 44 74 63
29 19 26 57 32
40 31 56 80 53
36 70 33 22 93
99 86 22 85 17
74 45 78 67 39
18 42 77 46 27
20 31 40 8 81
73 47 19 96 15
92 54 10 73 24
44 18 74 32 19
69 8 14 46 33
63 57 97 65 3
62 34 4 36 35
71 7 5 3 88
94 79 47 41 28
51 31 91 23 52
99 42 39 87 54
48 59 97 68 4
9 93 86 99 26
14 83 45 43 48
84 23 17 28 4
35 79 47 75 61
54 65 59 81 42
89 99 27 58 96
23 52 50 24 70
47 83 61 5 65
40 19 66 21 0
55 10 13 81 51
26 30 33 1 57
41 60 44 96 70
72 29 24 0 62
76 69 16 21 93
52 48 79 84 14
65 36 74 22 80
21 69 47 31 61
42 50 92 27 18
12 24 91 29 6
28 73 70 76 11
60 79 47 8 30
65 50 54 56 23
14 98 33 25 76
74 71 86 37 66
72 77 85 39 53
71 56 53 3 19
88 99 40 61 37
95 87 8 78 34
54 75 57 96 12
50 98 69 58 94
16 9 85 2 87
88 98 37 13 1
27 42 15 18 22
29 58 25 99 72
38 86 78 91 92
3 21 39 81 76
66 47 80 44 13
59 2 96 17 62
35 51 8 37 41
88 74 14 92 18
71 15 74 60 32
17 67 69 62 80
19 1 78 89 85
22 96 11 8 13
4 86 48 0 61
22 29 68 36 55
73 62 86 31 90
7 75 49 81 46
9 41 83 67 51
32 24 59 5 99
84 94 25 18 57
76 6 98 79 29
42 10 71 89 5
74 78 53 85 51
64 20 49 47 37
95 22 29 37 87
13 54 0 28 74
21 50 49 8 92
81 58 34 2 43
65 19 63 52 76
15 69 67 23 21
82 84 20 83 53
49 59 86 2 31
71 89 68 40 79
76 25 42 22 13
82 11 88 77 92
48 8 61 13 64
32 72 80 67 3
52 4 25 75 94
53 20 33 6 16
41 95 57 46 17
50 3 99 74 28
97 39 73 58 70
75 35 94 51 87
12 44 43 21 71
74 0 85 48 21
42 28 16 6 53
51 25 18 72 47
83 4 37 79 29
96 39 78 44 56
45 60 35 49 4
25 94 68 34 56
54 17 61 74 50
70 48 98 5 14
15 85 21 8 22
29 33 86 96 62
2 43 61 10 46
11 12 76 31 80
88 78 37 92 14
53 57 90 74 1
32 56 43 50 60
0 77 72 51 37
71 40 69 97 38
65 2 67 47 81
54 79 82 84 90
82 26 28 87 93
61 33 38 89 12
25 13 5 37 35
15 67 8 94 16
95 59 64 41 70
85 22 43 18 13
64 73 96 16 84
61 44 12 37 11
47 35 80 32 14
2 41 60 29 86
52 87 78 6 61
50 21 54 4 2
91 1 35 48 72
99 43 69 44 40
30 41 19 29 27
10 20 95 69 22
66 53 77 37 28
51 89 85 48 21
16 14 60 73 43
96 86 12 97 90
48 7 67 47 96
71 61 60 64 18
13 15 57 86 93
46 41 53 88 32
82 65 26 34 10
80 92 2 54 5
0 17 78 81 43
33 15 51 73 61
71 31 47 38 11
52 29 23 97 14
76 52 54 92 80
74 50 11 27 78
63 9 25 38 20
3 90 39 37 15
87 45 17 93 62