Day 5: If You Give A Seed A Fertilizer

day-05.livemd

Hannes Wüthrich

@hwuethrich

aoc2023

More notebooks

Day 5: If You Give A Seed A Fertilizer

Mix.install([
  {:smaoc, git: "https://github.com/nettinho/smaoc"}
])

Part 1

You take the boat and find the gardener right where you were told he would be: managing a giant “garden” that looks more to you like a farm.

“A water source? Island Island is the water source!” You point out that Snow Island isn’t receiving any water.

“Oh, we had to stop the water because we ran out of sand to filter it with! Can’t make snow with dirty water. Don’t worry, I’m sure we’ll get more sand soon; we only turned off the water a few days… weeks… oh no.” His face sinks into a look of horrified realization.

“I’ve been so busy making sure everyone here has food that I completely forgot to check why we stopped getting more sand! There’s a ferry leaving soon that is headed over in that direction - it’s much faster than your boat. Could you please go check it out?”

You barely have time to agree to this request when he brings up another. “While you wait for the ferry, maybe you can help us with our food production problem. The latest Island Island Almanac just arrived and we’re having trouble making sense of it.”

The almanac (your puzzle input) lists all of the seeds that need to be planted. It also lists what type of soil to use with each kind of seed, what type of fertilizer to use with each kind of soil, what type of water to use with each kind of fertilizer, and so on. Every type of seed, soil, fertilizer and so on is identified with a number, but numbers are reused by each category - that is, soil 123 and fertilizer 123 aren’t necessarily related to each other.

For example:

seeds: 79 14 55 13

seed-to-soil map:
50 98 2
52 50 48

soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15

fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4

water-to-light map:
88 18 7
18 25 70

light-to-temperature map:
45 77 23
81 45 19
68 64 13

temperature-to-humidity map:
0 69 1
1 0 69

humidity-to-location map:
60 56 37
56 93 4

The almanac starts by listing which seeds need to be planted: seeds 79, 14, 55, and 13.

The rest of the almanac contains a list of maps which describe how to convert numbers from a source category into numbers in a destination category. That is, the section that starts with seed-to-soil map: describes how to convert a seed number (the source) to a soil number (the destination). This lets the gardener and his team know which soil to use with which seeds, which water to use with which fertilizer, and so on.

Rather than list every source number and its corresponding destination number one by one, the maps describe entire ranges of numbers that can be converted. Each line within a map contains three numbers: the destination range start, the source range start, and the range length.

Consider again the example seed-to-soil map:

50 98 2
52 50 48

The first line has a destination range start of 50, a source range start of 98, and a range length of 2. This line means that the source range starts at 98 and contains two values: 98 and 99. The destination range is the same length, but it starts at 50, so its two values are 50 and 51. With this information, you know that seed number 98 corresponds to soil number 50 and that seed number 99 corresponds to soil number 51.

The second line means that the source range starts at 50 and contains 48 values: 50, 51, …, 96, 97. This corresponds to a destination range starting at 52 and also containing 48 values: 52, 53, …, 98, 99. So, seed number 53 corresponds to soil number 55.

Any source numbers that aren’t mapped correspond to the same destination number. So, seed number 10 corresponds to soil number 10.

So, the entire list of seed numbers and their corresponding soil numbers looks like this:

With this map, you can look up the soil number required for each initial seed number:

Seed number 79 corresponds to soil number 81.
Seed number 14 corresponds to soil number 14.
Seed number 55 corresponds to soil number 57.
Seed number 13 corresponds to soil number 13.

The gardener and his team want to get started as soon as possible, so they’d like to know the closest location that needs a seed. Using these maps, find the lowest location number that corresponds to any of the initial seeds. To do this, you’ll need to convert each seed number through other categories until you can find its corresponding location number. In this example, the corresponding types are:

Seed 79, soil 81, fertilizer 81, water 81, light 74, temperature 78, humidity 78, location 82.
Seed 14, soil 14, fertilizer 53, water 49, light 42, temperature 42, humidity 43, location 43.
Seed 55, soil 57, fertilizer 57, water 53, light 46, temperature 82, humidity 82, location 86.
Seed 13, soil 13, fertilizer 52, water 41, light 34, temperature 34, humidity 35, location 35.

So, the lowest location number in this example is 35.

What is the lowest location number that corresponds to any of the initial seed numbers?

Part 2

Everyone will starve if you only plant such a small number of seeds. Re-reading the almanac, it looks like the seeds: line actually describes ranges of seed numbers.

