AoC 2024: Day 8

Main thread for Day 8 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 8 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

312us release fast for this one https://zigbin.io/866874

3 Likes

Quite a bit of cleanup potential here, but it runs fast enough.
https://zigbin.io/2f5d88

1 Like

Could use some cleanup but good enough for now.

Part 1 & 2
const std = @import("std");

const util = @import("util.zig");
const gpa = util.gpa;

const data = @embedFile("data/day08.txt");

const Point = struct { x: i64, y: i64 };

const lim = 50;
var antennas = std.AutoHashMap(u8, std.ArrayList(Point)).init(gpa);
var grid = [_][lim]u8{[_]u8{0} ** lim} ** lim;

pub fn main() !void {
    var lines = std.mem.tokenizeScalar(u8, data, '\n');
    var x: usize = 0;
    while (lines.next()) |line| : (x += 1) {
        grid[x] = line[0..lim].*;

        for (line, 0..) |c, y| {
            if (c == '.') continue;

            const entry = antennas.getOrPut(c) catch unreachable;
            if (!entry.found_existing) {
                entry.value_ptr.* = std.ArrayList(Point).init(gpa);
            }

            try entry.value_ptr.*.append(Point{ .x = @intCast(x), .y = @intCast(y) });
        }
    }

    std.debug.print("part1: {}\n", .{part1()});
    std.debug.print("part2: {}\n", .{part2()});
}

fn part1() u32 {
    var distinct: u32 = 0;
    var p1_grid = grid;

    var antennas_it = antennas.iterator();
    while (antennas_it.next()) |entry| {
        const items = entry.value_ptr.*.items;

        if (items.len < 2) continue;

        for (items, 0..) |a, i| {
            for (items[i + 1 ..]) |b| {
                const an_a = Point{ .x = a.x + 2 * (b.x - a.x), .y = a.y + 2 * (b.y - a.y) };
                const an_b = Point{ .x = b.x + 2 * (a.x - b.x), .y = b.y + 2 * (a.y - b.y) };

                if (insertAntinode(&p1_grid, an_a)) distinct += 1;
                if (insertAntinode(&p1_grid, an_b)) distinct += 1;
            }
        }
    }

    return distinct;
}

fn part2() u32 {
    var distinct: u32 = 0;
    var p2_grid = grid;

    var antennas_it = antennas.iterator();
    while (antennas_it.next()) |entry| {
        const items = entry.value_ptr.*.items;

        if (items.len < 2) continue;

        for (items, 0..) |a, i| {
            for (items[i + 1 ..]) |b| {
                const ab_x = b.x - a.x;
                const ab_y = b.y - a.y;
                const ba_x = a.x - b.x;
                const ba_y = a.y - b.y;

                var j: i64 = 1;
                while (true) : (j += 1) {
                    const an_a = Point{ .x = a.x + j * (ab_x), .y = a.y + j * (ab_y) };

                    if (an_a.x < 0 or an_a.y < 0 or an_a.x >= lim or an_a.y >= lim) break;
                    if (insertAntinode(&p2_grid, an_a)) distinct += 1;
                }

                j = 1;
                while (true) : (j += 1) {
                    const an_b = Point{ .x = b.x + j * (ba_x), .y = b.y + j * (ba_y) };

                    if (an_b.x < 0 or an_b.y < 0 or an_b.x >= lim or an_b.y >= lim) break;
                    if (insertAntinode(&p2_grid, an_b)) distinct += 1;
                }
            }
        }
    }

    return distinct;
}

fn insertAntinode(g: *[lim][lim]u8, an: Point) bool {
    if (an.x < 0 or an.y < 0 or an.x >= lim or an.y >= lim) return false;
    if (g[@intCast(an.x)][@intCast(an.y)] == '#') return false;
    g[@intCast(an.x)][@intCast(an.y)] = '#';

    return true;
}
Benchmark 1: ./zig-out/bin/day08
  Time (mean ± σ):     246.0 µs ±  34.1 µs    [User: 159.2 µs, System: 28.9 µs]
  Range (min … max):   191.3 µs … 666.2 µs    10263 runs

  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.

Part two took me longer than it should have because i kept mixing up my cols and rows :sweat_smile:.

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

const input = @embedFile("input.txt");
const map_width = 50;
const map_height = 50;

const MapPos = struct {
    row: usize,
    col: usize,
};

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const map = try parseMap(arena.allocator());

    var antinodes = std.AutoHashMap(MapPos, void).init(arena.allocator());

    var frequencies = map.iterator();
    while (frequencies.next()) |entry| {
        const positions = entry.value_ptr.items;
        for (positions, 0..) |pos_a, i| {
            for (positions[i + 1 ..]) |pos_b| {
                if (locateAntiNode(pos_a, pos_b)) |anti_a| {
                    try antinodes.put(anti_a, {});
                }
                if (locateAntiNode(pos_b, pos_a)) |anti_b| {
                    try antinodes.put(anti_b, {});
                }
            }
        }
    }

    std.log.info("{d}", .{antinodes.count()});
}

/// Returns null if the anti node is out of map bounds.
fn locateAntiNode(a: MapPos, b: MapPos) ?MapPos {
    return MapPos{
        .row = offset(a.row, b.row) orelse return null,
        .col = offset(a.col, b.col) orelse return null,
    };
}

