day3.zig (28032B)
1 const std = @import("std"); 2 const Setup = @import("common.zig").Setup; 3 4 pub fn main() !void { 5 // var setup = try Setup.get(); 6 // defer setup.deinit(); 7 try std.fmt.format(std.io.getStdOut().writer(), "day 3 pt1: {}\n", .{try solve(std.heap.page_allocator, puzzle_input)}); 8 try std.fmt.format(std.io.getStdOut().writer(), "day 3 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)}); 9 } 10 11 const Grid = struct { 12 buf: []const u8, 13 width: usize, 14 height: usize, 15 16 spans: std.ArrayList(u32), // numbers we read from the grid 17 span_ix: []usize, // grid mapping of index into spans list 18 19 fn init(a: std.mem.Allocator, input: []const u8) !Grid { 20 const spix = try a.alloc(usize, input.len); 21 @memset(spix, std.math.maxInt(usize)); 22 23 errdefer a.free(spix); 24 const height = std.mem.count(u8, input, "\n")+1; 25 const width = std.mem.indexOfScalar(u8, input, '\n') orelse return error.NoNewlines; 26 return .{ 27 .buf = input, 28 .width = width, 29 .height = height, 30 .spans = std.ArrayList(u32).init(a), 31 .span_ix = spix, 32 }; 33 } 34 fn get(self: Grid, x: usize, y: usize) ?u8 { 35 if (x >= self.width) return null; 36 if (y >= self.height) return null; 37 // width +1 becuase the buffer still has newlines in it 38 return self.buf[((self.width+1) * y) + x]; 39 } 40 41 fn get_span_ix(self: Grid, x: usize, y: usize) ?usize { 42 if (x >= self.width) return null; 43 if (y >= self.height) return null; 44 const res = self.span_ix[((self.width+1) * y) + x]; 45 if (res == std.math.maxInt(usize)) return null; 46 return res; 47 } 48 49 fn set_span_ix(self: *Grid, x: usize, y: usize, span_ix: usize) void { 50 self.span_ix[((self.width+1) * y) + x] = span_ix; 51 } 52 53 fn deinit(self: *Grid, a: std.mem.Allocator) void { 54 a.free(self.span_ix); 55 } 56 }; 57 58 // iterate over the map 59 // tracking if we're in a 'span' of digits 60 // at the end of the 'span', parse the number and check all the surrounding 61 // cells. If any are symbols other than . or a digit, then this span is a 62 // part number and add it to the sum. 63 fn solve(a: std.mem.Allocator, input: []const u8) !u32 { 64 var spanBuf = std.ArrayList(u8).init(a); 65 var spanStart: usize = 0; // easier than backtracking 66 defer spanBuf.deinit(); 67 var grid = try Grid.init(a, input); 68 defer grid.deinit(a); 69 var sum: u32 = 0; 70 for (0..grid.height) |y| { 71 spanBuf.clearRetainingCapacity(); 72 for (0..grid.width) |x| { 73 const ch = grid.get(x, y) orelse return error.IndexError; 74 if (std.ascii.isDigit(ch)) { 75 if (spanBuf.items.len == 0) { 76 spanStart = x; 77 } 78 try spanBuf.append(ch); 79 } 80 // end-of-span, either hit a non-digit or end of line 81 if ((!std.ascii.isDigit(ch) or (x==grid.width-1)) and spanBuf.items.len > 0) { 82 const num = try std.fmt.parseInt(u32, spanBuf.items, 10); 83 spanBuf.clearRetainingCapacity(); 84 // now check all the surrounding positions including diagonals, for non-digits and points 85 const search_x_end = x; 86 const search_x_start = std.math.sub(usize, spanStart, 1) catch spanStart; 87 const is_part: bool = br: for (search_x_start..(search_x_end)+1) |x_p| { 88 const search_y_start = std.math.sub(usize, y, 1) catch y; 89 const search_y_end = y+1; 90 for (search_y_start..(search_y_end+1)) |y_p| { 91 if (grid.get(x_p, y_p)) |adj| { 92 if (!std.ascii.isDigit(adj) and adj != '.') { 93 //std.log.info("found symbol {c} next to num {}", .{adj, num}); 94 break :br true; 95 } 96 } 97 } 98 } else { 99 //std.log.info("no symbol next to num {}", .{num}); 100 break :br false; 101 }; 102 if (is_part) { 103 sum += num; 104 } 105 } 106 } 107 } 108 return sum; 109 } 110 111 // iterate over the map, finding 'spans' like before. 112 // Except this time, store the span's number in a arraylist 113 // and record the number's index in the cells (in a 'shadow' grid) 114 // where the span covered the cell 115 // Then make a second pass to find gears, and check the 'shadow' grid 116 // for adjescent spans. If there are exactly 2 adjescent spans, 117 // lookup their values from the arraylist and multiple them together! 118 fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u32 { 119 var spanBuf = std.ArrayList(u8).init(a); 120 var spanStart: usize = 0; // easier than backtracking 121 defer spanBuf.deinit(); 122 var grid = try Grid.init(a, input); 123 defer grid.deinit(a); 124 var allSpans = std.ArrayList(u32).init(a); 125 defer allSpans.deinit(); 126 127 for (0..grid.height) |y| { 128 spanBuf.clearRetainingCapacity(); 129 for (0..grid.width) |x| { 130 const ch = grid.get(x, y) orelse return error.IndexError; 131 if (std.ascii.isDigit(ch)) { 132 if (spanBuf.items.len == 0) { 133 spanStart = x; 134 } 135 try spanBuf.append(ch); 136 } 137 // end-of-span, either hit a non-digit or end of line 138 if ((!std.ascii.isDigit(ch) or (x==grid.width-1)) and spanBuf.items.len > 0) { 139 const num = try std.fmt.parseInt(u32, spanBuf.items, 10); 140 spanBuf.clearRetainingCapacity(); 141 const spanIx = allSpans.items.len; 142 try allSpans.append(num); 143 const mark_x_start = spanStart; 144 const mark_x_end = if (std.ascii.isDigit(ch)) x else x-1; 145 for (mark_x_start..(mark_x_end+1)) |mark_x| { 146 grid.set_span_ix(mark_x, y, spanIx); 147 } 148 } 149 } 150 } 151 152 // Second pass, find the gears 153 var sum: u32 = 0; 154 var spixes = std.AutoHashMap(usize, bool).init(a); 155 defer spixes.deinit(); 156 // find gears 157 for (0..grid.height) |y| { 158 for (0..grid.width) |x| { 159 const ch = grid.get(x, y) orelse @panic("borken"); 160 if (ch == '*') { 161 std.log.warn("gear at x{}y{}", .{x, y}); 162 const mx = std.math.sub(usize, x, 1) catch x; 163 const my = std.math.sub(usize, y, 1) catch y; 164 165 // Find adjescent spans 166 spixes.clearRetainingCapacity(); 167 for (mx..(x+2)) |x_p| { 168 for (my..(y+2)) |y_p| { 169 if (grid.get_span_ix(x_p, y_p)) |spix| { 170 try spixes.put(spix, true); 171 } 172 } 173 } 174 var ki = spixes.keyIterator(); 175 if (ki.next()) |first| { 176 const m = allSpans.items[first.*]; 177 //std.log.warn("span val m{}", .{m}); 178 if (ki.next()) |second| { 179 const m2 = allSpans.items[second.*]; 180 //std.log.warn("span val m2{}", .{m2}); 181 // _EXACTLY_ two gears! 182 if (ki.next() == null) { 183 sum += (m*m2); 184 } 185 } 186 } 187 } 188 } 189 } 190 return sum; 191 } 192 193 194 195 test "pt1" { 196 try std.testing.expectEqual(@as(u32, 4361), try solve(std.testing.allocator, test_input)); 197 } 198 199 test "pt2" { 200 try std.testing.expectEqual(@as(u32, 467835), try solve_pt2(std.testing.allocator, test_input)); 201 } 202 203 const test_input = 204 \\467..114.. 205 \\...*...... 206 \\..35..633. 207 \\......#... 208 \\617*...... 209 \\.....+.58. 210 \\..592..... 211 \\......755. 212 \\...$.*.... 213 \\.664.598.. 214 ; 215 216 const puzzle_input = 217 \\.......497...........................858...923...128..................227..801........487.....664........................................... 218 \\436........765..............140.......+....................859.............*.........+.................960........668....................... 219 \\...*982...........=..........=....203......266.263...375*....=...402....691..-....................*..........575....................13...... 220 \\.............114...588...............*............*......631........*.......952...463..14.......661..........=...706......*333.........595.. 221 \\...194.........*..............743...917.&......375.....................................*...............544*.......*....664.................. 222 \\...*.....807..452....81..........*......969..#......309*................/....873....941...828.197..........427.728...............566...13... 223 \\.243........*.....80.......329....470.......145.475.....111........*659..259....+........*....%........569..............%.....*....*....*... 224 \\.........130......*....385*............123......................199.......................640.....463..%.........978....920...266..380.83... 225 \\.....323........870.........+...........$.........466......453........................297...........*............*.......................... 226 \\........*.=..............588.....*786......$.........*........*.......390*.....886...*....227...728..852.......606....*863.......916..396... 227 \\.....538...287................301........133.....539..........33.537......466..$...793..+..........*...............218.....721........*..... 228 \\...............986.........=.......................................*...%...............222..-.......701.271...............#.........437..... 229 \\......*3.........*.626.68...419...740...........................806...976.......875.........174..............735.............=488........... 230 \\...790.........487....*................./532..13............................*....-.....503..........*11..734..........978.19......622....... 231 \\...................&....712.68=.619+.........*.......................863...596.....2.....*.......160.....+...&659........*.........-....-757 232 \\437*.......#........520...*..........304....568.974.255.318.183.........*.......&.....675......................................849.......... 233 \\....161.....687.710.....854.............*.......*......*....&...441......891.....476..........616.......$........235..434.880...*..673+..... 234 \\..................*...............683.....800.120..............*....807..................................707.....*....-....*...74........562 235 \\....@...#988...487..#685..........-......*..............251.146.............................142@....74...........398....769..........238*... 236 \\....848....../................-.$.....662.........773..*...........895.......591...........................233.............................. 237 \\797.........611..........@.186...429..........304*....468.....554....*..........*...960......82.......*810...+.534..660....645...313./...... 238 \\......239..............509...............720*......................844..939=..508......*...........401............*.......*.......*...649... 239 \\........=........158.......$.....=...........200......409....982.....................46................126.....517....303.647.660........... 240 \\...530....=......*..........704.69...................*.......*..................@879........589..131.................*........*............. 241 \\......*..871...672....................611*........415.......283.569.21....842/........-109.&.......*.......157$...719.......679.$........... 242 \\....664..............664......668.........203....................&...%............................14..................427.......833..484.... 243 \\....................*........*.......434.......796...........65............................................-479.126..*..............+....... 244 \\.....382..........121.....836.........*........@...............*789.......624........350&..........*544............$.6.........882....513... 245 \\....%.....406.........................848........625...%...88.........382..+..971.................5......*622...........914....*....%....... 246 \\..............627....816........641..............*.....373./.............*..../...912..651.162........557........901...&.....503.337....59.. 247 \\...357...........*.........552...*..816..........240......................636.....*...*.....*.............@..993....*....................... 248 \\......*934....961...=..43..*...324.....@...............726.888....370...........170.805...517........639.389....*..929.................953.. 249 \\.16...............408.*...94..................................*......&..............................*......../...9........605............... 250 \\.......571....13......512........591+.......976.......895....489...........751.......474.760.........240.....931............*............... 251 \\...464../..................608..............*........*................$.94*........................................486.......172............ 252 \\...*......121........=.....*.......$......909.......583............128........929...................765.............*............+....24.... 253 \\.............*.......762....230..422..285.....434......................390.....=.....921.................261....#...949.....382...903.*..... 254 \\............595........................*.......*...................833*..............%.......973..$....@...*.268........506*..........251... 255 \\967...................................25....234...........................306....281..........=..36..918.432....../406........344...$....... 256 \\.....700*610.......=...839......917......33......610@................537....=....@............................%........20.402.@.....926..... 257 \\..............%.768...*....................*...@............93..161.%...............74$......%.........96..298..........%..+............+519 258 \\...........925.......586...................264..85...721....*...*.............................371.................822.=..................... 259 \\...............540...........-....447....................987.....305.............379@.707..............670...397...*..842....552.464........ 260 \\.....666......*....844....515.......*..............+114..............977...............&...393........*.........$.800...........*........... 261 \\.....*...647...696..*..............203....................418.....19............522........*.......462................57...786..........561. 262 \\....691.....$.......756...165.....................596.32...%........#..280.259$..........398..............425.............*....719..796..... 263 \\.............../.........=........1/..305............*.........451......&..........332.......706............&.......327.841...........*..... 264 \\.74..........791.............=........+.....................+...-..................+..........*.....................*...............419..371 265 \\...*927..........352.......148..........401....459...+....998......$783........@............444..$.......959..106.366....................... 266 \\............190..........*......385.............*....846......................907.826..585.......447.441..*..*............7......871........ 267 \\.................142....944....$.................634.............587..@..930..........*......935.....*...819.29.....3......*35.............. 268 \\......967....415*......................=980.....................%....58.-......317..74......../.....922..............-.207........../....... 269 \\.........................................................................................................175....................369.233..... 270 \\.........................+....645.$........%.....620.+429....951......616.................................*............524$................. 271 \\....799...551*602........920..+....503..654....-...*............*....=......395.........451....263.......897..................370........... 272 \\......-.......................................409......970....661.............*............+...*....48...................475..$........839.. 273 \\..97...................../.....@497....%..........446$...*...............533..794.....432-.....167...*.....722...486........*...500...*..... 274 \\..............459......540.............110................569............&..................#.....................#........785.*.......455.. 275 \\........815....*...........................*452......./......................365.........929....*978.=................709........+..84...... 276 \\....427*......466.............608*796..............680......................*......&.........142.....603.................#......621..*...... 277 \\.........635............@....................302..................296-.....679...801..290..................464..............980......627.... 278 \\....../.../........%...850.......*108....513*........656...*739........715...............@.......713.......*...................*............ 279 \\354+..245.......629...........995.....................$..41.....=.....@.....................45..........840......506+...$.....148........... 280 \\..........995.................................&541............914.510.....950...../...........*53..28...................275........138...... 281 \\.............*812..665...../.........................101.308..............*......691.482.............*........902.585.......@.......*....... 282 \\.........../........./...292...............#..........-....*....@307......661..........*.210......135....932%...........992..54..191..931... 283 \\...400..649...............................504.196.........88........................581.............................743*.............&...... 284 \\...*.........140..............642....891.............309...............................................695......361..............603........ 285 \\....170.643#..*.................*....*.......*24.....*....................932.291.....538....461.........*........*..275............&....... 286 \\.............725......494......23...279...713..../....449............*........*...../...=......*..........434..............785.............. 287 \\.....991..........946.............................830.........136.439.24...519......289.......408...579........708.650*......*.370.13....410 288 \\......*..887........#..688.673.........218......................-...............941....................$.......%.......927.722....*......... 289 \\....124....*...........*..../....427....*.............312................................................922...........................307.. 290 \\...........706...16..934..*.......*......608....459..&..........761.....................647..641...........*.............242............*... 291 \\..5*715..-........+........122.....262........./...........928....%............728..610*......*..502.....222..40.....923..+...........540... 292 \\.........701.............=..............291...............*.........351.........*............141.%............*.../.....*....725............ 293 \\..............314.......878....%.......*......=..820*.....988..204.....-.....889......119............797...........395....+.............287. 294 \\..................671........322....101......257.....733........@.....................=.............*..........544......600.......862....... 295 \\..421.......582...%..............................484...............565.....+...831...........695...384.#...592.=............240....../.904.. 296 \\....*..........*........570...........&....=........*629......717&.*.......93......726../961....*......535..*........767../......715....*... 297 \\....439.....630............../..%...615...912......................777............*..............602.........567..3........107....$..77..... 298 \\....................914.....3...2.=.............763...&885......................185....182.......................*......-......+............ 299 \\...372...383........*..............60.............*............&..38.681...............*.....459....../........117...504......358..480-..... 300 \\............+.990..33...........................834.......@..33......................494....*........181.66+................................ 301 \\...............*......*...492..............176..........857...........376.315................954.....................*982.......763......... 302 \\329=..........179....245...*...61...........*...*................%......+....*.....352*509.........952#..69..620..423.............*......... 303 \\.........................131.....*17......191.33.306...../.....144..503......491.............................................298...415...... 304 \\...................$...................................426.........*...............526.669.....&498..698...$............447.....+........... 305 \\.............575...142.617......890..............%...............212..730.519.971..&......*384.........@....18.219.........*................ 306 \\.......*537..*.........*........*.........677...587..407...120*........./....*...................................+......334..........700.... 307 \\....944......636..848........743.....388..*....................109..........................................................540.40..*....... 308 \\.................*....596............*....155..324...820.520.................=...............443...94...........621.276......*..+..910...... 309 \\...............276.....-.........376...........*........*....................739......368....=..............428....*......434..........878.. 310 \\932....28.....................-..=....207......959....................289.........196.*........................*...............-.......=.... 311 \\...*........................172....#.#.....688.........25..944...725...&............*..110.....148...426.483..771../932......800............ 312 \\.947............................457....931*.............-....*...#.......834......721.........*.........*.............................477... 313 \\.....*491......*.........*114.................191.....$...213........909*...................194............633....%...792..605.633...#...... 314 \\.............108......611.....+719...........*.....696........865...............120................=724...%....950.../......*...../......... 315 \\...320............*.................260/...121.........338...*........719.180.........516.....*.............................649............. 316 \\.....#...643.......941......*160......................*......140...94....*...............*..39.789................*......&.........81...597. 317 \\............*..135.......532.................%90...608............*............+515....743.............+...194.993.669..259..+.............. 318 \\.....%....948.....*............262..695.712....................623.....*...................473........602...*...............83......679..... 319 \\..259.............447.............%.*...............363.............105...................@........=......+.........................*....... 320 \\......957....659........299..........................%...599..898.+.................464.......606.237..768..416@....=...............228..... 321 \\.376..$.........*..........*..2.........@557......./.......*.*.....517..........859*.........*....................855...877.427.........*... 322 \\.........*468..535......500....$................117......726.381........428...$................@........43....472.......*...*...........476. 323 \\......517................................951........%............-..249..@.....920...........859........*........*....825.393...15.......... 324 \\...........770.......&16.....278...417......$.....626...-23....954.....#..............................868.......502............*............ 325 \\.....373..*...................%...*.....254................................................246.#530....................982....179....635.... 326 \\......*...538.....................362...-...........162.........................180=........*..................278.......*............+..... 327 \\....138.......922..............................543................6....12....&.............92...150...............*.......994............... 328 \\................+.....+................388....*..........................*....788............../..................220.............834....... 329 \\.....................301.593.597.............500..603......928....966................/.............536.......768.............800............ 330 \\................*64........*.../..&.....924.........*........-...$....................203.............-...+..../...............*..423.&451.. 331 \\.............453....*......638.....314..*...896....459...............96...................186............581................846....*........ 332 \\....&188.........624.400...............268....@...........................664...............*...12.943............#733...................... 333 \\.............................597...765................388......149..468.....+............698......*....143........................426....... 334 \\.......................878...*.........875..............*..871*.....*..............929....................$.504*..............473.%......... 335 \\...245..........94.651..*.....915.........*.........40.440........236.................*511.45........994........753..................887.... 336 \\...#..............*.....459............212...18*964.*.........=71..........768..827............./.....*......................567............ 337 \\.....787.2..781*....................................827....................*...*..............437.....813.......317.....102.....*333........ 338 \\..........*.....285............@..-...........304.......821.622.....953...377.997......320....................@./.....%....*..........254... 339 \\.......877..636.....42......772..419.....189..*................&....*.....................=.17......366*....563......228...153.............. 340 \\...............*.....$................&....*...839......218.........449......................*..409.....69............................652... 341 \\.....576......255..............593...397............469..%......#.......+568.......374......499....*...........541..477.........%137..*..... 342 \\.......*............@319.................$.35..........*.....207...............808*.................933.737...........*.502............367.. 343 \\.....807....219../.....................436......226@...266........215...................................*................................... 344 \\..............*...769.....41*....922............................$..*.......271.........350..........677.346......................662....725. 345 \\..............175............979.*...#........215..............652..39......$....=61......*..154...................................*........ 346 \\...426..............335*.........487.194.........*42...................790.............+.750.@......&..............253...337....617..717.... 347 \\...+....908.............489.................../............14...278.../....953.......316.......*856.44.50...../.......*................$.... 348 \\.........%..90.................437..........848...........................*......714........708..........*223.588.....884....871.801........ 349 \\494@..........*..33...........*.........779.....424.550....923............779.......*...340........738.......................*....*..131.603 350 \\.....50..481.........=.....643...........@......%............*.......815......681..263....*........*...5.....256*11.377$....872.903.*....... 351 \\.....*...............635.......698..........583...148........708........................323.243..201.....................*..........377.132. 352 \\...502........883............/..*..............$...*....994.........*....479@.................$......804.443..........584................... 353 \\.............*..............893..581..534........376..+..........174.119.........138............670...*....$.834............4............... 354 \\.....+....234...904.323..=..............&.894..........439.@838............*.....*........47........555........*............*........932.... 355 \\...594............*...$.654.....+.........*........................84.*....7...231.$102.......286.......*760....817.......719.........*..... 356 \\..................620............806......866.................559......440...........................310...........................590..547. 357 ;