You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
92 lines
2.3 KiB
Zig
92 lines
2.3 KiB
Zig
const std = @import("std");
|
|
|
|
pub fn main() !void {
|
|
const content = @embedFile("data.txt");
|
|
var lines = std.mem.split(u8, content, "\n");
|
|
|
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
|
|
const allocator = gpa.allocator();
|
|
|
|
const instructions = lines.next().?;
|
|
_ = lines.next();
|
|
|
|
var map = std.StringArrayHashMap([]const u8).init(allocator);
|
|
defer map.deinit();
|
|
|
|
while (lines.next()) |line| {
|
|
if (line.len == 0) {
|
|
break;
|
|
}
|
|
|
|
try map.put(line[0..3], line[7..15]);
|
|
}
|
|
|
|
var i: u16 = 0;
|
|
var cur = try allocator.dupe(u8, "AAA");
|
|
while (true) : (i += 1) {
|
|
if (std.mem.eql(u8, cur, "ZZZ")) {
|
|
break;
|
|
}
|
|
const ins = instructions[i % instructions.len];
|
|
const nodes = map.get(cur).?;
|
|
if (ins == 'L') {
|
|
std.mem.copy(u8, cur, nodes[0..3]);
|
|
} else {
|
|
std.mem.copy(u8, cur, nodes[5..8]);
|
|
}
|
|
}
|
|
|
|
std.debug.print("Part 1: {d}\n", .{i});
|
|
|
|
// Part 2
|
|
var nodes = std.ArrayList([]const u8).init(allocator);
|
|
defer nodes.deinit();
|
|
|
|
var steps = std.ArrayList(u32).init(allocator);
|
|
defer steps.deinit();
|
|
|
|
// Find starting nodes
|
|
for (map.keys()) |k| {
|
|
if (k[2] == 'A') {
|
|
try nodes.append(k);
|
|
}
|
|
}
|
|
|
|
// for each starting node, how long until we get to a Z-ending node
|
|
for (nodes.items) |node| {
|
|
var j: u32 = 0;
|
|
cur = try allocator.dupe(u8, node);
|
|
while (true) : (j += 1) {
|
|
// std.debug.print("checking node: {s}\n", .{cur});
|
|
if (cur[2] == 'Z') {
|
|
break;
|
|
}
|
|
const ins = instructions[j % instructions.len];
|
|
|
|
const next = map.get(cur).?;
|
|
if (ins == 'L') {
|
|
std.mem.copy(u8, cur, next[0..3]);
|
|
} else {
|
|
std.mem.copy(u8, cur, next[5..8]);
|
|
}
|
|
}
|
|
try steps.append(j);
|
|
}
|
|
|
|
var lowest: u64 = steps.items[0];
|
|
for (0..steps.items.len - 1) |j| {
|
|
lowest = lcm(lowest, steps.items[j + 1]).?;
|
|
}
|
|
std.debug.print("Part 2: {d}\n", .{lowest});
|
|
}
|
|
|
|
fn lcm(left: u64, right: u64) ?u64 {
|
|
var i: u64 = @max(left, right);
|
|
while (true) : (i += @max(left, right)) {
|
|
if (i % left == 0 and i % right == 0) {
|
|
return @as(u64, @intCast(i));
|
|
}
|
|
}
|
|
return null;
|
|
}
|