AoC 2023: Day 14

Brainstorming
1

Main thread for Day 14 of the 2024 advent of code. Feel free to discuss the challenge and ask questions. If particular discussions become large, we can break them off into new threads.

Some Rules:

  1. Please try to keep spoilers within spoiler tags. This is done by typing [spoiler]text to be blurred[\spoiler]. If you have longer sections you can also use the [details=“Title”] tags.
  2. Have Fun

Day 14 Challenge

Templates:

Resources:

Previous days discussions

Day 1: AoC 2024: Day 1
Day 2: AoC 2024: Day 2
Day 3: AoC 2024: Day 3
Day 4: AoC 2024: Day 4
Day 5: AoC 2024: Day 5
Day 6: AoC 2024: Day 6
Day 7: AoC 2024: Day 7
Day 8: AoC 2024: Day 8
Day 9: AoC 2024: Day 9
Day 10: AoC 2024: Day 10
Day 11: AoC 2024: Day 11
Day 12: AoC 2024: Day 12
Day 13: AoC 2024: Day 13

2

Day 14 Part 2 is insanely brutal.

3

My key observation for part 2 was: you need to guess a heuristic that will allow you to identify when the tree is showing up; since you have no idea what this tree will look like, it is better to try simpler heuristics and display the candidates, to let your human eyes determine when you found it.

1 Like
4

Part 2 caught me off-guard a little, but after some observation of the output, patterns started to emerge! A nice change of pace!

https://zigbin.io/9392d7

5

I’ve observed setting a breakpoint where forms the triangle.

1 Like
6

Wo part two was weird: I noticed some pattern appearing in regular intervals (with some initial offset). One was kind of vertical (every 103 frames) and one horizontal (every 101 frames). so I only printed frames, that were multiples of these intervals (plus offset). That enabled me to find it quite quickly

Solution 1 
const std = @import("std");

//const input = @embedFile("./small.inp");
const input = @embedFile("./big.inp");

const ndim: usize = 2;
const robot_t = struct {
    pos: [ndim]i32,
    vel: [ndim]i32,

    const Self = @This();

    pub fn apply_pbc(self: *Self, nx: usize, ny: usize) void {
        while (self.pos[0] >= nx) {
            self.pos[0] -= @as(i32, @intCast(nx));
        }
        while (self.pos[0] < 0) {
            self.pos[0] += @as(i32, @intCast(nx));
        }
        while (self.pos[1] >= ny) {
            self.pos[1] -= @as(i32, @intCast(ny));
        }
        while (self.pos[1] < 0) {
            self.pos[1] += @as(i32, @intCast(ny));
        }
    }

    pub fn step(self: *Self) void {
        for (0..ndim) |idim| {
            self.pos[idim] += self.vel[idim];
        }
    }
};

