aoc-2020-zig

commit 2c4ba26b5e747c7a477413690ef5ae068c635596
parent bffd1c1d6a3b5f65ba78ca34d77e23b37e3a53a3
Author: Louis Burda <quent.burda@gmail.com>
Date:   Sat,  5 Dec 2020 17:01:52 +0100

added alternate day 5 implementation by interpreting seat code as binary string

Diffstat:
M
src/day5/main.zig
 | 
50
+++++++++++++++++++-------------------------------

1 file changed, 19 insertions(+), 31 deletions(-)
diff --git a/src/day5/main.zig b/src/day5/main.zig
@@ -1,55 +1,43 @@
 const std = @import("std");
 const aoc = @import("aoc");
 
-const Range = struct { min: u16, max: u16 };
-
 const row_count = 128;
 const col_count = 8;
 
-fn binarySearch(code: []const u8, max: u16, comptime front_id: u8, comptime back_id: u8) !u16 {
-    var possible = Range{ .min = 0, .max = max - 1 };
-    for (code) |b| {
-        _ = switch (b) {
-            front_id => possible.max = @floatToInt(u16, //
-                std.math.floor(@intToFloat(f32, possible.min + possible.max) / 2.0)),
-            back_id => possible.min = @floatToInt(u16, //
-                std.math.ceil(@intToFloat(f32, possible.min + possible.max) / 2.0)),
-            else => return aoc.Error.InvalidInput,
-        };
-    }
-    if (possible.min != possible.max)
-        return aoc.Error.InvalidInput;
-    return possible.min;
+// Input is coded in a way that we can do an implicit binary search by replacing
+// identifiers for the lower half with "0" and for the upper halb with "1"
+// See commit <f1b717029cf3262c1fa2760124af258924d668da> for actual binary search
+
+fn code2Id(input: []const u8) !u32 {
+    var value: u32 = 0;
+    for (input) |c|
+        value = value * 2 + @boolToInt(c == 'B' or c == 'R');
+    return value;
 }
 
 fn part1(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
     var lineit = std.mem.tokenize(input, "\n");
-    var answer: ?u32 = null;
+    var answer: u32 = 0;
     while (lineit.next()) |line| {
-        const row = try binarySearch(line[0..7], row_count, 'F', 'B');
-        const col = try binarySearch(line[7..10], col_count, 'L', 'R');
-        const id = row * 8 + col;
-        if (answer == null or id > answer.?)
-            answer = id;
+        const id = try code2Id(line[0..10]);
+        answer = std.math.max(answer, id);
     }
-    std.debug.print("{}\n", .{answer.?});
+    std.debug.print("{}\n", .{answer});
 }
 
 fn part2(allocator: *std.mem.Allocator, input: []u8, args: [][]u8) !void {
     var lineit = std.mem.tokenize(input, "\n");
     var seats = [_]u1{0} ** (row_count * col_count);
+    var min: u32 = std.math.inf_u32;
     while (lineit.next()) |line| {
-        const row = try binarySearch(line[0..7], row_count, 'F', 'B');
-        const col = try binarySearch(line[7..10], col_count, 'L', 'R');
-        const id = row * 8 + col;
+        const id = try code2Id(line);
+        min = std.math.min(min, id);
         seats[id] = 1;
     }
 
-    for (seats) |b, i| {
-        if ((i == 0 or seats[i - 1] == 1) and
-            (i == seats.len - 1 or seats[i + 1] == 1) and seats[i] == 0)
-        {
-            std.debug.print("{}\n", .{i});
+    for (seats[min..]) |b, i| {
+        if (seats[min + i] == 0) {
+            std.debug.print("{}\n", .{min + i});
             break;
         }
     }