this repo has no description
hauleth.dev
1# Day 21
2
3```elixir
4Mix.install([:kino_aoc])
5```
6
7## Section
8
9<!-- livebook:{"attrs":{"assign_to":"puzzle_input","day":"21","session_secret":"ADVENT_OF_CODE_SESSION","year":"2023"},"chunks":null,"kind":"Elixir.KinoAOC.HelperCell","livebook_object":"smart_cell"} -->
10
11```elixir
12{:ok, puzzle_input} =
13 KinoAOC.download_puzzle("2023", "21", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION"))
14```
15
16```elixir
17# puzzle_input =
18"""
19...........
20.....###.#.
21.###.##..#.
22..#.#...#..
23....#.#....
24.##..S####.
25.##..#...#.
26.......##..
27.##.#.####.
28.##..##.##.
29...........
30"""
31```
32
33```elixir
34lines =
35 puzzle_input
36 |> String.split("\n", trim: true)
37
38map =
39 for {line, y} <- Enum.with_index(lines),
40 {char, x} <- Enum.with_index(to_charlist(line)),
41 char != ?.,
42 do: {char, {x, y}}
43
44%{?# => obstacles, ?S => [start]} = Enum.group_by(map, &elem(&1, 0), &elem(&1, 1))
45
46height = length(lines)
47width = byte_size(hd(lines))
48
49obstacles = MapSet.new(obstacles)
50{sx, sy} = start
51```
52
53```elixir
54defmodule Day21 do
55 def build_distance_map(width, height, start, obstacles) do
56 distances =
57 for x <- 0..width,
58 y <- 0..height,
59 {x, y} not in obstacles,
60 into: %{},
61 do: {{x, y}, nil}
62
63 do_build(Map.put(distances, start, 0), neighbours(start, width, height), width, height)
64 end
65
66 defp do_build(distances, [], _w, _h), do: distances
67
68 defp do_build(distances, [{x, y} | rest], w, h)
69 when is_nil(:erlang.map_get({x, y}, distances)) do
70 {min, next} =
71 Enum.reduce(neighbours({x, y}, w, h), {nil, []}, fn
72 {nx, ny}, {min, acc} ->
73 case Map.fetch(distances, {nx, ny}) do
74 {:ok, nil} -> {min, [{nx, ny} | acc]}
75 {:ok, val} -> {min(min, val), acc}
76 :error -> {min, acc}
77 end
78 end)
79
80 distances
81 |> Map.put({x, y}, min + 1)
82 |> do_build(rest ++ next, w, h)
83 end
84
85 defp do_build(distances, [_ | rest], w, h), do: do_build(distances, rest, w, h)
86
87 defp neighbours({x, y}, w, h),
88 do:
89 Enum.filter(
90 [
91 {x + 1, y},
92 {x - 1, y},
93 {x, y + 1},
94 {x, y - 1}
95 ],
96 &in_map?(&1, w, h)
97 )
98
99 def in_map?({x, y}, w, h), do: x in 0..w and y in 0..h
100end
101```
102
103```elixir
104dist = Day21.build_distance_map(width, height, start, obstacles)
105```
106
107## Part 1
108
109```elixir
110radius = 64
111
112potential_positions =
113 for dx <- -radius..radius,
114 dy <- -radius..radius,
115 rem(dx + dy, 2) == 0,
116 p = {sx + dx, sy + dy},
117 dist[p] <= radius,
118 do: {sx + dx, sy + dy}
119```
120
121```elixir
122length(potential_positions)
123```
124
125## Part 2
126
127```elixir
128{width, height}
129```
130
131```elixir
132radius = 26_501_365
133```
134
135<!-- livebook:{"offset":2664,"stamp":{"token":"XCP.IMvv8hCgLT5Uhw7XM98joJcCpiLODkv-dad_ZINIVpWiR15rOQ16JvnrIbZyWUgwLtcUNcu0O_o0fM9c_SHVKVz5kQtylMQU9zFIW02WoyY4Mif4i-dzdI_vkWqFZENooA","version":2}} -->