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 1_000_000_000_000 # must match value in AOC module!
  @cost 1
  @wall_cell "#"
  @straight_cost 1
  @turn_cost 1_001 # turn + straight_cost
  
  def find_spot(grid, value) do
    AOC.grid_cells(grid)
    |> Enum.find(fn cell -> grid[cell] == value end)
  end

  # These are special versions that re-calculate "future" nodes after a smaller
  # cost is found for an already-calculated node.
  def shortest_path(_grid, [], _node_map, _cost_function, _finish), do: "WTF?"
  def shortest_path(grid, latest_nodes, node_map, cost_function, finish) do
    # AdventOfCode.inspect([latest_nodes, finish], label: "-----")
    {updated_node_map, neighbor_nodes} =
      latest_nodes
      |> Enum.reduce({node_map, MapSet.new()}, fn node, {map, set} ->
        # Do not create a path *beyond* the finish
        unvisited_neighbors = if node == finish do
            []
          else
            grid
            |> AOC.neighbors4(node)
            |> Enum.filter(fn neighbor ->
              neighbor in Map.keys(node_map) && node_map[neighbor].cost > node_map[node].cost
            end)
          end

        unvisited_neighbors
        |> Enum.reduce({map, set}, fn neighbor, {map1, set1} ->
          {cost_function.(map1, node, neighbor), MapSet.put(set1, neighbor)}
        end)
      end)
#     |> IO.inspect(label: "{updated_node_map, neighbor_nodes}")

    future_neighbors = MapSet.to_list(neighbor_nodes)
      # |> Enum.sort()
      # |> Enum.reverse()

#    if updated_node_map[finish].path == [] do
    if future_neighbors != [] do
      shortest_path(grid, future_neighbors, updated_node_map, cost_function, finish)
    else
      updated_node_map
    end
  end

  def shortest_path(grid, start, finish) do
    # Step 1: Find the unvisited set.
    node_map =
      Enum.reject(AOC.grid_cells(grid), fn k -> grid[k] == @wall_cell end)
      # Step 2: Assign distances to unvisited nodes. The start node will get a 0 distance.
      |> Enum.reduce(%{}, fn index, acc ->
        if index == start do
          Map.put(acc, index, %{cost: 0, path: [start]})
        else
          # Note: an empty path list means it is un-visited
          Map.put(acc, index, %{cost: @infinity, path: []})
        end
      end)

    # |> inspect(label: "node_map")

    cost_function = fn map, a, b ->
      # This handles Step 3 and Step 4: update path and distance from neighbors.
      cost_from_a = map[a].cost + @cost

      if map[b].cost < cost_from_a do
        # Nothing to do - the node already has the lower cost & path
        map
      else
        Map.put(map, b, %{cost: cost_from_a, path: map[a].path ++ [b]})
      end
    end

    shortest_path(grid, [start], node_map, cost_function, finish)
  end

  def solve1(text) do
    maze = AOC.as_maze(text)
    start = maze[:S]
    finish = maze[:E]
    direction = "E"

    # Step 1: Find the unvisited set.
    node_map = AOC.grid_cells(maze)
               # Step 2: Assign distances to unvisited nodes. The start node will get a 0 distance.
               |> Enum.reduce(maze, fn index, acc ->
      if index == start do
        Map.put(acc, index, %{cost: 0, path: [start], direction: direction})
      else
        # Note: an empty path list means it is un-visited
        Map.put(acc, index, %{cost: @infinity, path: [], direction: direction})
      end
    end)
    # AOC.display_grid(maze)

    cost_function = fn map, a, b ->
      if finish in [a, b], do: AOC.inspect([a, b, map[a], map[b]])
      
      # IO.puts("cost_function #{a} -> #{b}")
      # This handles Step 3 and Step 4: update path and distance from neighbors.
      # NOTE: only track east-west direction ("E") or north-south ("N")
      direction = (abs(a - b) == 1) &amp;&amp; "E" || "N"
      direction_cost = (direction == map[a].direction) &amp;&amp; @straight_cost || @turn_cost
      cost_from_a = map[a].cost + direction_cost
      # AOC.inspect([direction, a, b, map[a].cost, direction_cost, cost_from_a])
      if map[a].cost >= @infinity, do: raise("oops")
      if map[b].cost <= cost_from_a do
        if b == finish do
          AOC.inspect([cost_from_a, a, b, map[a], map[b]], label: "at finish")
        end
        # Nothing to do - the node already has the lower cost & path
        map
      else
        Map.put(map, b, %{cost: cost_from_a, path: map[a].path ++ [b], direction: direction})
      end
    end
    updated_node_map = shortest_path(maze, [start], node_map, cost_function, finish)
    %{path: _finish_path, cost: _finish_cost} = updated_node_map[finish]
    
  end

  # def solve2(text) do
  #   parse(text)
  # end
end

# Example:

data.()
|> Day16.solve1()
|> IO.inspect(label: "\n*** Part 1 solution (example: 11048)")
# 135512

###########
#........E#
#.#.#.###.#
#S..#...#.#
###########