fn offset(a: usize, b: usize) ?usize {
    const res = if (a > b)
        a + (a - b)
    else if (b - a > a)
        null
    else
        a - (b - a);

    return if (res < 50) res else null;
}

fn parseMap(allocator: std.mem.Allocator) !std.AutoHashMap(u8, std.ArrayListUnmanaged(MapPos)) {
    var map = std.AutoHashMap(u8, std.ArrayListUnmanaged(MapPos)).init(allocator);

    var line_iter = std.mem.tokenizeScalar(u8, input, '\n');
    var row: usize = 0;
    while (line_iter.next()) |line| {
        for (line, 0..) |ch, col| {
            if (ch == '.') continue;
            std.debug.assert(std.ascii.isAlphanumeric(ch));
            const gop = try map.getOrPutValue(ch, .empty);
            try gop.value_ptr.append(allocator, MapPos{
                .row = row,
                .col = col,
            });
        }
        row += 1;
    }

    return map;
}
Part 2
const std = @import("std");

const input = @embedFile("input.txt");
const map_width = 50;
const map_height = 50;

const MapPos = struct {
    row: usize,
    col: usize,

    pub fn offset(pos: MapPos, d_row: i32, d_col: i32) ?MapPos {
        const row: i32 = @intCast(pos.row);
        const col: i32 = @intCast(pos.col);
        const s_row = row + d_row;
        const s_col = col + d_col;

        if (s_row < 0 or s_row >= map_height or s_col < 0 or s_col >= map_width) {
            return null;
        }

        return MapPos{
            .row = @intCast(s_row),
            .col = @intCast(s_col),
        };
    }
};

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();

    const map = try parseMap(arena.allocator());

    var antinodes = std.AutoHashMap(MapPos, void).init(arena.allocator());

    var frequencies = map.iterator();
    while (frequencies.next()) |entry| {
        const positions = entry.value_ptr.items;
        for (positions, 0..) |pos_a, i| {
            for (positions[i + 1 ..]) |pos_b| {
                var d_col = @as(i32, @intCast(pos_a.col)) - @as(i32, @intCast(pos_b.col));
                var d_row = @as(i32, @intCast(pos_a.row)) - @as(i32, @intCast(pos_b.row));

                const gcd = std.math.gcd(@abs(d_col), @abs(d_row));
                d_col = @divExact(d_col, @as(i32, @intCast(gcd)));
                d_row = @divExact(d_row, @as(i32, @intCast(gcd)));

                var antinode = pos_a;
                while (true) {
                    try antinodes.put(antinode, {});
                    antinode = antinode.offset(d_row, d_col) orelse break;
                }

                d_col = -d_col;
                d_row = -d_row;

                antinode = pos_a;
                while (true) {
                    try antinodes.put(antinode, {});
                    antinode = antinode.offset(d_row, d_col) orelse break;
                }
            }
        }
    }

    std.log.info("{d}", .{antinodes.count()});
}

/// Returns null if the antinode is out of map bounds.
fn locateAntiNode(a: MapPos, b: MapPos) ?MapPos {
    return MapPos{
        .row = offset(a.row, b.row) orelse return null,
        .col = offset(a.col, b.col) orelse return null,
    };
}

fn offset(a: usize, b: usize) ?usize {
    const res = if (a > b)
        a + (a - b)
    else if (b - a > a)
        return null
    else
        a - (b - a);

    return if (res < 50) res else null;
}

fn parseMap(allocator: std.mem.Allocator) !std.AutoHashMap(u8, std.ArrayListUnmanaged(MapPos)) {
    var map = std.AutoHashMap(u8, std.ArrayListUnmanaged(MapPos)).init(allocator);

    var line_iter = std.mem.tokenizeScalar(u8, input, '\n');
    var row: usize = 0;
    while (line_iter.next()) |line| {
        for (line, 0..) |ch, col| {
            if (ch == '.') continue;
            std.debug.assert(std.ascii.isAlphanumeric(ch));
            const gop = try map.getOrPutValue(ch, .empty);
            try gop.value_ptr.append(allocator, MapPos{
                .row = row,
                .col = col,
            });
        }
        row += 1;
    }

    return map;
}

Around 80us. Could not make it faster by storing results in a hashmap like others have done. Not sure about the price I am paying for my big array abstraction and for having simd indices everywhere. I heard that for just 2 dimensions simd can be slower in some cases.

https://zigbin.io/e069e9

Got it done. I felt like this one was pretty straightforward, but maybe i’m just traumatized from day 6.

One thing for sure, is looking at others Zig code has inspired me to do things differently and to look at other tools from the stdlib.

https://zigbin.io/7411e3

Benchmark 1 (10000 runs): ./zig-out/bin/day08
  measurement          mean ± σ            min … max           outliers
  wall_time           299us ± 94.8us     211us … 2.03ms        838 ( 8%)
  peak_rss            950KB ±  327       946KB …  950KB         64 ( 1%)
  cpu_cycles         64.4K  ± 13.4K     47.4K  …  125K           3 ( 0%)
  instructions        107K  ± 0.33       107K  …  107K        1160 (12%)
  cache_references    677   ± 52.0       558   … 1.33K         300 ( 3%)
  cache_misses       1.74   ± 12.3         0   …  454         1530 (15%)
  branch_misses       831   ±  523       178   … 1.55K           0 ( 0%)

Of course running on my computer. I Don’t have time for it now, but it would be great to set up maybe a github rep, or action that can be run that runs the tests nd provides performance, on a similar machine.