const std = @import("std");
const path = "../data/day04/input.txt";
const retSize = u16;
const grid_size = 5;
const grid_item_size = u7;
const Board = struct {
items: [grid_size][grid_size]grid_item_size,
row: [grid_size]u5 = [_]u5{0} ** grid_size,
col: [grid_size]u5 = [_]u5{0} ** grid_size,
pub fn value(self: @This()) retSize {
var ret: retSize = 0;
for (self.items) |row, rowID| {
for (row) |item, col| {
if (self.row[rowID] & (@as(u5, 1) <<| col) == 0) {
ret += item;
}
}
}
return ret;
}
};
const Bingo = struct {
numbers: std.ArrayList(grid_item_size),
boards: std.ArrayList(Board),
};
fn parseInput(allocator: std.mem.Allocator) anyerror!Bingo {
const input = @embedFile(path);
var lines = std.mem.split(u8, input, "\n");
var ret = Bingo{
.numbers = std.ArrayList(grid_item_size).init(allocator),
.boards = std.ArrayList(Board).init(allocator),
};
var gridRow: u3 = 0;
var gridCol: u3 = 0;
var g = Board{ .items = undefined };
var idx: usize = 0;
while (lines.next()) |line| : (idx += 1) {
// read in numbers
if (idx == 0) {
var nums = std.mem.tokenize(u8, line, ",");
while (nums.next()) |num| {
try ret.numbers.append(try std.fmt.parseUnsigned(grid_item_size, num, 10));
}
continue;
}
// read in Grids
var items = std.mem.tokenize(u8, line, " ");
while (items.next()) |item| {
const value = try std.fmt.parseUnsigned(grid_item_size, item, 10);
g.items[gridRow][gridCol] = value;
gridCol += 1;
}
gridCol = 0;
if (line.len != 0) gridRow += 1;
// append grid
if (gridRow == 5) {
try ret.boards.append(g);
gridRow = 0;
gridCol = 0;
// create new grid
g = Board{ .items = undefined };
}
}
return ret;
}
fn first() anyerror!retSize {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var bg = try parseInput(allocator);
defer { // cleanup code
bg.boards.deinit();
bg.numbers.deinit();
}
for (bg.numbers.items) |num| {
boards_loop: for (bg.boards.items) |_, idx| {
var grid = &bg.boards.items[idx];
for (grid.items) |row, i| {
for (row) |item, j| {
if (item == num) {
// increase row, col counter
grid.row[i] += @as(u5, 1) <<| j;
grid.col[j] += @as(u5, 1) <<| i;
// check if row or grid equals to 11111, return when true
if ((grid.row[i] == 0b11111) or (grid.col[j] == 0b11111)) {
return num * grid.value();
}
// break out to grid loop
continue :boards_loop;
}
}
}
}
}
unreachable;
}
fn second() anyerror!retSize {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
const allocator = gpa.allocator();
var bg = try parseInput(allocator);
defer { // cleanup code
bg.boards.deinit();
bg.numbers.deinit();
}
var to_remove = std.ArrayList(usize).init(allocator);
defer to_remove.deinit();
for (bg.numbers.items) |num| {
boards_loop: for (bg.boards.items) |_, idx| {
var grid = &bg.boards.items[idx];
for (grid.items) |row, i| {
for (row) |item, j| {
if (item == num) {
// increase row, col counter
grid.row[i] += @as(u5, 1) <<| j;
grid.col[j] += @as(u5, 1) <<| i;
// check if row or grid equals to 11111, return when true
if ((grid.row[i] == 0b11111) or (grid.col[j] == 0b11111)) {
if (bg.boards.items.len == 1) {
return num * grid.value();
} else {
try to_remove.append(idx);
}
}
// break out to grid loop
continue :boards_loop;
}
}
}
}
std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));
for (to_remove.items) |idx| {
_ = bg.boards.swapRemove(idx);
}
try to_remove.resize(0);
}
unreachable;
}
pub fn main() anyerror!void {
var timer = try std.time.Timer.start();
_ = try first();
const f = timer.lap() / 1000;
_ = try second();
const s = timer.lap() / 1000;
std.debug.print("Day 4 \t\tfirst: {d}µs \t\tsecond: {d}µs\n", .{ f, s });
}
test "first" {
try std.testing.expectEqual(@as(retSize, 11536), try first());
}
test "second" {
try std.testing.expectEqual(@as(retSize, 1284), try second());
}