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
127
128
129
130
131
132
133
134
135
136
137
138
|
const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const mem = std.mem;
const isDigit = std.ascii.isDigit;
const Self = @This();
const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
const MapOfNumDesc = std.HashMap(NumDesc, void, NumDescCtx, 80);
const NumDesc = struct {
i: u64,
left: u64,
right: u64,
};
const NumDescCtx = struct {
pub fn hash(self: @This(), K: NumDesc) u64 {
_ = self;
return K.left | (K.right << 32);
}
pub fn eql(self: @This(), K1: NumDesc, K2: NumDesc) bool {
_ = self;
// Checking .i and .left can uniquely identify the number in the grid
return K1.i == K2.i and K1.left == K2.left;
}
};
fn isSymbol(c: u8) bool {
return c != '.' and !std.ascii.isDigit(c);
}
fn isGear(c: u8) bool {
return c == '*';
}
fn getNumberAt(map: ArrayList([]const u8), i: u64, j: u64) NumDesc {
var left: u64 = j;
var right: u64 = j;
// Lookahead checking to avoid dropping below 0
while (left > 0 and
isDigit(map.items[i][left - 1])) : (left -= 1)
{}
while (right < map.items.len and
isDigit(map.items[i][right])) : (right += 1)
{}
return NumDesc{
.i = i,
.left = left,
.right = right,
};
}
// Evaluated numbers are managed by the caller for more flexibility.
// P1: Each number is only evaluated once
// P2: Each number may be evaluated an arbitrary number of times
fn findAdjacent(map: ArrayList([]const u8), i: u64, j: u64, evaluated: *MapOfNumDesc) ArrayList(u64) {
var surroundNums = ArrayList(u64).init(allocator);
for (@max(i - 1, 0)..@min(i + 2, map.items.len)) |ai| {
for (@max(j - 1, 0)..@min(j + 2, map.items[0].len)) |aj| {
if (!isDigit(map.items[ai][aj])) {
continue;
}
const p = getNumberAt(map, ai, aj);
const s = map.items[p.i][p.left..p.right];
const n = std.fmt.parseInt(u64, s, 10) catch unreachable;
if (evaluated.contains(p)) {
continue;
}
evaluated.put(p, undefined) catch unreachable;
surroundNums.append(n) catch unreachable;
}
}
return surroundNums;
}
fn part1(map: ArrayList([]const u8)) void {
var ans: u64 = 0;
var evaluated = MapOfNumDesc.init(allocator);
defer evaluated.deinit();
for (map.items, 0..) |line, i| {
for (line, 0..) |c, j| {
if (isSymbol(c)) {
const adj = findAdjacent(map, i, j, &evaluated);
for (adj.items) |adj_num| {
ans += adj_num;
}
}
}
}
print("{d}\n", .{ans});
}
fn part2(map: ArrayList([]const u8)) void {
var ans: u64 = 0;
var evaluated = MapOfNumDesc.init(allocator);
defer evaluated.deinit();
for (map.items, 0..) |line, i| {
for (line, 0..) |c, j| {
if (isGear(c)) {
const adj = findAdjacent(map, i, j, &evaluated);
evaluated.clearRetainingCapacity();
if (adj.items.len == 2) {
ans += adj.items[0] * adj.items[1];
}
}
}
}
print("{d}\n", .{ans});
}
pub fn main() !void {
var splitLines = mem.splitScalar(u8, fin, '\n');
var lines = ArrayList([]const u8).init(allocator);
while (splitLines.next()) |line| {
try lines.append(line);
}
part1(lines);
part2(lines);
}
|
