this repo has no description
hauleth.dev
1<!-- vim:ft=markdown -->
2
3<!-- livebook:{"persist_outputs":true} -->
4
5# Day 23
6
7## Section
8
9```elixir
10input =
11 File.stream!("day23.txt")
12 |> Enum.map(fn line ->
13 for <<c <- line>>, c in 'ABCD', do: String.to_atom(<<c + 32>>)
14 end)
15 |> Enum.reject(&(&1 == []))
16 |> Enum.zip()
17 |> Enum.map(&Tuple.to_list/1)
18 |> Enum.zip_with(~w[a b c d]a, &{&2, &1})
19 |> Map.new()
20```
21
22<!-- livebook:{"output":true} -->
23
24```
25%{a: [:d, :b], b: [:d, :a], c: [:c, :b], d: [:c, :a]}
26```
27
28Graph of the possible movements. `--` and `|` have multiply 1 and `---`, `\`, and `/` have
29multiply 2.
30
31```
32.--.---.---.---.---.--.
33 \ / \ / \ / \ /
34 . . . .
35 | | | |
36 . . . .
37```
38
39```elixir
40defmodule Day23 do
41 @costs %{a: 1, b: 10, c: 100, d: 1000}
42 @rooms %{a: -3, b: -1, c: 1, d: 3}
43
44 # - - - - - + + + + +
45 # 5 4 3 2 1 0 1 2 3 4 5
46 # A B C D
47 # A B C D
48
49 defp memoize(tid, args, func) do
50 case :ets.lookup(tid, args) do
51 [{^args, value}] ->
52 value
53
54 [] ->
55 value = func.()
56 :ets.insert(tid, {args, value})
57 value
58 end
59 end
60
61 def process(stacks) do
62 tid = :ets.new(:memoize, [:public, :set])
63 depth = length(stacks[:a])
64
65 try do
66 do_process(stacks, %{}, target(depth), depth, tid)
67 after
68 :ets.delete(tid)
69 end
70 end
71
72 defp do_process(target, _, target, _depth, _tid), do: 0
73
74 defp do_process(stacks, hall, target, depth, tid) do
75 memoize(tid, [stacks, hall], fn ->
76 possible_moves(stacks, hall, depth)
77 |> Enum.map(fn {new_stack, new_hall, cost} ->
78 cost + do_process(new_stack, new_hall, target, depth, tid)
79 end)
80 |> Enum.min(&<=/2, fn -> :inf end)
81 end)
82 end
83
84 defp possible_moves(stacks, hall, depth) do
85 hall_to_room(stacks, hall, depth) ++ room_to_hall(stacks, hall, depth)
86 end
87
88 defp hall_to_room(stacks, hall, depth) do
89 # IO.inspect({stacks, hall, depth}, label: elem(__ENV__.function, 0))
90 for {pos, t} <- hall,
91 clear_path_to_room?(t, pos, hall),
92 accepts?(t, stacks),
93 {size, new_stacks} = into_room(t, stacks),
94 do: {new_stacks, Map.delete(hall, pos), cost(t, pos, @rooms[t], depth - size)}
95 end
96
97 defp room_to_hall(stacks, hall, depth) do
98 []
99 end
100
101 defp clear_path_to_room?(t, pos, hall) do
102 hall
103 |> Map.keys()
104 |> Enum.find(&(&1 in min(pos, @rooms[t])..max(pos, @rooms[t])))
105 |> case do
106 nil -> true
107 _ -> false
108 end
109 end
110
111 defp accepts?(t, stacks), do: Enum.all?(stacks[t], &(&1 == t))
112
113 defp into_room(t, stacks) do
114 Map.get_and_update!(stacks, t, &{length(&1), [t | &1]})
115 end
116
117 defp target(depth) do
118 for v <- ~w[a b c d]a,
119 into: %{},
120 do: {v, List.duplicate(v, depth)}
121 end
122
123 def cost(elem, from, to, depth) do
124 @costs[elem] * (depth + abs(to - from))
125 end
126end
127```
128
129<!-- livebook:{"output":true} -->
130
131```
132warning: variable "depth" is unused (if the variable is not meant to be used, prefix it with an underscore)
133 day23.livemd#cell:58: Day23.room_to_hall/3
134
135warning: variable "hall" is unused (if the variable is not meant to be used, prefix it with an underscore)
136 day23.livemd#cell:58: Day23.room_to_hall/3
137
138warning: variable "stacks" is unused (if the variable is not meant to be used, prefix it with an underscore)
139 day23.livemd#cell:58: Day23.room_to_hall/3
140
141```
142
143<!-- livebook:{"output":true} -->
144
145```
146{:module, Day23, <<70, 79, 82, 49, 0, 0, 23, ...>>, {:cost, 4}}
147```
148
149```elixir
150Day23.process(input)
151```
152
153<!-- livebook:{"output":true} -->
154
155```
156:inf
157```