Day 20
Mix.install([:kino_aoc])Section
{:ok, puzzle_input} =
KinoAOC.download_puzzle("2024", "20", System.fetch_env!("LB_ADVENT_OF_CODE_SESSION")){:ok,
"#############################################################################################################################################\n#...#...#...#...#.........#.........###...#.....#...#.....#...#.......#...#...###...#...#...###.......#.........#...#...#...#...............#\n#.#.#.#.#.#.#.#.#.#######.#.#######.###.#.#.###.#.#.#.###.#.#.#.#####.#.#.#.#.###.#.#.#.#.#.###.#####.#.#######.#.#.#.#.#.#.#.#############.#\n#.#.#.#.#.#...#.#.....#...#.#.......#...#.#...#.#.#.#...#...#.#.#.....#.#.#.#.#...#...#.#.#...#...#...#.....#...#.#.#.#...#...#.........#...#\n#.#.#.#.#.#####.#####.#.###.#.#######.###.###.#.#.#.###.#####.#.#.#####.#.#.#.#.#######.#.###.###.#.#######.#.###.#.#.#########.#######.#.###\n#.#.#.#.#...#...#...#.#...#.#.#.....#...#...#.#.#.#...#.#.....#.#.###...#.#.#.#.......#.#.#...#...#.....###.#.....#...#...#...#.......#...###\n#.#.#.#.###.#.###.#.#.###.#.#.#.###.###.###.#.#.#.###.#.#.#####.#.###.###.#.#.#######.#.#.#.###.#######.###.###########.#.#.#.#######.#######\n#.#.#.#.#...#...#.#.#.#...#.#.#.#...###...#.#.#.#.#...#.#...#...#...#...#...#.....###.#.#.#...#.....#...#...#.......#...#...#...#.....#.....#\n#.#.#.#.#.#####.#.#.#.#.###.#.#.#.#######.#.#.#.#.#.###.###.#.#####.###.#########.###.#.#.###.#####.#.###.###.#####.#.#########.#.#####.###.#\n#.#.#.#.#.....#.#.#...#.#...#...#.....#...#...#.#.#...#.#...#.....#...#...#.......#...#...#...#.....#...#...#.....#.#.........#...#.....#...#\n#.#.#.#.#####.#.#.#####.#.###########.#.#######.#.###.#.#.#######.###.###.#.#######.#######.###.#######.###.#####.#.#########.#####.#####.###\n#.#...#.....#.#.#.#.....#...#.....#...#...#.....#...#.#.#...#...#...#.#...#.......#.......#...#.......#.....#.....#...........#...#.....#...#\n#.#########.#.#.#.#.#######.#.###.#.#####.#.#######.#.#.###.#.#.###.#.#.#########.#######.###.#######.#######.#################.#.#####.###.#\n#.#...#...#...#...#...#####.#...#...#####.#.###...#.#.#.#...#.#.....#...#...#.....###...#.#...#...###...#...#.#...#...#.....###.#.###...#...#\n#.#.#.#.#.###########.#####.###.#########.#.###.#.#.#.#.#.###.###########.#.#.#######.#.#.#.###.#.#####.#.#.#.#.#.#.#.#.###.###.#.###.###.###\n#...#...#...#.......#...#...#...#...###...#...#.#.#.#.#.#.###.......#.....#...#...#...#.#.#.###.#.#...#.#.#.#...#...#...#...#...#...#...#...#\n###########.#.#####.###.#.###.###.#.###.#####.#.#.#.#.#.#.#########.#.#########.#.#.###.#.#.###.#.#.#.#.#.#.#############.###.#####.###.###.#\n#...###...#...#...#...#...#...#...#.#...#...#.#.#.#.#...#...###...#.#.....#.....#.#...#...#.#...#.#.#.#.#.#...#...........#...#.....#...#...#\n#.#.###.#.#####.#.###.#####.###.###.#.###.#.#.#.#.#.#######.###.#.#.#####.#.#####.###.#####.#.###.#.#.#.#.###.#.###########.###.#####.###.###\n#.#.#...#.....#.#...#.....#...#.#...#...#.#...#.#...#.......#...#.#.#.....#.....#.###.....#.#...#.#.#.#...#...#...........#...#.....#.#...###\n#.#.#.#######.#.###.#####.###.#.#.#####.#.#####.#####.#######.###.#.#.#########.#.#######.#.###.#.#.#.#####.#############.###.#####.#.#.#####\n#.#...#.....#.#.#...#...#...#...#.#...#.#...#...#.....#.....#...#.#.#.......#...#...#...#.#.....#.#.#.#.....#.............#...#.....#.#.#...#\n#.#####.###.#.#.#.###.#.###.#####.#.#.#.###.#.###.#####.###.###.#.#.#######.#.#####.#.#.#.#######.#.#.#.#####.#############.###.#####.#.#.#.#\n#.#...#.#...#...#.....#.....#.....#.#.#.#...#...#.#...#...#.....#.#.#.....#.#.....#...#.#...#.....#.#.#.....#.#...###...###.#...#...#.#.#.#.#\n#.#.#.#.#.###################.#####.#.#.#.#####.#.#.#.###.#######.#.#.###.#.#####.#####.###.#.#####.#.#####.#.#.#.###.#.###.#.###.#.#.#.#.#.#\n#.#.#...#.................#...#...#.#.#.#.#.....#.#.#.###.......#.#.#...#...#...#...#...#...#.#.....#.#...#.#.#.#.....#.....#.....#...#...#.#\n#.#.#####################.#.###.#.#.#.#.#.#.#####.#.#.#########.#.#.###.#####.#.###.#.###.###.#.#####.#.#.#.#.#.###########################.#\n#.#.....#.................#.###.#.#.#.#.#.#...#...#.#...#...#...#.#.#...#...#.#.#...#...#...#.#...#...#.#.#.#.#.#.....#.......#.....#...#...#\n#.#####.#.#################.###.#.#.#.#.#.###.#.###.###.#.#.#.###.#.#.###.#.#.#.#.#####.###.#.###.#.###.#.#.#.#.#.###.#." <> ...}#puzzle_input =
"""
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
"""warning: outdented heredoc line. The contents inside the heredoc should be indented at the same level as the closing """. The following is forbidden:
def text do
"""
contents
"""
end
Instead make sure the contents are indented as much as the heredoc closing:
def text do
"""
contents
"""
end
The current heredoc line is indented too little
└─ Workspace/hauleth/advent-of-code/2024/day20.livemd#cell:iyjl3w4kz3srtwoq:3:3
"###############\n#...#...#.....#\n#.#.#.#.#.###.#\n#S#...#.#.#...#\n#######.#.#.###\n#######.#.#...#\n#######.#.###.#\n###..E#...#...#\n###.#######.###\n#...###...#...#\n#.#####.#.###.#\n#.#...#.#.#...#\n#.#.#.#.#.#.###\n#...#...#...###\n###############\n"map =
puzzle_input
|> String.split("\n")
|> Enum.with_index()
|> Enum.flat_map(fn {row, y} ->
row
|> String.split("", trim: true)
|> Enum.with_index()
|> Enum.map(fn {c, x} ->
{{x, y}, c}
end)
end)[
{{0, 0}, "#"},
{{1, 0}, "#"},
{{2, 0}, "#"},
{{3, 0}, "#"},
{{4, 0}, "#"},
{{5, 0}, "#"},
{{6, 0}, "#"},
{{7, 0}, "#"},
{{8, 0}, "#"},
{{9, 0}, "#"},
{{10, 0}, "#"},
{{11, 0}, "#"},
{{12, 0}, "#"},
{{13, 0}, "#"},
{{14, 0}, "#"},
{{15, 0}, "#"},
{{16, 0}, "#"},
{{17, 0}, "#"},
{{18, 0}, "#"},
{{19, 0}, "#"},
{{20, 0}, "#"},
{{21, 0}, "#"},
{{22, 0}, "#"},
{{23, 0}, "#"},
{{24, 0}, "#"},
{{25, 0}, "#"},
{{26, 0}, "#"},
{{27, 0}, "#"},
{{28, 0}, "#"},
{{29, 0}, "#"},
{{30, 0}, "#"},
{{31, 0}, "#"},
{{32, 0}, "#"},
{{33, 0}, "#"},
{{34, 0}, "#"},
{{35, 0}, "#"},
{{36, 0}, "#"},
{{37, 0}, "#"},
{{38, 0}, "#"},
{{39, 0}, "#"},
{{40, 0}, "#"},
{{41, 0}, "#"},
{{42, 0}, "#"},
{{43, 0}, "#"},
{{44, 0}, "#"},
{{45, 0}, "#"},
{{46, 0}, "#"},
{{47, ...}, "#"},
{{...}, ...},
{...},
...
]%{"#" => walls, "." => road, "S" => [start], "E" => [finish]} =
Enum.group_by(map, &elem(&1, 1), &elem(&1, 0))%{
"#" => [
{0, 0},
{1, 0},
{2, 0},
{3, 0},
{4, 0},
{5, 0},
{6, 0},
{7, 0},
{8, 0},
{9, 0},
{10, 0},
{11, 0},
{12, 0},
{13, 0},
{14, 0},
{15, 0},
{16, 0},
{17, 0},
{18, 0},
{19, 0},
{20, 0},
{21, 0},
{22, 0},
{23, 0},
{24, 0},
{25, 0},
{26, 0},
{27, 0},
{28, 0},
{29, 0},
{30, 0},
{31, 0},
{32, 0},
{33, 0},
{34, 0},
{35, 0},
{36, 0},
{37, 0},
{38, 0},
{39, 0},
{40, 0},
{41, 0},
{42, 0},
{43, 0},
{44, 0},
{45, 0},
{46, 0},
{47, ...},
{...},
...
],
"." => [
{1, 1},
{2, 1},
{3, 1},
{5, 1},
{6, 1},
{7, 1},
{9, 1},
{10, 1},
{11, 1},
{13, 1},
{14, 1},
{15, 1},
{17, 1},
{18, 1},
{19, 1},
{20, 1},
{21, 1},
{22, 1},
{23, 1},
{24, 1},
{25, 1},
{27, 1},
{28, 1},
{29, 1},
{30, 1},
{31, 1},
{32, 1},
{33, 1},
{34, 1},
{35, 1},
{39, 1},
{40, 1},
{41, 1},
{43, 1},
{44, 1},
{45, 1},
{46, 1},
{47, 1},
{49, 1},
{50, 1},
{51, 1},
{53, 1},
{54, 1},
{55, 1},
{56, 1},
{57, 1},
{59, ...},
{...},
...
],
"E" => [{27, 59}],
"S" => [{49, 53}]
}defmodule Race do
def distances(start, finish, walls) do
do_distances(start, finish, 0, MapSet.new(walls), %{})
end
defp do_distances(finish, finish, n, _, acc),
do: Map.put(acc, finish, n)
defp do_distances(current, finish, n, walls, acc) do
acc = Map.put(acc, current, n)
current
|> neigh()
|> Enum.reject(&(&1 in walls or Map.has_key?(acc, &1)))
|> hd()
|> do_distances(finish, n + 1, walls, acc)
end
def neigh({x, y}, d \\ 1) do
for {dx, dy} <- [{0, d}, {0, -d}, {d, 0}, {-d, 0}], do: {x + dx, y + dy}
end
def neighbours({x, y}, r \\ 1) do
for dx <- -r..r,
dy <- -r..r,
{dx, dy} != {0, 0},
d = abs(dx) + abs(dy),
d <= r,
do: {x + dx, y + dy}
end
def d({xa, ya}, {xb, yb}) do
abs(xa - xb) + abs(ya - yb)
end
end{:module, Race, <<70, 79, 82, 49, 0, 0, 17, ...>>, {:d, 2}}steps = Race.distances(start, finish, walls)%{
{18, 103} => 8261,
{61, 121} => 7060,
{65, 63} => 2098,
{77, 129} => 6964,
{1, 26} => 695,
{116, 69} => 4441,
{83, 76} => 4281,
{117, 125} => 5656,
{103, 106} => 5785,
{30, 113} => 8041,
{89, 14} => 2511,
{35, 30} => 1133,
{37, 53} => 32,
{11, 39} => 384,
{131, 5} => 2998,
{65, 43} => 1754,
{139, 46} => 3615,
{12, 135} => 7871,
{65, 131} => 7046,
{49, 117} => 7412,
{29, 25} => 1108,
{83, 36} => 2319,
{47, 27} => 1556,
{4, 81} => 8645,
{13, 124} => 8295,
{121, 77} => 4608,
{103, 39} => 3756,
{119, 60} => 4389,
{13, 85} => 8604,
{63, 81} => 6682,
{111, 108} => 5755,
{111, 103} => 5764,
{15, 92} => 8587,
{1, 101} => 8500,
{20, 3} => 939,
{61, 95} => 6878,
{23, 67} => 9208,
{78, 75} => 6545,
{79, 17} => 2358,
{17, 137} => 7852,
{124, 93} => 4933,
{138, 9} => 3283,
{58, 33} => 1667,
{67, 105} => 6818,
{47, 44} => 1195,
{122, 137} => 5595,
{13, 55} => 154,
{97, 138} => 6129,
{75, ...} => 2165,
{...} => 1616,
...
}Part 1
Enum.reduce(steps, 0, fn {pos, start}, acc ->
count =
steps
|> Map.take(Race.neighbours(pos, 2))
|> Enum.count(fn {last, finish} ->
finish - start - Race.d(pos, last) >= 100
end)
count + acc
end)1393Part 2
We can notice that we are looking for shortcuts in circle of radius $r$ defined in Taxicab metric ($d(a, b) = \sum_{i} |a_i - b_i|$). That makes code pretty simple and allows us to reuse ideas from Part 1.
steps
|> Task.async_stream(
fn {pos, start} ->
steps
|> Map.take(Race.neighbours(pos, 20))
|> Enum.count(fn {last, finish} ->
finish - start - Race.d(pos, last) >= 100
end)
end,
ordered: false
)
|> Enum.reduce(0, fn {:ok, count}, acc ->
count + acc
end)990096