Here is my solution:
1 Like
part 1:
part 2:
It took me a while but ended up being a pretty clean solution in the end, I tried to leverage elixir’s duplicate function definitions today and I think it paid off, otherwise there would have been a mess of conditional logic.
I feel like I am slowly getting used to a more “Elixir/Functional” approach to the problems but I’ve got a fair way to go before it becomes natural 
Part 1:
defmodule Recursion do
def part1(lines) do
parse(lines)
|> explore("start", [])
|> List.flatten()
|> Enum.count(&(&1 == "end"))
end
defp explore(_, "end", visited), do: ["end" | visited]
defp explore(map, current_cave, visited) do
map
|> Map.get(current_cave)
|> Enum.filter(fn cave -> cave == String.upcase(cave) || cave not in visited end)
|> Enum.map(fn cave ->
explore(map, cave, [current_cave | visited])
end)
end
defp parse(lines) do
caves = lines |> Enum.map(&String.split(&1, "-", trim: true))
caves
|> Enum.map(&Enum.reverse/1)
|> Enum.concat(caves)
|> Enum.group_by(&Enum.at(&1, 0), &Enum.at(&1, 1))
end
end
Recursion.part1(lines)
Part 2:
defmodule Recursion do
def part2(lines) do
parse(lines)
|> explore("start", [], true)
|> List.flatten()
|> Enum.count(&(&1 == "end"))
end
defp explore(_, "end", visited, _), do: ["end" | visited]
defp explore(_, "start", [_|_] = visited, _), do: visited
defp explore(map, current_cave, visited, small) do
small =
cond do
small == false -> false
current_cave == String.downcase(current_cave) && current_cave in visited -> false
true -> true
end
map
|> Map.get(current_cave)
|> Enum.filter(fn cave -> small || cave == String.upcase(cave) || cave not in visited end)
|> Enum.map(fn cave ->
explore(map, cave, [current_cave | visited], small)
end)
end
defp parse(lines) do
caves = lines |> Enum.map(&String.split(&1, "-", trim: true))
caves
|> Enum.map(&Enum.reverse/1)
|> Enum.concat(caves)
|> Enum.group_by(&Enum.at(&1, 0), &Enum.at(&1, 1))
end
end
Recursion.part2(lines)
I could probably spend some time a refactor them into a single solution…
Here is my solution
At first it was pretty slow (~6s for part2), and I naively fixed it via memoizing the result of count_paths with an Agent.
Only then I realized that performance problems were due to the fact I was using a regex for the “small cave” check 
On the bright side I learnt how to profile elixir code 
3 Likes
Had a few hiccups on part 2 partly because I didn’t pay attention to the detail
After some optimization my solution can now finish (and is pretty fast) on fly.io free tier livebook!
1 Like
I thought part 2 was easy after part 1. However, it didn’t work for the bigger example. I wasn’t able to address the bug until I went to bed, and then I got the idea of why it didn’t work (maybe when in the dream). This morning I got up and just fixed it.
Here’s my solution:
defmodule PathFinder do
# I don't know how to make this work:
# defguard is_big(<<char, _::binary>>) when char in ?A..?Z
def find_all_paths(map, allow_visit_twice \\ false) do
[{["start"], %{allow_visit_twice: allow_visit_twice}}]
|> recur(map)
end
defp recur(paths, map) do
paths
|> Enum.flat_map(fn
{["end" | _], _} = result ->
[result]
{[p | walked], seen} ->
{visit_count, seen} =
Map.get_and_update(seen, p, fn
nil -> {1, 1}
n when is_integer(n) -> {n + 1, n + 1}
end)
seen = maybe_lock_twice_visit(seen, p, visit_count)
new_paths =
for np <- Map.fetch!(map, p),
can_visit?(np, seen) do
{
[np, p | walked],
seen
}
end
recur(new_paths, map)
end)
end
defp can_visit?(p, seen),
do: Map.get(seen, p, 0) < limit_of(p, seen)
defp limit_of("start", _), do: 1
defp limit_of(<<char, _::binary>>, _) when char in ?A..?Z, do: :infinity
defp limit_of(_, %{allow_visit_twice: true}), do: 2
defp limit_of(_, _), do: 1
defp maybe_lock_twice_visit(%{allow_visit_twice: false} = seen, _, _n), do: seen
defp maybe_lock_twice_visit(seen, <<char, _::binary>>, _n) when char in ?A..?Z, do: seen
defp maybe_lock_twice_visit(seen, _, 1), do: seen
defp maybe_lock_twice_visit(seen, _, _), do: %{seen | allow_visit_twice: false}
end
Question:
How can I make this work?
defguard is_big(<<char, _::binary>>) when char in ?A..?Z
I made a simple State struct to hold nodes and their histories for a BFS.
defp travel_caves(states, map, path_count \\ 0)
defp travel_caves([], _, path_count), do: path_count
defp travel_caves(states, map, path_count) do
next_states =
Enum.reduce(states, [], fn %State{current: current} = state, acc ->
map
|> Map.fetch!(current)
|> valid_neighbor_states(state)
|> Kernel.++(acc)
end)
{unfinished_states, finished_count} = process_states(next_states)
travel_caves(unfinished_states, map, path_count + finished_count)
end
Part 2’s additional requirements were easy to implement by just extending the State to have a couple extra keys.
Full solution here.
What was the bug? I’m stuck on part 2. I get the smaller sample correct but the larger ones not so much.
Is your answer too high or too low?
too high
Probably either
- allowing more than one small cave to be passed through twice
- allowing “start” to be passed through twice
- not ending promptly after “end” is reached
It’s definitely the first. I just can’t figure out why. My output shows some paths with two small caves duplicated. Probably because I’m checking before recursing. Hmm.
What logic are you using to meet that requirement? I went with a boolean flag inside each path which is turned off when the first duplicate happens.
Yeah, that’s a good idea. My algorithm builds the path by appending subpaths, but I’m checking for duplicates before recursing to build the next sub path. So then I return a subpath with one duplicate but I already said one duplicate was okay. Using a flag or just changing the timing of the check should fix it. Thanks for the insight.
============
ADDENDUM: LOL. I was already passing a flag for part 2. Once a duplicate is found treating subpaths the same as for part 1 eliminates further duplicates getting through.
1 Like
For me, it was checking and updating the seen state at the wrong time. I hope it helps.
Mine was the same. I was checking for a duplicate and recursing to add a subpath, also checking for duplicate in the subpath but never checking if the parent and sub both contained duplicates. Fix was simple.
