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
|
const std = @import("std");
const print = std.debug.print;
const assert = std.debug.assert;
const ArrayList = std.ArrayList;
const HashMap = std.HashMap;
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 Rule = struct {
key: u32,
left: u32,
right: u32,
pub fn endsWith(key: u32, e: u8) bool {
return key & 0b1111_1111 == e;
}
pub fn hash(s: []const u8) u32 {
assert(s.len == 3);
return s[2] | (@as(u32, s[1]) << 8) | (@as(u32, s[0]) << 16);
}
pub fn init(text: []const u8) Rule {
var splitTokens = mem.splitAny(u8, text, " =(),");
var nonEmpty = [3]u32{ undefined, undefined, undefined };
var i: usize = 0;
while (splitTokens.next()) |tok| {
if (tok.len != 3) {
continue;
}
nonEmpty[i] = hash(tok);
i += 1;
}
assert(i == 3);
return Rule{
.key = nonEmpty[0],
.left = nonEmpty[1],
.right = nonEmpty[2],
};
}
};
const RuleCtx = struct {
pub fn hash(_: @This(), K: u32) u64 {
return K;
}
pub fn eql(_: @This(), K1: u32, K2: u32) bool {
return K1 == K2;
}
};
const RuleMap = HashMap(u32, Rule, RuleCtx, 80);
fn evaluate(instructions: []const u8, rules: RuleMap, start: u32, isPart1: bool) u64 {
const zzz = Rule.hash("ZZZ");
var curr = start;
var steps: u64 = 0;
while (if (isPart1) (curr != zzz) else !Rule.endsWith(curr, 'Z')) : (steps += 1) {
const in = instructions[steps % instructions.len];
curr = switch (in) {
'L' => rules.get(curr).?.left,
'R' => rules.get(curr).?.right,
else => unreachable,
};
}
return steps;
}
pub fn part1(instructions: []const u8, rules: RuleMap) void {
const ans = evaluate(instructions, rules, Rule.hash("AAA"), true);
print("{d}\n", .{ans});
}
fn gcd(a_: u64, b_: u64) u64 {
var a = a_;
var b = b_;
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a;
}
fn lcm(a: u64, b: u64) u64 {
return a / gcd(a, b) * b;
}
pub fn part2(instructions: []const u8, rules: RuleMap) void {
var ans: u64 = 1;
var keyIt = rules.keyIterator();
while (keyIt.next()) |k| {
if (Rule.endsWith(k.*, 'A')) {
const steps = evaluate(instructions, rules, k.*, false);
ans = lcm(ans, steps);
}
}
print("{d}\n", .{ans});
}
pub fn main() !void {
var splitLines = mem.splitScalar(u8, fin, '\n');
var rules = RuleMap.init(allocator);
var instructions = splitLines.next().?;
_ = splitLines.next();
while (splitLines.next()) |line| {
const R = Rule.init(line);
try rules.put(R.key, R);
}
part1(instructions, rules);
part2(instructions, rules);
}
|
