Aetherus
Advent of Code 2023 - Day 12
I tried to use combinatorial to solve today’s puzzles but failed (my brain burned out 
). In the end I just used brute force with memoization.
Task.async_stream turned out to be very helpful. It both let me handle each line of input concurrently, and allows me to abuse process dictionaries 
defmodule AoC2023.Day12 do
# `input` for both parts are things like
#
# [
# {"???.###", [1,1,3]},
# {".??..??...###.", [1,1,3]},
# ...
# ]
@spec part1([{String.t(), [pos_integer()]}]) :: non_neg_integer()
def part1(input) do
input
|> Task.async_stream(fn {springs, counts} ->
aux(springs, ".", counts)
end, ordered: false)
|> Stream.map(&elem(&1, 1))
|> Enum.sum()
end
@spec part2([{String.t(), [pos_integer()]}]) :: non_neg_integer()
def part2(input) do
input
|> Enum.map(fn {springs, counts} ->
{
List.duplicate(springs, 5) |> Enum.join("?"),
List.duplicate(counts, 5) |> List.flatten()
}
end)
|> part1()
end
@spec aux(
springs :: String.t(),
previous_spring :: String.t(),
counts :: [pos_integer()]
) :: non_neg_integer()
defp aux("", _, []), do: 1
defp aux("", _, [0]), do: 1
defp aux("", _, _), do: 0
defp aux("#" <> _, _, []), do: 0
defp aux("#" <> _, _, [0 | _]), do: 0
defp aux("#" <> rest, _, [h | t]), do: aux(rest, "#", [h - 1 | t])
defp aux("." <> rest, _, []), do: aux(rest, ".", [])
defp aux("." <> rest, "#", [0 | t]), do: aux(rest, ".", t)
defp aux("." <> _, "#", [_ | _]), do: 0
defp aux("." <> rest, ".", counts), do: aux(rest, ".", counts)
defp aux("?" <> rest, "#", []), do: aux(rest, ".", [])
defp aux("?" <> rest, "#", [0 | t]), do: aux(rest, ".", t)
defp aux("?" <> rest, "#", [h | t]), do: aux(rest, "#", [h - 1 | t])
defp aux("?" <> rest, ".", []), do: aux(rest, ".", [])
defp aux("?" <> rest, ".", [0 | t]), do: aux(rest, ".", t)
defp aux("?" <> rest, ".", [h | t]) do
memoized({rest, [h | t]}, fn ->
aux(rest, "#", [h - 1 | t]) + aux(rest, ".", [h | t])
end)
end
defp memoized(key, fun) do
with nil <- Process.get(key) do
fun.() |> tap(&Process.put(key, &1))
end
end
end
Most Liked
Aetherus
I still need to try your solution in a debugging way to fully understand it.
Here’s what I think about dynamic programming. It’s just brute force with some sort of caching. When we talk about caching, we know each entry needs a key. I think it doesn’t matter what the key is, as long as it’s consistent. If the keys are continuous non-negative integers or tuples of integers, in imperative languages we usually use an array or a 2D array or a 3D array as our store. But we don’t have to restrict ourselves to that kind of caching mechanism. We can use maps, GenServers, ETS tables, process dictionaries, or even databases as the cache store as long as it provides a fast way of lookup for an exact match, and what the type of the keys are just doesn’t matter.
Aetherus
I don’t know whether it’s O(1) or O(log N) either. According to my benchmark (not for this puzzle), process dictionary is faster than ETS, which in turn is faster than a plain map, and Agent is the slowest.
bjorng
I spent most time to get part 1 to work; I solved part 2 by adding memoization:
igorb
igorb
Just tried changing my solution to use process dictionaries instead — besides a much cleaner solution, it seems that this version is indeed around 10% faster than my old ETS-based approach. Never used process dictionaries in this way, thanks for sharing your solution! Learned a new thing today.
Popular in Challenges
Other popular topics
Latest on Elixir Forum
Sponsor Spotlight
Enabling companies to succeed by building software people love.
Categories:
Sub Categories:
Forums
Our Sponsors
Build Elixir applications with speed and confidence.
Supporting innovation across the BEAM ecosystem.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Practical resources that improve the lives of professional developers.
Producing high quality Elixir screencasts since 2017.
Enabling companies to succeed by building software people love.
Courses that'll move you from confusion to "Aha, now I get it!"