//➜ Cell(4, 2) true false 3,2|4,2
echo(move(Cell(3, 2), East), inside(Cell(0, 0)), inside(Cell(cols, 0)), passage(Cell(4, 2), Cell(3, 2)))

// Sets are copied, never changed: `adding` returns a new set with one more key.
fun adding(keys: Set, k) = new Set([...keys, k])

// The next pseudo-random seed (Park–Miller), and eight orders of the four
// directions, from which the seed picks one at each cell.
fun next(s) = s * 48271 % 2147483647

val orders = [
  [North, East, South, West], [North, West, East, South], [East, South, North, West],
  [East, North, West, South], [South, West, North, East], [South, East, West, North],
  [West, North, South, East], [West, South, East, North]
]

data class State(visited: Set, passages: Set, seed: Num)

// Visit a cell, then try each neighbour in a random order. A neighbour that
// is still unvisited gets a passage to this cell and is carved recursively.
// (Mutually recursive functions go in the same block.)
fun carve(cell, st) = if st is State(visited, passages, s) then
  let start = State(adding(visited, key(cell)), passages, next(s))
  orders.at(next(s) % orders.length).reduce((st, d, _, _) => step(cell, d, st), start)
fun step(cell, d, st) = if
  let n = move(cell, d)
  inside(n) and st is State(visited, passages, s) and not visited.has(key(n)) then
    carve(n, State(visited, adding(passages, passage(cell, n)), s))
  else st

let maze = carve(Cell(0, 0), State(new Set(), new Set(), seed))

fun connected(a, b) = if maze is State(_, passages, _) then passages.has(passage(a, b))

// A perfect maze is a tree: one passage fewer than there are cells.
//➜ 143 144
echo(maze.passages.size, maze.visited.size)

/**
 * Solving: in a perfect maze there is exactly one path between two cells.
 * A search either finds it, `Some(path)`, or comes back with `None`.
 */

data class Some(value)
object None

val goal = Cell(cols - 1, rows - 1)

// Try the directions one by one; the first that leads to the goal wins.
fun solve(cell, prev) =
  if key(cell) == key(goal) then Some([cell])
  else tryFrom(cell, prev, [North, East, South, West], 0)
fun tryFrom(cell, prev, dirs: Array, i) = if
  i == dirs.length then None
  let n = move(cell, dirs.at(i))
  inside(n) and connected(cell, n) and key(n) != key(prev) and solve(n, cell) is Some(rest) then
    Some([cell, ...rest])
  else tryFrom(cell, prev, dirs, i + 1)

let path = if solve(Cell(0, 0), Cell(-1, -1)) is Some(p) then p else []