The values on the initial seeds: line come in pairs. Within each pair, the first value is the start of the range and the second value is the length of the range. So, in the first line of the example above:

seeds: 79 14 55 13

This line describes two ranges of seed numbers to be planted in the garden. The first range starts with seed number 79 and contains 14 values: 79, 80, …, 91, 92. The second range starts with seed number 55 and contains 13 values: 55, 56, …, 66, 67.

Now, rather than considering four seed numbers, you need to consider a total of 27 seed numbers.

In the above example, the lowest location number can be obtained from seed number 82, which corresponds to soil 84, fertilizer 84, water 84, light 77, temperature 45, humidity 46, and location 46. So, the lowest location number is 46.

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?

Solution

defmodule Smaoc.Solution do
  def solve(:part1, input) do
    {seeds, maps} = parse_input(input)

    find_location = fn seed ->
      Enum.reduce(maps, seed, &amp;map_number/2)
    end

    seeds
    |> Enum.map(find_location)
    |> Enum.min()
  end

  def solve(:part2, input) do
    {seeds, maps} = parse_input(input)

    seed_ranges =
      seeds
      |> Stream.chunk_every(2)
      |> Stream.map(fn [start, len] -> start..(start + len) end)

    maps = reverse_maps(maps)

    valid_seed? = fn location ->
      seed = Enum.reduce(maps, location, &amp;map_number/2)
      Enum.any?(seed_ranges, &amp;(seed in &amp;1))
    end

    Stream.iterate(0, &amp;(&amp;1 + 1))
    |> Stream.chunk_every(1000)
    |> Task.async_stream(&amp;Enum.find(&amp;1, valid_seed?), timeout: :infinity)
    |> Enum.find_value(fn {:ok, seed} -> seed end)
  end

  def reverse_maps(maps) do
    maps
    |> Enum.reverse()
    |> Enum.map(&amp;reverse_map/1)
  end

  def reverse_map(ranges) do
    Enum.map(ranges, fn {dst, src, len} -> {src, dst, len} end)
  end

  defp parse_input(input) do
    [seeds | maps] =
      input
      |> String.split("\n\n", trim: true)
      |> Enum.reject(&amp;(&amp;1 == ""))

    seeds =
      seeds
      |> String.trim_leading("seeds: ")
      |> String.split(" ")
      |> Enum.map(&amp;String.to_integer/1)

    maps = Enum.map(maps, &amp;parse_map/1)

    {seeds, maps}
  end

  def map_number(map, n) when is_list(map) do
    Enum.find_value(map, n, &amp;map_number(&amp;1, n))
  end

  def map_number({dst, src, len}, n) when n in src..(src + len) do
    dst + (n - src)
  end

  def map_number({_, _, _}, _), do: nil

  defp parse_map(block) do
    [_ | lines] = String.split(block, "\n", trim: true)

    Enum.map(lines, fn line ->
      [dst, src, len] =
        String.split(line, " ", trim: true)
        |> Enum.map(&amp;String.to_integer/1)

      {dst, src, len}
    end)
  end
end

year = "2023"
day = "5"
run_config = ["example", "puzzle", "part1", "part2"]

