path: root/day3.zig

const std = @import("std");
const Setup = @import("common.zig").Setup;

pub fn main() !void {
    // var setup = try Setup.get();
    // defer setup.deinit();
    try std.fmt.format(std.io.getStdOut().writer(), "day 3 pt1: {}\n", .{try solve(std.heap.page_allocator, puzzle_input)});
    try std.fmt.format(std.io.getStdOut().writer(), "day 3 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)});
}

const Grid = struct {
    buf: []const u8,
    width: usize,
    height: usize,

    spans: std.ArrayList(u32), // numbers we read from the grid
    span_ix: []usize, // grid mapping of index into spans list

    fn init(a: std.mem.Allocator, input: []const u8) !Grid {
        var spix = try a.alloc(usize, input.len);
        @memset(spix, std.math.maxInt(usize));

        errdefer a.free(spix);
        const height = std.mem.count(u8, input, "\n")+1;
        const width = std.mem.indexOfScalar(u8, input, '\n') orelse return error.NoNewlines;
        return .{
            .buf = input,
            .width = width,
            .height = height,
            .spans = std.ArrayList(u32).init(a),
            .span_ix = spix,
        };
    }
    fn get(self: Grid, x: usize, y: usize) ?u8 {
        if (x >= self.width) return null;
        if (y >= self.height) return null;
        // width +1 becuase the buffer still has newlines in it
        return self.buf[((self.width+1) * y) + x];
    }

    fn get_span_ix(self: Grid, x: usize, y: usize) ?usize {
        if (x >= self.width) return null;
        if (y >= self.height) return null;
        const res = self.span_ix[((self.width+1) * y) + x];
        if (res == std.math.maxInt(usize)) return null;
        return res;
    }

    fn set_span_ix(self: *Grid, x: usize, y: usize, span_ix: usize) void {
        self.span_ix[((self.width+1) * y) + x] = span_ix;
    }

    fn deinit(self: *Grid, a: std.mem.Allocator) void {
        a.free(self.span_ix);
    }
};

// iterate over the map
// tracking if we're in a 'span' of digits
// at the end of the 'span', parse the number and check all the surrounding
// cells. If any are symbols other than . or a digit, then this span is a 
// part number and add it to the sum.
fn solve(a: std.mem.Allocator, input: []const u8) !u32 {
    var spanBuf = std.ArrayList(u8).init(a);
    var spanStart: usize = 0; // easier than backtracking
    defer spanBuf.deinit();
    var grid = try Grid.init(a, input);
    defer grid.deinit(a);
    var sum: u32 = 0;
    for (0..grid.height) |y| {
        spanBuf.clearRetainingCapacity();
        for (0..grid.width) |x| {
            const ch = grid.get(x, y) orelse return error.IndexError;
            if (std.ascii.isDigit(ch)) {
                if (spanBuf.items.len == 0) {
                    spanStart = x;
                }
                try spanBuf.append(ch);
            } 
            // end-of-span, either hit a non-digit or end of line
            if ((!std.ascii.isDigit(ch) or (x==grid.width-1)) and spanBuf.items.len > 0) {
                const num = try std.fmt.parseInt(u32, spanBuf.items, 10);
                spanBuf.clearRetainingCapacity();
                // now check all the surrounding positions including diagonals, for non-digits and points
                const search_x_end = x;
                const search_x_start = std.math.sub(usize, spanStart, 1) catch spanStart;
                const is_part: bool = br: for (search_x_start..(search_x_end)+1) |x_p| {
                    const search_y_start = std.math.sub(usize, y, 1) catch y;
                    const search_y_end = y+1;
                    for (search_y_start..(search_y_end+1)) |y_p| {
                        if (grid.get(x_p, y_p)) |adj| {
                            if (!std.ascii.isDigit(adj) and adj != '.') {
                                //std.log.info("found symbol {c} next to num {}", .{adj, num});
                                break :br true;
                            }
                        }
                    }
                } else {
                    //std.log.info("no symbol next to num {}", .{num});
                    break :br false;
                };
                if (is_part) {
                    sum += num;
                }
            }
        }
    }
    return sum;
}

// iterate over the map, finding 'spans' like before. 
// Except this time, store the span's number in a arraylist
// and record the number's index in the cells (in a 'shadow' grid) 
// where the span covered the cell
// Then make a second pass to find gears, and check the 'shadow' grid 
// for adjescent spans. If there are exactly 2 adjescent spans, 
// lookup their values from the arraylist and multiple them together!
fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u32 {
    var spanBuf = std.ArrayList(u8).init(a);
    var spanStart: usize = 0; // easier than backtracking
    defer spanBuf.deinit();
    var grid = try Grid.init(a, input);
    defer grid.deinit(a);
    var allSpans = std.ArrayList(u32).init(a);
    defer allSpans.deinit();
    
    for (0..grid.height) |y| {
        spanBuf.clearRetainingCapacity();
        for (0..grid.width) |x| {
            const ch = grid.get(x, y) orelse return error.IndexError;
            if (std.ascii.isDigit(ch)) {
                if (spanBuf.items.len == 0) {
                    spanStart = x;
                }
                try spanBuf.append(ch);
            } 
            // end-of-span, either hit a non-digit or end of line
            if ((!std.ascii.isDigit(ch) or (x==grid.width-1)) and spanBuf.items.len > 0) {
                const num = try std.fmt.parseInt(u32, spanBuf.items, 10);
                spanBuf.clearRetainingCapacity();
                const spanIx = allSpans.items.len;
                try allSpans.append(num);
                const mark_x_start = spanStart;
                const mark_x_end = if (std.ascii.isDigit(ch)) x else x-1;
                for (mark_x_start..(mark_x_end+1)) |mark_x| {
                    grid.set_span_ix(mark_x, y, spanIx);
                }
            }
        }
    }

    // Second pass, find the gears
    var sum: u32 = 0;
    var spixes = std.AutoHashMap(usize, bool).init(a);
    defer spixes.deinit();
    // find gears
    for (0..grid.height) |y| {
        for (0..grid.width) |x| {
            const ch = grid.get(x, y) orelse @panic("borken");
            if (ch == '*') {
                std.log.warn("gear at x{}y{}", .{x, y});
                const mx = std.math.sub(usize, x, 1) catch x;
                const my = std.math.sub(usize, y, 1) catch y;

                // Find adjescent spans
                spixes.clearRetainingCapacity();
                for (mx..(x+2)) |x_p| {
                    for (my..(y+2)) |y_p| {
                        if (grid.get_span_ix(x_p, y_p)) |spix| {
                            try spixes.put(spix, true);
                        }
                    }
                }
                var ki = spixes.keyIterator();
                if (ki.next()) |first| {
                    var m = allSpans.items[first.*];
                    //std.log.warn("span val m{}", .{m});
                    if (ki.next()) |second| {
                        var m2 = allSpans.items[second.*];
                        //std.log.warn("span val m2{}", .{m2});
                        // _EXACTLY_ two gears!
                        if (ki.next() == null) {
                            sum += (m*m2);
                        }
                    }
                }
            }
        }
    }
    return sum;
}



test "pt1" {
    try std.testing.expectEqual(@as(u32, 4361), try solve(std.testing.allocator, test_input));
}

test "pt2" {
    try std.testing.expectEqual(@as(u32, 467835), try solve_pt2(std.testing.allocator, test_input));
}

const test_input = 
    \\467..114..
    \\...*......
    \\..35..633.
    \\......#...
    \\617*......
    \\.....+.58.
    \\..592.....
    \\......755.
    \\...$.*....
    \\.664.598..
    ;

const puzzle_input = 
\\.......497...........................858...923...128..................227..801........487.....664...........................................
\\436........765..............140.......+....................859.............*.........+.................960........668.......................
\\...*982...........=..........=....203......266.263...375*....=...402....691..-....................*..........575....................13......
\\.............114...588...............*............*......631........*.......952...463..14.......661..........=...706......*333.........595..
\\...194.........*..............743...917.&......375.....................................*...............544*.......*....664..................
\\...*.....807..452....81..........*......969..#......309*................/....873....941...828.197..........427.728...............566...13...
\\.243........*.....80.......329....470.......145.475.....111........*659..259....+........*....%........569..............%.....*....*....*...
\\.........130......*....385*............123......................199.......................640.....463..%.........978....920...266..380.83...
\\.....323........870.........+...........$.........466......453........................297...........*............*..........................
\\........*.=..............588.....*786......$.........*........*.......390*.....886...*....227...728..852.......606....*863.......916..396...
\\.....538...287................301........133.....539..........33.537......466..$...793..+..........*...............218.....721........*.....
\\...............986.........=.......................................*...%...............222..-.......701.271...............#.........437.....
\\......*3.........*.626.68...419...740...........................806...976.......875.........174..............735.............=488...........
\\...790.........487....*................./532..13............................*....-.....503..........*11..734..........978.19......622.......
\\...................&....712.68=.619+.........*.......................863...596.....2.....*.......160.....+...&659........*.........-....-757
\\437*.......#........520...*..........304....568.974.255.318.183.........*.......&.....675......................................849..........
\\....161.....687.710.....854.............*.......*......*....&...441......891.....476..........616.......$........235..434.880...*..673+.....
\\..................*...............683.....800.120..............*....807..................................707.....*....-....*...74........562
\\....@...#988...487..#685..........-......*..............251.146.............................142@....74...........398....769..........238*...
\\....848....../................-.$.....662.........773..*...........895.......591...........................233..............................
\\797.........611..........@.186...429..........304*....468.....554....*..........*...960......82.......*810...+.534..660....645...313./......
\\......239..............509...............720*......................844..939=..508......*...........401............*.......*.......*...649...
\\........=........158.......$.....=...........200......409....982.....................46................126.....517....303.647.660...........
\\...530....=......*..........704.69...................*.......*..................@879........589..131.................*........*.............
\\......*..871...672....................611*........415.......283.569.21....842/........-109.&.......*.......157$...719.......679.$...........
\\....664..............664......668.........203....................&...%............................14..................427.......833..484....
\\....................*........*.......434.......796...........65............................................-479.126..*..............+.......
\\.....382..........121.....836.........*........@...............*789.......624........350&..........*544............$.6.........882....513...
\\....%.....406.........................848........625...%...88.........382..+..971.................5......*622...........914....*....%.......
\\..............627....816........641..............*.....373./.............*..../...912..651.162........557........901...&.....503.337....59..
\\...357...........*.........552...*..816..........240......................636.....*...*.....*.............@..993....*.......................
\\......*934....961...=..43..*...324.....@...............726.888....370...........170.805...517........639.389....*..929.................953..
\\.16...............408.*...94..................................*......&..............................*......../...9........605...............
\\.......571....13......512........591+.......976.......895....489...........751.......474.760.........240.....931............*...............
\\...464../..................608..............*........*................$.94*........................................486.......172............
\\...*......121........=.....*.......$......909.......583............128........929...................765.............*............+....24....
\\.............*.......762....230..422..285.....434......................390.....=.....921.................261....#...949.....382...903.*.....
\\............595........................*.......*...................833*..............%.......973..$....@...*.268........506*..........251...
\\967...................................25....234...........................306....281..........=..36..918.432....../406........344...$.......
\\.....700*610.......=...839......917......33......610@................537....=....@............................%........20.402.@.....926.....
\\..............%.768...*....................*...@............93..161.%...............74$......%.........96..298..........%..+............+519
\\...........925.......586...................264..85...721....*...*.............................371.................822.=.....................
\\...............540...........-....447....................987.....305.............379@.707..............670...397...*..842....552.464........
\\.....666......*....844....515.......*..............+114..............977...............&...393........*.........$.800...........*...........
\\.....*...647...696..*..............203....................418.....19............522........*.......462................57...786..........561.
\\....691.....$.......756...165.....................596.32...%........#..280.259$..........398..............425.............*....719..796.....
\\.............../.........=........1/..305............*.........451......&..........332.......706............&.......327.841...........*.....
\\.74..........791.............=........+.....................+...-..................+..........*.....................*...............419..371
\\...*927..........352.......148..........401....459...+....998......$783........@............444..$.......959..106.366.......................
\\............190..........*......385.............*....846......................907.826..585.......447.441..*..*............7......871........
\\.................142....944....$.................634.............587..@..930..........*......935.....*...819.29.....3......*35..............
\\......967....415*......................=980.....................%....58.-......317..74......../.....922..............-.207........../.......
\\.........................................................................................................175....................369.233.....
\\.........................+....645.$........%.....620.+429....951......616.................................*............524$.................
\\....799...551*602........920..+....503..654....-...*............*....=......395.........451....263.......897..................370...........
\\......-.......................................409......970....661.............*............+...*....48...................475..$........839..
\\..97...................../.....@497....%..........446$...*...............533..794.....432-.....167...*.....722...486........*...500...*.....
\\..............459......540.............110................569............&..................#.....................#........785.*.......455..
\\........815....*...........................*452......./......................365.........929....*978.=................709........+..84......
\\....427*......466.............608*796..............680......................*......&.........142.....603.................#......621..*......
\\.........635............@....................302..................296-.....679...801..290..................464..............980......627....
\\....../.../........%...850.......*108....513*........656...*739........715...............@.......713.......*...................*............
\\354+..245.......629...........995.....................$..41.....=.....@.....................45..........840......506+...$.....148...........
\\..........995.................................&541............914.510.....950...../...........*53..28...................275........138......
\\.............*812..665...../.........................101.308..............*......691.482.............*........902.585.......@.......*.......
\\.........../........./...292...............#..........-....*....@307......661..........*.210......135....932%...........992..54..191..931...
\\...400..649...............................504.196.........88........................581.............................743*.............&......
\\...*.........140..............642....891.............309...............................................695......361..............603........
\\....170.643#..*.................*....*.......*24.....*....................932.291.....538....461.........*........*..275............&.......
\\.............725......494......23...279...713..../....449............*........*...../...=......*..........434..............785..............
\\.....991..........946.............................830.........136.439.24...519......289.......408...579........708.650*......*.370.13....410
\\......*..887........#..688.673.........218......................-...............941....................$.......%.......927.722....*.........
\\....124....*...........*..../....427....*.............312................................................922...........................307..
\\...........706...16..934..*.......*......608....459..&..........761.....................647..641...........*.............242............*...
\\..5*715..-........+........122.....262........./...........928....%............728..610*......*..502.....222..40.....923..+...........540...
\\.........701.............=..............291...............*.........351.........*............141.%............*.../.....*....725............
\\..............314.......878....%.......*......=..820*.....988..204.....-.....889......119............797...........395....+.............287.
\\..................671........322....101......257.....733........@.....................=.............*..........544......600.......862.......
\\..421.......582...%..............................484...............565.....+...831...........695...384.#...592.=............240....../.904..
\\....*..........*........570...........&....=........*629......717&.*.......93......726../961....*......535..*........767../......715....*...
\\....439.....630............../..%...615...912......................777............*..............602.........567..3........107....$..77.....
\\....................914.....3...2.=.............763...&885......................185....182.......................*......-......+............
\\...372...383........*..............60.............*............&..38.681...............*.....459....../........117...504......358..480-.....
\\............+.990..33...........................834.......@..33......................494....*........181.66+................................
\\...............*......*...492..............176..........857...........376.315................954.....................*982.......763.........
\\329=..........179....245...*...61...........*...*................%......+....*.....352*509.........952#..69..620..423.............*.........
\\.........................131.....*17......191.33.306...../.....144..503......491.............................................298...415......
\\...................$...................................426.........*...............526.669.....&498..698...$............447.....+...........
\\.............575...142.617......890..............%...............212..730.519.971..&......*384.........@....18.219.........*................
\\.......*537..*.........*........*.........677...587..407...120*........./....*...................................+......334..........700....
\\....944......636..848........743.....388..*....................109..........................................................540.40..*.......
\\.................*....596............*....155..324...820.520.................=...............443...94...........621.276......*..+..910......
\\...............276.....-.........376...........*........*....................739......368....=..............428....*......434..........878..
\\932....28.....................-..=....207......959....................289.........196.*........................*...............-.......=....
\\...*........................172....#.#.....688.........25..944...725...&............*..110.....148...426.483..771../932......800............
\\.947............................457....931*.............-....*...#.......834......721.........*.........*.............................477...
\\.....*491......*.........*114.................191.....$...213........909*...................194............633....%...792..605.633...#......
\\.............108......611.....+719...........*.....696........865...............120................=724...%....950.../......*...../.........
\\...320............*.................260/...121.........338...*........719.180.........516.....*.............................649.............
\\.....#...643.......941......*160......................*......140...94....*...............*..39.789................*......&.........81...597.
\\............*..135.......532.................%90...608............*............+515....743.............+...194.993.669..259..+..............
\\.....%....948.....*............262..695.712....................623.....*...................473........602...*...............83......679.....
\\..259.............447.............%.*...............363.............105...................@........=......+.........................*.......
\\......957....659........299..........................%...599..898.+.................464.......606.237..768..416@....=...............228.....
\\.376..$.........*..........*..2.........@557......./.......*.*.....517..........859*.........*....................855...877.427.........*...
\\.........*468..535......500....$................117......726.381........428...$................@........43....472.......*...*...........476.
\\......517................................951........%............-..249..@.....920...........859........*........*....825.393...15..........
\\...........770.......&16.....278...417......$.....626...-23....954.....#..............................868.......502............*............
\\.....373..*...................%...*.....254................................................246.#530....................982....179....635....
\\......*...538.....................362...-...........162.........................180=........*..................278.......*............+.....
\\....138.......922..............................543................6....12....&.............92...150...............*.......994...............
\\................+.....+................388....*..........................*....788............../..................220.............834.......
\\.....................301.593.597.............500..603......928....966................/.............536.......768.............800............
\\................*64........*.../..&.....924.........*........-...$....................203.............-...+..../...............*..423.&451..
\\.............453....*......638.....314..*...896....459...............96...................186............581................846....*........
\\....&188.........624.400...............268....@...........................664...............*...12.943............#733......................
\\.............................597...765................388......149..468.....+............698......*....143........................426.......
\\.......................878...*.........875..............*..871*.....*..............929....................$.504*..............473.%.........
\\...245..........94.651..*.....915.........*.........40.440........236.................*511.45........994........753..................887....
\\...#..............*.....459............212...18*964.*.........=71..........768..827............./.....*......................567............
\\.....787.2..781*....................................827....................*...*..............437.....813.......317.....102.....*333........
\\..........*.....285............@..-...........304.......821.622.....953...377.997......320....................@./.....%....*..........254...
\\.......877..636.....42......772..419.....189..*................&....*.....................=.17......366*....563......228...153..............
\\...............*.....$................&....*...839......218.........449......................*..409.....69............................652...
\\.....576......255..............593...397............469..%......#.......+568.......374......499....*...........541..477.........%137..*.....
\\.......*............@319.................$.35..........*.....207...............808*.................933.737...........*.502............367..
\\.....807....219../.....................436......226@...266........215...................................*...................................
\\..............*...769.....41*....922............................$..*.......271.........350..........677.346......................662....725.
\\..............175............979.*...#........215..............652..39......$....=61......*..154...................................*........
\\...426..............335*.........487.194.........*42...................790.............+.750.@......&..............253...337....617..717....
\\...+....908.............489.................../............14...278.../....953.......316.......*856.44.50...../.......*................$....
\\.........%..90.................437..........848...........................*......714........708..........*223.588.....884....871.801........
\\494@..........*..33...........*.........779.....424.550....923............779.......*...340........738.......................*....*..131.603
\\.....50..481.........=.....643...........@......%............*.......815......681..263....*........*...5.....256*11.377$....872.903.*.......
\\.....*...............635.......698..........583...148........708........................323.243..201.....................*..........377.132.
\\...502........883............/..*..............$...*....994.........*....479@.................$......804.443..........584...................
\\.............*..............893..581..534........376..+..........174.119.........138............670...*....$.834............4...............
\\.....+....234...904.323..=..............&.894..........439.@838............*.....*........47........555........*............*........932....
\\...594............*...$.654.....+.........*........................84.*....7...231.$102.......286.......*760....817.......719.........*.....
\\..................620............806......866.................559......440...........................310...........................590..547.
;