# AoC 2024: Day 8

**URL:** <https://ziggit.dev/t/aoc-2024-day-8/7207>\
**Category:** Brainstorming\
**Tags:** advent-of-code\
**Created:** [December 8, 2024, 5:05am UTC](https://ziggit.dev/t/aoc-2024-day-8/7207 "2024-12-08T05:05:59Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Calder-Ty](https://ziggit.dev/user_avatar/ziggit.dev/calder-ty/32/10237_2.png) [@Calder-Ty](https://ziggit.dev/u/Calder-Ty)\
**Post date:** [December 8, 2024, 5:05am UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/1 "2024-12-08T05:05:59Z")

</div>

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](https://adventofcode.com/2024/day/8)

Templates:

- [GitHub - JacobCrabill/AdventOfCode-2024: My solutions for Advent of Code, 2024](https://github.com/JacobCrabill/AdventOfCode-2024)
- [GitHub - SpexGuy/Zig-AoC-Template: A template for Advent of Code participants using Zig](https://github.com/SpexGuy/Zig-AoC-Template)

Resources:

- [Advent of Code in Zig | Loris Cro's Blog](https://kristoff.it/blog/advent-of-code-zig) :Advice and Tips on How to do AoC with Zig
- [https://zigbin.io](https://zigbin.io) : A website for sharing zig code
- [Documentation - The Zig Programming Language](https://ziglang.org/documentation/master/) : Zig Language Reference
- [Zig Documentation](https://ziglang.org/documentation/master/std/) : Zig Standard Library Docs
- [Docs](https://ziggit.dev/docs) : Community Created Docs and Tutorials
- Private Leaderboard (189 Seats left) code: 1910115-f465b6d3

> **Previous days discussions**
>
> Day 1: [AoC 2024: Day 1](https://ziggit.dev/t/aoc-2024-day-1/7100)  
> Day 2: [AoC 2024: Day 2](https://ziggit.dev/t/aoc-2024-day-2/7119)  
> Day 3: [AoC 2024: Day 3](https://ziggit.dev/t/aoc-2024-day-3/7136)  
> Day 4: [AoC 2024: Day 4](https://ziggit.dev/t/aoc-2024-day-4/7150)  
> Day 5: [AoC 2024: Day 5](https://ziggit.dev/t/aoc-2024-day-5/7167)  
> Day 6: [AoC 2024: Day 6](https://ziggit.dev/t/aoc-2024-day-6/7183)  
> Day 7: [AoC 2024: Day 7](https://ziggit.dev/t/aoc-2024-day-7/7196)

---

<div class="post-metadata">

**Author:** ![Travis](https://ziggit.dev/letter_avatar_proxy/v4/letter/t/bbce88/32.png) [@Travis](https://ziggit.dev/u/Travis)\
**Post date:** [December 8, 2024, 7:02am UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/2 "2024-12-08T07:02:53Z")

</div>

312us release fast for this one [https://zigbin.io/866874](https://zigbin.io/866874)

---

<div class="post-metadata">

**Author:** ![erikwastaken](https://ziggit.dev/letter_avatar_proxy/v4/letter/e/8baadc/32.png) [@erikwastaken](https://ziggit.dev/u/erikwastaken)\
**Post date:** [December 8, 2024, 8:32am UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/3 "2024-12-08T08:32:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![maxsch](https://ziggit.dev/user_avatar/ziggit.dev/maxsch/32/3887_2.png) [@maxsch](https://ziggit.dev/u/maxsch)\
**Post date:** [December 8, 2024, 6:24pm UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/4 "2024-12-08T18:24:44Z")

</div>

Could use some cleanup but good enough for now.

> **Part 1 & 2**
>
> ```zig
> 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;
> }
> 
> ```

```sh
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.

```

---

<div class="post-metadata">

**Author:** ![n0s4](https://ziggit.dev/user_avatar/ziggit.dev/n0s4/32/2227_2.png) [@n0s4](https://ziggit.dev/u/n0s4)\
**Post date:** [December 8, 2024, 8:46pm UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/6 "2024-12-08T20:46:41Z")

</div>

Part two took me longer than it should have because i kept mixing up my `col`s and `row`s 😅.

> **Part 1**
>
> ```zig
> 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**
>
> ```zig
> 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;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![ProfBof](https://ziggit.dev/letter_avatar_proxy/v4/letter/p/a88e4f/32.png) [@ProfBof](https://ziggit.dev/u/ProfBof)\
**Post date:** [December 9, 2024, 3:45am UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/7 "2024-12-09T03:45:43Z")

</div>

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](https://zigbin.io/e069e9)

---

<div class="post-metadata">

**Author:** ![Calder-Ty](https://ziggit.dev/user_avatar/ziggit.dev/calder-ty/32/10237_2.png) [@Calder-Ty](https://ziggit.dev/u/Calder-Ty)\
**Post date:** [December 9, 2024, 4:12am UTC](https://ziggit.dev/t/aoc-2024-day-8/7207/8 "2024-12-09T04:12:29Z")

</div>

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](https://zigbin.io/7411e3)

```plaintext
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.