Day 15

Helpers

defmodule Helpers do
  def data() do
    "data/day15.txt"
    |> File.stream!()
    |> Stream.map(&String.trim/1)
  end
end

defmodule PairingHeap do
  @enforce_keys [:elem]
  defstruct elem: nil, subheaps: []

  def new(), do: :empty
  def new(elem), do: %PairingHeap{elem: elem}
  def new(elem, subheaps), do: %PairingHeap{elem: elem, subheaps: subheaps}

  def empty?(:empty), do: true
  def empty?(_heap), do: false

  def insert(heap, elem) do
    elem
    |> new()
    |> meld(heap)
  end

  def meld(:empty, heap2), do: heap2
  def meld(heap1, :empty), do: heap1

  def meld(heap1 = %PairingHeap{elem: e1}, heap2 = %PairingHeap{elem: e2}) when e1 < e2,
    do: new(e1, [heap2 | heap1.subheaps])

  def meld(heap1 = %PairingHeap{elem: e1}, heap2 = %PairingHeap{elem: e2}) when e1 >= e2,
    do: new(e2, [heap1 | heap2.subheaps])

  def find_min(:empty), do: nil
  def find_min(heap), do: heap.elem

  def delete_min(:empty), do: :empty
  def delete_min(heap), do: merge_pairs(heap.subheaps)

  def pop_min(heap), do: {find_min(heap), delete_min(heap)}

  def merge_pairs([]), do: :empty
  def merge_pairs([heap]), do: heap

  def merge_pairs([heap1, heap2 | heaps]),
    do:
      heap1
      |> meld(heap2)
      |> meld(merge_pairs(heaps))
end

defmodule Cave do
  @enforce_keys [:risk_levels, :width, :height]
  defstruct risk_levels: %{}, width: 0, height: 0, tile_x: 1, tile_y: 1

  def new(risk_levels, width, height, tile_x \\ 1, tile_y \\ 1) do
    %Cave{
      risk_levels: build_risk_levels(risk_levels, width, height),
      width: width,
      height: height,
      tile_x: tile_x,
      tile_y: tile_y
    }
  end

  defp build_risk_levels(risk_levels, width, height) do
    for(x <- 0..(width - 1), y <- 0..(height - 1), do: {x, y})
    |> Enum.zip(risk_levels)
    |> Enum.into(%{})
  end

  defguardp is_in_cave(cave, x, y)
            when x in 0..(cave.width * cave.tile_x - 1) and
                   y in 0..(cave.height * cave.tile_y - 1)

  def neighbours(cave, {x, y}) when not is_in_cave(cave, x, y), do: []

  def neighbours(cave, {x, y}) do
    [
      # north
      {x, y - 1},
      # south
      {x, y + 1},
      # east
      {x + 1, y},
      # west
      {x - 1, y}
    ]
    |> Enum.map(fn coord -> {coord, get(cave, coord)} end)
    |> Enum.filter(fn {{x, y}, _risk_level} -> is_in_cave(cave, x, y) end)
  end

  def get(cave, {x, y}) when not is_in_cave(cave, x, y), do: nil

  def get(cave, {x, y}) do
    actual_x = rem(x, cave.width)
    actual_y = rem(y, cave.height)

    actual_x_tile = div(x, cave.width)
    actual_y_tile = div(y, cave.height)

    risk_level = cave.risk_levels[{actual_x, actual_y}] + actual_x_tile + actual_y_tile
    actual_risk_level = rem(risk_level - 1, 9) + 1

    actual_risk_level
  end

  def shortest_paths(cave, from) do
    q = PairingHeap.new() |> PairingHeap.insert({0, from})
    dist = %{from => 0}
    do_shortest(cave, from, q, dist)
  end

  # ugly imperative -> FP dijkstra  port - needs cleaning up, but works
  defp do_shortest(cave, from, q, dist) do
    if PairingHeap.empty?(q) do
      dist
    else
      {{expected_d, coord}, new_q} = PairingHeap.pop_min(q)
      current_d = dist[coord]

      if current_d == expected_d do
        {new_q, new_dist} =
          cave
          |> neighbours(coord)
          |> Enum.reduce({new_q, dist}, &amp;neighbour_distance(&amp;1, &amp;2, current_d))

        do_shortest(cave, from, new_q, new_dist)
      else
        do_shortest(cave, from, new_q, dist)
      end
    end
  end

  defp neighbour_distance({coord, risk_level}, {q, dist}, current_d) do
    alt = current_d + risk_level

    if alt < Map.get(dist, coord, :infinity) do
      {
        PairingHeap.insert(q, {alt, coord}),
        Map.put(dist, coord, alt)
      }
    else
      {q, dist}
    end
  end
end

Part 1

import Helpers

width = 100
height = 100

cave =
  data()
  |> Stream.flat_map(&String.graphemes/1)
  |> Stream.map(&String.to_integer/1)
  |> Enum.to_list()
  |> Cave.new(width, height)

top_left = {0, 0}
bottom_right = {width - 1, height - 1}
shortest_dist = cave |> Cave.shortest_paths(top_left)
shortest_dist[bottom_right]

Part 2

import Helpers

width = 100
height = 100
tile_x = 5
tile_y = 5

cave =
  data()
  |> Stream.flat_map(&String.graphemes/1)
  |> Stream.map(&String.to_integer/1)
  |> Enum.to_list()
  |> Cave.new(width, height, tile_x, tile_y)

top_left = {0, 0}
bottom_right = {width * tile_x - 1, height * tile_y - 1}
shortest_dist = cave |> Cave.shortest_paths(top_left)
shortest_dist[bottom_right]