this repo has no description
hauleth.dev
1<!-- vim:set ft=markdown: -->
2
3<!-- livebook:{"persist_outputs":true} -->
4
5# Day 12
6
7```elixir
8input =
9 File.read!("day12.txt")
10 |> String.split("\n")
11 |> Enum.map(&String.split(&1, "-"))
12
13graph =
14 Enum.reduce(input, %{}, fn [a, b], acc ->
15 acc
16 |> Map.update(a, [b], &[b | &1])
17 |> Map.update(b, [a], &[a | &1])
18 end)
19
20defmodule Day12 do
21 def dfs(graph, start, finish), do: dfs(graph, start, finish, [start])
22
23 defp dfs(_graph, vertex, vertex, _visited), do: 1
24
25 defp dfs(graph, vertex, finish, visited) do
26 (graph[vertex] -- visited)
27 |> Enum.reduce(0, fn vertex, acc ->
28 visited = if small?(vertex), do: [vertex | visited], else: visited
29
30 acc + dfs(graph, vertex, finish, visited)
31 end)
32 end
33
34 def dfs2(graph, start, finish), do: dfs2(graph, start, finish, %{start => :inf})
35
36 defp dfs2(_graph, vertex, vertex, _visited), do: 1
37
38 defp dfs2(graph, vertex, finish, visited) do
39 (graph[vertex] -- keys(visited))
40 |> Enum.reduce(0, fn vertex, acc ->
41 visited = if small?(vertex), do: Map.update(visited, vertex, 1, &(&1 + 1)), else: visited
42
43 acc + dfs2(graph, vertex, finish, visited)
44 end)
45 end
46
47 defp keys(map) do
48 if Enum.any?(map, fn {_, v} -> v == 2 end) do
49 # there is already some vertex visited twice
50 Map.keys(map)
51 else
52 for {k, v} <- map, v > 1, do: k
53 end
54 end
55
56 defp small?(<<c>> <> _), do: c in ?a..?z
57end
58```
59
60```output
61{:module, Day12, <<70, 79, 82, 49, 0, 0, 15, ...>>, {:small?, 1}}
62```
63
64## Task 1
65
66```elixir
67Day12.dfs(graph, "start", "end")
68```
69
70```output
714167
72```
73
74## Task 2
75
76```elixir
77Day12.dfs2(graph, "start", "end")
78```
79
80```output
8198441
82```