{"header":{"message":"Solve day15","description":null,"timestamp":"2022-12-17T18:46:18.644204525Z","authors":[{}]},"hash":"D7GBA7SY7RLJWWNKR2TAQWSD2Q53IWWVQ63EXXQWSLBEDB5ZNEKAC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["D7GBA7SY7RLJWWNKR2TAQWSD2Q53IWWVQ63EXXQWSLBEDB5ZNEKAC","Solve day15"],["AA",null],["2BFUSZ5LMQTRGFHXBM572CTSJJOY75U4UCPNFKUD6ETFHWU2DTEQC","Solve day14"],["6WJPOP3LUG2I75AXQSC2ZI6WMHLLFDHCWEO3UV5XAKH67D7K2LFQC","Solve day04"],["IISEBR52NLKVBJJEBSYWXI4LG2Y3E5GPNZJ66CA26K6IBXP3DOHQC","Solve day07"],["WC64ZGNE5CFYQR5SLPNMGPQJKTAIYUD4EE4J2MZ74YRCL7RIQNHQC","Solve day03"],["BMPRLYZ3LIGIOEFYVBYAG3ZGA34IU3GSRWXJT24AXRMVH7FT5IDQC","Solve day09"],["5FITZYLXP6RMEMO3HJU4TQAEE7H355H2TNJJAM2GCNNUC4VZBJBQC","Solve day08"],["YJL3GJPLRE4WKBAJ4H7P7H2ZNXIW5MXOFEUCWGZQWDALCNRUMWGQC","Solve day11"],["BMVU5JZZ7P6OFVYIELRHKMQH7XTGCTNQDRZINSXVYEQKQ4K65DBQC","Solve day12"],["B7WMDH6SSILSWYJDOVVAFQKVY7OKG4Z43EORSTLYKT54KLYUVDGQC","Solve day05"],["X5GKEVTZTQHMFJYNKP3UY6IPZS4ZSS7GZUZ2TODKVWRUKT654WLAC","Import AoC template"],["VTRQE7TUTF5CLFUPCFURXGT3SUHNNVABFDLI4LF76RIUW2QV5NUQC","Solve day02"],["CVV5BF3YOVVDOA4NDO6JRWZLNWSKJ26GLCVXNP66V7FN3235MCXQC","Solve day10"],["K4ZMUQAUI3INPZN5SXEX2MM4SRZXED7TNCS3DN6DADOFUT5XOPRQC","Solve day06"],["SA6HSFMF7YEOYQNAOLLC7PSNTGRHKAYIWF5ZIQALRQTS4N3MEFUAC","Solve day13"],["V2BPQIR2KMSVDOCF5NT2BKYENX24B3AOPFTIOOKSWFXC6UR5VROQC","Solve day01"]],"deps":["2BFUSZ5LMQTRGFHXBM572CTSJJOY75U4UCPNFKUD6ETFHWU2DTEQC"],"known":["X5GKEVTZTQHMFJYNKP3UY6IPZS4ZSS7GZUZ2TODKVWRUKT654WLAC","VTRQE7TUTF5CLFUPCFURXGT3SUHNNVABFDLI4LF76RIUW2QV5NUQC","WC64ZGNE5CFYQR5SLPNMGPQJKTAIYUD4EE4J2MZ74YRCL7RIQNHQC","6WJPOP3LUG2I75AXQSC2ZI6WMHLLFDHCWEO3UV5XAKH67D7K2LFQC","B7WMDH6SSILSWYJDOVVAFQKVY7OKG4Z43EORSTLYKT54KLYUVDGQC","K4ZMUQAUI3INPZN5SXEX2MM4SRZXED7TNCS3DN6DADOFUT5XOPRQC","IISEBR52NLKVBJJEBSYWXI4LG2Y3E5GPNZJ66CA26K6IBXP3DOHQC","5FITZYLXP6RMEMO3HJU4TQAEE7H355H2TNJJAM2GCNNUC4VZBJBQC","BMPRLYZ3LIGIOEFYVBYAG3ZGA34IU3GSRWXJT24AXRMVH7FT5IDQC","CVV5BF3YOVVDOA4NDO6JRWZLNWSKJ26GLCVXNP66V7FN3235MCXQC","YJL3GJPLRE4WKBAJ4H7P7H2ZNXIW5MXOFEUCWGZQWDALCNRUMWGQC","BMVU5JZZ7P6OFVYIELRHKMQH7XTGCTNQDRZINSXVYEQKQ4K65DBQC","SA6HSFMF7YEOYQNAOLLC7PSNTGRHKAYIWF5ZIQALRQTS4N3MEFUAC"]},"hunks":[{"Replacement":{"inode":{"change":3,"pos":50},"path":"src/main.zig","line":5,"ins":{"up_context":[{"change":3,"pos":105}],"down_context":[{"change":3,"pos":121}],"flag":"BLOCK","start":0,"end":17,"inode":{"change":3,"pos":50}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":3,"pos":105},"to":{"change":2,"start":0,"end":17},"introduced_by":2}],"inode":{"change":3,"pos":50}},"ins_contents":[{"Add":"const DAYS = 15;"}],"del_contents":[{"Del":"const DAYS = 14;\n"}]}},{"Edit":{"inode":{"change":3,"pos":50},"path":"src/main.zig","line":22,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":58}],"down_context":[{"change":3,"pos":187}],"flag":"BLOCK","start":18,"end":58,"inode":{"change":3,"pos":50}}},"contents":[{"Add":" const day15 = @import(\"day15.zig\");"}]}},{"Edit":{"inode":{"change":3,"pos":50},"path":"src/main.zig","line":40,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":89}],"down_context":[{"change":3,"pos":228}],"flag":"BLOCK","start":59,"end":89,"inode":{"change":3,"pos":50}}},"contents":[{"Add":" _ = @import(\"day15.zig\");"}]}},{"FileAdd":{"meta":{"basename":"day15.txt","metadata":0},"context":[{"change":17,"pos":18}],"contents":[{"Add":"Sensor at x=2983166, y=2813277: closest beacon is at x=3152133, y=2932891"},{"Add":"Sensor at x=2507490, y=122751: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=3273116, y=2510538: closest beacon is at x=3152133, y=2932891"},{"Add":"Sensor at x=1429671, y=995389: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=2465994, y=2260162: closest beacon is at x=2734551, y=2960647"},{"Add":"Sensor at x=2926899, y=3191882: closest beacon is at x=2734551, y=2960647"},{"Add":"Sensor at x=1022491, y=1021177: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=1353273, y=1130973: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=1565476, y=2081049: closest beacon is at x=1597979, y=2000000"},{"Add":"Sensor at x=1841125, y=1893566: closest beacon is at x=1597979, y=2000000"},{"Add":"Sensor at x=99988, y=71317: closest beacon is at x=86583, y=-1649857"},{"Add":"Sensor at x=3080600, y=3984582: closest beacon is at x=3175561, y=4138060"},{"Add":"Sensor at x=3942770, y=3002123: closest beacon is at x=3724687, y=3294321"},{"Add":"Sensor at x=1572920, y=2031447: closest beacon is at x=1597979, y=2000000"},{"Add":"Sensor at x=218329, y=1882777: closest beacon is at x=1597979, y=2000000"},{"Add":"Sensor at x=1401723, y=1460526: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=2114094, y=985978: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=3358586, y=3171857: closest beacon is at x=3152133, y=2932891"},{"Add":"Sensor at x=1226284, y=3662922: closest beacon is at x=2514367, y=3218259"},{"Add":"Sensor at x=3486366, y=3717867: closest beacon is at x=3724687, y=3294321"},{"Add":"Sensor at x=1271873, y=831354: closest beacon is at x=1515109, y=970092"},{"Add":"Sensor at x=3568311, y=1566400: closest beacon is at x=3152133, y=2932891"},{"Add":"Sensor at x=3831960, y=3146611: closest beacon is at x=3724687, y=3294321"},{"Add":"Sensor at x=2505534, y=3196726: closest beacon is at x=2514367, y=3218259"},{"Add":"Sensor at x=2736967, y=3632098: closest beacon is at x=2514367, y=3218259"},{"Add":"Sensor at x=3963402, y=3944423: closest beacon is at x=3724687, y=3294321"},{"Add":"Sensor at x=1483115, y=2119639: closest beacon is at x=1597979, y=2000000"}]}},{"FileAdd":{"meta":{"basename":"day15.zig","metadata":0},"context":[{"change":3,"pos":15}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":""},{"Add":"const PATH = \"input/day15.txt\";"},{"Add":"const Str = []const u8;"},{"Add":""},{"Add":"pub fn first(allocator: std.mem.Allocator) !usize {"},{"Add":" var zone = try parseInput(allocator, @embedFile(PATH));"},{"Add":" defer zone.sens.deinit();"},{"Add":""},{"Add":" // We have a beacon on that line, that's why the '-1'"},{"Add":" return try zone.noBeacon(allocator, 2_000_000) - 1;"},{"Add":"}"},{"Add":""},{"Add":"pub fn second(allocator: std.mem.Allocator) !usize {"},{"Add":" const MAX = 4_000_000;"},{"Add":" var arena = std.heap.ArenaAllocator.init(allocator);"},{"Add":" defer arena.deinit();"},{"Add":""},{"Add":" var zone = try parseInput(arena.allocator(), @embedFile(PATH));"},{"Add":" defer zone.sens.deinit();"},{"Add":""},{"Add":" var line: isize = 0;"},{"Add":" while (line <= MAX) : (line += 1) {"},{"Add":" const ret = try zone.noBeaconLimit(arena.allocator(), line, 0, MAX);"},{"Add":" // std.debug.print(\"ret: {d}\\n\", .{ret});"},{"Add":" if (ret < MAX + 1) {"},{"Add":" // std.debug.print(\"{d}\\n\", .{line});"},{"Add":" return ret * 4_000_000 + @intCast(usize, line);"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unreachable;"},{"Add":"}"},{"Add":""},{"Add":"test \"day15a\" {"},{"Add":" try std.testing.expectEqual(@as(usize, 6078701), try first(std.testing.allocator));"},{"Add":"}"},{"Add":""},{"Add":"test \"day15b\" {"},{"Add":" try std.testing.expectEqual(@as(usize, 12567351400528), try second(std.testing.allocator));"},{"Add":"}"},{"Add":""},{"Add":"const Coord = struct {"},{"Add":" x: isize,"},{"Add":" y: isize,"},{"Add":""},{"Add":" fn lessThan(context: void, a: @This(), b: @This()) bool {"},{"Add":" _ = context;"},{"Add":" return a.x < b.x;"},{"Add":" }"},{"Add":"};"},{"Add":""},{"Add":"const Pair = struct {"},{"Add":" sensor: Coord,"},{"Add":" manhattan: isize,"},{"Add":"};"},{"Add":""},{"Add":"const Zone = struct {"},{"Add":" sens: std.ArrayList(Pair),"},{"Add":""},{"Add":" fn noBeaconLimit("},{"Add":" self: @This(),"},{"Add":" allocator: std.mem.Allocator,"},{"Add":" line_number: isize,"},{"Add":" min: isize,"},{"Add":" max: isize,"},{"Add":" ) !usize {"},{"Add":" var intervals = std.ArrayList(Coord).init(allocator);"},{"Add":" defer intervals.deinit();"},{"Add":""},{"Add":" for (self.sens.items) |pair| {"},{"Add":" const perp = try std.math.absInt(pair.sensor.y - line_number);"},{"Add":" const diff = pair.manhattan - perp;"},{"Add":" if (diff < 0) continue;"},{"Add":""},{"Add":" const interval = .{ .x = pair.sensor.x - diff, .y = pair.sensor.x + diff };"},{"Add":" try intervals.append(interval);"},{"Add":" }"},{"Add":""},{"Add":" std.sort.sort(Coord, intervals.items, {}, Coord.lessThan);"},{"Add":""},{"Add":" var unique = std.ArrayList(Coord).init(allocator);"},{"Add":" defer unique.deinit();"},{"Add":""},{"Add":" try unique.append(intervals.items[0]);"},{"Add":""},{"Add":" var idx: usize = 1;"},{"Add":" while (idx < intervals.items.len) : (idx += 1) {"},{"Add":" const item = intervals.items[idx];"},{"Add":" const top = unique.items[unique.items.len - 1];"},{"Add":""},{"Add":" if (top.y < item.x) {"},{"Add":" try unique.append(item);"},{"Add":" } else if (top.y < item.y) {"},{"Add":" unique.items[unique.items.len - 1].y = item.y;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" var counter: usize = 0;"},{"Add":" for (unique.items) |item| {"},{"Add":" counter += @intCast(usize, std.math.min(item.y, max) - std.math.max(item.x, min)) + 1;"},{"Add":" }"},{"Add":""},{"Add":" if (counter < max + 1) {"},{"Add":" return @intCast(usize, unique.items[0].y) + 1;"},{"Add":" }"},{"Add":""},{"Add":" return counter;"},{"Add":" }"},{"Add":""},{"Add":" fn noBeacon(self: @This(), allocator: std.mem.Allocator, line_number: isize) !usize {"},{"Add":" var intervals = std.ArrayList(Coord).init(allocator);"},{"Add":" defer intervals.deinit();"},{"Add":""},{"Add":" for (self.sens.items) |pair| {"},{"Add":" const perp = try std.math.absInt(pair.sensor.y - line_number);"},{"Add":" const diff = pair.manhattan - perp;"},{"Add":" if (diff < 0) continue;"},{"Add":""},{"Add":" const interval = .{ .x = pair.sensor.x - diff, .y = pair.sensor.x + diff };"},{"Add":" try intervals.append(interval);"},{"Add":" }"},{"Add":""},{"Add":" std.sort.sort(Coord, intervals.items, {}, Coord.lessThan);"},{"Add":""},{"Add":" var unique = std.ArrayList(Coord).init(allocator);"},{"Add":" defer unique.deinit();"},{"Add":""},{"Add":" try unique.append(intervals.items[0]);"},{"Add":""},{"Add":" var idx: usize = 1;"},{"Add":" while (idx < intervals.items.len) : (idx += 1) {"},{"Add":" const item = intervals.items[idx];"},{"Add":" const top = unique.items[unique.items.len - 1];"},{"Add":""},{"Add":" if (top.y < item.x) {"},{"Add":" try unique.append(item);"},{"Add":" } else if (top.y < item.y) {"},{"Add":" unique.items[unique.items.len - 1].y = item.y;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" var counter: usize = 0;"},{"Add":" for (unique.items) |item| {"},{"Add":" // std.debug.print(\"{d} <-> {d}\\n\", .{ item.x, item.y });"},{"Add":" counter += @intCast(usize, item.y - item.x) + 1;"},{"Add":" }"},{"Add":""},{"Add":" return counter;"},{"Add":" }"},{"Add":"};"},{"Add":""},{"Add":"fn manhattan(a: Coord, b: Coord) !isize {"},{"Add":" const x = try std.math.absInt(a.x - b.x);"},{"Add":" const y = try std.math.absInt(a.y - b.y);"},{"Add":" return x + y;"},{"Add":"}"},{"Add":""},{"Add":"fn parseInput(allocator: std.mem.Allocator, in: Str) !Zone {"},{"Add":" var zone: Zone = undefined;"},{"Add":" zone.sens = std.ArrayList(Pair).init(allocator);"},{"Add":""},{"Add":" var lines = std.mem.tokenize(u8, in, \"\\n\");"},{"Add":" while (lines.next()) |line| {"},{"Add":" var split = std.mem.tokenize(u8, line, \":\");"},{"Add":""},{"Add":" // Sensor"},{"Add":" var scrd = std.mem.tokenize(u8, split.next().?[10..], \", \");"},{"Add":" // std.debug.print(\"{s} {s}\\n\", .{ scrd.next().?, scrd.next().? });"},{"Add":" const sx = try std.fmt.parseInt(isize, scrd.next().?[2..], 10);"},{"Add":" const sy = try std.fmt.parseInt(isize, scrd.next().?[2..], 10);"},{"Add":" const s = .{ .x = sx, .y = sy };"},{"Add":""},{"Add":" // Beacon"},{"Add":" var bcrd = std.mem.tokenize(u8, split.next().?[22..], \", \");"},{"Add":" // std.debug.print(\"{s} {s}\\n\", .{ bcrd.next().?, bcrd.next().? });"},{"Add":" const bx = try std.fmt.parseInt(isize, bcrd.next().?[2..], 10);"},{"Add":" const by = try std.fmt.parseInt(isize, bcrd.next().?[2..], 10);"},{"Add":" const b = .{ .x = bx, .y = by };"},{"Add":""},{"Add":" const m = try manhattan(s, b);"},{"Add":""},{"Add":" try zone.sens.append(.{ .sensor = s, .manhattan = m });"},{"Add":" }"},{"Add":""},{"Add":" return zone;"},{"Add":"}"},{"Add":""},{"Add":"const test_input ="},{"Add":" \\\\Sensor at x=2, y=18: closest beacon is at x=-2, y=15"},{"Add":" \\\\Sensor at x=9, y=16: closest beacon is at x=10, y=16"},{"Add":" \\\\Sensor at x=13, y=2: closest beacon is at x=15, y=3"},{"Add":" \\\\Sensor at x=12, y=14: closest beacon is at x=10, y=16"},{"Add":" \\\\Sensor at x=10, y=20: closest beacon is at x=10, y=16"},{"Add":" \\\\Sensor at x=14, y=17: closest beacon is at x=10, y=16"},{"Add":" \\\\Sensor at x=8, y=7: closest beacon is at x=2, y=10"},{"Add":" \\\\Sensor at x=2, y=0: closest beacon is at x=2, y=10"},{"Add":" \\\\Sensor at x=0, y=11: closest beacon is at x=2, y=10"},{"Add":" \\\\Sensor at x=20, y=14: closest beacon is at x=25, y=17"},{"Add":" \\\\Sensor at x=17, y=20: closest beacon is at x=21, y=22"},{"Add":" \\\\Sensor at x=16, y=7: closest beacon is at x=15, y=3"},{"Add":" \\\\Sensor at x=14, y=3: closest beacon is at x=15, y=3"},{"Add":" \\\\Sensor at x=20, y=1: closest beacon is at x=15, y=3"},{"Add":";"}]}}],"owner":"voroskoi","repo":"aoc2022-zig","token":"IGyPAbolPCpMoyKt7rQCXiimA0b194T74CnjznG7NT4=","login":null}

…

Dependencies

Change contents