adventofcode

commit

3c1ee255e328002f4bd0d739e1262a8bae525bb4

parent

9257b3fec2a284f608f65bac3a154a95aa4353cb

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2025-12-18 14:48

2025-12-11

Diffstat

3 files changed, 145 insertions, 0 deletions

diff --git a/2025/11/solution.zig b/2025/11/solution.zig

@@ -0,0 +1,122 @@
   -1     1 const std = @import("std");
   -1     2 
   -1     3 const Names = std.ArrayList(u24);
   -1     4 const Graph = std.AutoHashMap(u24, struct {
   -1     5     count: usize,
   -1     6     level: usize,
   -1     7     outputs: Names,
   -1     8 });
   -1     9 
   -1    10 fn decode(s: []const u8) u24 {
   -1    11     return ((@as(u24, s[0]) << 0) + (@as(u24, s[1]) << 8) + (@as(u24, s[2]) << 16));
   -1    12 }
   -1    13 
   -1    14 const YOU = decode("you");
   -1    15 const SVR = decode("svr");
   -1    16 const DAC = decode("dac");
   -1    17 const FFT = decode("fft");
   -1    18 const OUT = decode("out");
   -1    19 
   -1    20 fn setLevels(allocator: std.mem.Allocator, graph: *Graph) !void {
   -1    21     // TODO: we are assuming here that SVR is the root of the DAC
   -1    22     var queue = std.ArrayList(struct { u24, usize }).empty;
   -1    23     defer queue.deinit(allocator);
   -1    24     try queue.append(allocator, .{ SVR, 1 });
   -1    25 
   -1    26     while (queue.pop()) |item| {
   -1    27         const name, const level = item;
   -1    28         var value = graph.getPtr(name).?;
   -1    29         if (level > value.level) {
   -1    30             value.level = level;
   -1    31             for (value.outputs.items) |output| {
   -1    32                 try queue.append(allocator, .{ output, level + 1 });
   -1    33             }
   -1    34         }
   -1    35     }
   -1    36 }
   -1    37 
   -1    38 fn countPaths(graph: *Graph, start: u24, end: u24) !usize {
   -1    39     var g = try graph.clone();
   -1    40     defer g.deinit();
   -1    41 
   -1    42     var s = g.getPtr(start).?;
   -1    43     const e = g.getPtr(end).?;
   -1    44     s.count = 1;
   -1    45 
   -1    46     for (s.level..e.level) |level| {
   -1    47         var iterator = g.iterator();
   -1    48         while (iterator.next()) |entry| {
   -1    49             if (entry.value_ptr.level == level) {
   -1    50                 for (entry.value_ptr.outputs.items) |output| {
   -1    51                     var o = g.getPtr(output).?;
   -1    52                     o.count += entry.value_ptr.count;
   -1    53                 }
   -1    54             }
   -1    55         }
   -1    56     }
   -1    57 
   -1    58     return e.count;
   -1    59 }
   -1    60 
   -1    61 pub fn main() !void {
   -1    62     const allocator = std.heap.smp_allocator;
   -1    63 
   -1    64     const path: [:0]const u8 = std.mem.span(std.os.argv[1]);
   -1    65     var file = try std.fs.cwd().openFile(path, .{});
   -1    66     defer file.close();
   -1    67 
   -1    68     var buffer: [1024]u8 = undefined;
   -1    69     var reader = file.reader(&buffer);
   -1    70 
   -1    71     var graph = Graph.init(allocator);
   -1    72     defer {
   -1    73         var iterator = graph.iterator();
   -1    74         while (iterator.next()) |entry| {
   -1    75             entry.value_ptr.outputs.deinit(allocator);
   -1    76         }
   -1    77         graph.deinit();
   -1    78     }
   -1    79 
   -1    80     while (reader.interface.peekDelimiterExclusive('\n')) |line| {
   -1    81         reader.interface.toss(line.len + 1);
   -1    82 
   -1    83         const name = decode(line[0..3]);
   -1    84         var outputs = Names.empty;
   -1    85         var i: usize = 5;
   -1    86         while (i < line.len) {
   -1    87             try outputs.append(allocator, decode(line[i .. i + 3]));
   -1    88             i += 4;
   -1    89         }
   -1    90         try graph.put(name, .{
   -1    91             .count = 0,
   -1    92             .level = 0,
   -1    93             .outputs = outputs,
   -1    94         });
   -1    95     } else |err| switch (err) {
   -1    96         error.EndOfStream => {},
   -1    97         else => |e| return e,
   -1    98     }
   -1    99 
   -1   100     try graph.put(OUT, .{
   -1   101         .count = 0,
   -1   102         .level = 0,
   -1   103         .outputs = Names.empty,
   -1   104     });
   -1   105 
   -1   106     try setLevels(allocator, &graph);
   -1   107 
   -1   108     const part1 = try countPaths(&graph, YOU, OUT);
   -1   109     std.debug.print("part1: {}\n", .{part1});
   -1   110 
   -1   111     var part2: usize = 1;
   -1   112     if (graph.get(DAC).?.level < graph.get(FFT).?.level) {
   -1   113         part2 *= try countPaths(&graph, SVR, DAC);
   -1   114         part2 *= try countPaths(&graph, DAC, FFT);
   -1   115         part2 *= try countPaths(&graph, FFT, OUT);
   -1   116     } else {
   -1   117         part2 *= try countPaths(&graph, SVR, FFT);
   -1   118         part2 *= try countPaths(&graph, FFT, DAC);
   -1   119         part2 *= try countPaths(&graph, DAC, OUT);
   -1   120     }
   -1   121     std.debug.print("part2: {}\n", .{part2});
   -1   122 }

diff --git a/2025/11/test1.txt b/2025/11/test1.txt

@@ -0,0 +1,10 @@
   -1     1 aaa: you hhh
   -1     2 you: bbb ccc
   -1     3 bbb: ddd eee
   -1     4 ccc: ddd eee fff
   -1     5 ddd: ggg
   -1     6 eee: out
   -1     7 fff: out
   -1     8 ggg: out
   -1     9 hhh: ccc fff iii
   -1    10 iii: out

diff --git a/2025/11/test2.txt b/2025/11/test2.txt

@@ -0,0 +1,13 @@
   -1     1 svr: aaa bbb
   -1     2 aaa: fft
   -1     3 fft: ccc
   -1     4 bbb: tty
   -1     5 tty: ccc
   -1     6 ccc: ddd eee
   -1     7 ddd: hub
   -1     8 hub: fff
   -1     9 eee: dac
   -1    10 dac: fff
   -1    11 fff: ggg hhh
   -1    12 ggg: out
   -1    13 hhh: out