day5.zig (19161B)
1 const std = @import("std"); 2 3 pub fn main() !void { 4 try std.fmt.format(std.io.getStdOut().writer(), "day5 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)}); 5 try std.fmt.format(std.io.getStdOut().writer(), "day5 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)}); 6 } 7 8 fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 { 9 var puzzle = try Puzzle.parse(a, input); 10 defer puzzle.deinit(a); 11 // and now check the seeds 12 var min: u64 = std.math.maxInt(u64); 13 for (puzzle.seeds.items) |seed| { 14 var location = seed; 15 for (puzzle.maps.items) |map| { 16 location = map.apply(location); 17 } 18 min = @min(min, location); 19 } 20 return min; 21 } 22 23 // Naïvely trying to iterate results in too much calculation, so we have to be a bit smarter 24 // and handle only the ends of contiguous ranges. The Map.applyRange function will take a range 25 // and apply the map, splitting it into sub-ranges if necessary e.g. because a mapping only partially 26 // overlaps a range. 27 fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 { 28 var puzzle = try Puzzle.parse(a, input); 29 defer puzzle.deinit(a); 30 31 // Parse all the ranges of seeds 32 var ranges = std.ArrayList(Range).init(a); 33 defer ranges.deinit(); 34 for (0..(puzzle.seeds.items.len / 2)) |i| { 35 const start = puzzle.seeds.items[2 * i]; 36 const len = puzzle.seeds.items[(2 * i) + 1]; 37 try ranges.append(.{ 38 .start = start, 39 .end = start + len, 40 }); 41 } 42 43 // Go through the maps, map the ranges each time. 44 for (puzzle.maps.items) |map| { 45 const sr = try ranges.toOwnedSlice(); 46 for (sr) |range| { 47 try ranges.appendSlice(try map.applyRange(a, range)); 48 } 49 a.free(sr); 50 } 51 52 // Give me the start of the range with the lowest start 53 const fr = try ranges.toOwnedSlice(); 54 defer a.free(fr); 55 std.mem.sort(Range, fr, {}, Range.cmp); 56 return fr[0].start; 57 } 58 59 const Puzzle = struct { 60 seeds: std.ArrayList(u64), 61 maps: std.ArrayList(Map), 62 63 fn parse(a: std.mem.Allocator, input: []const u8) !Puzzle { 64 var groups = std.mem.split(u8, input, "\n\n"); 65 const seeds_str = groups.first(); 66 var seedToks = std.mem.tokenize(u8, seeds_str, " "); 67 _ = seedToks.next() orelse return error.NoSeeds; // ignore "seeds:" 68 var seeds = std.ArrayList(u64).init(a); 69 errdefer seeds.deinit(); 70 while (seedToks.next()) |seedTok| { 71 try seeds.append(try std.fmt.parseInt(u64, seedTok, 10)); 72 } 73 74 // now parse the maps... 75 var maps = std.ArrayList(Map).init(a); 76 errdefer { 77 for (maps.items) |*map| map.deinit(a); 78 maps.deinit(); 79 } 80 while (groups.next()) |group| { 81 const m = try Map.parse(a, group); 82 try maps.append(m); 83 } 84 return .{ 85 .seeds = seeds, 86 .maps = maps, 87 }; 88 } 89 fn deinit(self: *Puzzle, a: std.mem.Allocator) void { 90 self.seeds.deinit(); 91 for (self.maps.items) |*map| map.deinit(a); 92 self.maps.deinit(); 93 } 94 }; 95 96 const Map = struct { 97 entries: []MapEntry, // sorted by start 98 99 fn parse(a: std.mem.Allocator, input: []const u8) !Map { 100 var entries = std.ArrayList(MapEntry).init(a); 101 defer entries.deinit(); 102 var toks = std.mem.split(u8, input, "\n"); 103 _ = toks.first(); // discard the title. 104 while (toks.next()) |tok| { 105 const me = try MapEntry.parse(tok); 106 try entries.append(me); 107 } 108 const ee = try entries.toOwnedSlice(); 109 std.mem.sort(MapEntry, ee, {}, Map.cmp); 110 return .{ 111 .entries = ee, 112 }; 113 } 114 115 fn cmp(x: void, lhs: MapEntry, rhs: MapEntry) bool { 116 _ = x; 117 return lhs.source_start < rhs.source_start; 118 } 119 120 fn deinit(self: *Map, a: std.mem.Allocator) void { 121 a.free(self.entries); 122 } 123 124 fn apply(self: Map, in: u64) u64 { 125 for (self.entries) |entry| { 126 if (entry.apply(in)) |out| return out; 127 } else { 128 return in; 129 } 130 } 131 132 fn applyRange(self: Map, a: std.mem.Allocator, r: Range) ![]Range { 133 var res = std.ArrayList(Range).init(a); 134 defer res.deinit(); 135 var r2 = r; // mutable range for bits we have left... 136 for (self.entries) |me| { 137 if (me.source_end < r2.start) { 138 // ignore this map entry it's out of bounds 139 } else if (me.source_start >= r2.end) { 140 // ignore this map entry it's out of bounds 141 } else if (me.source_start <= r2.start and me.source_end >= r2.end) { 142 // whole range contained by map entry 143 try res.append(.{ 144 .start = me.apply(r2.start) orelse @panic("boo"), 145 .end = (me.apply(r2.end-1) orelse @panic("bar"))+1, 146 }); 147 const x = try res.toOwnedSlice(); 148 std.mem.sort(Range, x, {}, Range.cmp); 149 return x; 150 } else if (me.source_start < r2.start and me.source_end > r2.start and me.source_end < r2.end) { 151 // overlap start of range 152 try res.append(.{ 153 .start = me.apply(r2.start) orelse @panic("glub"), 154 .end = ( me.apply(me.source_end-1) orelse @panic("plub")) + 1, 155 }); 156 const ne = r2.end; 157 r2 = .{ 158 .start = me.source_end, 159 .end = ne, 160 }; 161 } else if (me.source_start >= r2.start and me.source_end > r2.end) { 162 // overlap end of range 163 try res.append(.{ 164 .start = r2.start, 165 .end = me.source_start, 166 }); 167 try res.append(.{ 168 .start = me.apply(me.source_start) orelse @panic("ploop"), 169 .end = (me.apply(r2.end-1) orelse @panic("gloop")) + 1, 170 }); 171 const x = try res.toOwnedSlice(); 172 std.mem.sort(Range, x, {}, Range.cmp); 173 return x; 174 } else if (me.source_start >= r2.start and me.source_end < r2.end) { 175 // map contained by range, 3 way split... 176 // overlap end of range 177 try res.append(.{ 178 .start = r2.start, 179 .end = me.source_start, 180 }); 181 try res.append(.{ 182 .start = me.apply(me.source_start) orelse @panic("ploop"), 183 .end = (me.apply(me.source_end-1) orelse @panic("gloop")) + 1, 184 }); 185 const ne = r2.end; 186 r2 = .{ 187 .start = me.source_end, 188 .end = ne, 189 }; 190 } 191 } else { 192 // we had an unmapped section, retain it (equivalent to identity map) 193 try res.append(r2); 194 } 195 const x = try res.toOwnedSlice(); 196 std.mem.sort(Range, x, {}, Range.cmp); 197 return x; 198 } 199 200 test "applyRange no overlap" { 201 const a = std.testing.allocator; 202 var m = try Map.parse(a, 203 \\foobar! 204 \\3 10 2 205 ); 206 defer m.deinit(a); 207 const res = try m.applyRange(a, .{.start = 8, .end = 10}); 208 defer a.free(res); 209 try std.testing.expectEqualSlices(Range, &[_]Range{.{.start = 8, .end = 10}}, res); 210 211 const res2 = try m.applyRange(a, .{.start = 12, .end = 13}); 212 defer a.free(res2); 213 try std.testing.expectEqualSlices(Range, &[_]Range{.{.start = 12, .end = 13}}, res2); 214 } 215 test "applyRange overlap start" { 216 const a = std.testing.allocator; 217 var m = try Map.parse(a, 218 \\foobar! 219 \\5 20 10 220 ); 221 defer m.deinit(a); 222 const res = try m.applyRange(a, .{.start = 25, .end = 35}); 223 defer a.free(res); 224 try std.testing.expectEqualSlices(Range, &[_]Range{.{.start = 10, .end = 15}, .{.start = 30, .end = 35}}, res); 225 } 226 test "applyRange overlap end" { 227 const a = std.testing.allocator; 228 var m = try Map.parse(a, 229 \\foobar! 230 \\5 20 10 231 ); 232 defer m.deinit(a); 233 const res = try m.applyRange(a, .{.start = 15, .end = 25}); 234 defer a.free(res); 235 try std.testing.expectEqualSlices(Range, &[_]Range{.{.start = 5, .end = 10}, .{.start = 15, .end = 20}}, res); 236 } 237 test "applyRange map contains whole range" { 238 const a = std.testing.allocator; 239 var m = try Map.parse(a, 240 \\foobar! 241 \\5 20 10 242 ); 243 defer m.deinit(a); 244 const res = try m.applyRange(a, .{.start = 20, .end = 30}); 245 defer a.free(res); 246 try std.testing.expectEqualSlices(Range, &[_]Range{.{.start = 5, .end = 15}}, res); 247 } 248 test "applyRange range contains whole map" { 249 const a = std.testing.allocator; 250 var m = try Map.parse(a, 251 \\foobar! 252 \\5 20 10 253 ); 254 defer m.deinit(a); 255 const res = try m.applyRange(a, .{.start = 15, .end = 35}); 256 defer a.free(res); 257 try std.testing.expectEqualSlices(Range, &[_]Range{.{.start = 5, .end = 15}, .{.start = 15, .end = 20}, .{.start = 30, .end = 35}}, res); 258 } 259 }; 260 261 const MapEntry = struct { 262 dest_start: u64, 263 source_start: u64, 264 range_len: u64, 265 266 source_end: u64, // exclusive bound 267 dest_end: u64, // exclusive bound 268 269 fn parse(input: []const u8) !MapEntry { 270 var toks = std.mem.tokenize(u8, input, " "); 271 const dest_start = try std.fmt.parseInt(u64, (toks.next() orelse return error.NoDest), 10); 272 const source_start = try std.fmt.parseInt(u64, (toks.next() orelse return error.NoSource), 10); 273 const range_len = try std.fmt.parseInt(u64, (toks.next() orelse return error.NoRange), 10); 274 return .{ 275 .dest_start = dest_start, 276 .source_start = source_start, 277 .range_len = range_len, 278 .source_end = source_start + range_len, 279 .dest_end = dest_start + range_len, 280 }; 281 } 282 283 fn apply(self: MapEntry, in: u64) ?u64 { 284 if (in >= self.source_start and in < (self.source_start + self.range_len)) { 285 const diff = in - self.source_start; 286 return self.dest_start + diff; 287 } 288 return null; 289 } 290 }; 291 292 const Range = struct { 293 start: u64, 294 end: u64, 295 fn cmp(_:void, lhs: Range, rhs: Range) bool { 296 return lhs.start < rhs.start; 297 } 298 }; 299 300 test "pt1" { 301 try std.testing.expectEqual(@as(u64, 35), try solve_pt1(std.testing.allocator, test_input)); 302 } 303 test "pt2" { 304 try std.testing.expectEqual(@as(u64, 46), try solve_pt2(std.testing.allocator, test_input)); 305 } 306 307 const test_input = 308 \\seeds: 79 14 55 13 309 \\ 310 \\seed-to-soil map: 311 \\50 98 2 312 \\52 50 48 313 \\ 314 \\soil-to-fertilizer map: 315 \\0 15 37 316 \\37 52 2 317 \\39 0 15 318 \\ 319 \\fertilizer-to-water map: 320 \\49 53 8 321 \\0 11 42 322 \\42 0 7 323 \\57 7 4 324 \\ 325 \\water-to-light map: 326 \\88 18 7 327 \\18 25 70 328 \\ 329 \\light-to-temperature map: 330 \\45 77 23 331 \\81 45 19 332 \\68 64 13 333 \\ 334 \\temperature-to-humidity map: 335 \\0 69 1 336 \\1 0 69 337 \\ 338 \\humidity-to-location map: 339 \\60 56 37 340 \\56 93 4 341 ; 342 343 const puzzle_input = 344 \\seeds: 202517468 131640971 1553776977 241828580 1435322022 100369067 2019100043 153706556 460203450 84630899 3766866638 114261107 1809826083 153144153 2797169753 177517156 2494032210 235157184 856311572 542740109 345 \\ 346 \\seed-to-soil map: 347 \\1393363309 644938450 159685707 348 \\2025282601 1844060172 19312202 349 \\1233103806 1026919253 32871092 350 \\1086566452 1933428941 86530991 351 \\1265974898 0 21589659 352 \\1357621124 1636167265 35742185 353 \\2343571960 2665606060 81121142 354 \\1585337376 809179011 202497192 355 \\3151050390 3039622538 54531851 356 \\2059837853 804624157 4554854 357 \\169037772 124717914 59280146 358 \\228317918 183998060 248114943 359 \\2646529073 2343571960 51673623 360 \\1173097443 1360585007 60006363 361 \\2000660015 1203115155 24622586 362 \\1059486394 1176035097 27080058 363 \\3129081851 4185259485 17367169 364 \\3599437884 3098755759 211817367 365 \\2810085327 3883695720 116314513 366 \\2424693102 4015066563 32329632 367 \\3398847262 2507128214 141172870 368 \\1787834568 432113003 212825447 369 \\1553049016 1603878905 32288360 370 \\3111414816 4202626654 17667035 371 \\4015961437 3493485543 279005859 372 \\3584381554 4000010233 15056330 373 \\609280127 1840486939 3573233 374 \\0 1603418622 460283 375 \\3302297495 3310573126 79244791 376 \\3811255251 4047396195 137863290 377 \\3381542286 2648301084 17304976 378 \\3280255848 3389817917 22041647 379 \\840113387 21589659 103128255 380 \\3949118541 3816852824 66842896 381 \\3205582241 4220293689 74673607 382 \\657286135 1420591370 182827252 383 \\1287564557 1863372374 70056567 384 \\460283 1671909450 168577489 385 \\2926399840 2746727202 103388997 386 \\3146449020 3094154389 4601370 387 \\943241642 1059790345 116244752 388 \\476432861 1227737741 132847266 389 \\612853360 2019959932 44432775 390 \\2698202696 2395245583 111882631 391 \\3029788837 3411859564 81625979 392 \\2044594803 1011676203 15243050 393 \\2457022734 2850116199 189506339 394 \\3540020132 3772491402 44361422 395 \\ 396 \\soil-to-fertilizer map: 397 \\1845319553 827629590 305617985 398 \\3122295925 2644420892 346256096 399 \\1459294850 681645131 145984459 400 \\1609507353 0 58999651 401 \\255693782 1322254706 15503402 402 \\1136906676 1310560683 7032394 403 \\609209731 1833691163 45329504 404 \\271197184 2213414186 148369535 405 \\3483324631 2990676988 343929863 406 \\3943098203 3619829050 148418709 407 \\2945015193 3803447520 177280732 408 \\504622935 1337758108 104586796 409 \\2644420892 3334606851 81771815 410 \\2909815432 3768247759 35199761 411 \\3468873015 4096571961 14451616 412 \\3827254494 3980728252 115843709 413 \\1044649784 1218303791 92256892 414 \\3468552021 4111023577 320994 415 \\1605279309 677417087 4228044 416 \\1668507004 58999651 176812549 417 \\978403972 1317593077 4661629 418 \\212737043 1879020667 42956739 419 \\916089003 1655081947 62314969 420 \\0 1442344904 212737043 421 \\1228536146 2361783721 230758704 422 \\419566719 1133247575 85056216 423 \\1143939070 1717396916 84597076 424 \\2726192707 4111344571 183622725 425 \\983065601 2151830003 61584183 426 \\2150937538 235812200 441604887 427 \\884391832 1801993992 31697171 428 \\654539235 1921977406 229852597 429 \\4091516912 3416378666 203450384 430 \\ 431 \\fertilizer-to-water map: 432 \\2549847515 3576009818 718957478 433 \\0 241538153 477666033 434 \\2425421388 2487425840 6333278 435 \\2431754666 2369332991 118092849 436 \\4172623904 3453666426 122343392 437 \\2050888028 0 241538153 438 \\2369332991 2493759118 56088397 439 \\477666033 719204186 1573221995 440 \\3268804993 2587418451 866247975 441 \\4135052968 2549847515 37570936 442 \\ 443 \\water-to-light map: 444 \\0 614660468 46162263 445 \\992982309 3320291957 519425172 446 \\2148695908 4242883656 34662742 447 \\2183358650 992982309 1749887545 448 \\622053693 575891430 38769038 449 \\1973119806 3839717129 175576102 450 \\3950667093 3281596434 38695523 451 \\46162263 0 575891430 452 \\1512407481 4015293231 227590425 453 \\1739997906 3048474534 233121900 454 \\3933246195 4277546398 17420898 455 \\3989362616 2742869854 305604680 456 \\ 457 \\light-to-temperature map: 458 \\3926915598 4278168812 16798484 459 \\1868013910 2147559018 140836186 460 \\750719301 1001446770 132766166 461 \\0 591148217 159571084 462 \\2757723179 3756680674 111319765 463 \\3526572182 1656447494 400343416 464 \\159571084 0 569934147 465 \\2869042944 3868000439 358532427 466 \\2008850096 3039560686 189896094 467 \\2649579616 3734175051 22505623 468 \\2270874649 2588070691 164667420 469 \\4008144721 2752738111 286822575 470 \\2435542069 2374033144 214037547 471 \\2672085239 2288395204 85637940 472 \\3450693140 2056790910 18639649 473 \\3469332789 3452574549 57239393 474 \\883485467 750719301 250727469 475 \\3943714082 3509813942 64430639 476 \\3227575371 3229456780 223117769 477 \\1708083440 3574244581 159930470 478 \\2198746190 2075430559 72128459 479 \\729505231 569934147 21214070 480 \\1656447494 4226532866 51635946 481 \\ 482 \\temperature-to-humidity map: 483 \\2530950430 2986195732 64296956 484 \\3097031068 3050492688 225336526 485 \\2595247386 2262922844 63415061 486 \\394235114 386308291 573314459 487 \\159338027 199058685 71729011 488 \\2107189180 2969998741 16196991 489 \\231067038 0 22309581 490 \\266735072 959622750 109765613 491 \\1941982137 2514902112 165207043 492 \\3525862760 2680109155 81512917 493 \\3809165514 2049071587 78022870 494 \\3887188384 2459869958 55032154 495 \\61551861 270787696 97786166 496 \\4083271930 3575006611 18595319 497 \\993228240 162831557 10548461 498 \\967549573 173380018 25678667 499 \\376500685 368573862 17734429 500 \\2877832272 3856947724 19626311 501 \\3607375677 4093177459 201789837 502 \\2519444451 4007134226 11505979 503 \\2658662447 4082384303 10793156 504 \\3322367594 3945539199 61595027 505 \\253376619 149473104 13358453 506 \\0 87921243 61551861 507 \\2961202681 2127094457 135828387 508 \\3942220538 3468929261 33142375 509 \\2669455603 2761622072 208376669 510 \\4197950728 3371912693 97016568 511 \\4101867249 3275829214 96083479 512 \\2446763340 1976390476 72681111 513 \\2313231287 2326337905 133532053 514 \\2897458583 4018640205 63744098 515 \\2123386171 3667102608 189845116 516 \\1003776701 22309581 65611662 517 \\3975362913 3593601930 73500678 518 \\4048863591 1941982137 34408339 519 \\3452927785 3502071636 72934975 520 \\3383962621 3876574035 68965164 521 \\ 522 \\humidity-to-location map: 523 \\0 853712401 14149303 524 \\2655090225 1087300934 303915897 525 \\2027272660 3174210041 18998832 526 \\1525779414 1936221923 38337972 527 \\4147713982 3193208873 142508118 528 \\2959006122 2143904256 380930882 529 \\1087300934 1765319513 65896883 530 \\1352738345 4121926227 173041069 531 \\1290854129 4060042011 61884216 532 \\3931908769 4005664051 54377960 533 \\4091732209 2524835138 55981773 534 \\653782902 95274560 214078802 535 \\477505648 85866717 9407843 536 \\2632545935 1543458967 22544290 537 \\123251703 309353362 97540905 538 \\3762564408 1974559895 169344361 539 \\3487433944 3409639319 23582322 540 \\318179985 430129950 159325663 541 \\1216931801 3335716991 12046317 542 \\1153197817 2580816911 63733984 543 \\14149303 406894267 23235683 544 \\2206646140 3433221641 320894268 545 \\3986286729 1566003257 105445480 546 \\37384986 0 85866717 547 \\2112775364 1671448737 93870776 548 \\2046271492 3107706169 66503872 549 \\3511016266 3754115909 251548142 550 \\1228978118 3347763308 61876011 551 \\1564117386 2644550895 463155274 552 \\3339937004 1391216831 147496940 553 \\486913491 589455613 166869411 554 \\4290222100 1538713771 4745196 555 \\220792608 756325024 97387377 556 \\2527540408 1831216396 105005527 557 ;