const floor_t = struct {
    nx: usize,
    ny: usize,
    robots: std.ArrayList(robot_t),

    const Self = @This();

    pub fn init(nx: usize, ny: usize, inputstr: []const u8, allocator: std.mem.Allocator) Self {
        var floor = Self{
            .nx = nx,
            .ny = ny,
            .robots = std.ArrayList(robot_t).init(allocator),
        };
        floor.read_robots(inputstr) catch |err| {
            std.debug.print("{?}\n", .{err});
        };
        return floor;
    }

    pub fn deinit(self: *Self) void {
        self.nx = 0;
        self.ny = 0;
        _ = self.robots.deinit();
    }

    pub fn read_robots(self: *Self, inputstr: []const u8) !void {
        var lines = std.mem.tokenizeScalar(u8, inputstr, '\n');

        while (lines.next()) |line| {
            var robot = robot_t{ .pos = undefined, .vel = undefined };
            var fields = std.mem.tokenizeScalar(u8, line, ' ');
            const posfield = fields.next() orelse "";
            var coords = std.mem.tokenizeScalar(u8, posfield[2..], ',');
            var i: usize = 0;
            while (coords.next()) |val| : (i += 1) {
                robot.pos[i] = try std.fmt.parseInt(i32, val, 10);
            }

            const velfield = fields.next() orelse "";
            coords = std.mem.tokenizeScalar(u8, velfield[2..], ',');
            i = 0;
            while (coords.next()) |val| : (i += 1) {
                robot.vel[i] = try std.fmt.parseInt(i32, val, 10);
            }

            try self.robots.append(robot);
        }
        return;
    }

    pub fn apply_pbc(self: *Self) void {
        for (self.robots.items) |*robot| {
            robot.apply_pbc(self.nx, self.ny);
        }
    }

    pub fn step(self: *Self) void {
        for (self.robots.items) |*robot| {
            robot.step();
        }
    }

    pub fn print(self: Self) void {
        for (0..self.ny) |y| {
            for (0..self.nx) |x| {
                var nfound: i32 = 0;
                for (self.robots.items) |robot| {
                    if (robot.pos[0] == x and robot.pos[1] == y) {
                        nfound += 1;
                    }
                }
                if (nfound > 0) {
                    std.debug.print("{d}", .{nfound});
                } else {
                    std.debug.print(".", .{});
                }
            }
            std.debug.print("\n", .{});
        }
    }

    pub fn safety(self: Self) usize {
        var nNorthWest: usize = 0;
        var nNorthEast: usize = 0;
        var nSouthWest: usize = 0;
        var nSouthEast: usize = 0;
        for (self.robots.items) |robot| {
            if (robot.pos[0] < self.nx / 2 and robot.pos[1] < self.ny / 2) {
                nNorthWest += 1;
            }
            if (robot.pos[0] > self.nx / 2 and robot.pos[1] < self.ny / 2) {
                nNorthEast += 1;
            }
            if (robot.pos[0] < self.nx / 2 and robot.pos[1] > self.ny / 2) {
                nSouthWest += 1;
            }
            if (robot.pos[0] > self.nx / 2 and robot.pos[1] > self.ny / 2) {
                nSouthEast += 1;
            }
        }
        return nNorthWest * nNorthEast * nSouthWest * nSouthEast;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var floor = floor_t.init(101, 103, input, allocator);
    //var floor = floor_t.init(11, 7, input, allocator);
    defer _ = floor.deinit();

    floor.print();
    std.debug.print("\n", .{});
    for (0..100) |_| {
        floor.step();
    }
    floor.apply_pbc();
    floor.print();
    const safety = floor.safety();

    std.debug.print("Safety value: {d}\n", .{safety});
}
Solution 2 
const std = @import("std");

//const input = @embedFile("./small.inp");
const input = @embedFile("./big.inp");

const ndim: usize = 2;
const robot_t = struct {
    pos: [ndim]i32,
    vel: [ndim]i32,

    const Self = @This();

    pub fn apply_pbc(self: *Self, nx: usize, ny: usize) void {
        while (self.pos[0] >= nx) {
            self.pos[0] -= @as(i32, @intCast(nx));
        }
        while (self.pos[0] < 0) {
            self.pos[0] += @as(i32, @intCast(nx));
        }
        while (self.pos[1] >= ny) {
            self.pos[1] -= @as(i32, @intCast(ny));
        }
        while (self.pos[1] < 0) {
            self.pos[1] += @as(i32, @intCast(ny));
        }
    }

    pub fn step(self: *Self) void {
        for (0..ndim) |idim| {
            self.pos[idim] += self.vel[idim];
        }
    }
};

const floor_t = struct {
    nx: usize,
    ny: usize,
    robots: std.ArrayList(robot_t),

    const Self = @This();

    pub fn init(nx: usize, ny: usize, inputstr: []const u8, allocator: std.mem.Allocator) Self {
        var floor = Self{
            .nx = nx,
            .ny = ny,
            .robots = std.ArrayList(robot_t).init(allocator),
        };
        floor.read_robots(inputstr) catch |err| {
            std.debug.print("{?}\n", .{err});
        };
        return floor;
    }

    pub fn deinit(self: *Self) void {
        self.nx = 0;
        self.ny = 0;
        _ = self.robots.deinit();
    }

    pub fn read_robots(self: *Self, inputstr: []const u8) !void {
        var lines = std.mem.tokenizeScalar(u8, inputstr, '\n');

        while (lines.next()) |line| {
            var robot = robot_t{ .pos = undefined, .vel = undefined };
            var fields = std.mem.tokenizeScalar(u8, line, ' ');
            const posfield = fields.next() orelse "";
            var coords = std.mem.tokenizeScalar(u8, posfield[2..], ',');
            var i: usize = 0;
            while (coords.next()) |val| : (i += 1) {
                robot.pos[i] = try std.fmt.parseInt(i32, val, 10);
            }

            const velfield = fields.next() orelse "";
            coords = std.mem.tokenizeScalar(u8, velfield[2..], ',');
            i = 0;
            while (coords.next()) |val| : (i += 1) {
                robot.vel[i] = try std.fmt.parseInt(i32, val, 10);
            }

            try self.robots.append(robot);
        }
        return;
    }

    pub fn apply_pbc(self: *Self) void {
        for (self.robots.items) |*robot| {
            robot.apply_pbc(self.nx, self.ny);
        }
    }

    pub fn step(self: *Self) void {
        for (self.robots.items) |*robot| {
            robot.step();
        }
    }

    pub fn print(self: Self) void {
        for (0..self.ny) |y| {
            for (0..self.nx) |x| {
                var nfound: i32 = 0;
                for (self.robots.items) |robot| {
                    if (robot.pos[0] == x and robot.pos[1] == y) {
                        nfound += 1;
                    }
                }
                if (nfound > 0) {
                    std.debug.print("{d}", .{nfound});
                } else {
                    std.debug.print(".", .{});
                }
            }
            std.debug.print("\n", .{});
        }
    }

    pub fn is_symmetric(self: Self) bool {
        var nsymmetric: usize = 0;
        var nasymmetric: usize = 0;
        const nxhalf = @divFloor(@as(i32, @intCast(self.nx)), 2);
        for (self.robots.items[0 .. self.robots.items.len - 1], 0..) |robot1, i| {
            var found_mirror = false;
            for (self.robots.items[i + 1 ..]) |robot2| {
                if (robot1.pos[1] == robot2.pos[1]) {
                    if (nxhalf - robot1.pos[0] == -1 * (nxhalf - robot2.pos[0])) {
                        found_mirror = true;
                        break;
                    }
                }
            }
            if (!found_mirror) {
                nasymmetric += 1;
            } else {
                nsymmetric += 1;
            }
        }

        const limit = 50;
        if (@divFloor(100 * nsymmetric, 100 * (nasymmetric + nsymmetric)) >= limit) {
            return true;
        } else {
            return false;
        }
    }

    pub fn empty_line(self: Self, linenum: i32) bool {
        for (self.robots.items) |robot| {
            if (robot.pos[0] == linenum) {
                return false;
            }
        }
        return true;
    }
};

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var floor = floor_t.init(101, 103, input, allocator);
    //var floor = floor_t.init(11, 7, input, allocator);
    defer _ = floor.deinit();

    floor.print();
    for (0..10000) |istep| {
        floor.step();
        floor.apply_pbc();
        if (istep >= 85) {
            if (@mod(istep - 50, 103) == 0 or @mod(istep - 85, 101) == 0) {
                std.debug.print("\n{d}\n", .{istep + 1});
                floor.print();
            }
        }
    }
}
8

This is my solution for part 2: I just counted how many bots do not have any bots directly next to them in each iteration. That loop is aborted when the initial state is back again and everything repeats. The point in time where the minimum amount of bots have no neighbors is the moment when they are in formation.

9

part 2 was fun!

to spot the drawing I assumed it would probably have horizontal lines - so I looked for 3/4/5 consecutive robots on the first 10000 iterations, printed the result in a file and spotted the outlier with gnuplot.

10

ok I got lucky there. I thought the Christmas tree would fill the whole grid so I counted the number of bots in a giant triangle and stopped when 3/4 of them were there. Luckily the little tree was in my big triangle so it worked. I should have looked for patches of bots, or looking for bots with many neighbors like others did.

https://zigbin.io/06b545

11

I rendered the output states into 32x32 tiles in a 1024x1024 output image. 1024 results per image so I had to flip through roughly 8 images to find the first tree. :slight_smile: Below is the output image with the tree.

image
image1024×1024 198 KB