Advent of Code 2024

aoc_helpers_path =
  __ENV__.file
  |> String.split("#")
  |> hd()
  |> Path.dirname()
  |> then(fn dir ->
    [dir, "..", "aoc_helpers"]
  end)
  |> Path.join()

Mix.install([
  {:aoc_helpers, path: aoc_helpers_path}
])

Day 20

import AocHelpers

Kino.configure(inspect: [charlists: :as_lists])

input = download_puzzle(2024, 20, cookie: System.get_env("AOC_COOKIE"))

sample = """
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
"""

Kino.nothing()

defmodule Day20 do
  def parse(input) do
    input
    |> grid()
  end

  def find_path(grid) do
    s = find_pos(grid, "S")

    find_path(grid, s, MapSet.new(), [])
  end

  def find_path(grid, pos, seen, path) do
    path = [pos | path]
    seen = MapSet.put(seen, pos)

    if Map.get(grid, pos) == "E" do
      path
    else
      next =
        neighbours(pos)
        |> Enum.filter(&(Map.get(grid, &1) in ["E", "."] && !MapSet.member?(seen, &1)))
        |> hd()

      find_path(grid, next, seen, path)
    end
  end

  def best_cheats(input, t, cutoff) do
    {grid, _w, _h} =
      input
      |> parse()

    # there is only one path
    path = find_path(grid)
    n = (Enum.count(path) - 1)

    # steps from a given cell to the end
    # ie. we can cheat and know how many steps are left without taking them
    memo =
      path
      |> Enum.with_index()
      |> Enum.into(Map.new())

    path
    |> Enum.flat_map(fn start ->
      start
      |> neighbours(t)
      |> Enum.filter(&Map.has_key?(memo, &1))
      |> Enum.map(&{start, &1, manhattan_dist(start, &1)})
    end)
    |> Enum.map(fn {a, b, d} ->
      t = n - Map.get(memo, a) + Map.get(memo, b) + d
      n - t
    end)
    |> Enum.filter(&(&1 >= cutoff))
    # |> Enum.frequencies()
    # |> Enum.sort_by(fn {k, _v} -> k end)
    |> Enum.count()
  end
end

import Day20

Part 1

input
|> best_cheats(2, 100)

Part 2

input
|> best_cheats(20, 100)