const std = @import("std");

const PATH = "input/day16.txt";

const Str = []const u8;

const InputType = u10;
const Range = [2]InputType;
const ticket_lenght = 20;
const Ticket = [ticket_lenght]InputType;

const Data = struct {
    ranges: []Range,
    tickets: []Ticket,
};

pub fn first(allocator: ?std.mem.Allocator) anyerror!usize {
    const file = @embedFile(PATH);

    const ranges = try parseRanges(allocator.?, file);
    defer allocator.?.free(ranges);

    var sum: usize = 0;
    var empty_lines: u2 = 0;
    var lines = std.mem.split(u8, file, "\n");
    while (lines.next()) |line| {
        if (line.len == 0) {
            empty_lines += 1;
            continue;
        }
        if (empty_lines < 2) continue;
        if (line[0] < 48 or line[0] > 57) continue;
        var numbers = std.mem.tokenize(u8, line, ",");

        nums: while (numbers.next()) |num_str| {
            const num = try std.fmt.parseUnsigned(InputType, num_str, 0);
            for (ranges) |range| {
                if (num >= range[0] and num <= range[1]) continue :nums;
            }
            sum += num;
        }
    }

    return sum;
}

pub fn second(allocator: ?std.mem.Allocator) anyerror!usize {
    const data = try parseData(allocator.?, @embedFile(PATH));
    defer {
        allocator.?.free(data.ranges);
        allocator.?.free(data.tickets);
    }

    var prod: usize = 1;

    var found_columns = std.StaticBitSet(ticket_lenght).initEmpty();
    var found_ranges: u20 = 0;

    while (true) {
        var idx: usize = 0;
        ranges: while (idx < data.ranges.len / 2) : (idx += 1) {
            std.debug.assert(idx < data.ranges.len / 2);

            if (found_ranges & @as(u20, 1) << @intCast(u5, idx) != 0) continue;

            // starting value is out of range, guaranteen uniqueness
            var match: usize = ticket_lenght;

            var col: usize = 0;
            cols: while (col < ticket_lenght) : (col += 1) {
                std.debug.assert(col < ticket_lenght);

                // skip already found columns
                if (found_columns.isSet(col)) continue;

                for (data.tickets) |ticket| {
                    if (!( // first range
                        (ticket[col] >= data.ranges[2 * idx][0] and
                        ticket[col] <= data.ranges[2 * idx][1]) or
                        // second range
                        (ticket[col] >= data.ranges[2 * idx + 1][0] and
                        ticket[col] <= data.ranges[2 * idx + 1][1])))
                    {
                        // number out of range, go to next column
                        continue :cols;
                    }
                }

                // there was a previous valid match, so this range is not unique
                if (match != 20) continue :ranges;

                match = col;
            }

            // only one matching column found
            found_columns.set(match);
            found_ranges |= @as(u20, 1) << @intCast(u5, idx);

            // some "departure"
            if (idx < 6) prod *= data.tickets[0][match];

            // first six range found
            if (found_ranges & 0b111111 == 0b111111) return prod;
        }
    }

    unreachable;
}

fn parseData(allocator: std.mem.Allocator, input: Str) !Data {
    var lines = std.mem.split(u8, input, "\n");

    var data: Data = undefined;
    var ranges = std.ArrayList(Range).init(allocator);

    while (lines.next()) |line| {
        if (line.len == 0) break;
        var name_range = std.mem.tokenize(u8, line, ":");
        while (name_range.next()) |nr| {
            var rngs = std.mem.tokenize(u8, nr, " ");
            while (rngs.next()) |rng| {
                if (rng[0] < 48 or rng[0] > 57) continue; // skip non-numbers
                var lo_hi = std.mem.tokenize(u8, rng, "-");
                try ranges.append(.{
                    try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),
                    try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),
                });
            }
        }
    }

    data.ranges = try ranges.toOwnedSlice();

    var tickets = std.ArrayList(Ticket).init(allocator);

    lines: while (lines.next()) |line| {
        if (line.len == 0) continue;
        if (line[0] < 48 or line[0] > 57) continue;

        var ticket: Ticket = undefined;

        var numbers = std.mem.tokenize(u8, line, ",");

        var idx: usize = 0;
        nums: while (numbers.next()) |num_str| : (idx += 1) {
            ticket[idx] = try std.fmt.parseUnsigned(InputType, num_str, 0);
            for (data.ranges) |range| {
                if (ticket[idx] >= range[0] and ticket[idx] <= range[1]) continue :nums;
            }
            continue :lines;
        }

        try tickets.append(ticket);
    }

    data.tickets = try tickets.toOwnedSlice();

    return data;
}

fn parseRanges(allocator: std.mem.Allocator, input: Str) ![]Range {
    var lines = std.mem.split(u8, input, "\n");

    var ranges = std.ArrayList(Range).init(allocator);

    while (lines.next()) |line| {
        if (line.len == 0) break;
        var name_range = std.mem.tokenize(u8, line, ":");
        while (name_range.next()) |nr| {
            var rngs = std.mem.tokenize(u8, nr, " ");
            while (rngs.next()) |rng| {
                if (rng[0] < 48 or rng[0] > 57) continue; // skip non-numbers
                var lo_hi = std.mem.tokenize(u8, rng, "-");
                try ranges.append(.{
                    try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),
                    try std.fmt.parseUnsigned(InputType, lo_hi.next().?, 0),
                });
            }
        }
    }

    return ranges.toOwnedSlice();
}

test "day16a" {
    try std.testing.expectEqual(@as(usize, 19087), try first(std.testing.allocator));
}

test "day16b" {
    try std.testing.expectEqual(@as(usize, 1382443095281), try second(std.testing.allocator));
}