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