remove naive intersection impl

6 files changed, 58 insertions, 104 deletions

diff --git a/day-1/main.zig b/day-1/main.zig
index 0af8162..d985c9b 100644
--- a/day-1/main.zig
+++ b/day-1/main.zig
@@ -1,7 +1,7 @@
 const std = @import("std");
 const min_idx = @import("util/mem.zig").min_idx;
 
-pub fn puzzle_1(input: []u8) !i32 {
+pub fn puzzle_1(input: []const u8) !i32 {
     var iter = std.mem.split(u8, input, "\n");
     var count: i32 = 0;
     var max: i32 = 0;
@@ -20,7 +20,7 @@ pub fn puzzle_1(input: []u8) !i32 {
     return max;
 }
 
-pub fn puzzle_2(input: []u8) !i32 {
+pub fn puzzle_2(input: []const u8) !i32 {
     var iter = std.mem.split(u8, input, "\n");
     var count: i32 = 0;
     var max: [3]i32 = std.mem.zeroes([3]i32);
diff --git a/day-2/main.zig b/day-2/main.zig
index f493580..3289ad2 100644
--- a/day-2/main.zig
+++ b/day-2/main.zig
@@ -79,7 +79,7 @@ const match_impl = struct {
     }
 };
 
-pub fn puzzle_1(input: []u8) u16 {
+pub fn puzzle_1(input: []const u8) u16 {
     var iter = std.mem.split(u8, input, "\n");
 
     var score: u16 = 0;
@@ -94,7 +94,7 @@ pub fn puzzle_1(input: []u8) u16 {
     return score;
 }
 
-pub fn puzzle_2(input: []u8) u16 {
+pub fn puzzle_2(input: []const u8) u16 {
     var iter = std.mem.split(u8, input, "\n");
 
     var score: u16 = 0;
diff --git a/day-3/main.zig b/day-3/main.zig
index 0bba2f3..57057bf 100644
--- a/day-3/main.zig
+++ b/day-3/main.zig
@@ -1,48 +1,39 @@
 const std = @import("std");
-const dupl_values = @import("util/mem.zig").dupl_values;
 
-pub fn puzzle_1(allocator: std.mem.Allocator, input: []u8) !u16 {
+pub fn puzzle_1(input: []const u8) u16 {
     var iter = std.mem.split(u8, input, "\n");
 
     var count: u16 = 0;
     while (iter.next()) |line| {
-        const duplicates = try dupl_values(
-            u8,
-            allocator,
-            &[_][]const u8{
-                line[0 .. line.len / 2],
-                line[line.len / 2 ..],
-            },
-        );
-        defer allocator.free(duplicates);
-
-        for (duplicates) |char| {
-            count += char_to_priority(char);
+        var p1: u64 = 0;
+        var p2: u64 = 0;
+
+        for (line[0 .. line.len / 2]) |_, i| {
+            p1 |= @as(u64, 1) << @intCast(u6, line[i] - 65); // 65 == 'A'
+            p2 |= @as(u64, 1) << @intCast(u6, line[i + line.len / 2] - 65);
         }
+
+        count += char_to_priority(@intCast(u8, 65 + 63) - @clz(p1 & p2));
     }
 
     return count;
 }
 
-pub fn puzzle_2(allocator: std.mem.Allocator, input: []u8) !u16 {
+pub fn puzzle_2(input: []const u8) u16 {
     var iter = std.mem.split(u8, input, "\n");
 
     var count: u16 = 0;
-    while (iter.next()) |line| {
-        const duplicates = try dupl_values(
-            u8,
-            allocator,
-            &[_][]const u8{
-                line,
-                iter.next().?,
-                iter.next().?,
-            },
-        );
-        defer allocator.free(duplicates);
-
-        for (duplicates) |char| {
-            count += char_to_priority(char);
+    mainLoop: while (true) {
+        var parts = std.mem.zeroes([3]u64);
+
+        for (parts) |*p| {
+            const line = iter.next() orelse break :mainLoop;
+            for (line) |_, i| {
+                p.* |= @as(u64, 1) << @intCast(u6, line[i] - 65);
+            }
         }
+
+        count += char_to_priority(@intCast(u8, 65 + 63) - @clz(parts[0] & parts[1] & parts[2]));
     }
 
     return count;
diff --git a/day-4/main.zig b/day-4/main.zig
index 794254b..6c0d193 100644
--- a/day-4/main.zig
+++ b/day-4/main.zig
@@ -1,6 +1,6 @@
 const std = @import("std");
 
-pub fn puzzle_1(input: []u8) !u16 {
+pub fn puzzle_1(input: []const u8) !u16 {
     var iter = std.mem.split(u8, input, "\n");
 
     var count: u16 = 0;
@@ -15,7 +15,7 @@ pub fn puzzle_1(input: []u8) !u16 {
     return count;
 }
 
-pub fn puzzle_2(input: []u8) !u16 {
+pub fn puzzle_2(input: []const u8) !u16 {
     var iter = std.mem.split(u8, input, "\n");
 
     var count: u16 = 0;
diff --git a/main.zig b/main.zig
index a10e87e..6609a2f 100644
--- a/main.zig
+++ b/main.zig
@@ -4,7 +4,7 @@ test {
     std.testing.refAllDecls(@This());
 }
 
-fn solve(allocator: std.mem.Allocator, puzzle: anytype, input: []u8) !i32 {
+fn solve(allocator: std.mem.Allocator, puzzle: anytype, input: []const u8) !i32 {
     return blk: {
         switch (@typeInfo(@TypeOf(puzzle))) {
             .Fn => |f| {
@@ -27,7 +27,6 @@ fn solve(allocator: std.mem.Allocator, puzzle: anytype, input: []u8) !i32 {
 }
 
 const testing_allocator = std.testing.allocator;
-const slurp = @import("util/file.zig").slurp;
 
 // same as the real comptimePrint but inlined, see: https://github.com/ziglang/zig/issues/12635
 inline fn comptimePrint(comptime fmt: []const u8, args: anytype) *const [std.fmt.count(fmt, args):0]u8 {
@@ -43,29 +42,50 @@ test "test" {
     const t = [_]struct {
         day: type,
         expect: []const i32,
+        input: []const u8,
     }{
-        .{ .day = @import("day-1/main.zig"), .expect = &[_]i32{ 69912, 208180 } },
-        .{ .day = @import("day-2/main.zig"), .expect = &[_]i32{ 12855, 13726 } },
-        .{ .day = @import("day-3/main.zig"), .expect = &[_]i32{ 8039, 2510 } },
-        .{ .day = @import("day-4/main.zig"), .expect = &[_]i32{ 483, 874 } },
+        .{ .day = @import("day-1/main.zig"), .input = @embedFile("day-1/input"), .expect = &[_]i32{ 69912, 208180 } },
+        .{ .day = @import("day-2/main.zig"), .input = @embedFile("day-2/input"), .expect = &[_]i32{ 12855, 13726 } },
+        .{ .day = @import("day-3/main.zig"), .input = @embedFile("day-3/input"), .expect = &[_]i32{ 8039, 2510 } },
+        .{ .day = @import("day-4/main.zig"), .input = @embedFile("day-4/input"), .expect = &[_]i32{ 483, 874 } },
     };
 
     std.debug.print("\n", .{});
 
     inline for (t) |aoc_day, day| {
         std.debug.print("\n", .{});
-        const file_buffer = try slurp(std.testing.allocator, comptimePrint("./day-{d}/input", .{day + 1}));
-        defer testing_allocator.free(file_buffer);
-
         inline for (aoc_day.expect) |expected, idx| {
             const fn_name = comptimePrint("puzzle_{d}", .{idx + 1});
             const puzzle = @field(aoc_day.day, fn_name);
+            const start_time = try std.time.Instant.now();
+
+            const result = try solve(
+                testing_allocator,
+                puzzle,
+                aoc_day.input[0 .. aoc_day.input.len - 1], // remove the last '^\n$'
+            );
+
+            const end_time = try std.time.Instant.now();
+            const elapsed_us = end_time.since(start_time) / std.time.ns_per_us;
 
-            const result = try solve(testing_allocator, puzzle, file_buffer);
             if (result == expected) {
-                std.debug.print("day={d}, puzzle_{d}={d}\n", .{ day + 1, idx + 1, result });
+                std.debug.print("day={d}, puzzle_{d}={d}, input_bytes={d}, time={d}µs\n", .{
+                    day + 1,
+                    idx + 1,
+                    result,
+                    aoc_day.input.len,
+                    elapsed_us,
+                });
             } else {
-                std.debug.print("day={d}, puzzle_{d}={d}, expected={d}\n", .{ day + 1, idx + 1, result, expected });
+                std.debug.print("day={d}, puzzle_{d}={d}, input_bytes={d}, time={d}µs, expected={d}\n", .{
+                    day + 1,
+                    idx + 1,
+                    result,
+                    aoc_day.input.len,
+                    elapsed_us,
+                    expected,
+                });
+                return error.UnexpectedValue;
             }
         }
     }
diff --git a/util/mem.zig b/util/mem.zig
index 3b68dad..728db44 100644
--- a/util/mem.zig
+++ b/util/mem.zig
@@ -17,60 +17,3 @@ pub fn min_idx(comptime T: type, slice: []const T) usize {
     }
     return idx;
 }
-
-/// Returns a slice of the duplicated values amongst all slices.
-/// { {1,2,3,4}, {4,5,6,1} } -> {1,4}
-pub fn dupl_values(comptime T: type, allocator: std.mem.Allocator, haystacks: []const []const T) ![]T {
-    var haystacks_maps = blk: {
-        var r = std.ArrayList(std.AutoHashMap(T, bool)).init(allocator);
-        for (haystacks) |haystack| {
-            var haystack_map = std.AutoHashMap(T, bool).init(allocator);
-            for (haystack) |item| {
-                try haystack_map.put(item, true);
-            }
-            try r.append(haystack_map);
-        }
-        break :blk r.toOwnedSlice();
-    };
-
-    defer blk: {
-        for (haystacks_maps) |*haystack| {
-            haystack.deinit();
-        }
-        allocator.free(haystacks_maps);
-        break :blk;
-    }
-
-    var dupl = std.ArrayList(T).init(allocator);
-    var seen = std.AutoHashMap(T, bool).init(allocator);
-    defer seen.deinit();
-
-    for (haystacks[0]) |item| {
-        if (seen.contains(item))
-            continue;
-
-        try seen.put(item, true);
-
-        var duplicated = true;
-
-        for (haystacks_maps[1..]) |map| {
-            if (!map.contains(item)) {
-                duplicated = false;
-                continue;
-            }
-        }
-
-        if (duplicated)
-            try dupl.append(item);
-    }
-
-    return dupl.toOwnedSlice();
-}
-
-test "dupl_values" {
-    const haystack = [_][]const u8{ &[_]u8{ 1, 2, 3, 1 }, &[_]u8{ 2, 3, 1, 5 }, &[_]u8{ 3, 2, 1, 4 } };
-    var foo = try dupl_values(u8, testing_allocator, &haystack);
-    defer testing_allocator.free(foo);
-
-    try std.testing.expect(std.mem.eql(u8, foo, &[_]u8{ 1, 2, 3 }));
-}