Day 16
# Note: when making the next template, something like this works well:
# `cat day04.livemd | sed 's/16/04/' > day04.livemd`
# When inspecting lists of numbers, use "charlists: :as_lists"
#
Mix.install([
# Join the string so a copy of dayN to dayM doesn't destroy it.
{:kino, "~> 0.1" <> "4.2"}
])
# Join the string so a copy of dayN to dayM doesn't destroy it.
IEx.Helpers.c("/Users/johnb/dev/2" <> "0" <> "2" <> "4adventOfCode/advent_of_code.ex")
alias AdventOfCode, as: AOC
alias Kino.Input
Installation and Data
input_example = Kino.Input.textarea("Example Data", monospace: true)
input_puzzleInput = Kino.Input.textarea("Puzzle Input", monospace: true)
input_source_select =
Kino.Input.select("Source", [{:example, "example"}, {:puzzle_input, "puzzle input"}])
data = fn ->
(Kino.Input.read(input_source_select) == :example &&
Kino.Input.read(input_example)) ||
Kino.Input.read(input_puzzleInput)
end
Solution
defmodule Day16 do
@infinity 10_000_000
@wall "#"
# @floor "."
def parse(text) do
text
|> AOC.as_grid()
end
def find_spot(grid, value) do
AOC.grid_cells(grid)
|> Enum.find(fn cell -> grid[cell] == value end)
end
def score_path(path) do
[start, next] = Enum.slice(path, 0..1)
start_score = (next == start + 1) && 0 || 1000
finish_score = 0 # we don't care what direction they face
path_score = Enum.count(path) - 1
# AOC.inspect([start_score, finish_score, path_score])
path
|> Enum.chunk_every(3, 1, :discard)
|> Enum.reduce(start_score + finish_score + path_score, fn [a,b,c], acc ->
acc + (((a + c) / 2 == b) && 0 || 1000)
end)
end
def find_paths(_grid, finish, finish, path) do
path
# |> AOC.inspect(label: "complete!")
|> score_path()
# |> AOC.inspect(label: "score")
end
def find_paths(grid, start, finish, path) do
# AOC.inspect([start, finish, path])
n4 = AOC.neighbors4(grid, start)
|> Enum.reject(fn cell -> cell in path end)
|> Enum.reject(fn cell -> grid[cell] == @wall end)
# |> AOC.inspect(label: "n4")
if n4 == [] do
:blocked
else
n4
|> Enum.map(fn cell ->
find_paths(grid, cell, finish, path ++ [cell])
end)
|> Enum.reject(fn list -> list in [nil, [], :blocked] end)
end
end
def flatter([first | _rest] = path) when is_integer(first), do: path
def flatter([[path]]), do: flatter(path)
# Dijkstra's Algorithm - first attempt
# def calculate_cost_to_unvisited_neighbors(grid, costs, unvisited) do
# 1..Enum.count(unvisited)
# |> Enum.reduce_while(costs, fn step, acc ->
# visited_cells = Map.keys(acc)
# cells_with_unvisited_neighbors = visited_cells
# |> Enum.reduce(%{}, fn cell, acc1 ->
# unvisited_neighbors = AOC.neighbors4(grid, cell)
# |> Enum.reject(fn neighbor -> neighbor in visited_cells end)
# if unvisited_neighbors == [] do
# acc1
# else
# put_in(acc1, [cell], unvisited_neighbors)
# end
# end)
# cells_with_unvisited_neighbors
# |> Enum.reduce(acc, fn {cell1, neighbors}, acc1 ->
# Enum.reduce(neighbors, fn neighbor, acc2 ->
# {cost, delta} = acc1[cell1].cost +
# if abs(neighbor - cell) == acc1[cell].delta do
# {1, acc2[cell].delta}
# else
# {1000, abs(neighbor - cell)}
# end
# get_and_update_in(acc2, [neighbor], fn previous_cost ->
# if is_nil(previous_cost) || previous_cost > cost do
# {previous_cost, cost}
# else
# {previous_cost, previous_cost}
# end
# end)
# end)
# end)
# |> AOC.inspect(label: "#{step}")
# end)
# end
def dijkstra(_grid, [], cells, _cells_to_check), do: {cells}
def dijkstra(grid, unvisited, cells, cells_to_check) do
Enum.reduce(cells_to_check, {unvisited, cells, cells_to_check},
fn cell, {unvisited1, cells1, cells_to_check1} ->
n4 = AOC.neighbors4(grid, cell)
|> Enum.reject(fn cell1 -> grid[cell1] == @wall end)
|> Enum.filter(fn cell1 -> cell1 in unvisited1 end)
if n4 == [] do
{unvisited1, cells1, cells_to_check1}
else
Enum.reduce(n4, {unvisited1, cells1, cells_to_check1},
fn neighbor, {_unvisited2, cells2, _cells_to_check2} ->
{cost, ddelta} = if abs(neighbor - cell) == cells[cell].delta do
{1, cells[cell].delta}
else
{1000, abs(neighbor - cell)}
end
get_and_update_in(cells2, [neighbor],
fn %{cost: pcost, delta: _pdelta} = previous_cost ->
if pcost > cost do
{previous_cost, %{cost: cost, delta: ddelta}}
else
{previous_cost, previous_cost}
end
end)
end)
end
end)
end
def solve1(text) do
grid = parse(text)
start = find_spot(grid, "S")
finish = find_spot(grid, "E")
AOC.inspect([start, finish], label: "start & finish")
# per https://en.wikipedia.org/wiki/Dijkstra's_algorithm#Algorithm
nodes = AOC.grid_cells(grid)
|> Enum.filter(fn cell -> grid[cell] != @wall end)
|> Enum.reduce(%{}, fn cell, acc ->
put_in(acc, [cell], %{cost: @infinity, delta: 1}) # 1 == East/West
end)
|> put_in([start, :cost], 0)
unvisited = Map.keys(nodes) -- [start]
dijkstra(grid, unvisited, nodes, [start])
unvisited = unvisited -- [start]
AOC.inspect(Enum.count(unvisited))
AOC.inspect(unvisited)
# costs = %{start => %{cost: 0, delta: 1}} # delta tells us direction
# costs = calculate_cost_to_unvisited_neighbors(grid, costs, unvisited, now)
# costs[finish]
end
def solve2(text) do
parse(text)
end
end
# Example:
data.()
|> Day16.solve1()
|> IO.inspect(label: "\n*** Part 1 solution (example: 11048)")
#
# data.()
# |> Day16.solve2()
# |> IO.inspect(label: "\n*** Part 2 solution (example: )")
#