I finally got back to it!
this day is Kida fun and part2 can be fast achieved by comparing Range. But I was lazy so I just interacted everything through a list and used the same logic. as part 1, but with Task.async between all ranges.
It took 30 min to compute everything on my MacBook Air M2. XD Basically the time I had to do the dishes and see the result.
https://github.com/pedrosnk/coffee_and_kata/blob/main/aoc_2023/day_05/lib/day05.ex
Wow, you are way more patient than me. I will give a solution maybe 5 minutes before I just kill it.
I was basically multitasking at the time. If I was focusing on the problem probably would start over again after 1 min. Humans are definitely not meant to paralyze everything.
Another “calculate the result of applying maps to input ranges, splitting as necessary” solution for part 2.
Getting the heart of intersect right was really tricky, but it ended up very symmetrical.
defmodule Day5Part2 do
def read(filename) do
[{:seeds, seeds} | mappings] =
File.read!(filename)
|> String.split("\n\n")
|> Enum.map(&String.split(&1, ~r{:\s+}))
|> Enum.map(fn [label, value] -> parse(label, value) end)
{seeds, Map.new(mappings)}
end
defp parse("seeds", value) do
value
|> parse_numbers()
|> parse_ranges()
|> then(&{:seeds, &1})
end
defp parse(label, value) do
%{"from" => from, "to" => to} = parse_label(label)
{from, {to, parse_mapping(value)}}
end
defp parse_numbers(value) do
value
|> String.split(" ")
|> Enum.map(&String.to_integer/1)
end
defp parse_ranges(numbers) do
numbers
|> Enum.chunk_every(2)
|> Enum.map(fn [start, len] -> {start..start+len, 0} end)
|> normalize()
end
@regex ~r{(?<from>\w+)-to-(?<to>\w+) map}
defp parse_label(label) do
Regex.named_captures(@regex, label)
end
defp parse_mapping(value) do
value
|> String.split("\n")
|> Enum.map(&parse_numbers/1)
|> Enum.map(&parse_one_mapping/1)
end
defp parse_one_mapping([dest_start, source_start, len]) do
{source_start..(source_start+len-1), dest_start - source_start}
end
def intersect(source, []), do: [source]
def intersect({r_source, o_source}, [{r_map, o_map} | rest] = mapping) do
cond do
disjoint?({r_source, o_source}, r_map) ->
intersect({r_source, o_source}, rest)
r_source.first + o_source < r_map.first ->
# extra at the front
thru = Range.new(r_source.first, r_map.first-1-o_source, 1)
new_r1 = Range.new(r_map.first-o_source, r_source.last, 1)
[{thru, o_source} | intersect({new_r1, o_source}, mapping)]
r_source.last + o_source > r_map.last ->
# extra at the end
thru = Range.new(r_map.last+1-o_source, r_source.last, 1)
new_r1 = Range.new(r_source.first, r_map.last-o_source, 1)
[{new_r1, o_source+o_map} | intersect({thru, o_source}, mapping)]
true ->
# completely inside r_map
[{r_source, o_source+o_map}]
end
end
defp disjoint?({r1, off}, r2) do
r1
|> then(&Range.new(&1.first + off, &1.last + off, 1))
|> Range.disjoint?(r2)
end
def mapping_product(mapping) do
"seed"
|> Stream.unfold(&next_mapping(&1, mapping))
|> Stream.map(&normalize/1)
|> Enum.to_list()
end
defp next_mapping(label, mapping) do
case Map.get(mapping, label) do
nil -> nil
{next_label, ranges} ->
{ranges, next_label}
end
end
def normalize(ranges) do
Enum.sort_by(ranges, &elem(&1, 0).first)
end
end
{seeds, mapping} = Day5Part2.read("input.txt")
product = Day5Part2.mapping_product(mapping)
Enum.reduce(product, seeds, fn mapping, acc ->
acc
|> Enum.flat_map(&Day5Part2.intersect(&1, mapping))
|> Day5Part2.normalize()
end)
|> Enum.map(fn {r, o} -> r.first + o end)
|> Enum.min()
|> IO.inspect
I managed to bring down the execution time from ~30 minutes (laptop did not enjoy this) to ~1ms using your approach. Really nice and elegant solution, thank you!