.....613...................................439............498.........................438......617....343.............942...................
.......*............790...........269..735..*........................../679..............*444.*.........*.......147...*.............441.....
....539......422.......*......662*........*..691..........*124.15..675.................=.......404...872............237......930.....+......
........334.............861.........%....479..........424.......+.@.......402.......314...905................833........*293................
..........#.......................906.................*...............950.....................712...437.........*142.359........551.14......
....509.....=...........890...................&........9................./..847.154..568............@...102................280...*..........
.....*..950.67.............-......161.......530....=...................=............*...../..............@.......................426........
614...............................*.............59.591.....259*.......342...427..........29../.........-....................946.............
.......896........808..............6.............*.............35............./......538.....572....510...677*380...........=...............
.......*.............*534..814................879...............................615/....*............................90.........580...413...
.......810..........................................714.260..498..........386..........877......754........793...943.*............/.....*...
.....................845..#..483........55...643.......*......&.....421..+.....+...527.....938............*.......*...993...............706.
....339*..370..........-.540.@.....337..........*........39........*........404......&.......*...483...308.....567................../.......
..........*......994..............*......855..356.768.....*.....114...@195..................976....-...............496.61...610...369.200...
..........15........*...@890...447.........*.........*.303......................821..251*....................8........*....+................
...962.............260...................@..716....893..............304............*.....537.........805.....#..........................388.
............201*........................281.............471........*...../.....=....959...............%..238....180..641@...................
....278.........132..........65...&.........*920.......*.......831..97..828.....533......#368............../.......*......66-...............
.....*................*......*..627......343..........111.....*.....................................*.100$........693..........780..........
...974........474..537.759.101.......366....................183...............461*178..850.......644.........57.............................
..........67$.@.........................*...879..................54.100..355.................794.............=.....................826.530..
494*549...............670...=194.....173............329=....*14....*........*....811*303....*....891..541........975........................
........................*................403.............591................667............630....*.....$.667*....#...*......819.........19.
572...@.......%.......271..........910.........578.551..........818.534...........................217.........809.....262.....+.............
.....105.......748..............%........637...*...*........515....*...................119............*143..@.....258.......................
.20........115........714....525...491....*..768...647.....*...................433..../............583.......404..#..............268........
.......650..*.....%......%............*.311............275.283.306..=659.....................499........@................652.176............
..100.....#.193.637..........828...806.............725*........*..............................@......418........370.......@........86&..977.
......350................229..$.............................%...724.....#.981*582..$...............................*.38.....38.503......$...
.......#..380...........*.............311........%..........968......647..........33..................634*13......72./...%...*..*...........
............*.203*52.......+........./...........295.....................888..........277...938..662.........3.........619.320...766........
....149...883..............817...........163............959..........8.....*.811%............*......&...354..+.....392......................
....................727........789......*...............@...............739.........537....326.............*......*.......&925.........938..
..383..505.166......-.........*.......565......491........136.....693..........870.%...........#...........654..&..313.................*....
.........=..$..801....962.....787..........181......186.../..........*103........+............826....599.......289.....311.768..........986.
.292.414..........*......*................*..................214.....................439.@130...........+...52........*.....*.....989*......
.........221......149....405...@...........393..........714.....&.......652............*............607....*.........412....682.......982...
.........*......................491.......................*..............-......906..909.......885.....%.747......19........................
......567.........193........1..................925.........78......117.....797*................@............208............................
.............943..*.....571...*.....919.487............/....+.........*.......................................*......433.922.......795......
....66......*....92..........367.......*....883.625.....479....852@.............277.635............860.......940..21....*....995.....&......
.........206............595%...................*............./.......................*......691.......*..........*..........*...............
.....766.............&................=...........*...649-.241...56..@724..713..836.863.......=....676...+..824.506......247..$132..........
.....................278..........917..864.....219...............+............%.*......................973.........................744......
.........912...............%......*................979....-953...................733.............&................................*.........
.........@........$........995....905......552...................391.........40=.......388.......141...................731*640.....511......
123..662...989.672............................*........611......+.....%910.............*....5......................584......................
...*...*../...........................306.....289.*....*.............................673.....*........970..51....@....*...............#.....
...916.23.......14..828........908.................181.227......26....190.....723..*.......877...513...@...*..977......319..867/...997..76..
..........158........=............$..............................%............#...605....................264.......569.....................1
.....453..*............................815.430*........946..840.........................456.........152................23...................
216.....*.389...........930............*.......211.......-...*.....635..472*185.................................@444...*.....783...966......
...*...72.................*..........527...+...............636.......*.............746....575.....5...276.821........568.+......*...-.......
..765...........991........686..142*......588......@...........366....395.............*..*...............................983...266..........
.................+..................383.............330..&......%...............337.853.337........927.@703.&513......................855...
...652................=../..@.............431....48......512...............541....%.................+.............-...835/.......%......*...
.....*..205.....510.92..901.778............*......./............588.........#..........@....................968.603........820...75....844..
...560............/........................597...................&.......#............698..........427........*...../249....................
..............817..........50..........208..................149..........169........................*......835..............522.............
.....-......................*............*.....470......%..*.......151.................731.......395..979.........200.........#.......$.....
..242.........698........763............531.....*....252...533.....*.........64.........*...233.........*............*262.............498...
........994.....*...............620.639......575................934..606.99....*....770.72.#......@.............................-...........
.......*.........658..355.........#...*............*...*597..............*...645......*........292........-..354...@.......409...515........
........453..594.......#..............571..=552.193...8.............820...69.........877....%..........846.....*...525.446....*........*386.
....&...........#..................................................*....-.................652.................500............361....290.....
...833..................652.....410..924*72..........*.../104.....231.223....@...%....775................375................................
.................470...........*..................663.......................179.10....&.........256..770*............243.........354........
...*5.............*............962......-....................../.....529...................../.....*.........39.255./.......73......&.......
...............253..766....$.............659........$497..241.656....&....630................262.212...154.......*............*.............
...................*....755...................375...........*................@...........................*.....936...159.......786...981....
...................78....................426.....*39....885..835....432..............439.................335............@...................
.......*574.785............................................*................736......*.....860....395...........381...........@..114...825..
....557........@.............187.....640......514.36*.....834.........630...@....*..194......#....-......*......*....164....440.%.....*.....
...................744.908....*........*......*......185......................165........635..........464.354..104.................996......
.........................*.805..604..375...326........................*.................../....970.....................*....................
....751.....776.......661.......*.................777*........434..952.662....2......................$.923...........99.463.........&.514...
....*........*.....55..........414..............................*..............$......&522........378............+............*....89..*....
.331.......403..94..................547.551..............300...600........=......452.......976.+...............213.........815.757..........
.....209-......*...760...............@...*.............................963........+..........*.906.......785...........................+....
958...........319....@.....+.334..........640.................................798.........611......678.....*..630.......389............426..
.........../............961..*..................608..472...........45...........*...................*....390.............*..................
.....597..191......&861.......279.689.............=....*.972*..........560......900.............548..97.......240...51....2....411.......233
......*.......379.................*......+...........770.....989...955...&.214#.........*588.......*.............%..$.......................
....982.&.......................82....850...450......................*...............755.....799....539.....298.........993........788......
.........901....382.......569...............&........428............281.....=599.........98.../....................789.@......956.=....450..
.................*..497/..*...664....*...............%.........610................/944.....*....778......713*375.....*.................*....
.......@......637........443.../...905............................*883.......389...........563......................388...$.....*559....386.
........241.......*597.........................876..............$........731*.....192.483..............#958...%..*......828..100............
...89&.........994.........*228...............#...........18...413..............1....*...........*..........157...453.......................
..........573...........198............447........488.672../.#......&383.........%.....589........511..................46...................
.....*449......$...228*................+.............*........662.........%.............*....321........34%....838&...*.....................
..592.......659...............=...........................................188..248....836......*....................141..%......344.........
............................564....481..............-..........................................861............%...........93.....$...$.936..
..........618.287......490$.......-............*..304.........662.........@....196...@...72*.........918.339.999.-.................28.......
.............*..............................556.......812.272.....235@.510...#.....51.......804...........#.......209......323=.............
.../471..474.................446.......*........855....*....#..............265..................588.24.......522............................
............*........86..755..+........664........*.....311........793.361.....685.......859..../...@..158......=...667#...........871......
...........529.........&.*.........................624........578....*...................*..................334..........843................
....32#........12..818...406......888.........555........678...*...................@....796.%........159.......-.......$.......@142..289....
..........797..@...*..........246....*..........*.............473............485..683.......526.......*................987...........*......
...272....-.......763...........*...............546....203......................%..................560.....294........................921...
......+...............439...144..909....221...............*245.............847....971..........812............*.............................
...........66....+.........*.........20......337.....591.......*.226.&.....*.......-..+113........./........321..756...518....*.............
......325......166..........848................*.267*........857..*..34.....471.............579+.851...322........#...*........125..........
.........*..........157......................77..................567....646...........................*......783....634.5....@..............
.598.497.275.......&......908=............................................$.......172*324...$263.....207......&.........@...340...160....80.
....*..................#........484..833.998....*.....#.......945.135.......108..................104........................................
..............908....645..264*..........*....581.332...519.......*.........*...........811..................214&..$............57...........
....%543.......@..............807..768.......................23............578.........&.....545...................988........*.........#...
...........547..........&.818........*................669....*........395.........88........*.....964*.....................230..105....471..
......................231.&.........645....*982..398...@.....442..........................311.........466....168..788..474......-...........
..233......638.254......................824..........%...........676.....413......818.............................*.......*.................
..............*.........672.137..............866...862...376........*.........933*............455.................158....682..180*333.......
........454$...........*.......................*........#.............................../18.....*.....677...664.........................%867
..............318....107...........*793.....361...............................*................372.......*.....*509......765.203....737.....
.................%........*.216.831....................509.....392............508...........&...........780.........219.....*......&....*635
334............&........862................945.....162*.........*.......529.......164.......627.381*........591........*83...........155....
.......278...476....363....../.........785.%................431...........*..........*529...........194......*..............982*91..........
.......*..................994..480.....*......*.......236...*........825.450......&.......&..797*.......634.249.......................626...
408.699........*527............*....900....145.880...*......833......*...........456....914......432...*...............391..537........*....
.........................836..955.....................126............557.............................870...38..........*.....*.......388....
.................+275.......*..................=................/............526..................................-....66....587............
..........................400....&............933.......*.....535........455*.....&...209.699........90....*10..207...............*.67......
..............757................719.-............*..-...38.....................22.....*..+...254.....$.736..................201.80.+.......
.....86.584............+..*..........531........335.949.......500...........544.....22.11....*......%.........774*434...337...........331...
.183...*............553....691..131..........................*.................*..............186..591..=171............................*...
...*..........645........*.........*.......365............654......*........843..649.............................673.....867........#.218...
....533..206..*...528=...618........891.41*......................988.596........$......%......391..506..672...../...........*103..926.......
............$.49..............*.....................445................@..../......&..678...................61..............................
..63.............998.......927...295..600....303..........352..............358...464......234.......-.......*....517.......-778....32..641..
....*693............*..............*...*...+.../..70......@...417......*.......$.........*..........417...940.....@....................*....
.................529...561.......706...894.740.......117=....+.......251....642...&763..183..................................$..............
544.651.......+........*....951..................438............505..................................309......800..........534..............
...*...........864.....930....*...36*.......418....*...............*................703...............*.........%..431................=.....
...........463................73.....476............942...55.....127..........................560..959................*.............255.....
......%...*.......176..969#...............@35...............*........-.........242...............=.........147.......914....191.............
....71....686................*.................260.........62.423...823..............-.....................*...................=.186........
.................521..447....940...123........*.................+..........62....855..452...............455.......264....9..........*165....
.......$608..675*.....*.../.......*............72......../...........*484....*....=................................*......*.....%...........
...................302..476.......64.....................159......815......445..........965........................558...824....281......98.

