Restructure repo and update solutions to zig 0.10.1HEADmaster

6 files changed, 334 insertions, 0 deletions

diff --git a/src/23/input b/src/23/input
new file mode 100644
index 0000000..db9c9c6
--- /dev/null
+++ b/src/23/input
@@ -0,0 +1 @@
+476138259
diff --git a/src/23/input-test b/src/23/input-test
new file mode 100644
index 0000000..ab40847
--- /dev/null
+++ b/src/23/input-test
@@ -0,0 +1 @@
+389125467
diff --git a/src/23/main.zig b/src/23/main.zig
new file mode 100644
index 0000000..0754ab8
--- /dev/null
+++ b/src/23/main.zig
@@ -0,0 +1,194 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+// Links in this list are arranges in a circle
+const RingLink = struct {
+    data: u32,
+    next: *RingLink,
+    const Self = @This();
+
+    pub fn insertNext(self: *Self, link: *RingLink) void {
+        link.next = self.next;
+        self.next = link;
+    }
+
+    pub fn popNext(self: *Self) !*Self {
+        const nlink = self.next;
+        if (nlink == self) return error.EmptyRingList;
+        self.next = nlink.next;
+        return nlink;
+    }
+
+    pub fn length(self: *Self) usize {
+        var count: usize = 1;
+        var link = self.next;
+        while (link != self) : (link = link.next) {
+            count += 1;
+        }
+        return count;
+    }
+
+    pub fn advance(self: *Self, count: usize) *RingLink {
+        var link = self;
+        var counter: usize = 0;
+        while (counter < count) : (link = link.next) {
+            counter += 1;
+        }
+        return link;
+    }
+};
+
+fn printLinks(start: *RingLink, end: *RingLink, skipfirst: bool) void {
+    var link = start;
+    var b = skipfirst;
+    while (b or link != end) : (link = link.next) {
+        b = false;
+        aoc.debugfmt("{} ", .{link.data});
+    }
+}
+
+fn parseInput(input: []const u8, lookup: []RingLink, list: *?*RingLink) !u32 {
+    var max: u32 = 0;
+    var link: *RingLink = undefined;
+    for (input) |c, i| {
+        if (c == '\n') break;
+        const v = try std.fmt.parseInt(u32, input[i .. i + 1], 10);
+        if (v > max) max = v;
+        if (list.* == null) {
+            list.* = &lookup[v];
+            link = list.*.?;
+            link.next = link;
+        } else {
+            link.insertNext(&lookup[v]);
+            link = link.next;
+        }
+    }
+    return max;
+}
+
+fn doRound(list: *RingLink, len: u32, lookup: []RingLink, current: **RingLink, max: u32, round: usize) !void {
+    _ = list;
+    var target = (current.*.data + max - 2) % max + 1;
+    var k: usize = 0;
+    var check = current.*.next;
+    while (k < 9) : (k += 1) {
+        if (check.data == target)
+            target = (target + max - 2) % max + 1;
+
+        check = if (k % 3 == 0) current.*.next else check.next;
+    }
+    var closest = &lookup[target];
+
+    if (aoc.debug) {
+        aoc.debugfmt("\n-- move {} --\ncups:", .{round});
+
+        if (aoc.debuglvl == 1) {
+            var start = current.*.advance(len - ((round - 1) % len));
+            var link = start;
+            while (true) {
+                if (link == current.*) {
+                    aoc.debugfmt(" ({})", .{link.data});
+                } else {
+                    aoc.debugfmt("  {} ", .{link.data});
+                }
+                link = link.next;
+                if (link == start) break;
+            }
+            aoc.debugfmt("\n", .{});
+        } else {
+            aoc.debugfmt("\n{} {} {}\n", .{ current.*.data, target, closest.data });
+            aoc.debugfmt(".. ", .{});
+            printLinks(current.*, current.*.next.next.next.next, false);
+            aoc.debugfmt("..\n.. ", .{});
+            printLinks(closest, closest.next.next.next.next, false);
+            aoc.debugfmt("..\n", .{});
+        }
+    }
+
+    var i: usize = 0;
+    while (i < 3) : (i += 1) {
+        const poplink = try current.*.popNext();
+        closest.insertNext(poplink);
+        closest = poplink;
+    }
+
+    current.* = current.*.next;
+}
+
+fn createLookup(allocator: std.mem.Allocator, len: usize) ![]RingLink {
+    var lookup = try allocator.alloc(RingLink, len + 1);
+    errdefer allocator.free(lookup);
+
+    var i: usize = 1;
+    while (i <= len) : (i += 1) {
+        lookup[i] = RingLink{ .data = @intCast(u32, i), .next = undefined };
+    }
+
+    return lookup;
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+    _ = args;
+
+    var lookup = try createLookup(allocator, 9);
+    defer allocator.free(lookup);
+
+    var list: ?*RingLink = null;
+    const max = try parseInput(input, lookup, &list);
+    if (list == null) return aoc.Error.InvalidInput;
+    const real_len = @intCast(u32, list.?.length());
+
+    var round: usize = 0;
+    var current = list.?;
+    while (round < 100) : (round += 1) {
+        try doRound(list.?, real_len, lookup, &current, max, round + 1);
+    }
+
+    var start = &lookup[1];
+    var link = start.next;
+
+    var parts = std.ArrayList(u8).init(allocator);
+    defer parts.deinit();
+    while (link != start) : (link = link.next) {
+        try parts.append('0' + @intCast(u8, link.data));
+    }
+
+    return try std.fmt.allocPrint(allocator, "{s}", .{parts.items});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+    _ = args;
+
+    var lookup = try createLookup(allocator, 1000000);
+    defer allocator.free(lookup);
+
+    var list: ?*RingLink = null;
+    _ = try parseInput(input, lookup, &list);
+    if (list == null) return aoc.Error.InvalidInput;
+    const real_len = list.?.length();
+
+    var end = list.?.advance(real_len - 1);
+    var i = real_len + 1;
+    while (i <= 1000000) : (i += 1) {
+        end.insertNext(&lookup[i]);
+        end = end.next;
+    }
+
+    var round: usize = 0;
+    var current = list.?;
+    while (round < 10000000) : (round += 1) {
+        if (round % 1000000 == 0) aoc.debugfmt(".", .{});
+        try doRound(list.?, 1000000, lookup, &current, 1000000, round + 1);
+    }
+    aoc.debugfmt("\n", .{});
+
+    var link = (&lookup[1]).next;
+
+    const a = @intCast(u64, link.data);
+    const b = @intCast(u64, link.next.data);
+    aoc.debugfmt("{} * {} = {}\n", .{ a, b, a * b });
+
+    return try std.fmt.allocPrint(allocator, "{}", .{a * b});
+}
+
+pub const main = aoc.main(part1, part2, .{ "97245386", "156180332979" });
diff --git a/src/23/notes b/src/23/notes
new file mode 100644
index 0000000..0fc11ad
--- /dev/null
+++ b/src/23/notes
@@ -0,0 +1,14 @@
+we start with a list of numbers 1 to 1mil
+
+10 million rounds of moving 3 items from one place to another (depending on input)
+
+need to know the product of two labels after cup 1
+
+- is the product itself predictable?
+    - No, its the same as a random product of two numbers between 1 and mil
+- can we optimize our algo for part 1?
+    - 1 million numbers (1MiB * 8) is not too bad, but 10 million rounds of ordered removes and inserts is very computationally intense.. could fix that with a linked list
+- can we reduce the search space?
+    - for cup 1 we need to know the two cups after it.. those cups were placed there either during a round
+      where 2 was the current or when 1 was the current and numbers between 1 and the ones next to it now were moved (not really predictable)
+
diff --git a/src/23/part1 b/src/23/part1
new file mode 100644
index 0000000..933857b
--- /dev/null
+++ b/src/23/part1
@@ -0,0 +1,97 @@
+--- Day 23: Crab Cups ---
+
+The small crab challenges you to a game! The crab is going to mix up some cups, and you
+have to predict where they'll end up.
+
+The cups will be arranged in a circle and labeled clockwise (your puzzle input). For
+example, if your labeling were 32415, there would be five cups in the circle; going clockwise around
+the circle from the first cup, the cups would be labeled 3, 2, 4, 1, 5, and then back to 3 again.
+
+Before the crab starts, it will designate the first cup in your list as the current
+cup. The crab is then going to do 100 moves.
+
+Each move, the crab does the following actions:
+
+
+ - The crab picks up the three cups that are immediately clockwise of the
+current cup. They are removed from the circle; cup spacing is adjusted as necessary to
+maintain the circle.
+ - The crab selects a destination cup: the cup with a label equal to the
+current cup's label minus one. If this would select one of the cups that was just
+picked up, the crab will keep subtracting one until it finds a cup that wasn't just picked up. If at
+any point in this process the value goes below the lowest value on any cup's label, it
+wraps around to the highest value on any cup's label instead.
+ - The crab places the cups it just picked up so that they are immediately clockwise of
+the destination cup. They keep the same order as when they were picked up.
+ - The crab selects a new current cup: the cup which is immediately clockwise of the
+current cup.
+
+
+For example, suppose your cup labeling were 389125467. If the crab were to do merely 10 moves, the
+following changes would occur:
+
+-- move 1 --
+cups: (3) 8  9  1  2  5  4  6  7 
+pick up: 8, 9, 1
+destination: 2
+
+-- move 2 --
+cups:  3 (2) 8  9  1  5  4  6  7 
+pick up: 8, 9, 1
+destination: 7
+
+-- move 3 --
+cups:  3  2 (5) 4  6  7  8  9  1 
+pick up: 4, 6, 7
+destination: 3
+
+-- move 4 --
+cups:  7  2  5 (8) 9  1  3  4  6 
+pick up: 9, 1, 3
+destination: 7
+
+-- move 5 --
+cups:  3  2  5  8 (4) 6  7  9  1 
+pick up: 6, 7, 9
+destination: 3
+
+-- move 6 --
+cups:  9  2  5  8  4 (1) 3  6  7 
+pick up: 3, 6, 7
+destination: 9
+
+-- move 7 --
+cups:  7  2  5  8  4  1 (9) 3  6 
+pick up: 3, 6, 7
+destination: 8
+
+-- move 8 --
+cups:  8  3  6  7  4  1  9 (2) 5 
+pick up: 5, 8, 3
+destination: 1
+
+-- move 9 --
+cups:  7  4  1  5  8  3  9  2 (6)
+pick up: 7, 4, 1
+destination: 5
+
+-- move 10 --
+cups: (5) 7  4  1  8  3  9  2  6 
+pick up: 7, 4, 1
+destination: 3
+
+-- final --
+cups:  5 (8) 3  7  4  1  9  2  6 
+
+In the above example, the cups' values are the labels as they appear moving clockwise around the
+circle; the current cup is marked with ( ).
+
+After the crab is done, what order will the cups be in? Starting after the cup labeled
+1, collect the other cups' labels clockwise into a single string with no extra characters; each
+number except 1 should appear exactly once. In the above example, after 10 moves, the cups clockwise
+from 1 are labeled 9, 2, 6, 5, and so on, producing 92658374. If the crab were to
+complete all 100 moves, the order after cup 1 would be 67384529.
+
+Using your labeling, simulate 100 moves. What are the labels on the cups after cup 1?
+
+
diff --git a/src/23/part2 b/src/23/part2
new file mode 100644
index 0000000..71e4559
--- /dev/null
+++ b/src/23/part2
@@ -0,0 +1,27 @@
+--- Part Two ---
+
+Due to what you can only assume is a mistranslation (you're not exactly fluent in Crab), you are
+quite surprised when the crab starts arranging many cups in a circle on your raft -
+one million (1000000) in total.
+
+Your labeling is still correct for the first few cups; after that, the remaining cups are just
+numbered in an increasing fashion starting from the number after the highest number in your list and
+proceeding one by one until one million is reached. (For example, if your labeling were 54321, the
+cups would be numbered 5, 4, 3, 2, 1, and then start counting up from 6 until one million is
+reached.) In this way, every number from one through one million is used exactly once.
+
+After discovering where you made the mistake in translating Crab Numbers, you realize the small crab
+isn't going to do merely 100 moves; the crab is going to do ten million (10000000)
+moves!
+
+The crab is going to hide your stars - one each - under the two cups that will
+end up immediately clockwise of cup 1. You can have them if you predict what the labels on those
+cups will be when the crab is finished.
+
+In the above example (389125467), this would be 934001 and then 159792; multiplying these together
+produces 149245887792.
+
+Determine which two cups will end up immediately clockwise of cup 1. What do you get if you
+multiply their labels together?
+
+