import {
  add,
  distance,
  eq,
  find,
  grid,
  HashMap,
  inputDay,
  range,
} from "./lib/utilities.js"

Array(15) [Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15), Array(15)]

const test = grid(`###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
`)
display(test)

const input = await inputDay(20, { parser: grid })

const NN = [-2, 0]
const N = [-1, 0]
const NE = [-1, 1]
const E = [0, 1]
const EE = [0, 2]
const SE = [1, 1]
const S = [1, 0]
const SS = [2, 0]
const SW = [1, -1]
const W = [0, -1]
const WW = [0, -2]
const NW = [-1, -1]
const WALL = "#"
const FLOOR = "."
const END = "E"

part 1

I already have a function to do a search through a maze and show me the cost to the end from any point along the path, so the important insight is that the savings of any cheat is the difference between the cost of the point we start the cheat from and the end.

That means that we only need to do pathfinding once, then for every point on the path, find every cheat, and check its value.

Let's start with a function to find every valid cheat from one given point on a map

/* for every possible direction of a 2-ps cheat, return the point if it is
 * valid */
function findCheats(map, pt) {
  return [NN, N, NE, E, EE, SE, S, SS, SW, W, WW, NW]
    .map(d => add(pt, d))
    .filter(([y, x]) => [FLOOR, END].includes(map[y]?.[x]))
}

Now do pathfinding on the map, and for each point on the path get every cheat. For every cheat, add one to the number of valid cheats if the difference in cost is greater than the threshold.

I've elided the search function because it's exactly the same as day 18's

function race(map, cheatF = findCheats, threshold = 99, debug = false) {
  const start = find(map, "S")
  const end = find(map, "E")
  const [cost, cameFrom] = search(map, start, end, debug)
  let sum = 0
  for (const [pt] of cameFrom) {
    const [y, x] = pt.split(",").map(Number)
    if (eq([y, x], end)) continue
    sum += cheatF(map, [y, x], 2)
      .map(
        ([yy, xx]) =>
          cost.get([yy, xx]) - cost.get([y, x]) - distance([y, x], [yy, xx]),
      )
      .filter(x => x > threshold).length
  }
  return sum
}

display(race(test, findCheats, 12, true))
display(race(input, findCheats, 99, true))

part 2

I generated each valid possible cheat vector with this code, and saved it to lib/day20points.js

