{"header":{"message":"Day4: add a 10 times faster solution","description":null,"timestamp":"2022-01-13T11:13:21.652614808Z","authors":[{}]},"hash":"NNEOPQV6SNXJVL3UOUR45I4PLDL5IV72FE4GAQPJSHHRXGFL6QTAC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["NNEOPQV6SNXJVL3UOUR45I4PLDL5IV72FE4GAQPJSHHRXGFL6QTAC","Day4: add a 10 times faster solution"],["AA",null],["W4P3BJJLXCXZEIOGWLTYBFEKD3NWLP2EAGN47ZXPBTHZ5KSC747QC","Add solution for day04"],["DEBJKGU2F4MD5O3DMLE3XPKOGJOAG2KZHMQX7DP52RAP4HBKGFSQC","Day03/2: add a faster solution with bitwise operators and ArrayList"],["ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC","Add build files and solution for day1"],["I2F5R3WUAQR4YWAZPUJ6FVZYMFLOEO7I2BQFW4JFKTDHPR5ERBYQC","Add solution for day03"],["ZY26UMBLD4WVCQYQ63H72K5P3MQ7Q43WBZHBY7M2FZFNSDEYF6QAC","README: add Optimizations and fails part"],["CD3QNDB3NQYMOMGANUU5B2XOX2LMII57DQ53Q2HJC5DSM4GCJB3AC","Add solution for day02"],["4C6H6ZYD4SVDHKIXD76SSFYE32V3GTY75WO6OVXZTL5JA3I3XL5AC","Add README file"]],"deps":["W4P3BJJLXCXZEIOGWLTYBFEKD3NWLP2EAGN47ZXPBTHZ5KSC747QC","DEBJKGU2F4MD5O3DMLE3XPKOGJOAG2KZHMQX7DP52RAP4HBKGFSQC"],"known":["ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC","CD3QNDB3NQYMOMGANUU5B2XOX2LMII57DQ53Q2HJC5DSM4GCJB3AC","4C6H6ZYD4SVDHKIXD76SSFYE32V3GTY75WO6OVXZTL5JA3I3XL5AC","I2F5R3WUAQR4YWAZPUJ6FVZYMFLOEO7I2BQFW4JFKTDHPR5ERBYQC","ZY26UMBLD4WVCQYQ63H72K5P3MQ7Q43WBZHBY7M2FZFNSDEYF6QAC"]},"hunks":[{"FileMove":{"meta":{"basename":"day04_map.zig","metadata":0},"old":[{"basename":"day04.zig","metadata":0}],"up":[{"change":4,"pos":15}],"down":[{"change":2,"pos":34}],"show_perms":false}},{"FileAdd":{"meta":{"basename":"day04.zig","metadata":0},"context":[{"change":4,"pos":15}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":""},{"Add":"const path = \"../data/day04/input.txt\";"},{"Add":""},{"Add":"const retSize = u16;"},{"Add":""},{"Add":"const grid_size = 5;"},{"Add":"const grid_item_size = u7;"},{"Add":"const Board = struct {"},{"Add":" items: [grid_size][grid_size]grid_item_size,"},{"Add":" row: [grid_size]u5 = [_]u5{0} ** grid_size,"},{"Add":" col: [grid_size]u5 = [_]u5{0} ** grid_size,"},{"Add":" pub fn value(self: @This()) retSize {"},{"Add":" var ret: retSize = 0;"},{"Add":" for (self.items) |row, rowID| {"},{"Add":" for (row) |item, col| {"},{"Add":" if (self.row[rowID] & (@as(u5, 1) <<| col) == 0) {"},{"Add":" ret += item;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" return ret;"},{"Add":" }"},{"Add":"};"},{"Add":""},{"Add":"const Bingo = struct {"},{"Add":" numbers: std.ArrayList(grid_item_size),"},{"Add":" boards: std.ArrayList(Board),"},{"Add":"};"},{"Add":""},{"Add":"fn parseInput(allocator: std.mem.Allocator) anyerror!Bingo {"},{"Add":" const input = @embedFile(path);"},{"Add":" var lines = std.mem.split(u8, input, \"\\n\");"},{"Add":""},{"Add":" var ret = Bingo{"},{"Add":" .numbers = std.ArrayList(grid_item_size).init(allocator),"},{"Add":" .boards = std.ArrayList(Board).init(allocator),"},{"Add":" };"},{"Add":""},{"Add":" var gridRow: u3 = 0;"},{"Add":" var gridCol: u3 = 0;"},{"Add":" var g = Board{ .items = undefined };"},{"Add":""},{"Add":" var idx: usize = 0;"},{"Add":" while (lines.next()) |line| : (idx += 1) {"},{"Add":" // read in numbers"},{"Add":" if (idx == 0) {"},{"Add":" var nums = std.mem.tokenize(u8, line, \",\");"},{"Add":" while (nums.next()) |num| {"},{"Add":" try ret.numbers.append(try std.fmt.parseUnsigned(grid_item_size, num, 10));"},{"Add":" }"},{"Add":" continue;"},{"Add":" }"},{"Add":""},{"Add":" // read in Grids"},{"Add":" var items = std.mem.tokenize(u8, line, \" \");"},{"Add":" while (items.next()) |item| {"},{"Add":" const value = try std.fmt.parseUnsigned(grid_item_size, item, 10);"},{"Add":" g.items[gridRow][gridCol] = value;"},{"Add":" gridCol += 1;"},{"Add":" }"},{"Add":" gridCol = 0;"},{"Add":""},{"Add":" if (line.len != 0) gridRow += 1;"},{"Add":""},{"Add":" // append grid"},{"Add":" if (gridRow == 5) {"},{"Add":" try ret.boards.append(g);"},{"Add":" gridRow = 0;"},{"Add":" gridCol = 0;"},{"Add":" // create new grid"},{"Add":" g = Board{ .items = undefined };"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return ret;"},{"Add":"}"},{"Add":""},{"Add":"fn first() anyerror!retSize {"},{"Add":" var gpa = std.heap.GeneralPurposeAllocator(.{}){};"},{"Add":" const allocator = gpa.allocator();"},{"Add":""},{"Add":" var bg = try parseInput(allocator);"},{"Add":" defer { // cleanup code"},{"Add":" bg.boards.deinit();"},{"Add":" bg.numbers.deinit();"},{"Add":" }"},{"Add":""},{"Add":" for (bg.numbers.items) |num| {"},{"Add":" boards_loop: for (bg.boards.items) |_, idx| {"},{"Add":" var grid = &bg.boards.items[idx];"},{"Add":" for (grid.items) |row, i| {"},{"Add":" for (row) |item, j| {"},{"Add":" if (item == num) {"},{"Add":" // increase row, col counter"},{"Add":" grid.row[i] += @as(u5, 1) <<| j;"},{"Add":" grid.col[j] += @as(u5, 1) <<| i;"},{"Add":" // check if row or grid equals to 11111, return when true"},{"Add":" if ((grid.row[i] == 0b11111) or (grid.col[j] == 0b11111)) {"},{"Add":" return num * grid.value();"},{"Add":" }"},{"Add":" // break out to grid loop"},{"Add":" continue :boards_loop;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unreachable;"},{"Add":"}"},{"Add":""},{"Add":"fn second() anyerror!retSize {"},{"Add":" var gpa = std.heap.GeneralPurposeAllocator(.{}){};"},{"Add":" const allocator = gpa.allocator();"},{"Add":""},{"Add":" var bg = try parseInput(allocator);"},{"Add":" defer { // cleanup code"},{"Add":" bg.boards.deinit();"},{"Add":" bg.numbers.deinit();"},{"Add":" }"},{"Add":""},{"Add":" var to_remove = std.ArrayList(usize).init(allocator);"},{"Add":" defer to_remove.deinit();"},{"Add":""},{"Add":" for (bg.numbers.items) |num| {"},{"Add":" boards_loop: for (bg.boards.items) |_, idx| {"},{"Add":" var grid = &bg.boards.items[idx];"},{"Add":" for (grid.items) |row, i| {"},{"Add":" for (row) |item, j| {"},{"Add":" if (item == num) {"},{"Add":" // increase row, col counter"},{"Add":" grid.row[i] += @as(u5, 1) <<| j;"},{"Add":" grid.col[j] += @as(u5, 1) <<| i;"},{"Add":" // check if row or grid equals to 11111, return when true"},{"Add":" if ((grid.row[i] == 0b11111) or (grid.col[j] == 0b11111)) {"},{"Add":" if (bg.boards.items.len == 1) {"},{"Add":" return num * grid.value();"},{"Add":" } else {"},{"Add":" try to_remove.append(idx);"},{"Add":" }"},{"Add":" }"},{"Add":" // break out to grid loop"},{"Add":" continue :boards_loop;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));"},{"Add":" for (to_remove.items) |idx| {"},{"Add":" _ = bg.boards.swapRemove(idx);"},{"Add":" }"},{"Add":" try to_remove.resize(0);"},{"Add":" }"},{"Add":""},{"Add":" unreachable;"},{"Add":"}"},{"Add":""},{"Add":"pub fn main() anyerror!void {"},{"Add":" var timer = try std.time.Timer.start();"},{"Add":""},{"Add":" _ = try first();"},{"Add":" const f = timer.lap() / 1000;"},{"Add":" _ = try second();"},{"Add":" const s = timer.lap() / 1000;"},{"Add":""},{"Add":" std.debug.print(\"Day 4 \\t\\tfirst: {d}µs \\t\\tsecond: {d}µs\\n\", .{ f, s });"},{"Add":"}"},{"Add":""},{"Add":"test \"first\" {"},{"Add":" try std.testing.expectEqual(@as(retSize, 11536), try first());"},{"Add":"}"},{"Add":""},{"Add":"test \"second\" {"},{"Add":" try std.testing.expectEqual(@as(retSize, 1284), try second());"},{"Add":"}"}]}},{"Replacement":{"inode":{"change":4,"pos":34},"path":"README.md","line":30,"ins":{"up_context":[{"change":4,"pos":644}],"down_context":[{"change":4,"pos":644}],"flag":"BLOCK","start":5282,"end":5319,"inode":{"change":4,"pos":34}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":644},"to":{"change":3,"start":5138,"end":5171},"introduced_by":3}],"inode":{"change":4,"pos":34}},"ins_contents":[{"Add":"### First version: day03_string.zig:"}],"del_contents":[{"Del":"First version: day03_string.zig:\n"}]}},{"Replacement":{"inode":{"change":4,"pos":34},"path":"README.md","line":35,"ins":{"up_context":[{"change":3,"pos":5173}],"down_context":[{"change":3,"pos":5188}],"flag":"BLOCK","start":5320,"end":5339,"inode":{"change":4,"pos":34}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":5173},"to":{"change":3,"start":5173,"end":5188},"introduced_by":3}],"inode":{"change":4,"pos":34}},"ins_contents":[{"Add":"### Final version:"}],"del_contents":[{"Del":"Final version:\n"}]}},{"Edit":{"inode":{"change":4,"pos":34},"path":"README.md","line":42,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":773}],"down_context":[{"change":4,"pos":773}],"flag":"BLOCK","start":5340,"end":5374,"inode":{"change":4,"pos":34}}},"contents":[{"Add":"### First version: day04_map.zig:"}]}},{"Edit":{"inode":{"change":4,"pos":34},"path":"README.md","line":50,"atom":{"NewVertex":{"up_context":[{"change":4,"pos":1155}],"down_context":[],"flag":"BLOCK","start":5375,"end":5816,"inode":{"change":4,"pos":34}}},"contents":[{"Add":""},{"Add":"### Final version:"},{"Add":"I am using `ArrayList` for holding the numbers and boards just like the first"},{"Add":"version, but the `Board` representation is vastly simplified. Items are stored"},{"Add":"in a 5x5 array and I keep track of marked numbers in `row` and `col` which are"},{"Add":"`[5]u5` so it is easier to check if we reached a bingo, do not have to loop through"},{"Add":"the board every time."},{"Add":""},{"Add":"This version runs around 1200-1400 μs, so 10x faster than the first version."}]}}],"owner":"voroskoi","repo":"aoc2021-zig","token":"dX4jl35ScjW/FuUc3DRS2AmPfhCifzVJv8YPyW0i+6I=","login":null}

…

Dependencies

Change contents