Powered by AppSignal & Oban Pro
Would you like to see your link here? Contact us

Day 16

day16.livemd

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 &amp;&amp;
     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) &amp;&amp; 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) &amp;&amp; 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: )")
#