commit 37bcc7dedc24240162a4869bafc5e375c6cbf4eb
parent dce8c1112bee0915f35ef256ae875ca220e9f854
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 23 Dec 2020 14:33:46 +0100
day 23 - stash before rewrite (only part 1)
Diffstat:
6 files changed, 277 insertions(+), 0 deletions(-)
diff --git a/src/day23/input b/src/day23/input
@@ -0,0 +1 @@
+476138259
diff --git a/src/day23/input-test b/src/day23/input-test
@@ -0,0 +1 @@
+389125467
diff --git a/src/day23/main.zig b/src/day23/main.zig
@@ -0,0 +1,137 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+// totally overengineered..
+const Ring = struct {
+ list: std.ArrayList(u32),
+ indeces: std.ArrayList(*usize),
+
+ const Self = @This();
+
+ fn init(allocator: *std.mem.Allocator) Self {
+ return Ring{
+ .list = std.ArrayList(u32).init(allocator),
+ .indeces = std.ArrayList(*usize).init(allocator),
+ };
+ }
+
+ fn deinit(self: *Self) void {
+ self.list.deinit();
+ self.indeces.deinit();
+ }
+
+ fn size(self: *Self) usize {
+ return self.list.items.len;
+ }
+
+ fn track(self: *Self, p: *usize) !void {
+ try self.indeces.append(p);
+ }
+
+ fn untrack(self: *Self, p: *usize) void {
+ const ind = std.mem.indexOfScalar(*usize, self.indeces.items, p);
+ if (ind != null) _ = self.indeces.swapRemove(ind.?);
+ }
+
+ fn advanceIndex(self: *Self, ind: usize, off: i64) usize {
+ return (ind + @intCast(usize, @mod(off, @intCast(i64, self.list.items.len)) + @intCast(i64, self.list.items.len))) % self.list.items.len;
+ }
+
+ fn dist(self: *Self, a: usize, b: usize) usize { // a - b (wrapped)
+ return ((a % self.size()) + self.size() - (b % self.size())) % self.size();
+ }
+
+ fn removeAt(self: *Self, ind: usize) u32 {
+ for (self.indeces.items) |v, i| {
+ if (v.* > ind) v.* -= 1;
+ }
+ return self.list.orderedRemove(ind);
+ }
+
+ fn insertAt(self: *Self, ind: usize, item: u32) !void {
+ for (self.indeces.items) |v| {
+ if (v.* >= ind) v.* += 1;
+ }
+ try self.list.insert(ind, item);
+ }
+};
+
+fn parseInput(input: []u8, list: *std.ArrayList(u32)) !u32 {
+ var max: u32 = 0;
+ 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;
+ try list.append(v);
+ }
+ return max;
+}
+
+fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var ring = Ring.init(allocator);
+ defer ring.deinit();
+
+ var max = try parseInput(input, &ring.list);
+
+ 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;
+ try ring.list.append(v);
+ }
+
+ if (ring.size() < 5) return aoc.Error.InvalidInput;
+
+ var current: usize = 0;
+ try ring.track(¤t);
+
+ var round: u32 = 0;
+ while (round < 100) : (round += 1) {
+ var target = if (ring.list.items[current] == 0) max else ring.list.items[current] - 1;
+ var closest: usize = current;
+ for (ring.list.items) |v, i| {
+ if (ring.dist(target, v) < ring.dist(target, ring.list.items[closest]) and ring.dist(i, current) > 3) {
+ closest = i;
+ }
+ }
+
+ if (aoc.debug) {
+ std.debug.print("\n-- move {} --\ncups: ", .{round + 1});
+ for (ring.list.items) |v, i| {
+ if (i > 0) std.debug.print(" ", .{});
+ if (i == current) {
+ std.debug.print("({})", .{v});
+ } else {
+ std.debug.print(" {} ", .{v});
+ }
+ }
+ std.debug.print("\npick up: ", .{});
+ }
+
+ try ring.track(&closest);
+ var i: usize = 0;
+ while (i < 3) : (i += 1) {
+ if (aoc.debug) {
+ if (i > 0) std.debug.print(" ", .{});
+ std.debug.print("{}", .{ring.list.items[ring.advanceIndex(current, 1)]});
+ }
+ const v = ring.removeAt(ring.advanceIndex(current, 1));
+ try ring.insertAt(ring.advanceIndex(closest, @intCast(i64, 1 + i)), v);
+ }
+ ring.untrack(&closest);
+
+ if (aoc.debug) std.debug.print("\ndestination: {}\n", .{ring.list.items[closest]});
+ current = (current + 1) % ring.list.items.len;
+ }
+
+ var start = std.mem.indexOfScalar(u32, ring.list.items, 1).?;
+ var i: u32 = 0;
+ while (i < ring.size() - 1) : (i += 1) {
+ std.debug.print("{}", .{ring.list.items[ring.advanceIndex(start, 1 + i)]});
+ }
+ std.debug.print("\n", .{});
+}
+
+fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {}
+
+pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day23/notes b/src/day23/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/day23/part1 b/src/day23/part1
@@ -0,0 +1,97 @@
+--- Day 23: Crab Cups ---
+
+The small crab challenges [1m[37myou[0m 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 [1m[37mclockwise[0m (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 [1m[37mcurrent
+cup[0m. The crab is then going to do [1m[37m100 moves[0m.
+
+Each [1m[37mmove[0m, the crab does the following actions:
+
+
+ - The crab picks up the [1m[37mthree cups[0m that are immediately [1m[37mclockwise[0m of the
+[1m[37mcurrent cup[0m. They are removed from the circle; cup spacing is adjusted as necessary to
+maintain the circle.
+ - The crab selects a [1m[37mdestination cup[0m: the cup with a [1m[37mlabel[0m equal to the
+[1m[37mcurrent cup's[0m 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
+[1m[37mwraps around[0m to the highest value on any cup's label instead.
+ - The crab places the cups it just picked up so that they are [1m[37mimmediately clockwise[0m of
+the destination cup. They keep the same order as when they were picked up.
+ - The crab selects a new [1m[37mcurrent cup[0m: 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 [1m[37mcurrent cup[0m is marked with ( ).
+
+After the crab is done, what order will the cups be in? Starting [1m[37mafter the cup labeled
+1[0m, 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 [1m[37m92658374[0m. If the crab were to
+complete all 100 moves, the order after cup 1 would be [1m[37m67384529[0m.
+
+Using your labeling, simulate 100 moves. [1m[37mWhat are the labels on the cups after cup 1?[0m
+
+
diff --git a/src/day23/part2 b/src/day23/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 [1m[37mmany[0m cups in a circle on your raft -
+[1m[37mone million[0m (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 [1m[37mten million[0m (10000000)
+moves!
+
+The crab is going to hide your [1m[33mstars[0m - one each - under the [1m[37mtwo cups that will
+end up immediately clockwise of cup 1[0m. 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 [1m[37m149245887792[0m.
+
+Determine which two cups will end up immediately clockwise of cup 1. [1m[37mWhat do you get if you
+multiply their labels together?[0m
+
+
