diff options
| -rw-r--r-- | day-1/main.zig | 4 | ||||
| -rw-r--r-- | day-2/main.zig | 4 | ||||
| -rw-r--r-- | day-3/main.zig | 49 | ||||
| -rw-r--r-- | day-4/main.zig | 4 | ||||
| -rw-r--r-- | main.zig | 44 | ||||
| -rw-r--r-- | util/mem.zig | 57 |
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; @@ -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 })); -} |