Restructure repo and update solutions to zig 0.10.1HEADmaster

6 files changed, 266 insertions, 0 deletions

diff --git a/src/13/input b/src/13/input
new file mode 100644
index 0000000..c16c8bb
--- /dev/null
+++ b/src/13/input
@@ -0,0 +1,2 @@
+1001612
+19,x,x,x,x,x,x,x,x,41,x,x,x,37,x,x,x,x,x,821,x,x,x,x,x,x,x,x,x,x,x,x,13,x,x,x,17,x,x,x,x,x,x,x,x,x,x,x,29,x,463,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,23
diff --git a/src/13/input-test b/src/13/input-test
new file mode 100644
index 0000000..d76f619
--- /dev/null
+++ b/src/13/input-test
@@ -0,0 +1,2 @@
+939
+7,13,x,x,59,x,31,19
diff --git a/src/13/main.zig b/src/13/main.zig
new file mode 100644
index 0000000..0252e2b
--- /dev/null
+++ b/src/13/main.zig
@@ -0,0 +1,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" });
diff --git a/src/13/notes b/src/13/notes
new file mode 100644
index 0000000..7930ccf
--- /dev/null
+++ b/src/13/notes
@@ -0,0 +1,6 @@
+3 x 4
+
+    1 (4)
+    2 (8)
+    3 (12)
+    8
diff --git a/src/13/part1 b/src/13/part1
new file mode 100644
index 0000000..b4ffca7
--- /dev/null
+++ b/src/13/part1
@@ -0,0 +1,65 @@
+--- Day 13: Shuttle Search ---
+
+Your ferry can make it safely to a nearby port, but it won't get much further. When you call to book
+another ship, you discover that no ships embark from that port to your vacation island. You'll need
+to get from the port to the nearest airport.
+
+Fortunately, a shuttle bus service is available to bring you from the sea port to the airport!  Each
+bus has an ID number that also indicates how often the bus leaves for the airport.
+
+Bus schedules are defined based on a timestamp that measures the number of
+minutes since some fixed reference point in the past. At timestamp 0, every bus simultaneously
+departed from the sea port. After that, each bus travels to the airport, then various other
+locations, and finally returns to the sea port to repeat its journey forever.
+
+The time this loop takes a particular bus is also its ID number: the bus with ID 5 departs from the
+sea port at timestamps 0, 5, 10, 15, and so on. The bus with ID 11 departs at 0, 11, 22, 33, and so
+on. If you are there when the bus departs, you can ride that bus to the airport!
+
+Your notes (your puzzle input) consist of two lines.  The first line is your estimate of the
+earliest timestamp you could depart on a bus. The second line lists the bus IDs that
+are in service according to the shuttle company; entries that show x must be out of service, so you
+decide to ignore them.
+
+To save time once you arrive, your goal is to figure out the earliest bus you can take to
+the airport. (There will be exactly one such bus.)
+
+For example, suppose you have the following notes:
+
+939
+7,13,x,x,59,x,31,19
+
+Here, the earliest timestamp you could depart is 939, and the bus IDs in service are 7, 13, 59, 31,
+and 19. Near timestamp 939, these bus IDs depart at the times marked D:
+
+time   bus 7   bus 13  bus 59  bus 31  bus 19
+929      .       .       .       .       .
+930      .       .       .       D       .
+931      D       .       .       .       D
+932      .       .       .       .       .
+933      .       .       .       .       .
+934      .       .       .       .       .
+935      .       .       .       .       .
+936      .       D       .       .       .
+937      .       .       .       .       .
+938      D       .       .       .       .
+939      .       .       .       .       .
+940      .       .       .       .       .
+941      .       .       .       .       .
+942      .       .       .       .       .
+943      .       .       .       .       .
+944      .       .       D       .       .
+945      D       .       .       .       .
+946      .       .       .       .       .
+947      .       .       .       .       .
+948      .       .       .       .       .
+949      .       D       .       .       .
+
+The earliest bus you could take is bus ID 59. It doesn't depart until timestamp 944, so you would
+need to wait 944 - 939 = 5 minutes before it departs. Multiplying the bus ID by the number of
+minutes you'd need to wait gives 295.
+
+What is the ID of the earliest bus you can take to the airport multiplied by the number of
+minutes you'll need to wait for that bus?
+
+
diff --git a/src/13/part2 b/src/13/part2
new file mode 100644
index 0000000..c8f8f3b
--- /dev/null
+++ b/src/13/part2
@@ -0,0 +1,79 @@
+--- Part Two ---
+
+The shuttle company is running a contest: one gold coin for anyone that can find the earliest
+timestamp such that the first bus ID departs at that time and each subsequent listed bus ID departs
+at that subsequent minute. (The first line in your input is no longer relevant.)
+
+For example, suppose you have the same list of bus IDs as above:
+
+7,13,x,x,59,x,31,19
+An x in the schedule means there are no constraints on what bus IDs must depart at that time.
+
+This means you are looking for the earliest timestamp (called t) such that:
+
+
+ - Bus ID 7 departs at timestamp t.
+ - Bus ID 13 departs one minute after timestamp t.
+ - There are no requirements or restrictions on departures at two or three minutes after timestamp
+t.
+ - Bus ID 59 departs four minutes after timestamp t.
+ - There are no requirements or restrictions on departures at five minutes after timestamp t.
+ - Bus ID 31 departs six minutes after timestamp t.
+ - Bus ID 19 departs seven minutes after timestamp t.
+
+
+The only bus departures that matter are the listed bus IDs at their specific offsets from t. Those
+bus IDs can depart at other times, and other bus IDs can depart at those times.  For example, in the
+list above, because bus ID 19 must depart seven minutes after the timestamp at which bus ID 7
+departs, bus ID 7 will always also be departing with bus ID 19 at seven minutes after
+timestamp t.
+
+In this example, the earliest timestamp at which this occurs is 1068781:
+
+time     bus 7   bus 13  bus 59  bus 31  bus 19
+1068773    .       .       .       .       .
+1068774    D       .       .       .       .
+1068775    .       .       .       .       .
+1068776    .       .       .       .       .
+1068777    .       .       .       .       .
+1068778    .       .       .       .       .
+1068779    .       .       .       .       .
+1068780    .       .       .       .       .
+1068781    D       .       .       .       .
+1068782    .       D       .       .       .
+1068783    .       .       .       .       .
+1068784    .       .       .       .       .
+1068785    .       .       D       .       .
+1068786    .       .       .       .       .
+1068787    .       .       .       D       .
+1068788    D       .       .       .       D
+1068789    .       .       .       .       .
+1068790    .       .       .       .       .
+1068791    .       .       .       .       .
+1068792    .       .       .       .       .
+1068793    .       .       .       .       .
+1068794    .       .       .       .       .
+1068795    D       D       .       .       .
+1068796    .       .       .       .       .
+1068797    .       .       .       .       .
+
+In the above example, bus ID 7 departs at timestamp 1068788 (seven minutes after t). This is fine;
+the only requirement on that minute is that bus ID 19 departs then, and it does.
+
+Here are some other examples:
+
+
+ - The earliest timestamp that matches the list 17,x,13,19 is 3417.
+ - 67,7,59,61 first occurs at timestamp 754018.
+ - 67,x,7,59,61 first occurs at timestamp 779210.
+ - 67,7,x,59,61 first occurs at timestamp 1261476.
+ - 1789,37,47,1889 first occurs at timestamp 1202161486.
+
+
+However, with so many bus IDs in your list, surely the actual earliest timestamp will be larger than
+100000000000000!
+
+What is the earliest timestamp such that all of the listed bus IDs depart at offsets
+matching their positions in the list?
+
+