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
|
const std = @import("std");
const aoc = @import("aoc");
fn gcd(a: u64, b: u64) u64 {
var ac = a;
var bc = b;
while (true) {
if (ac > bc) {
ac = ac % bc;
if (ac == 0) return bc;
} else {
bc = bc % ac;
if (bc == 0) return ac;
}
}
}
fn lcm(a: u64, b: u64) u64 {
return @divExact(a * b, gcd(a, b));
}
fn waittime(start: u32, busid: u32) u32 {
return (busid - (start % busid)) % busid;
}
fn printRegion(buses: []u32, start: u64, end: u64) void {
aoc.debugfmt(" ", .{});
for (buses) |bus| {
aoc.debugfmt(" {:^5}", .{bus});
}
aoc.debugfmt("\n", .{});
var i = start;
while (i < end) : (i += 1) {
aoc.debugfmt("{:<10}", .{i});
for (buses) |bus| {
var c: u8 = '.';
if (bus > 0 and i % bus == 0) c = 'D';
aoc.debugfmt(" {c} ", .{c});
}
aoc.debugfmt("\n", .{});
}
aoc.debugfmt("\n", .{});
}
fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
_ = args;
var lineit = std.mem.tokenize(u8, input, "\n");
var start = try std.fmt.parseInt(u32, lineit.next().?, 10);
var bestbus: ?u32 = null;
var busit = std.mem.tokenize(u8, lineit.next().?, ",");
while (busit.next()) |bus| {
if (bus[0] == 'x') continue;
const val = try std.fmt.parseInt(u32, bus, 10);
if (bestbus == null or waittime(start, val) < waittime(start, bestbus.?)) {
bestbus = val;
}
}
const answer = bestbus.? * waittime(start, bestbus.?);
return try std.fmt.allocPrint(allocator, "{d}", .{answer});
}
fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
_ = args;
var lineit = std.mem.tokenize(u8, input, "\n");
_ = try std.fmt.parseInt(u32, lineit.next().?, 10);
var busses = std.ArrayList(u32).init(allocator);
defer busses.deinit();
var busit = std.mem.tokenize(u8, lineit.next().?, ",");
const first = try std.fmt.parseInt(u32, busit.next().?, 10);
try busses.append(first);
var offset: u64 = 0;
var cycle: u64 = first;
var delay: u32 = 1;
while (busit.next()) |bus| : (delay += 1) {
if (bus[0] == 'x') {
try busses.append(0);
continue;
}
const val = try std.fmt.parseInt(u32, bus, 10);
try busses.append(val);
var mult: u64 = @divFloor(offset + delay, val);
if ((offset + delay) % val != 0) mult += 1;
while ((mult * val - offset - delay) % cycle != 0) {
mult += std.math.max(1, @divFloor(cycle - (mult * val - offset - delay) % cycle, val));
}
offset = mult * val - delay;
cycle = lcm(cycle, val);
if (aoc.debug) {
printRegion(busses.items, offset, offset + delay + 1);
printRegion(busses.items, offset + cycle, offset + cycle + delay + 1);
aoc.debugfmt("{}\n", .{offset});
}
}
printRegion(busses.items, offset, offset + busses.items.len);
return try std.fmt.allocPrint(allocator, "{}", .{offset});
}
pub const main = aoc.main(part1, part2, .{ "6568", "554865447501099" });
|