"[[-20,0],[-19,-1],[-19,0],[-19,1],[-18,-2],[-18,-1],[-18,0],[-18,1],[-18,2],[-17,-3],[-17,-2],[-17,-1],[-17,0],[-17,1],[-17,2],[-17,3],[-16,-4],[-16,-3],[-16,-2],[-16,-1],[-16,0],[-16,1],[-16,2],[-16,3],[-16,4],[-15,-5],[-15,-4],[-15,-3],[-15,-2],[-15,-1],[-15,0],[-15,1],[-15,2],[-15,3],[-15,4],[-15,5],[-14,-6],[-14,-5],[-14,-4],[-14,-3],[-14,-2],[-14,-1],[-14,0],[-14,1],[-14,2],[-14,3],[-14,4],[-14,5],[-14,6],[-13,-7],[-13,-6],[-13,-5],[-13,-4],[-13,-3],[-13,-2],[-13,-1],[-13,0],[-13,1],[-13,2],[-13,3],[-13,4],[-13,5],[-13,6],[-13,7],[-12,-8],[-12,-7],[-12,-6],[-12,-5],[-12,-4],[-12,-3],[-12,-2],[-12,-1],[-12,0],[-12,1],[-12,2],[-12,3],[-12,4],[-12,5],[-12,6],[-12,7],[-12,8],[-11,-9],[-11,-8],[-11,-7],[-11,-6],[-11,-5],[-11,-4],[-11,-3],[-11,-2],[-11,-1],[-11,0],[-11,1],[-11,2],[-11,3],[-11,4],[-11,5],[-11,6],[-11,7],[-11,8],[-11,9],[-10,-10],[-10,-9],[-10,-8],[-10,-7],[-10,-6],[-10,-5],[-10,-4],[-10,-3],[-10,-2],[-10,-1],[-10,0],[-10,1],[-10,2],[-10,3],[-10,4],[-10,5],[-10,6],[-10,7],[-10,8],[-10,9],[-10,10],[-9,-11],[-9,-10],[-9,-9],[-9,-8],[-9,-7],[-9,-6],[-9,-5],[-9,-4],[-9,-3],[-9,-2],[-9,-1],[-9,0],[-9,1],[-9,2],[-9,3],[-9,4],[-9,5],[-9,6],[-9,7],[-9,8],[-9,9],[-9,10],[-9,11],[-8,-12],[-8,-11],[-8,-10],[-8,-9],[-8,-8],[-8,-7],[-8,-6],[-8,-5],[-8,-4],[-8,-3],[-8,-2],[-8,-1],[-8,0],[-8,1],[-8,2],[-8,3],[-8,4],[-8,5],[-8,6],[-8,7],[-8,8],[-8,9],[-8,10],[-8,11],[-8,12],[-7,-13],[-7,-12],[-7,-11],[-7,-10],[-7,-9],[-7,-8],[-7,-7],[-7,-6],[-7,-5],[-7,-4],[-7,-3],[-7,-2],[-7,-1],[-7,0],[-7,1],[-7,2],[-7,3],[-7,4],[-7,5],[-7,6],[-7,7],[-7,8],[-7,9],[-7,10],[-7,11],[-7,12],[-7,13],[-6,-14],[-6,-13],[-6,-12],[-6,-11],[-6,-10],[-6,-9],[-6,-8],[-6,-7],[-6,-6],[-6,-5],[-6,-4],[-6,-3],[-6,-2],[-6,-1],[-6,0],[-6,1],[-6,2],[-6,3],[-6,4],[-6,5],[-6,6],[-6,7],[-6,8],[-6,9],[-6,10],[-6,11],[-6,12],[-6,13],[-6,14],[-5,-15],[-5,-14],[-5,-13],[-5,-12],[-5,-11],[-5,-10],[-5,-9],[-5,-8],[-5,-7],[-5,-6],[-5,-5],[-5,-4],[-5,-3],[-5,-2],[-5,-1],[-5,0],[-5,1],[-5,2],[-5,3],[-5,4],[-5,5],[-5,6],[-5,7],[-5,8],[-5,9],[-5,10],[-5,11],[-5,12],[-5,13],[-5,14],[-5,15],[-4,-16],[-4,-15],[-4,-14],[-4,-13],[-4,-12],[-4,-11],[-4,-10],[-4,-9],[-4,-8],[-4,-7],[-4,-6],[-4,-5],[-4,-4],[-4,-3],[-4,-2],[-4,-1],[-4,0],[-4,1],[-4,2],[-4,3],[-4,4],[-4,5],[-4,6],[-4,7],[-4,8],[-4,9],[-4,10],[-4,11],[-4,12],[-4,13],[-4,14],[-4,15],[-4,16],[-3,-17],[-3,-16],[-3,-15],[-3,-14],[-3,-13],[-3,-12],[-3,-11],[-3,-10],[-3,-9],[-3,-8],[-3,-7],[-3,-6],[-3,-5],[-3,-4],[-3,-3],[-3,-2],[-3,-1],[-3,0],[-3,1],[-3,2],[-3,3],[-3,4],[-3,5],[-3,6],[-3,7],[-3,8],[-3,9],[-3,10],[-3,11],[-3,12],[-3,13],[-3,14],[-3,15],[-3,16],[-3,17],[-2,-18],[-2,-17],[-2,-16],[-2,-15],[-2,-14],[-2,-13],[-2,-12],[-2,-11],[-2,-10],[-2,-9],[-2,-8],[-2,-7],[-2,-6],[-2,-5],[-2,-4],[-2,-3],[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-2,3],[-2,4],[-2,5],[-2,6],[-2,7],[-2,8],[-2,9],[-2,10],[-2,11],[-2,12],[-2,13],[-2,14],[-2,15],[-2,16],[-2,17],[-2,18],[-1,-19],[-1,-18],[-1,-17],[-1,-16],[-1,-15],[-1,-14],[-1,-13],[-1,-12],[-1,-11],[-1,-10],[-1,-9],[-1,-8],[-1,-7],[-1,-6],[-1,-5],[-1,-4],[-1,-3],[-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],[-1,3],[-1,4],[-1,5],[-1,6],[-1,7],[-1,8],[-1,9],[-1,10],[-1,11],[-1,12],[-1,13],[-1,14],[-1,15],[-1,16],[-1,17],[-1,18],[-1,19],[0,-20],[0,-19],[0,-18],[0,-17],[0,-16],[0,-15],[0,-14],[0,-13],[0,-12],[0,-11],[0,-10],[0,-9],[0,-8],[0,-7],[0,-6],[0,-5],[0,-4],[0,-3],[0,-2],[0,-1],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[1,-19],[1,-18],[1,-17],[1,-16],[1,-15],[1,-14],[1,-13],[1,-12],[1,-11],[1,-10],[1,-9],[1,-8],[1,-7],[1,-6],[1,-5],[1,-4],[1,-3],[1,-2],[1,-1],[1,0],[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],[1,8],[1,9],[1,10],[1,11],[1,12],[1,13],[1,14],[1,15],[1,16],[1,17],[1,18],[1,19],[2,-18],[2,-17],[2,-16],[2,-15],[2,-14],[2,-13],[2,-12],[2,-11],[2,-10],[2,-9],[2,-8],[2,-7],[2,-6],[2,-5],[2,-4],[2,-3],[2,-2],[2,-1],[2,0],[2,1],[2,2],[2,3],[2,4],[2,5],[2,6],[2,7],[2,8],[2,9],[2,10],[2,11],[2,12],[2,13],[2,14],[2,15],[2,16],[2,17],[2,18],[3,-17],[3,-16],[3,-15],[3,-14],[3,-13],[3,-12],[3,-11],[3,-10],[3,-9],[3,-8],[3,-7],[3,-6],[3,-5],[3,-4],[3,-3],[3,-2],[3,-1],[3,0],[3,1],[3,2],[3,3],[3,4],[3,5],[3,6],[3,7],[3,8],[3,9],[3,10],[3,11],[3,12],[3,13],[3,14],[3,15],[3,16],[3,17],[4,-16],[4,-15],[4,-14],[4,-13],[4,-12],[4,-11],[4,-10],[4,-9],[4,-8],[4,-7],[4,-6],[4,-5],[4,-4],[4,-3],[4,-2],[4,-1],[4,0],[4,1],[4,2],[4,3],[4,4],[4,5],[4,6],[4,7],[4,8],[4,9],[4,10],[4,11],[4,12],[4,13],[4,14],[4,15],[4,16],[5,-15],[5,-14],[5,-13],[5,-12],[5,-11],[5,-10],[5,-9],[5,-8],[5,-7],[5,-6],[5,-5],[5,-4],[5,-3],[5,-2],[5,-1],[5,0],[5,1],[5,2],[5,3],[5,4],[5,5],[5,6],[5,7],[5,8],[5,9],[5,10],[5,11],[5,12],[5,13],[5,14],[5,15],[6,-14],[6,-13],[6,-12],[6,-11],[6,-10],[6,-9],[6,-8],[6,-7],[6,-6],[6,-5],[6,-4],[6,-3],[6,-2],[6,-1],[6,0],[6,1],[6,2],[6,3],[6,4],[6,5],[6,6],[6,7],[6,8],[6,9],[6,10],[6,11],[6,12],[6,13],[6,14],[7,-13],[7,-12],[7,-11],[7,-10],[7,-9],[7,-8],[7,-7],[7,-6],[7,-5],[7,-4],[7,-3],[7,-2],[7,-1],[7,0],[7,1],[7,2],[7,3],[7,4],[7,5],[7,6],[7,7],[7,8],[7,9],[7,10],[7,11],[7,12],[7,13],[8,-12],[8,-11],[8,-10],[8,-9],[8,-8],[8,-7],[8,-6],[8,-5],[8,-4],[8,-3],[8,-2],[8,-1],[8,0],[8,1],[8,2],[8,3],[8,4],[8,5],[8,6],[8,7],[8,8],[8,9],[8,10],[8,11],[8,12],[9,-11],[9,-10],[9,-9],[9,-8],[9,-7],[9,-6],[9,-5],[9,-4],[9,-3],[9,-2],[9,-1],[9,0],[9,1],[9,2],[9,3],[9,4],[9,5],[9,6],[9,7],[9,8],[9,9],[9,10],[9,11],[10,-10],[10,-9],[10,-8],[10,-7],[10,-6],[10,-5],[10,-4],[10,-3],[10,-2],[10,-1],[10,0],[10,1],[10,2],[10,3],[10,4],[10,5],[10,6],[10,7],[10,8],[10,9],[10,10],[11,-9],[11,-8],[11,-7],[11,-6],[11,-5],[11,-4],[11,-3],[11,-2],[11,-1],[11,0],[11,1],[11,2],[11,3],[11,4],[11,5],[11,6],[11,7],[11,8],[11,9],[12,-8],[12,-7],[12,-6],[12,-5],[12,-4],[12,-3],[12,-2],[12,-1],[12,0],[12,1],[12,2],[12,3],[12,4],[12,5],[12,6],[12,7],[12,8],[13,-7],[13,-6],[13,-5],[13,-4],[13,-3],[13,-2],[13,-1],[13,0],[13,1],[13,2],[13,3],[13,4],[13,5],[13,6],[13,7],[14,-6],[14,-5],[14,-4],[14,-3],[14,-2],[14,-1],[14,0],[14,1],[14,2],[14,3],[14,4],[14,5],[14,6],[15,-5],[15,-4],[15,-3],[15,-2],[15,-1],[15,0],[15,1],[15,2],[15,3],[15,4],[15,5],[16,-4],[16,-3],[16,-2],[16,-1],[16,0],[16,1],[16,2],[16,3],[16,4],[17,-3],[17,-2],[17,-1],[17,0],[17,1],[17,2],[17,3],[18,-2],[18,-1],[18,0],[18,1],[18,2],[19,-1],[19,0],[19,1],[20,0]]"

display(
  JSON.stringify(
    range(-20, 21)
      .flatMap(y => range(-20, 21).map(x => [y, x]))
      .filter(
        ([y, x]) => !(y == 0 && x == 0) && Math.abs(y) + Math.abs(x) <= 20,
      ),
  ),
)

Now we write a function to find cheats just like in part 1, but with our larger set of cheat vectors

import { points } from "./lib/day20points.js"

function findCheats2(map, pt) {
  return points
    .map(d => add(pt, d))
    .filter(([y, x]) => [FLOOR, END].includes(map[y]?.[x]))
}

And finally, search over the larger cheat vector space in exactly the same way

display(race(test, findCheats2, 69))
display(race(input, findCheats2, 99, true))

Day 20

prelude

part 1

part 2