day12.livemd

Hill Climbing Algorithm

Mix.install([
  {:kino, "~> 0.8.0"},
  {:kino_vega_lite, "~> 0.1.7"},
  {:vega_lite, "~> 0.1.6"},
  {:libgraph, "~> 0.16.0"}
])

alias VegaLite, as: Vl
:ok

Input

input = Kino.Input.textarea("Input:")

input =
  Kino.Input.read(input) |> String.trim() |> String.split("\n") |> Enum.map(&String.to_charlist/1)

grid =
  input
  |> Enum.with_index()
  |> Enum.reduce({%{}, nil, nil}, fn {line, row}, acc ->
    line
    |> Enum.with_index()
    |> Enum.reduce(
      acc,
      fn
        {?S, col}, _acc = {map, _s, e} ->
          {Map.put(map, {row, col}, ?a), {row, col}, e}

        {?E, col}, _acc = {map, s, _e} ->
          {Map.put(map, {row, col}, ?z), s, {row, col}}

        {ch, col}, _acc = {map, s, e} ->
          {Map.put(map, {row, col}, ch), s, e}
      end
    )
  end)

{map, start, end_} = grid

graph =
  Enum.reduce(map, Graph.new(type: :directed), fn {{row, col}, height}, graph ->
    graph |> Graph.add_vertex({row, col}, pos: {row, col}, height: height)
  end)

graph =
  Enum.reduce(map, graph, fn {{row, col}, height}, graph ->
    neighbours =
      [{row - 1, col}, {row, col + 1}, {row + 1, col}, {row, col - 1}]
      |> Enum.filter(fn {r, c} ->
        neighbour_height = Map.get(map, {r, c}, nil)
        neighbour_height != nil and neighbour_height <= height + 1
      end)

    edges = for n <- neighbours, do: {{row, col}, n}

    graph |> Graph.add_edges(edges)
  end)

render_graph = fn graph ->
  tmp = Path.join(System.tmp_dir!(), :crypto.strong_rand_bytes(10) |> Base.encode32())

  {:ok, dot} = Graph.to_dot(graph)
  File.write!(tmp <> ".dot", dot)
  {"", 0} = System.cmd("/opt/homebrew/bin/dot", ["-T", "png", tmp <> ".dot", "-o", tmp <> ".png"])

  png_data = File.read!(tmp <> ".png")
  image = Kino.Image.new(png_data, :png)

  # File.rm!(tmp <> ".dot")
  # File.rm!(tmp <> ".png")

  image
end

# render_graph.(graph)

Graph.edges(graph) |> Enum.count()

Graph.vertices(graph) |> Enum.count()

Part 1

shortest = Graph.Pathfinding.dijkstra(graph, start, end_)

length(shortest) - 1

shortest

render_map = fn map, shortest ->
  heights = map |> Enum.map(fn {{row, col}, height} -> %{x: col, y: row, height: height} end)

  path =
    shortest
    |> Enum.map(fn {row, col} ->
      text = [Map.get(map, {row, col})] |> List.to_string()
      %{x: col, y: row, label: text}
    end)

  height_layer =
    Vl.new()
    |> Vl.mark(:rect)
    |> Vl.data(values: heights)
    |> Vl.encode_field(:x, "x")
    |> Vl.encode_field(:y, "y")
    |> Vl.encode_field(:color, "height",
      type: :ordinal,
      legend: nil,
      scale: [scheme: "greens"]
    )

  shortest_layer =
    Vl.new()
    |> Vl.mark(:text)
    |> Vl.data(values: path)
    |> Vl.encode_field(:x, "x")
    |> Vl.encode_field(:y, "y")
    |> Vl.encode_field(:text, "label")

  Vl.new(width: 600, height: 600)
  |> Vl.layers([height_layer, shortest_layer])
end

render_map.(map, shortest)

Part 2

starts =
  Enum.filter(map, fn
    {_, ?a} -> true
    _ -> false
  end)
  |> Enum.map(fn {rc, _} -> rc end)

paths = for start <- starts, do: Graph.Pathfinding.dijkstra(graph, start, end_)
shortest = paths |> Enum.filter(&is_list/1) |> Enum.min_by(&length/1)
length(shortest) - 1