Day 5 - Advent of Code 2023
Mix.install([:kino, :benchee])Links
Input
input = Kino.Input.textarea("Please paste your input file:")input = input |> Kino.Input.read()
# input = AdventOfCode.Input.get!(5, 2023)"seeds: 3082872446 316680412 2769223903 74043323 4131958457 99539464 109726392 353536902 619902767 648714498 3762874676 148318192 1545670780 343889780 4259893555 6139816 3980757676 20172062 2199623551 196958359\n\nseed-to-soil map:\n2211745924 1281207339 39747980\n3648083739 2564129012 145170114\n4171944574 2333022880 44675857\n540694760 848661020 78793182\n256996824 588160543 260500477\n1870557289 1804847051 174857657\n3877597859 2853012070 228980636\n1634159465 2150723562 100770342\n3793253853 2293912908 39109972\n652571990 567856215 20304328\n2480343183 3372556760 130573730\n1831144195 528443121 39413094\n0 1690920197 113926854\n3145720856 3081992706 290564054\n624623106 1979704708 27948884\n3844601856 3751059243 32996003\n1260492360 1175075910 106131429\n1366623789 166330978 138490835\n1175000149 927454202 85492211\n696570061 1596389312 94530885\n2647046837 3784055246 498674019\n4216620431 2709299126 78346865\n953230443 1450000160 146389152\n791100946 1012946413 162129497\n1734929807 427093569 96214388\n672876318 403399826 23693743\n113926854 2007653592 143069970\n2045414946 0 166330978\n1099619595 328019272 75380554\n3832363825 4282729265 12238031\n619487942 523307957 5135164\n517497301 304821813 23197459\n2293912908 2377698737 186430275\n1505114624 1320955319 129044841\n2610916913 3714929319 36129924\n3436284910 3503130490 211798829\n4106578495 2787645991 65366079\n\nsoil-to-fertilizer map:\n2733576308 471599794 76965554\n1171423854 1329782324 37554133\n2640052871 928987130 93523437\n2015828352 548565348 204028986\n3562821857 3651707516 643259780\n1208977987 2596877127 12575372\n778871551 2204324824 392552303\n1221553359 2609452499 201089363\n3520687457 3069361301 42134400\n4240454288 3542205804 54513008\n2219857338 1367336457 420195533\n3034988650 3111495701 430710103\n307271757 0 471599794\n1422642722 2082393746 121931078\n3465698753 3596718812 54988704\n0 1022510567 307271757\n1544573800 1787531990 294861756\n4206081637 3034988650 34372651\n1839435556 752594334 176392796\n\nfertilizer-to-water map:\n1807260819 3957534991 337432305\n774926879 2718324291 701236360\n2351569884 1690420176 794087185\n313174888 2484507361 233816930\n3145657069 541109949 949949029\n546991818 313174888 227935061\n2144693124 3750658231 206876760\n4095606098 1491058978 199361198\n1476163239 3419560651 331097580\n\nwater-to-light map:\n3834982820 3688486185 202897824\n2016707141 372287565 116618935\n3386838019 3412408553 81116937\n1125723906 705568567 205087174\n4037880644 1840142480 150018623\n2359176858 4109550629 126312910\n3328178239 4050890849 58659780\n1801115923 3893484758 43944958\n1516002989 1645262885 194879595\n3501845456 488906500 216662067\n1373868013 2223115169 142134976\n3467954956 3641943956 33890500\n1845060881 3937429716 113461133\n3718507523 910655741 57371540\n3315526510 3675834456 12651729\n2936874590 2031117287 84929853\n1710882584 3551710617 90233339\n372287565 2365250145 753436341\n2133326076 968027281 225850782\n1330811080 1990161103 40956184\n1958522014 3493525490 58185127\n3021804443 3118686486 293722067\n2485489768 1193878063 451384822\n3775879063 4235863539 59103757\n1371767264 3891384009 2100749\n4187899267 2116047140 107068029\n\nlight-to-temperature map:\n156743496 2059819668 37694357\n4058204935 4136802755 38991573\n2484168315 1803830764 54458297\n2053264847 2531370441 7735546\n586814267 2539105987 96956250\n2538626612 2097514025 117228608\n4097196508 3782742182 197770788\n1246999413 607900903 25957627\n1877009740 1752361784 30081637\n683770517 3121708332 89729874\n1835387899 343006762 41621841\n1806332066 3242032508 29055833\n2212907940 137512351 205494411\n809588378 2954088675 69458905\n1689902424 3271088341 436818\n3306521233 894737794 308504080\n3235066415 3050253514 71454818\n1147299995 1960120250 99699418\n2046683718 749851354 6581129\n3782742182 4222506720 5456115\n2061000393 756432483 138305311\n792839631 591152156 16748747\n1478425864 2742612115 211476560\n2793367571 2636062237 73608402\n2471831801 2214742633 12336514\n194437853 1622309324 130052460\n3901915150 3980512970 156289785\n2655855220 0 137512351\n324490313 1359985370 262323954\n3855202758 4175794328 46712392\n2445108285 1782443421 21387343\n2467550357 3211438206 4281444" <> ...Solution
defmodule Day05 do
defdelegate parse(input), to: __MODULE__.Input
def part1(input) do
[{seeds_p1, _seed_ranges_p2} | maps] = parse(input)
seeds_p1
|> Enum.map(&seed_value(&1, maps))
|> Enum.min()
end
def part2(input) do
# [{seeds_p1, seed_ranges_p2} | maps] = parse(input)
parse(input)
end
def seed_value(seed, mappings) do
Enum.reduce(mappings, seed, fn {_type, maps}, seed ->
Enum.find_value(maps, fn
{source_range, _dest_range, diff} ->
if seed in source_range, do: seed + diff
_ ->
nil
end) || seed
end)
end
defmodule Input do
def parse(input) when is_binary(input) do
input
|> String.splitter("\n\n", trim: true)
|> parse()
end
def parse(input) do
Enum.map(input, &parse_line/1)
end
def parse_line("seeds: " <> seeds) do
seeds =
seeds
|> String.split(" ", trim: true)
|> Enum.map(&String.to_integer/1)
ranges =
seeds
|> Enum.chunk_every(2)
|> Enum.map(fn [start, size] ->
start..(start + size - 1)
end)
{seeds, Enum.sort(ranges)}
end
def parse_line(line) do
[type | maps] = String.split(line, "\n", trim: true)
[from, to] = Regex.run(~r/([a-z]+)\-to\-([a-z]+) map:/, type, capture: :all_but_first)
maps =
maps
|> Enum.map(fn m ->
[dest, source, length] =
String.split(m, " ", trim: true) |> Enum.map(&String.to_integer/1)
{
source..(source + length - 1),
dest..(dest + length - 1),
dest - source
}
end)
|> Enum.sort_by(&elem(&1, 1))
|> then(fn
[{_, 0.._, _} | _] = ranges ->
ranges
[{_, start.._, _} | _] = ranges ->
range = 0..(start - 1)
[{range, range, 0} | ranges]
end)
{_, _..caboose, _} = Enum.at(maps, -1)
{{from, to}, List.insert_at(maps, -1, {:end, caboose})}
end
end
end{:module, Day05, <<70, 79, 82, 49, 0, 0, 12, ...>>,
{:module, Day05.Input, <<70, 79, 82, ...>>, {:parse_line, 1}}}Part 1:
What is the lowest location number that corresponds to any of the initial seed numbers?
Your puzzle answer was 84470622.
Day05.part1(input)84470622Part 2:
Consider all of the initial seed numbers listed in the ranges on the first line of the almanac. What is the lowest location number that corresponds to any of the initial seed numbers?
Your puzzle answer was 26714516.
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, you should return to your Advent calendar and try another puzzle.
If you still want to see it, you can get your puzzle input.
Part 2 approach
Need to find the only part of the source range that truly overlaps with the desired destination range.
Consider the desired destination range of 313933177..333555331
The dest_range of 194437853..324490312 in the {source_range, dest_range, diff} value of:
{1622309324..1752361783, 194437853..324490312, _}
overlaps with 313933177..333555331, but only from 313933177 to 324490312.
Therefore, we should change to allowed source_range accordingly, to become:
{1741804648..1752361783, 313933177..324490312, _}ranges = [
# {"humidity", [0..55], 1},
# {"temperature", [69..69, 0..54], 2},
# {"light", [0..44, 77..86], 3},
# {"water", [0..17, 25..51, 84..93], 4},
# {"fertilizer", [11..28, 36..52, 53..55, 84..93], 5},
# {"soil", [84..93], 6},
# {"seed", [82..91], 7}
{"humidity", [0..229_212_352], 1},
{"temperature", [0..139_752_126, 333_555_332..403_393_402], 2},
{"light", [1_203_241_874..1_342_994_000], 3},
{"water", [783_086_535..910_655_740, 1_990_161_103..2_002_344_023], 4},
{"fertilizer", [2_726_483_947..2_854_053_152], 5},
{"soil", [464_507_433..548_565_347], 6},
{"seed", [795_671_152..848_661_019, 251_831_945..328_019_271, 848_661_020..856_531_607], 7}
]
find_next_range = fn
a..b, {_s1.._s2, d1..d2, diff} when d1 <= a and d2 >= b ->
(a - diff)..(b - diff)
a..b, {_s1..s2, _d1..d2, _} when d2 in a..b ->
adj = d2 - a
max(s2 - adj, 0)..s2
a..b, {s1.._s2, d1.._d2, _} when d1 in a..b ->
adj = b - d1
s1..(s1 + adj)
a..b, {:end, caboose} when a > caboose ->
a..b
_, _ ->
nil
end
Day05.part2(input)
|> Enum.reverse()
|> Enum.at(6)
|> elem(1)
# |> Enum.filter(fn {_source_range, dest_range, _diff} ->
# not Range.disjoint?(dest_range, 0..139752126)
# end)
|> Enum.map(&find_next_range.(464_507_433..548_565_347, &1))
|> Enum.reject(&is_nil/1)[795671152..848661019, 251831945..328019271, 848661020..856531607]Explanation (sort of)
I don’t even know if I can coherently explain what I did, but I’ll try:
I tried to work backwards from the 0..? location range to find what range(s) from the prior step would allow me to land on each desired downstream range. I had a function to help find the possible ranges from each prior step.
I manually went through each step because I wasn’t confident in my ability to program that recursion correctly, and I wanted to sanity check each step to catch bugs in my range logic along the way (there ended up being more than a few). I was also hopeful it wouldn’t take too many recursive iterations to find a valid starting range, which ended up being true (there were 3-4 dead end paths at the front that didn’t find any valid starting seed ranges).
I thought that when I finally found a starting seed range, the lower bound of that calculated range would be the answer - this is how the test case worked. This didn’t happen.
When I did find a happy path of possible starting seed ranges that overlapped with 1+ of my seed ranges, there were 3 such possible starting seed ranges.
Checking the lower and upper bounds of each of these possible starting seed ranges (to see what final location each produced) did help me narrow down the correct seed range - one of my upper bounds produced a lower final location than any of the other range bounds.
I used an iterative binary search backwards from that upper bound to narrow down each significant digit to the correct answer.
[{seeds_p1, seed_ranges_p2} | maps] = Day05.parse(input)
{
Day05.seed_value(795_671_152, maps),
Day05.seed_value(848_661_019, maps),
Day05.seed_value(251_831_945, maps),
Day05.seed_value(328_019_271, maps),
Day05.seed_value(848_661_020, maps),
Day05.seed_value(856_531_607, maps)
}
# seed_ranges_p2 |> Enum.any?(fn range -> 328019271 in range end){2978837264, 72612022, 4154147077, 95809481, 95809482, 103680069}{
Day05.seed_value(802_763_512, maps),
Day05.seed_value(802_763_513, maps),
Day05.seed_value(848_661_019, maps)
}{2985929624, 26714516, 72612022}