const std = @import("std");
const PATH = "input/day03.txt";
const directions = [_][2]i2{
    .{ -1, -1 },
    .{ -1, 0 },
    .{ -1, 1 },
    .{ 0, -1 },
    .{ 0, 1 },
    .{ 1, -1 },
    .{ 1, 0 },
    .{ 1, 1 },
};
pub fn first(allocator: std.mem.Allocator) !usize {
    _ = allocator;
    const input = @embedFile(PATH);
    const size = getSize(input);
    var sum: usize = 0;
    var row: usize = 0;
    var lines = std.mem.split(u8, input, "\n");
    while (lines.next()) |line| : (row += 1) {
        var frst: ?usize = null;
        var serial: bool = false;
        for (line, 0..) |ch, col| {
            switch (ch) {
                '0'...'9' => {
                    if (serial) continue; // if already serial go for the first dot
                    if (frst == null) frst = @intCast(col);
                    for (directions) |d| {
                        const diffcol = @as(isize, @bitCast(col)) + d[0];
                        if (diffcol < 0 or diffcol >= size[0]) continue;
                        const diffrow = @as(isize, @bitCast(row)) + d[1];
                        if (diffrow < 0 or diffrow >= size[1]) continue;
                        const n = input[@as(usize, @intCast(diffcol)) + @as(usize, @intCast(diffrow)) * (size[0] + 1)];
                        switch (n) {
                            '0'...'9', '.' => {},
                            else => {
                                serial = true;
                                break;
                            },
                        }
                    }
                },
                else => {
                    if (serial) {
                        sum += try std.fmt.parseUnsigned(usize, line[frst.?..@as(usize, @intCast(col))], 10);
                        serial = false;
                    }
                    frst = null;
                },
            }
        }
        // collect serials from the end of the line
        if (serial) {
            sum += try std.fmt.parseUnsigned(usize, line[frst.?..], 10);
        }
    }
    return sum;
}
pub fn second(allocator: std.mem.Allocator) !usize {
    const input = @embedFile(PATH);
    const GearList = std.ArrayList(usize);
    var gears = std.AutoHashMap(usize, GearList).init(allocator);
    defer {
        var it = gears.valueIterator();
        while (it.next()) |item| {
            item.deinit();
        }
        gears.deinit();
    }
    const size = getSize(input);
    var row: usize = 0;
    var lines = std.mem.split(u8, input, "\n");
    while (lines.next()) |line| : (row += 1) {
        var frst: ?usize = null;
        var gear: ?usize = null;
        for (line, 0..) |ch, col| {
            switch (ch) {
                '0'...'9' => {
                    if (gear != null) continue; // if already a gear go for the first dot
                    if (frst == null) frst = @intCast(col);
                    for (directions) |d| {
                        const diffcol = @as(isize, @bitCast(col)) + d[0];
                        if (diffcol < 0 or diffcol >= size[0]) continue;
                        const diffrow = @as(isize, @bitCast(row)) + d[1];
                        if (diffrow < 0 or diffrow >= size[1]) continue;
                        const place = @as(usize, @intCast(diffcol)) +
                            @as(usize, @intCast(diffrow)) * (size[0] + 1);
                        switch (input[place]) {
                            '*' => {
                                gear = place;
                                break;
                            },
                            else => {},
                        }
                    }
                },
                else => {
                    if (gear != null) {
                        const g = try std.fmt.parseUnsigned(usize, line[frst.?..@as(usize, @intCast(col))], 10);
                        const result = try gears.getOrPut(gear.?);
                        if (result.found_existing) {
                            try result.value_ptr.*.append(g);
                        } else {
                            var new_list = std.ArrayList(usize).init(allocator);
                            try new_list.append(g);
                            result.value_ptr.* = new_list;
                        }
                        gear = null;
                    }
                    frst = null;
                },
            }
        }
        // collect gears from the end of the line
        if (gear != null) {
            const g = try std.fmt.parseUnsigned(usize, line[frst.?..], 10);
            const result = try gears.getOrPut(gear.?);
            if (result.found_existing) {
                try result.value_ptr.*.append(g);
            } else {
                var new_list = std.ArrayList(usize).init(allocator);
                try new_list.append(g);
                result.value_ptr.* = new_list;
            }
        }
    }
    var sum: usize = 0;
    var it = gears.valueIterator();
    while (it.next()) |item| {
        if (item.items.len == 2) {
            const ratio = item.items[0] * item.items[1];
            sum += ratio;
        }
    }
    return sum;
}
fn getSize(input: []const u8) [2]usize {
    var lines = std.mem.split(u8, input, "\n");
    var ret: [2]usize = undefined;
    ret[0] = lines.next().?.len;
    ret[1] = 1;
    while (lines.next()) |line| {
        if (line.len == 0) continue;
        ret[1] += 1;
    }
    return ret;
}
test "day03a" {
    try std.testing.expectEqual(@as(usize, 527144), try first(std.testing.allocator));
}
test "day03b" {
    try std.testing.expectEqual(@as(usize, 81463996), try second(std.testing.allocator));
}
const test_input =
    \\467..114..
    \\...*......
    \\..35..633.
    \\......#...
    \\617*......
    \\.....+.58.
    \\..592.....
    \\......755.
    \\...$.*....
    \\.664.598..
;