commit 8438782e64c0eb5848531bf6d8bc3435e7fecb8e
parent 74d4c625d22e4845e95cb8f05be882cb5ee7f3db
Author: Louis Burda <quent.burda@gmail.com>
Date: Thu, 17 Dec 2020 13:53:17 +0100
added day 17
Diffstat:
5 files changed, 638 insertions(+), 0 deletions(-)
diff --git a/src/day17/input b/src/day17/input
@@ -0,0 +1,8 @@
+.###..#.
+##.##...
+....#.#.
+#..#.###
+...#...#
+##.#...#
+#..##.##
+#.......
diff --git a/src/day17/input-test b/src/day17/input-test
@@ -0,0 +1,3 @@
+.#.
+..#
+###
diff --git a/src/day17/main.zig b/src/day17/main.zig
@@ -0,0 +1,193 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+fn PosVec(comptime N: u32) type {
+ return struct { data: [N]i64 };
+}
+
+const Active = bool;
+
+fn forNeighbors(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), data: anytype, func: fn (map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: @TypeOf(data)) anyerror!void) !void {
+ var i: u32 = 0;
+ while (i < comptime std.math.pow(u32, 3, dims)) : (i += 1) {
+ var np: PosVec(dims) = undefined;
+ var d: u32 = 0;
+ var skip = true;
+ while (d < dims) : (d += 1) {
+ const offset = (i / std.math.pow(u32, 3, d)) % 3;
+ np.data[d] = p.data[d] + @intCast(i64, offset) - 1;
+ if (skip and offset != 1) skip = false;
+ }
+ if (skip) continue;
+ try func(map, np, data);
+ }
+}
+
+fn posStr(comptime dims: u32, p: PosVec(dims)) void {
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ std.debug.print("{} ", .{p.data[d]});
+ }
+}
+
+fn countActive(comptime dims: u32) fn (map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: *u32) anyerror!void {
+ const impl = struct {
+ fn func(map: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), d: *u32) anyerror!void {
+ d.* += @boolToInt(map.get(p) != null);
+ }
+ };
+ return impl.func;
+}
+
+fn addNew(comptime dims: u32) fn (oldmap: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), newmap: *std.AutoHashMap(PosVec(dims), Active)) anyerror!void {
+ const impl = struct {
+ fn func(oldmap: *std.AutoHashMap(PosVec(dims), Active), p: PosVec(dims), newmap: *std.AutoHashMap(PosVec(dims), Active)) anyerror!void {
+ if (newmap.get(p) != null) return;
+
+ var v = oldmap.get(p);
+ var state = (v != null);
+
+ var count: u32 = 0;
+ try forNeighbors(dims, oldmap, p, &count, countActive(dims));
+ if (state and count >= 2 and count <= 3 or !state and count == 3) {
+ try newmap.put(p, true);
+ }
+ }
+ };
+ return impl.func;
+}
+
+fn simulateRound(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active), allocator: *std.mem.Allocator) !void {
+ var newmap = std.AutoHashMap(PosVec(dims), Active).init(allocator);
+ errdefer newmap.deinit();
+
+ var mapit = map.iterator();
+ while (mapit.next()) |kv| {
+ try forNeighbors(dims, map, kv.key, &newmap, addNew(dims));
+ try addNew(dims)(map, kv.key, &newmap);
+ }
+
+ std.mem.swap(std.AutoHashMap(PosVec(dims), Active), map, &newmap);
+ newmap.deinit();
+}
+
+fn sliceProduct(data: []i64) i64 {
+ var product: i64 = 1;
+ for (data) |v| {
+ product *= v;
+ }
+ return product;
+}
+
+fn printMap(comptime dims: u32, map: *std.AutoHashMap(PosVec(dims), Active)) void {
+ var min: ?PosVec(dims) = null;
+ var max: ?PosVec(dims) = null;
+
+ var mapit = map.iterator();
+ while (mapit.next()) |kv| {
+ if (min == null) min = kv.key;
+ if (max == null) max = kv.key;
+
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ if (min.?.data[d] > kv.key.data[d]) min.?.data[d] = kv.key.data[d];
+ if (max.?.data[d] < kv.key.data[d]) max.?.data[d] = kv.key.data[d];
+ }
+ }
+
+ if (min == null or max == null) return;
+
+ var space: PosVec(dims) = undefined;
+ {
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ space.data[d] = max.?.data[d] - min.?.data[d];
+ }
+ }
+
+ var i: usize = 0;
+ while (i < sliceProduct(space.data[0..])) : (i += @intCast(usize, space.data[0] * space.data[1])) {
+ var np: PosVec(dims) = undefined;
+ var d: u32 = 0;
+ while (d < dims) : (d += 1) {
+ np.data[d] = min.?.data[d] + @mod(@divFloor(@intCast(i64, i), sliceProduct(space.data[0..d])), space.data[d]);
+ }
+
+ d = 2;
+ std.debug.print("Slice at: ", .{});
+ while (d < dims) : (d += 1) {
+ if (d > 2) std.debug.print(",", .{});
+ std.debug.print("{}.Dim = {} ", .{ d + 1, np.data[d] });
+ }
+ std.debug.print("\n", .{});
+
+ var y = min.?.data[1];
+ while (y <= max.?.data[1]) : (y += 1) {
+ var x = min.?.data[0];
+ while (x <= max.?.data[0]) : (x += 1) {
+ var v = np;
+ v.data[0] = x;
+ v.data[1] = y;
+ var c: u8 = '.';
+ if (map.get(v) != null) c = '#';
+ std.debug.print("{c}", .{c});
+ }
+ std.debug.print("\n", .{});
+ }
+ std.debug.print("\n", .{});
+ }
+}
+
+fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var map = std.AutoHashMap(PosVec(3), Active).init(allocator);
+ defer map.deinit();
+
+ var lineit = std.mem.tokenize(input, "\n");
+ var y: i64 = 0;
+ while (lineit.next()) |line| : (y += 1) {
+ for (line) |c, x| {
+ if (c != '#') continue;
+ try map.put(PosVec(3){ .data = [_]i64{ @intCast(i64, x), y, 0 } }, true);
+ }
+ }
+
+ var i: usize = 0;
+ while (i < 6) : (i += 1) {
+ try simulateRound(3, &map, allocator);
+ if (aoc.debug) {
+ std.debug.print("AFTER ROUND {}:\n", .{i + 1});
+ printMap(3, &map);
+ }
+ }
+
+ var answer: u32 = map.count();
+ std.debug.print("{}\n", .{answer});
+}
+
+fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
+ var map = std.AutoHashMap(PosVec(4), Active).init(allocator);
+ defer map.deinit();
+
+ var lineit = std.mem.tokenize(input, "\n");
+ var y: i64 = 0;
+ while (lineit.next()) |line| : (y += 1) {
+ for (line) |c, x| {
+ if (c != '#') continue;
+ try map.put(PosVec(4){ .data = [_]i64{ @intCast(i64, x), y, 0, 0 } }, true);
+ }
+ }
+
+ var i: usize = 0;
+ while (i < 6) : (i += 1) {
+ try simulateRound(4, &map, allocator);
+ if (aoc.debug) {
+ std.debug.print("AFTER ROUND {}:\n", .{i + 1});
+ printMap(4, &map);
+ }
+ }
+
+ var answer: u32 = map.count();
+ std.debug.print("{}\n", .{answer});
+}
+
+pub const main = aoc.gen_main(part1, part2);
diff --git a/src/day17/part1 b/src/day17/part1
@@ -0,0 +1,169 @@
+--- Day 17: Conway Cubes ---
+
+As your flight slowly drifts through the sky, the Elves at the Mythical Information Bureau at the
+North Pole contact you. They'd like some help debugging a malfunctioning experimental energy source
+aboard one of their super-secret imaging satellites.
+
+The experimental energy source is based on cutting-edge technology: a set of Conway Cubes contained
+in a pocket dimension! When you hear it's having problems, you can't help but agree to take a look.
+
+The pocket dimension contains an infinite 3-dimensional grid. At every integer 3-dimensional
+coordinate (x,y,z), there exists a single cube which is either [1m[37mactive[0m or
+[1m[37minactive[0m.
+
+In the initial state of the pocket dimension, almost all cubes start [1m[37minactive[0m. The only
+exception to this is a small flat region of cubes (your puzzle input); the cubes in this region
+start in the specified [1m[37mactive[0m (#) or [1m[37minactive[0m (.) state.
+
+The energy source then proceeds to boot up by executing six [1m[37mcycles[0m.
+
+Each cube only ever considers its [1m[37mneighbors[0m: any of the 26 other cubes where any of
+their coordinates differ by at most 1. For example, given the cube at x=1,y=2,z=3, its neighbors
+include the cube at x=2,y=2,z=2, the cube at x=0,y=2,z=3, and so on.
+
+During a cycle, [1m[37mall[0m cubes [1m[37msimultaneously[0m change their state according to
+the following rules:
+
+
+ - If a cube is [1m[37mactive[0m and [1m[37mexactly 2 or 3[0m of its neighbors are also
+active, the cube remains [1m[37mactive[0m. Otherwise, the cube becomes [1m[37minactive[0m.
+ - If a cube is [1m[37minactive[0m but [1m[37mexactly 3[0m of its neighbors are active, the
+cube becomes [1m[37mactive[0m. Otherwise, the cube remains [1m[37minactive[0m.
+
+
+The engineers responsible for this experimental energy source would like you to simulate the pocket
+dimension and determine what the configuration of cubes should be at the end of the six-cycle boot
+process.
+
+For example, consider the following initial state:
+
+.#.
+..#
+###
+
+Even though the pocket dimension is 3-dimensional, this initial state represents a small
+2-dimensional slice of it. (In particular, this initial state defines a 3x3x1 region of the
+3-dimensional space.)
+
+Simulating a few cycles from this initial state produces the following configurations, where the
+result of each cycle is shown layer-by-layer at each given z coordinate (and the frame of view
+follows the active cells in each cycle):
+
+Before any cycles:
+
+z=0
+.#.
+..#
+###
+
+
+After 1 cycle:
+
+z=-1
+#..
+..#
+.#.
+
+z=0
+#.#
+.##
+.#.
+
+z=1
+#..
+..#
+.#.
+
+
+After 2 cycles:
+
+z=-2
+.....
+.....
+..#..
+.....
+.....
+
+z=-1
+..#..
+.#..#
+....#
+.#...
+.....
+
+z=0
+##...
+##...
+#....
+....#
+.###.
+
+z=1
+..#..
+.#..#
+....#
+.#...
+.....
+
+z=2
+.....
+.....
+..#..
+.....
+.....
+
+
+After 3 cycles:
+
+z=-2
+.......
+.......
+..##...
+..###..
+.......
+.......
+.......
+
+z=-1
+..#....
+...#...
+#......
+.....##
+.#...#.
+..#.#..
+...#...
+
+z=0
+...#...
+.......
+#......
+.......
+.....##
+.##.#..
+...#...
+
+z=1
+..#....
+...#...
+#......
+.....##
+.#...#.
+..#.#..
+...#...
+
+z=2
+.......
+.......
+..##...
+..###..
+.......
+.......
+.......
+
+After the full six-cycle boot process completes, [1m[37m112[0m cubes are left in the
+[1m[37mactive[0m state.
+
+Starting with your given initial configuration, simulate six cycles. [1m[37mHow many cubes are
+left in the active state after the sixth cycle?[0m
+
+
diff --git a/src/day17/part2 b/src/day17/part2
@@ -0,0 +1,265 @@
+--- Part Two ---
+
+For some reason, your simulated results don't match what the experimental energy source engineers
+expected. Apparently, the pocket dimension actually has [1m[37mfour spatial dimensions[0m, not
+three.
+
+The pocket dimension contains an infinite 4-dimensional grid. At every integer 4-dimensional
+coordinate (x,y,z,w), there exists a single cube (really, a [1m[37mhypercube[0m) which is still
+either [1m[37mactive[0m or [1m[37minactive[0m.
+
+Each cube only ever considers its [1m[37mneighbors[0m: any of the 80 other cubes where any of
+their coordinates differ by at most 1. For example, given the cube at x=1,y=2,z=3,w=4, its neighbors
+include the cube at x=2,y=2,z=3,w=3, the cube at x=0,y=2,z=3,w=4, and so on.
+
+The initial state of the pocket dimension still consists of a small flat region of cubes.
+Furthermore, the same rules for cycle updating still apply: during each cycle, consider the
+[1m[37mnumber of active neighbors[0m of each cube.
+
+For example, consider the same initial state as in the example above. Even though the pocket
+dimension is 4-dimensional, this initial state represents a small 2-dimensional slice of it. (In
+particular, this initial state defines a 3x3x1x1 region of the 4-dimensional space.)
+
+Simulating a few cycles from this initial state produces the following configurations, where the
+result of each cycle is shown layer-by-layer at each given z and w coordinate:
+
+Before any cycles:
+
+z=0, w=0
+.#.
+..#
+###
+
+
+After 1 cycle:
+
+z=-1, w=-1
+#..
+..#
+.#.
+
+z=0, w=-1
+#..
+..#
+.#.
+
+z=1, w=-1
+#..
+..#
+.#.
+
+z=-1, w=0
+#..
+..#
+.#.
+
+z=0, w=0
+#.#
+.##
+.#.
+
+z=1, w=0
+#..
+..#
+.#.
+
+z=-1, w=1
+#..
+..#
+.#.
+
+z=0, w=1
+#..
+..#
+.#.
+
+z=1, w=1
+#..
+..#
+.#.
+
+
+After 2 cycles:
+
+z=-2, w=-2
+.....
+.....
+..#..
+.....
+.....
+
+z=-1, w=-2
+.....
+.....
+.....
+.....
+.....
+
+z=0, w=-2
+###..
+##.##
+#...#
+.#..#
+.###.
+
+z=1, w=-2
+.....
+.....
+.....
+.....
+.....
+
+z=2, w=-2
+.....
+.....
+..#..
+.....
+.....
+
+z=-2, w=-1
+.....
+.....
+.....
+.....
+.....
+
+z=-1, w=-1
+.....
+.....
+.....
+.....
+.....
+
+z=0, w=-1
+.....
+.....
+.....
+.....
+.....
+
+z=1, w=-1
+.....
+.....
+.....
+.....
+.....
+
+z=2, w=-1
+.....
+.....
+.....
+.....
+.....
+
+z=-2, w=0
+###..
+##.##
+#...#
+.#..#
+.###.
+
+z=-1, w=0
+.....
+.....
+.....
+.....
+.....
+
+z=0, w=0
+.....
+.....
+.....
+.....
+.....
+
+z=1, w=0
+.....
+.....
+.....
+.....
+.....
+
+z=2, w=0
+###..
+##.##
+#...#
+.#..#
+.###.
+
+z=-2, w=1
+.....
+.....
+.....
+.....
+.....
+
+z=-1, w=1
+.....
+.....
+.....
+.....
+.....
+
+z=0, w=1
+.....
+.....
+.....
+.....
+.....
+
+z=1, w=1
+.....
+.....
+.....
+.....
+.....
+
+z=2, w=1
+.....
+.....
+.....
+.....
+.....
+
+z=-2, w=2
+.....
+.....
+..#..
+.....
+.....
+
+z=-1, w=2
+.....
+.....
+.....
+.....
+.....
+
+z=0, w=2
+###..
+##.##
+#...#
+.#..#
+.###.
+
+z=1, w=2
+.....
+.....
+.....
+.....
+.....
+
+z=2, w=2
+.....
+.....
+..#..
+.....
+.....
+
+After the full six-cycle boot process completes, [1m[37m848[0m cubes are left in the
+[1m[37mactive[0m state.
+
+Starting with your given initial configuration, simulate six cycles in a 4-dimensional space.
+[1m[37mHow many cubes are left in the active state after the sixth cycle?[0m
+
+
