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
|
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.tokenizeAny(u8, text, " =(),");
return Rule{
.key = hash(splitTokens.next().?),
.left = hash(splitTokens.next().?),
.right = hash(splitTokens.next().?),
};
}
};
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);
const 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);
}
|
