make day06 faster

1 files changed, 20 insertions, 8 deletions

diff --git a/src/day06.zig b/src/day06.zig
index bbea665..9b7b8b5 100644
--- a/src/day06.zig
+++ b/src/day06.zig
@@ -27,15 +27,29 @@ pub fn solve(part: []u8, buffer: []u8, allocator: std.mem.Allocator) !void {
     }
 }
 
-fn locations(grid: *std.ArrayList([]u8), startx: i32, starty: i32, allocator: std.mem.Allocator) !std.AutoHashMap(std.meta.Tuple(&.{ i32, i32 }), void) {
+fn locations(grid: *std.ArrayList([]u8), startx: i32, starty: i32, allocator: std.mem.Allocator) !std.AutoHashMap(std.meta.Tuple(&.{ i32, i32, i32, i32 }), void) {
     var dirx: i32 = 0;
     var diry: i32 = -1;
     var x = startx;
     var y = starty;
-    var unique = std.AutoHashMap(std.meta.Tuple(&.{ i32, i32 }), void).init(allocator);
+
+    var history = try allocator.alloc(bool, grid.items.len * grid.items[0].len * 4);
+    defer allocator.free(history);
+
+    for (history) |*elem| {
+        elem.* = false;
+    }
+
+    var unique = std.AutoHashMap(std.meta.Tuple(&.{ i32, i32, i32, i32 }), void).init(allocator);
     errdefer unique.deinit();
+    const width: i32 = @intCast(grid.items[0].len);
 
     while (y >= 0 and y < grid.items.len and x >= 0 and x < grid.items[@intCast(y)].len) {
+        if (!history[@intCast(y * width + x)] and grid.items[@intCast(y)][@intCast(x)] != '#') {
+            try unique.put(.{ x, y, dirx, diry }, {});
+            history[@intCast(y * width + x)] = true;
+        }
+
         if (grid.items[@intCast(y)][@intCast(x)] == '#') {
             x -= dirx;
             y -= diry;
@@ -44,8 +58,6 @@ fn locations(grid: *std.ArrayList([]u8), startx: i32, starty: i32, allocator: st
             diry = temp;
         }
 
-        try unique.put(.{ x, y }, {});
-
         x += dirx;
         y += diry;
     }
@@ -85,10 +97,10 @@ fn part2(grid: *std.ArrayList([]u8), startx: i32, starty: i32, allocator: std.me
 
     while (iterator.next()) |location| {
         grid.items[@intCast(location[1])][@intCast(location[0])] = '#';
-        var dirx: i32 = 0;
-        var diry: i32 = -1;
-        var x = startx;
-        var y = starty;
+        var dirx: i32 = location[2];
+        var diry: i32 = location[3];
+        var x = location[0];
+        var y = location[1];
 
         for (history) |*elem| {
             elem.* = false;