d20

Section

ExUnit.start()

defmodule D20 do
  def parse(input) do
    for {line, row} <- Enum.with_index(String.split(input)),
        {char, col} <- Enum.with_index(String.to_charlist(line)),
        reduce: {MapSet.new(), nil, nil} do
      {walls, start, finish} ->
        case char do
          ?# -> {MapSet.put(walls, {row, col}), start, finish}
          ?S -> {walls, {row, col}, finish}
          ?E -> {walls, start, {row, col}}
          ?. -> {walls, start, finish}
        end
    end
  end

  def neighbors({r, c}, distance \\ 1) do
    for dr <- -distance..distance,
        range = distance - abs(dr),
        dc <- -range..range do
      {r + dr, c + dc}
    end
  end

  def dfs(_, goal, [pos | _] = path) when pos == goal, do: path

  def dfs(walls, goal, path) do
    [next] =
      neighbors(hd(path))
      |> Enum.filter(&amp;(!MapSet.member?(walls, &amp;1) &amp;&amp; !Enum.member?(path, &amp;1)))

    dfs(walls, goal, [next | path])
  end

  def manhattan({ar, ac}, {br, bc}), do: abs(ar - br) + abs(ac - bc)

  def cheats(_, _, _, _, [], _), do: []

  def cheats(walls, ncheats, visited, remaining, [pos | rest], len) do
    for dest <- neighbors(pos, ncheats),
        !MapSet.member?(visited, dest),
        shortcut = Map.get(remaining, dest),
        !is_nil(shortcut) do
      len + manhattan(dest, pos) + shortcut
    end
    |> Enum.concat(cheats(walls, ncheats, MapSet.put(visited, pos), remaining, rest, len + 1))
  end

  def run({walls, start, finish}, ncheats, threshold) do
    path = Enum.reverse(dfs(walls, finish, [start]))

    remaining =
      for {pos, i} <- Enum.with_index(path), into: %{} do
        {pos, length(path) - i}
      end

    cheats(walls, ncheats, MapSet.new(), remaining, path, 0)
    |> Enum.count(&amp;(length(path) - &amp;1 >= threshold))
  end

  def part1(parsed, threshold \\ 100) do
    run(parsed, 2, threshold)
  end

  def part2(parsed, threshold \\ 100) do
    run(parsed, 20, threshold)
  end

  use ExUnit.Case

  test "sample" do
    input = "###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
"
    assert 44 == parse(input) |> run(2, 1)
    assert 285 == parse(input) |> run(20, 50)
  end
end

ExUnit.run()

input = File.read!(__DIR__ <> "/input")
D20.parse(input) |> D20.part1()

D20.parse(input) |> D20.part2()