inputs = %{
  "puzzle" =>
    "seeds: 1132132257 323430997 2043754183 4501055 2539071613 1059028389 1695770806 60470169 2220296232 251415938 1673679740 6063698 962820135 133182317 262615889 327780505 3602765034 194858721 2147281339 37466509\n\nseed-to-soil map:\n1280158874 0 45923291\n0 1431836695 234754481\n2476778759 365219074 73714061\n3997869725 4152785341 16553125\n3014496893 3731980396 420804945\n3435301838 2667516045 60128827\n2784964719 2727644872 187996890\n792043155 613341484 49447658\n1444573280 2476024240 74468580\n2728723659 3675739336 56241060\n2704677524 4236229588 24046135\n2360313001 1780050354 116465758\n1326082165 226504189 118491115\n3495430665 3630596320 3607732\n1519041860 662789142 56785021\n3973462947 3383860003 24406778\n1575826881 45923291 119425025\n1695251906 766775600 665061095\n2667516045 3323175190 6512477\n4240794960 3329687667 54172336\n720792676 344995304 20223770\n489053726 438933135 143852141\n741016446 746305099 20470501\n3499038397 4169338466 66891122\n761486947 582785276 30556208\n3565929519 3249598798 73576392\n659636803 165348316 61155873\n234754481 2221724995 254299245\n2674028522 4260275723 30649002\n841490813 1896516112 325208883\n632905867 719574163 26730936\n1166699696 1666591176 113459178\n2972961609 3634204052 41535284\n4195000071 3408266781 45794889\n4190957500 4290924725 4042571\n3639505911 2915641762 333957036\n4014422850 3454061670 176534650\n\nsoil-to-fertilizer map:\n528009375 3804807330 65591757\n3608285775 3569685636 235121694\n432120564 3045118038 95888811\n3843407469 1792428879 363149111\n4206556580 2155577990 88410716\n3441777 3141006849 428678787\n1019419908 3870399087 424568209\n593601132 2619299262 425818776\n1443988117 3441777 1788987102\n3232975219 2243988706 375310556\n\nfertilizer-to-water map:\n3768646817 2541098841 42522952\n657445332 493998363 293094466\n3153469588 3947073749 287697992\n2513829777 3047249136 215146452\n968568929 29638292 96921246\n1600806946 1111339724 96961929\n3880726440 2687212715 52238929\n416544049 1090614661 20725063\n1749924539 4274983783 15782292\n1306572576 1208301653 21184719\n2134505230 4234771741 40212042\n1697768875 0 29638292\n3811169769 2617656044 69556671\n487527141 787092829 169918191\n3932965369 2583621793 34034251\n178562138 1471396125 237981911\n2728976229 3010972799 36276337\n2174717272 3262395588 176952386\n3035746039 1749924539 117723549\n2794475974 2764473831 241270065\n437269112 443740334 50258029\n2790274753 4290766075 4201221\n3441167580 3767315650 179758099\n3966999620 3439347974 327967676\n2351669658 2236446487 162160119\n1585319642 1229486372 15487304\n1327757295 186177987 257562347\n2765252566 2739451644 25022187\n950539798 1709378036 18029131\n1765706831 1867648088 368798399\n1199093816 1363917365 107478760\n3763417914 3005743896 5228903\n1065490175 957011020 133603641\n3620925679 2398606606 142492235\n59618449 1244973676 118943689\n0 126559538 59618449\n\nwater-to-light map:\n2368177077 1928300684 68416280\n3459327457 4032125413 181740227\n2874128303 2996109939 93290692\n40167335 1203835270 50270286\n2984608918 3988581415 43543998\n1295445723 891961544 129160430\n232873619 72411133 344405432\n4002859459 4225073350 66563582\n3451555101 2874128303 4441992\n3957368975 2950619455 45490484\n4192270745 3148930063 6297777\n1638782153 2125726715 498901151\n3028152916 2912054150 38565305\n577279051 1504061698 367203335\n3418071246 2878570295 33483855\n3897839543 3089400631 59529432\n2967418995 3166056654 3449280\n3641067684 3835626234 152955181\n4147219041 3436688572 45051704\n2436593357 1021121974 182713296\n3066718221 3484273209 351353025\n2647866375 1254105556 189577037\n4198568522 3340289798 96398774\n2619306653 39188438 21015758\n2982075985 3481740276 2532933\n4069423041 3155227840 10828814\n2186332185 1443682593 52835141\n90437621 678875874 142435998\n980629741 2624627866 212815546\n2239167326 1996716964 129009751\n1424606153 571958210 106917664\n0 1871265033 40167335\n2980967789 4223965154 1108196\n1619041805 450217426 19740348\n1193445287 469957774 102000436\n944482386 426277008 23940418\n4080251855 3169505934 66967186\n1548392133 821311872 70649672\n1531523817 1911432368 16868316\n2970868275 4213865640 10099514\n3455997093 4291636932 3330364\n2137683304 416816565 9460443\n3794022865 3236473120 103816678\n2147143747 0 39188438\n2640322411 1496517734 7543964\n968422804 60204196 12206937\n\nlight-to-temperature map:\n224631556 2579077346 68012835\n93390978 2647090181 93292258\n836334842 260175809 93895333\n3305235739 4175688657 119278639\n2495493200 354071142 67947352\n2563440552 648390650 214063090\n4184988573 4065709934 109978723\n930230175 2740382439 151863620\n2777503642 1813071562 114742417\n3424514378 3772814840 292895094\n1492090043 422018494 226372156\n3717409472 3176683751 126763710\n3273297 2243837725 90117681\n1216313119 2511603925 67473421\n4104753748 3096448926 80234825\n2392410003 1112358810 103083197\n759707869 2434976952 76626973\n2031212648 2333955406 101021546\n2132234194 0 260175809\n1718462199 1931087276 312750449\n186683236 1682505485 37948320\n1174711552 1070757243 41601567\n292644391 1215442007 467063478\n3844173182 3512234274 260580566\n1283786540 862453740 208303503\n3096448926 3303447461 208786813\n1082093795 1720453805 92617757\n0 1927813979 3273297\n\ntemperature-to-humidity map:\n1908382071 0 48093237\n1668173777 369927146 108464980\n2454615458 3265918092 19222900\n2948843885 2383489773 582426713\n1291899323 304752282 65174864\n4051886972 3793288156 243080324\n2849120094 3285140992 99723791\n2415628816 3186987107 38986642\n724194709 716571124 379381363\n1103576072 2070505932 18664072\n3531270598 1602200086 102620550\n4020906946 3755760878 30980026\n1122240144 2285968817 97520956\n2779959793 1533039785 69160301\n1357074187 2089170004 196798813\n1823337263 624772153 85044808\n561911923 1433912547 99127238\n2538151277 1095952487 222368482\n1776638757 709816961 6754163\n2248869517 1776958859 59989455\n2760519759 48093237 3497277\n3770981692 4278303020 16664276\n3755760878 4263082206 15220814\n2497298857 263899862 40852420\n2473838358 1900103862 23460499\n234010997 51590514 212309348\n661039161 1836948314 63155548\n0 1923564361 87630970\n1219761100 1704820636 72138223\n87630970 478392126 146380027\n1956475308 3462247498 171643650\n3787645968 3786740904 6547252\n2764017036 2054563175 15942757\n2171486802 3384864783 77382715\n446320345 1318320969 115591578\n1783392920 3225973749 39944343\n2308858972 2965916486 106769844\n1553873000 3072686330 114300777\n3794193220 4036368480 226713726\n2128118958 2011195331 43367844\n\nhumidity-to-location map:\n2944942064 3820503519 61983659\n3834803738 3234323053 106874653\n2156211251 3962463577 28956273\n483302901 3882487178 79976399\n2282996952 2161034243 46548053\n2629999410 1876993734 225283872\n3370099006 3129013552 105309501\n1029930529 620272722 135507476\n3572091970 2932598747 109287331\n3739626327 942443797 51739908\n3311342369 2102277606 58756637\n3941678391 399929037 136325691\n1245368468 58880743 172279414\n790057642 1189404679 239872887\n1498307968 3341197706 67668316\n273081010 616914814 3357908\n2501095485 2803694822 128903925\n3475408507 4198283833 96683463\n1860675375 3456652816 219039792\n245544342 2207582296 27536668\n3006925723 1666468371 210525363\n3791366235 3733939634 11933242\n1165438005 1502653815 79930463\n1691906495 231160157 168768880\n1590576804 994183705 101329691\n2079715167 2235118964 76496084\n276438918 3991419850 206863983\n563279300 2507766048 226778342\n2855283282 3408866022 47786794\n1565976284 2311615048 24600520\n3217451086 1095513396 93891283\n3803299477 1429277566 31504261\n4161888175 2757743175 45951647\n2903070076 1460781827 41871988\n3681379301 3675692608 58247026\n4207839822 3041886078 87127474\n2185167524 2734544390 23198785\n2329545005 2336215568 171550480\n4078004082 1582584278 83884093\n1417647882 536254728 80660086\n58880743 755780198 186663599\n2208366309 3745872876 74630643\n",
  "example" =>
    "seeds: 79 14 55 13\n\nseed-to-soil map:\n50 98 2\n52 50 48\n\nsoil-to-fertilizer map:\n0 15 37\n37 52 2\n39 0 15\n\nfertilizer-to-water map:\n49 53 8\n0 11 42\n42 0 7\n57 7 4\n\nwater-to-light map:\n88 18 7\n18 25 70\n\nlight-to-temperature map:\n45 77 23\n81 45 19\n68 64 13\n\ntemperature-to-humidity map:\n0 69 1\n1 0 69\n\nhumidity-to-location map:\n60 56 37\n56 93 4"
}

response =
  for part <- ["part1", "part2"], input_key <- ["puzzle", "example"] do
    {part, input_key}
  end

response =
  response
  |> Enum.filter(fn {part, input_key} ->
    part in run_config and input_key in run_config
  end)
  |> Enum.map(fn {part, input_key} ->
    [part, input_key, Smaoc.Solution.solve(String.to_atom(part), inputs[input_key])]
  end)

Smaoc.Response.new(%{response: response, run_config: run_config, year: year, day: day})

Back