{"header":{"message":"Add missing day16.zig","description":null,"timestamp":"2022-05-16T18:19:56.833538089Z","authors":[{}]},"hash":"UP23LKD7AAOVXG32BUBJELAO3USAIMPBNYYLN64BELKL7OUD4BCQC","authors":[{"login":"voroskoi","key":"Guf8VYJNUiWAqxwLxDSKxmvvtY65ht2zK2q4h6VhxrcZ"}],"deps":{"hashes":[["UP23LKD7AAOVXG32BUBJELAO3USAIMPBNYYLN64BELKL7OUD4BCQC","Add missing day16.zig"],["AA",null],["ONQOGY2EUWGA5ATHOESEQHAQJLBSNPX7MAHY53SOC3R2IPXSVJ6AC","Add solution for day01"]],"deps":["ONQOGY2EUWGA5ATHOESEQHAQJLBSNPX7MAHY53SOC3R2IPXSVJ6AC"],"known":[]},"hunks":[{"FileAdd":{"meta":{"basename":"day16.zig","metadata":0},"context":[{"change":2,"pos":15}],"contents":[{"Add":"const std = @import(\"std\");"},{"Add":""},{"Add":"const PATH = \"../input/day16.txt\";"},{"Add":""},{"Add":"const Str = []const u8;"},{"Add":""},{"Add":"const InputType = u10;"},{"Add":"const Range = [2]InputType;"},{"Add":"const ticket_lenght = 20;"},{"Add":"const Ticket = [ticket_lenght]InputType;"},{"Add":""},{"Add":"const Data = struct {"},{"Add":" ranges: []Range,"},{"Add":" tickets: []Ticket,"},{"Add":"};"},{"Add":""},{"Add":"pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {"},{"Add":" const file = @embedFile(PATH);"},{"Add":""},{"Add":" const ranges = try parseRanges(allocator.?, file);"},{"Add":" defer allocator.?.free(ranges);"},{"Add":""},{"Add":" var sum: usize = 0;"},{"Add":" var empty_lines: u2 = 0;"},{"Add":" var lines = std.mem.split(u8, file, \"\\n\");"},{"Add":" while (lines.next()) |line| {"},{"Add":" if (line.len == 0) {"},{"Add":" empty_lines += 1;"},{"Add":" continue;"},{"Add":" }"},{"Add":" if (empty_lines < 2) continue;"},{"Add":" if (line[0] < 48 or line[0] > 57) continue;"},{"Add":" var numbers = std.mem.tokenize(u8, line, \",\");"},{"Add":""},{"Add":" nums: while (numbers.next()) |num_str| {"},{"Add":" const num = try std.fmt.parseUnsigned(InputType, num_str, 0);"},{"Add":" for (ranges) |range| {"},{"Add":" if (num >= range[0] and num <= range[1]) continue :nums;"},{"Add":" }"},{"Add":" sum += num;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return sum;"},{"Add":"}"},{"Add":""},{"Add":"pub fn second(allocator: ?std.mem.Allocator) anyerror!usize {"},{"Add":" const data = try parseData(allocator.?, @embedFile(PATH));"},{"Add":" defer {"},{"Add":" allocator.?.free(data.ranges);"},{"Add":" allocator.?.free(data.tickets);"},{"Add":" }"},{"Add":""},{"Add":" var prod: usize = 1;"},{"Add":""},{"Add":" var found_columns = std.StaticBitSet(ticket_lenght).initEmpty();"},{"Add":" var found_ranges: u20 = 0;"},{"Add":""},{"Add":" while (true) {"},{"Add":" var idx: usize = 0;"},{"Add":" ranges: while (idx < data.ranges.len / 2) : (idx += 1) {"},{"Add":" std.debug.assert(idx < data.ranges.len / 2);"},{"Add":""},{"Add":" if (found_ranges & @as(u20, 1) << @intCast(u5, idx) != 0) continue;"},{"Add":""},{"Add":" // starting value is out of range, guaranteen uniqueness"},{"Add":" var match: usize = ticket_lenght;"},{"Add":""},{"Add":" var col: usize = 0;"},{"Add":" cols: while (col < ticket_lenght) : (col += 1) {"},{"Add":" std.debug.assert(col < ticket_lenght);"},{"Add":""},{"Add":" // skip already found columns"},{"Add":" if (found_columns.isSet(col)) continue;"},{"Add":""},{"Add":" for (data.tickets) |ticket| {"},{"Add":" if (!( // first range"},{"Add":" (ticket[col] >= data.ranges[2 * idx][0] and"},{"Add":" ticket[col] <= data.ranges[2 * idx][1]) or"},{"Add":" // second range"},{"Add":" (ticket[col] >= data.ranges[2 * idx + 1][0] and"},{"Add":" ticket[col] <= data.ranges[2 * idx + 1][1])))"},{"Add":" {"},{"Add":" // number out of range, go to next column"},{"Add":" continue :cols;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // there was a previous valid match, so this range is not unique"},{"Add":" if (match != 20) continue :ranges;"},{"Add":""},{"Add":" match = col;"},{"Add":" }"},{"Add":""},{"Add":" // only one matching column found"},{"Add":" found_columns.set(match);"},{"Add":" found_ranges |= @as(u20, 1) << @intCast(u5, idx);"},{"Add":""},{"Add":" // some \"departure\""},{"Add":" if (idx < 6) prod *= data.tickets[0][match];"},{"Add":""},{"Add":" // first six range found"},{"Add":" if (found_ranges & 0b111111 == 0b111111) return prod;"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" unreachable;"},{"Add":"}"},{"Add":""},{"Add":"fn parseData(allocator: std.mem.Allocator, input: Str) !Data {"},{"Add":" var lines = std.mem.split(u8, input, \"\\n\");"},{"Add":""},{"Add":" var data: Data = undefined;"},{"Add":" var ranges = std.ArrayList(Range).init(allocator);"},{"Add":""},{"Add":" while (lines.next()) |line| {"},{"Add":" if (line.len == 0) break;"},{"Add":" var name_range = std.mem.tokenize(u8, line, \":\");"},{"Add":" while (name_range.next()) |nr| {"},{"Add":" var rngs = std.mem.tokenize(u8, nr, \" \");"},{"Add":" while (rngs.next()) |rng| {"},{"Add":" if (rng[0] < 48 or rng[0] > 57) continue; // skip non-numbers"},{"Add":" var lo_hi = std.mem.tokenize(u8, rng, \"-\");"},{"Add":" try ranges.append(.{"},{"Add":" try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),"},{"Add":" try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),"},{"Add":" });"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" data.ranges = ranges.toOwnedSlice();"},{"Add":""},{"Add":" var tickets = std.ArrayList(Ticket).init(allocator);"},{"Add":""},{"Add":" lines: while (lines.next()) |line| {"},{"Add":" if (line.len == 0) continue;"},{"Add":" if (line[0] < 48 or line[0] > 57) continue;"},{"Add":""},{"Add":" var ticket: Ticket = undefined;"},{"Add":""},{"Add":" var numbers = std.mem.tokenize(u8, line, \",\");"},{"Add":""},{"Add":" var idx: usize = 0;"},{"Add":" nums: while (numbers.next()) |num_str| : (idx += 1) {"},{"Add":" ticket[idx] = try std.fmt.parseUnsigned(InputType, num_str, 0);"},{"Add":" for (data.ranges) |range| {"},{"Add":" if (ticket[idx] >= range[0] and ticket[idx] <= range[1]) continue :nums;"},{"Add":" }"},{"Add":" continue :lines;"},{"Add":" }"},{"Add":""},{"Add":" try tickets.append(ticket);"},{"Add":" }"},{"Add":""},{"Add":" data.tickets = tickets.toOwnedSlice();"},{"Add":""},{"Add":" return data;"},{"Add":"}"},{"Add":""},{"Add":"fn parseRanges(allocator: std.mem.Allocator, input: Str) ![]Range {"},{"Add":" var lines = std.mem.split(u8, input, \"\\n\");"},{"Add":""},{"Add":" var ranges = std.ArrayList(Range).init(allocator);"},{"Add":""},{"Add":" while (lines.next()) |line| {"},{"Add":" if (line.len == 0) break;"},{"Add":" var name_range = std.mem.tokenize(u8, line, \":\");"},{"Add":" while (name_range.next()) |nr| {"},{"Add":" var rngs = std.mem.tokenize(u8, nr, \" \");"},{"Add":" while (rngs.next()) |rng| {"},{"Add":" if (rng[0] < 48 or rng[0] > 57) continue; // skip non-numbers"},{"Add":" var lo_hi = std.mem.tokenize(u8, rng, \"-\");"},{"Add":" try ranges.append(.{"},{"Add":" try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),"},{"Add":" try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),"},{"Add":" });"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" return ranges.toOwnedSlice();"},{"Add":"}"},{"Add":""},{"Add":"test \"day16a\" {"},{"Add":" try std.testing.expectEqual(@as(usize, 19087), try first(std.testing.allocator));"},{"Add":"}"},{"Add":""},{"Add":"test \"day16b\" {"},{"Add":" try std.testing.expectEqual(@as(usize, 1382443095281), try second(std.testing.allocator));"},{"Add":"}"}]}}],"owner":"voroskoi","repo":"aoc2020-zig","token":"1aFTDUlLIunmAhNcGskAbqLQnMZ+bvb1ZFJ8/CVpDAI=","login":null}

…

Dependencies

Change contents