Advent of Code - Day 15: Chiton
Mix.install([:kino])Day 15: Chiton
Part One: Prompt
You've almost reached the exit of the cave, but the walls are getting closer together. Your submarine can barely still fit, though; the main problem is that the walls of the cave are covered in chitons, and it would be best not to bump any of them.
The cavern is large, but has a very low ceiling, restricting your motion to two dimensions. The shape of the cavern resembles a square; a quick scan of chiton density produces a map of risk level throughout the cave (your puzzle input). For example:
1163751742
1381373672
2136511328
3694931569
7463417111
1319128137
1359912421
3125421639
1293138521
2311944581
You start in the top left position, your destination is the bottom right position, and you cannot move diagonally. The number at each position is its risk level; to determine the total risk of an entire path, add up the risk levels of each position you enter (that is, don't count the risk level of your starting position unless you enter it; leaving it adds no risk to your total).
Your goal is to find a path with the lowest total risk. In this example, a path with the lowest total risk is highlighted here:
1---------
1---------
2136511---
------15--
-------1--
-------13-
--------2-
--------3-
--------21
---------1
The total risk of this path is 40 (the starting position is never entered, so its risk is not counted).
What is the lowest total risk of any path from the top left to the bottom right?
To begin, get your puzzle input.
Part One: Solution
input = Kino.Input.textarea("Please paste your input file:")lines = input |> Kino.Input.read() |> String.split("\n", trim: true)["6489887186259823155119378351872148719812918213519649577918412241959623221389974192429139298912991367",
"3859891261917894749518659872199265294116953513169391165342899913878588561865553734597561693917577259",
"7821697449796196228941887781377133998193483644892699199569294366179448944296919898443894894653982299",
"4521784638899152252884535888651941499199556787174181866459996191939865591888468793671399848719386874",
"9191996931799877154649198443239834219617959491499995891819688991189512152374148611392199689771321748",
"3667131999966376698925485914885119653598637984789199249717987982323518981692239229913697228977769187",
"5913911179874379588135157927159887689932919711124715316555782223929991889593659797141392198858861889",
"8889299854191893897698362569935143896411522526753243281794876746461747369943293918696398639953911511",
"6463567347538215129956611194361438953389822419896312246999991693527638996861829479689711567997995192",
"4969812254996785971152245859891328871698554194613499811274874939279976912834954128868111913733497634",
"8715226296411979999175491771891518398174152999617899176858298421743955979312992148338161118133772495",
"7989997198451591732186779418728991818771799995794999176147971519698195299959679496494381395415153939",
"7282692814783299921331798173611516298898794899725789859192132379219117118492499969761658218929927864",
"1342992871132334679195998919715589998911217792694649176999976859878194946915717791192969628795921896",
"1198594318116525819324277961659629619194282188583741151135327827985988397249852849998274177979884659",
"2948759488457996218881696122961499228919527561398512991239279917671118964912157265623911892599513341",
"1721619411197179647114339866313852894794263785891972697189216816957987796466513815441999997333837393",
"3375834591789764977977935817192389195669288849247457436183299942397325166499195293613453415691119331",
"3383251379988789959621411392916296699995912197528691115352699418473557811621889429574876824981465367",
"3946625971993126978662721165287737699957111997461919135155999927868159654568599845934641519931184857",
"1814219784816784397613259195177424337829849136888218979928947895987954996239299692997891322152598969",
"9167118929432986369621459985116955896895789531924573998849117693222897796967477579879164869645691987",
"9993931541269456449491677911123286988879389825977278399128481297719892848811719696399852796988151918",
"9893884365787225284723759349718218236629959279191199596535127988933911516948618826618861995591558212",
"9984997699594184215439998946186347579842727156615585749955918144359797292171113989999655891195231226",
"6519569284634811452859581242533679729318722199188497578918759345212444219469537986694271952662894183",
"1673153584676797169319899939187899839683837996566397291171477988821999223881914917719626289955111858",
"7146537276973579271975991138698798718183139181834274738682599352532928589621298131971429319935464919",
"2911336366179694233796282699294517727951719996114927296729974248127291213748482125674817329679322278",
"4798699184439539972938181916719984885811953923118182789714537319491196255791897212198915189411912489",
"7852118738919181535168449598885759915381876297123897699578914948274581139887226879962581681998894469",
"2918667954587166379414138982984796566391888998953829743959158938492499153199913868516322211627813911",
"1911191198236791992999514989515915961526982494489934936648985927464538438395828491299233338941422537",
"9861519197351334579955861514693812489919794188373831563893523762239644661783993119958349691911885978",
"1741796188248628177931939945714851283262278358937917679382912284585329923948919181599981922219159783",
"1918269993688698189196826775213217961928471115358414161749125718999932737938991944829186798198969188",
"6335968599954929332975183965197971948118259199311892138919168279994983228145986116959153969714994791",
"2294996932925629138737697471187317259977389438529157681417294638795539161967894892297711499619598914",
"8621919128831831818711188658183498495415179256744899519992376961651631159967999793957467811269819598",
"3486228927949465647719757181978926928894916813256577694958591299649458467861486232122397593137169986",
"9195326888839115399949459765722899699729351261768612954948887622916193153198249712582629784163892915",
"4946191927925146992288978981127654497969526715961851746313929219282191751297476541666118492999823964",
"6687919199698953659176799913987999589192872822569891946679824579135968776766721961199575772548589916",
"4134837613838699992499794185936511677831523879464926397999598699218495659219951997241941199797561898",
"6261448956192268429191952813481184164439771317735498973672159429878683873947826158193518449579369192",
"9968869557217691155988975292999388917423624394882599979257399494723919317766653218239966399782187116",
"9966829587494189799987695999513479929199725278387418789286142795498925915831139896844459884251964868",
"5396855967999263847161618545818977839821986999731717195938618127272182989829788669792191979169842532",
"7411292996999993111239118429943655151416518359136297412488899595883341818989997121211198297187911377",
"9196629191657399132973598379658919935439429224971517198796197371799969145169368359376974781195691986",
...]
max_x = lines |> List.first() |> String.length()
max_y = lines |> length()100
grid =
lines
|> Enum.with_index(1)
|> Enum.reduce(%{}, fn {row, y}, acc ->
row
|> String.split("", trim: true)
|> Enum.with_index(1)
|> Enum.into(acc, fn {col, x} -> {{x, y}, String.to_integer(col)} end)
end)
{max_x, max_y} = max_point = Enum.max(Map.keys(grid)){100, 100}
As we navigate, let's keep track of each point we've come to, and what the smallest total (and path taken) was to get to that point.
If we're ever on a path that comes to a point that has already been seen by a smaller total, let's drop the path we're on.
defmodule Queue do
def add([{lowest_weight, _} | _] = queue, xy, weight) when weight <= lowest_weight do
[{weight, xy} | queue]
end
def add([head | tail], xy, weight) do
[head | add(tail, xy, weight)]
end
def add([], xy, weight) do
[{weight, xy}]
end
end
defmodule Grid do
def print(grid) do
{max_x, max_y} = Enum.max(Map.keys(grid))
for y <- 1..max_y do
1..max_x
|> Enum.map(fn x -> Map.get(grid, {x, y}) end)
|> Enum.join()
|> IO.puts()
end
nil
end
end
defmodule Mover do
def navigate({map, queue}, grid) do
if Enum.empty?(queue), do: map, else: do_navigate({map, queue}, grid)
end
defp do_navigate({map, [{_, point} | queue]}, grid) do
{map, queue}
|> move(grid, point, :up)
|> move(grid, point, :down)
|> move(grid, point, :left)
|> move(grid, point, :right)
|> navigate(grid)
end
defp move({%{min: {_, y}} = map, queue}, _, {_, y}, :up), do: {map, queue}
defp move({%{max: {_, y}} = map, queue}, _, {_, y}, :down), do: {map, queue}
defp move({%{min: {x, _}} = map, queue}, _, {x, _}, :left), do: {map, queue}
defp move({%{max: {x, _}} = map, queue}, _, {x, _}, :right), do: {map, queue}
defp move({map, queue}, grid, point, direction) do
new_point = next_point(point, direction)
sum = Map.get(map, point) + Map.get(grid, new_point)
do_move({map, queue}, new_point, sum, Map.get(map, new_point))
end
defp do_move({map, queue}, point, sum, old_sum) when is_nil(old_sum) or old_sum > sum do
{
Map.put(map, point, sum),
Queue.add(queue, point, sum)
}
end
defp do_move(map, _, _, _), do: map
defp next_point({x, y}, :up), do: {x, y - 1}
defp next_point({x, y}, :down), do: {x, y + 1}
defp next_point({x, y}, :left), do: {x - 1, y}
defp next_point({x, y}, :right), do: {x + 1, y}
end{:module, Mover, <<70, 79, 82, 49, 0, 0, 14, ...>>, {:next_point, 2}}
map = %{
:min => {1, 1},
:max => max_point,
{1, 1} => 0
}
queue = Queue.add([], {1, 1}, 0)
{map, queue}
|> Mover.navigate(grid)
|> Map.get(max_point)609
What is the lowest total risk of any path from the top left to the bottom right?
Your puzzle answer was 609.
The first half of this puzzle is complete! It provides one gold star: *
Part Two: Prompt
Now that you know how to find low-risk paths in the cave, you can try to find your way out.
The entire cave is actually five times larger in both dimensions than you thought; the area you originally scanned is just one tile in a 5x5 tile area that forms the full map. Your original map tile repeats to the right and downward; each time the tile repeats to the right or downward, all of its risk levels are 1 higher than the tile immediately up or left of it. However, risk levels above 9 wrap back around to 1. So, if your original map had some position with a risk level of 8, then that same position on each of the 25 total tiles would be as follows:
8 9 1 2 3
9 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
Each single digit above corresponds to the example position with a value of 8 on the top-left tile. Because the full map is actually five times larger in both dimensions, that position appears a total of 25 times, once in each duplicated tile, with the values shown above.
Equipped with the full map, you can now find a path from the top left corner to the bottom right corner with the lowest total risk.
Using the full map, what is the lowest total risk of any path from the top left to the bottom right?
Part Two: Solution
# Increment grid 5 times in each direction
new_value = fn value, incr ->
case rem(value + incr, 9) do
0 -> 9
r -> r
end
end
big_grid =
Enum.reduce(grid, %{}, fn
{{x, y}, value}, big_grid ->
for x_inc <- 0..4, y_inc <- 0..4, reduce: big_grid do
acc ->
Map.put(
acc,
{x + max_x * x_inc, y + max_y * y_inc},
new_value.(value, x_inc + y_inc)
)
end
end)
{big_max_x, big_max_y} = max_point = Enum.max(Map.keys(big_grid)){500, 500}
# Grid.print(big_grid)nil
map = %{
:min => {1, 1},
:max => max_point,
{1, 1} => 0
}
queue = Queue.add([], {1, 1}, 0)
{map, queue}
|> Mover.navigate(big_grid)
|> Map.get(max_point)2925
Using the full map, what is the lowest total risk of any path from the top left to the bottom right?
Your puzzle answer was 2925.
Both parts of this puzzle are complete! They provide two gold stars: **
At this point, you should return to your Advent calendar and try another puzzle.
If you still want to see it, you can get your puzzle input.
