{"header":{"message":"Day03/2: add a faster solution with bitwise operators and ArrayList","description":null,"timestamp":"2022-01-13T06:56:14.836824934Z","authors":[{}]},"hash":"DEBJKGU2F4MD5O3DMLE3XPKOGJOAG2KZHMQX7DP52RAP4HBKGFSQC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["DEBJKGU2F4MD5O3DMLE3XPKOGJOAG2KZHMQX7DP52RAP4HBKGFSQC","Day03/2: add a faster solution with bitwise operators and ArrayList"],["AA",null],["I2F5R3WUAQR4YWAZPUJ6FVZYMFLOEO7I2BQFW4JFKTDHPR5ERBYQC","Add solution for day03"],["ZY26UMBLD4WVCQYQ63H72K5P3MQ7Q43WBZHBY7M2FZFNSDEYF6QAC","README: add Optimizations and fails part"],["W4P3BJJLXCXZEIOGWLTYBFEKD3NWLP2EAGN47ZXPBTHZ5KSC747QC","Add solution for day04"],["ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC","Add build files and solution for day1"],["CD3QNDB3NQYMOMGANUU5B2XOX2LMII57DQ53Q2HJC5DSM4GCJB3AC","Add solution for day02"],["4C6H6ZYD4SVDHKIXD76SSFYE32V3GTY75WO6OVXZTL5JA3I3XL5AC","Add README file"]],"deps":["I2F5R3WUAQR4YWAZPUJ6FVZYMFLOEO7I2BQFW4JFKTDHPR5ERBYQC","ZY26UMBLD4WVCQYQ63H72K5P3MQ7Q43WBZHBY7M2FZFNSDEYF6QAC"],"known":["ISKIMCRTCM4ZY34QENDO4AN7ZAKRRBPFLA5MYHXH2K6Q2WKJDZNQC","CD3QNDB3NQYMOMGANUU5B2XOX2LMII57DQ53Q2HJC5DSM4GCJB3AC","4C6H6ZYD4SVDHKIXD76SSFYE32V3GTY75WO6OVXZTL5JA3I3XL5AC","W4P3BJJLXCXZEIOGWLTYBFEKD3NWLP2EAGN47ZXPBTHZ5KSC747QC"]},"hunks":[{"FileMove":{"meta":{"basename":"day03_string.zig","metadata":0},"old":[{"basename":"day03.zig","metadata":0}],"up":[{"change":4,"pos":15}],"down":[{"change":2,"pos":65}],"show_perms":false}},{"FileAdd":{"meta":{"basename":"day03.zig","metadata":0},"context":[{"change":4,"pos":15}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":""},{"Add":"const path = \"../data/day03/input.txt\";"},{"Add":""},{"Add":"const retSize = u24;"},{"Add":"const lineSize = getLineSize();"},{"Add":""},{"Add":"fn first() anyerror!retSize {"},{"Add":" const input = @embedFile(path);"},{"Add":" var lines = std.mem.split(u8, input, \"\\n\");"},{"Add":""},{"Add":" var ones: [lineSize]retSize = undefined;"},{"Add":" var zeros: [lineSize]retSize = undefined;"},{"Add":""},{"Add":" while (lines.next()) |line| {"},{"Add":" for (line) |bit, idx| {"},{"Add":" if (bit == '0') {"},{"Add":" zeros[idx] += 1;"},{"Add":" } else {"},{"Add":" ones[idx] += 1;"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" var gammaRate: [lineSize]u8 = undefined;"},{"Add":" var epsilonRate: [lineSize]u8 = undefined;"},{"Add":""},{"Add":" for (ones) |val, i| {"},{"Add":" if (val > zeros[i]) {"},{"Add":" gammaRate[i] = '1';"},{"Add":" epsilonRate[i] = '0';"},{"Add":" } else {"},{"Add":" gammaRate[i] = '0';"},{"Add":" epsilonRate[i] = '1';"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" const gr = try std.fmt.parseUnsigned(retSize, &gammaRate, 2);"},{"Add":" const er = try std.fmt.parseUnsigned(retSize, &epsilonRate, 2);"},{"Add":""},{"Add":" return gr * er;"},{"Add":"}"},{"Add":""},{"Add":"fn second() anyerror!retSize {"},{"Add":" const input = @embedFile(path);"},{"Add":" var lines = std.mem.tokenize(u8, input, \"\\n\");"},{"Add":""},{"Add":" var buffer: [1000 * lineSize * 100]u8 = undefined;"},{"Add":" var fba = std.heap.FixedBufferAllocator.init(&buffer);"},{"Add":" const allocator = fba.allocator();"},{"Add":""},{"Add":" var lines_array = std.ArrayList(retSize).init(allocator);"},{"Add":" defer lines_array.deinit();"},{"Add":" var lines_array2 = std.ArrayList(retSize).init(allocator);"},{"Add":" defer lines_array2.deinit();"},{"Add":""},{"Add":" while (lines.next()) |line| {"},{"Add":" try lines_array.append(try std.fmt.parseUnsigned(retSize, line, 2));"},{"Add":" try lines_array2.append(try std.fmt.parseUnsigned(retSize, line, 2));"},{"Add":" }"},{"Add":""},{"Add":" const ox = try getOxigenRating(allocator, &lines_array);"},{"Add":" const co = try getCO2Rating(allocator, &lines_array2);"},{"Add":""},{"Add":" return ox * co;"},{"Add":"}"},{"Add":""},{"Add":"fn getOxigenRating(allocator: std.mem.Allocator, oxigen: *std.ArrayList(retSize)) anyerror!retSize {"},{"Add":" var to_remove = std.ArrayList(usize).init(allocator);"},{"Add":" defer to_remove.deinit();"},{"Add":""},{"Add":" var idx: usize = lineSize;"},{"Add":" while (oxigen.items.len > 1) : (idx -= 1) {"},{"Add":" var ones: retSize = 0;"},{"Add":" var zeros: retSize = 0;"},{"Add":""},{"Add":" // count ones and zeros"},{"Add":" for (oxigen.items) |line| {"},{"Add":" if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {"},{"Add":" ones += 1;"},{"Add":" } else {"},{"Add":" zeros += 1;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // std.debug.print(\"{d} {d} {d}\", .{ones, zeros, idx-1});"},{"Add":""},{"Add":" for (oxigen.items) |line, i| {"},{"Add":" if (ones >= zeros) {"},{"Add":" if ((line & (@as(retSize, 1) <<| idx - 1)) == 0) {"},{"Add":" try to_remove.append(i);"},{"Add":" }"},{"Add":" } else {"},{"Add":" if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {"},{"Add":" try to_remove.append(i);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));"},{"Add":" for (to_remove.items) |i| {"},{"Add":" _ = oxigen.swapRemove(i);"},{"Add":" }"},{"Add":" try to_remove.resize(0);"},{"Add":""},{"Add":" // std.debug.print(\"{d}\\n\", .{oxigen.items.len});"},{"Add":" }"},{"Add":""},{"Add":" return oxigen.items[0];"},{"Add":"}"},{"Add":""},{"Add":"fn getCO2Rating(allocator: std.mem.Allocator, co2: *std.ArrayList(retSize)) anyerror!retSize {"},{"Add":" var to_remove = std.ArrayList(usize).init(allocator);"},{"Add":" defer to_remove.deinit();"},{"Add":""},{"Add":" var idx: usize = lineSize;"},{"Add":" while (co2.items.len > 1) : (idx -= 1) {"},{"Add":" var ones: retSize = 0;"},{"Add":" var zeros: retSize = 0;"},{"Add":""},{"Add":" // count ones and zeros"},{"Add":" for (co2.items) |line| {"},{"Add":" if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {"},{"Add":" ones += 1;"},{"Add":" } else {"},{"Add":" zeros += 1;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // std.debug.print(\"{d} {d} {d}\", .{ones, zeros, idx-1});"},{"Add":""},{"Add":" for (co2.items) |line, i| {"},{"Add":" if (zeros <= ones) {"},{"Add":" if ((line & (@as(retSize, 1) <<| idx - 1)) != 0) {"},{"Add":" try to_remove.append(i);"},{"Add":" }"},{"Add":" } else {"},{"Add":" if ((line & (@as(retSize, 1) <<| idx - 1)) == 0) {"},{"Add":" try to_remove.append(i);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" std.sort.sort(usize, to_remove.items, {}, comptime std.sort.desc(usize));"},{"Add":" for (to_remove.items) |i| {"},{"Add":" _ = co2.swapRemove(i);"},{"Add":" }"},{"Add":" try to_remove.resize(0);"},{"Add":""},{"Add":" // std.debug.print(\"{d}\\n\", .{co2.items.len});"},{"Add":" }"},{"Add":""},{"Add":" return co2.items[0];"},{"Add":"}"},{"Add":""},{"Add":"fn getLineSize() usize {"},{"Add":" const input = @embedFile(path);"},{"Add":""},{"Add":" var ret: usize = 0;"},{"Add":" for (input) |bit, idx| {"},{"Add":" if (bit == '\\n') {"},{"Add":" ret = idx;"},{"Add":" break;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return ret;"},{"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 3 \\t\\tfirst: {d}µs \\t\\tsecond: {d}µs\\n\", .{ f, s });"},{"Add":"}"},{"Add":""},{"Add":"test \"first\" {"},{"Add":" try std.testing.expectEqual(@as(retSize, 3847100), try first());"},{"Add":"}"},{"Add":""},{"Add":"test \"second\" {"},{"Add":" try std.testing.expectEqual(@as(retSize, 4105235), try second());"},{"Add":"}"}]}},{"Edit":{"inode":{"change":4,"pos":34},"path":"README.md","line":10,"atom":{"EdgeMap":{"edges":[{"previous":"","flag":"DELETED","from":{"change":3,"pos":194},"to":{"change":4,"start":251,"end":252},"introduced_by":3},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":251},"to":{"change":4,"start":251,"end":252},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":252},"to":{"change":4,"start":252,"end":295},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":295},"to":{"change":4,"start":295,"end":304},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":304},"to":{"change":3,"start":195,"end":271},"introduced_by":3}],"inode":{"change":4,"pos":34}}},"contents":[{"Del":"\n"},{"Del":"# Ideas to enhance various solution speed\n\n"},{"Del":"## Day 3\n"},{"Del":"\nInstead of using strings, try comparing bitwise. It should go much faster.\n"}]}},{"Edit":{"inode":{"change":4,"pos":34},"path":"README.md","line":30,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":644}],"down_context":[{"change":3,"pos":644}],"flag":"BLOCK","start":5138,"end":5171,"inode":{"change":4,"pos":34}}},"contents":[{"Add":"First version: day03_string.zig:"}]}},{"Edit":{"inode":{"change":4,"pos":34},"path":"README.md","line":34,"atom":{"NewVertex":{"up_context":[{"change":3,"pos":762}],"down_context":[{"change":3,"pos":762}],"flag":"BLOCK","start":5172,"end":5386,"inode":{"change":4,"pos":34}}},"contents":[{"Add":""},{"Add":"Final version:"},{"Add":"Using `std.ArrayList` instead of `std.BufSet` and bitwise operators instead of"},{"Add":"strings makes things faster. ~2200 μs with `std.testing.allocator` and ~950 μs"},{"Add":"with `std.heap.FixedBufferAllocator`."}]}}],"owner":"voroskoi","repo":"aoc2021-zig","token":"UzYV4oqlwvOa73UqJQvqAPIPUi9kSsRvMlSM9xH4OVg=","login":null}

…

Dependencies

Change contents