examples/maze/

# The maze: a rectangle of characters, and the arithmetic that turns a position
# into one number.
#
#     #   wall          S   where you start
#     .   open          E   where you are going
#
# **A position is an index, not a pair.** `row * width + column` is the whole
# reason the solver can use a `{i64: i64}` for "how I got here": the language has
# no tuples and a record key would work, but one number is what makes the map
# cheap to read and the encoding is three lines with its own test.
#
# Every row must be the same width. A ragged maze is refused rather than padded,
# because padding invents open squares and a solver that walks through one has
# found a path the file does not describe.

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_EMPTY_MAZE: str
    "empty_maze"

constant ERR_MISSING_MARK: str
    "missing_mark"

constant ERR_RAGGED_MAZE: str
    "ragged_maze"

constant ERR_REPEATED_MARK: str
    "repeated_mark"

record Grid
    rows: [str]
    width: i64
    height: i64

constant WALL: u8
    '#'

constant START: u8
    'S'

constant GOAL: u8
    'E'

function split_lines(text: str) -> [str]
    out: [str] @= []
    start: i64 @= 0
    i: i64 @= 0

    while i < text.len()
        if text[i] == '\n'
            out @ out.push(text.slice(from: start, to: i))
            start @ i + 1
        i @ i + 1

    if start < text.len()
        out @ out.push(text.slice(from: start, to: text.len()))
    return out

function read(text: str) -> Grid?
    rows: [str] @= []

    for line in split_lines(text)
        if line != ""
            rows @ rows.push(line)

    if rows.len() == 0
        return fail(code: ERR_EMPTY_MAZE, msg: "the file has no rows")
    width = rows[0].len()

    for line in rows
        if line.len() != width
            return fail(code: ERR_RAGGED_MAZE, msg: "every row must be " + width.to_str() + " wide")

    g = Grid(rows: rows, width: width, height: rows.len())
    _ = locate(g, START)?
    _ = locate(g, GOAL)?
    return ok(g)

## Positions

function index_of(g: Grid, row: i64, column: i64) -> i64
    return row * g.width + column

function row_of(g: Grid, index: i64) -> i64
    return index / g.width

function column_of(g: Grid, index: i64) -> i64
    return index % g.width

function at(g: Grid, index: i64) -> u8
    return g.rows[row_of(g, index)][column_of(g, index)]

function inside(g: Grid, row: i64, column: i64) -> bool
    return row >= 0 && row < g.height && column >= 0 && column < g.width

function is_open(g: Grid, index: i64) -> bool
    return at(g, index) != WALL

# Where the one square marked `mark` is. Exactly one: a maze with two starts is
# a maze whose answer depends on which one the reader meant.
function locate(g: Grid, mark: u8) -> i64?
    found: i64 @= 0 - 1

    for row in range(from: 0, to: g.height)
        for column in range(from: 0, to: g.width)
            index = index_of(g, row: row, column: column)

            if at(g, index) == mark
                if found >= 0
                    return fail(code: ERR_REPEATED_MARK, msg: "the maze has more than one `" + one_char(mark) + "`")
                found @ index

    if found < 0
        return fail(code: ERR_MISSING_MARK, msg: "the maze has no `" + one_char(mark) + "`")
    return ok(found)

# One byte as a `str`, for a message. There is no `chr`, so the two marks this
# program can complain about are spelled out where they are declared.
function one_char(mark: u8) -> str
    if mark == START
        return "S"

    if mark == GOAL
        return "E"
    return "#"

# The four squares you can step to: inside the maze, and not a wall.
function neighbours(g: Grid, index: i64) -> [i64]
    row = row_of(g, index)
    column = column_of(g, index)
    out: [i64] @= []
    out @ step(g, out, row: row - 1, column: column)
    out @ step(g, out, row: row + 1, column: column)
    out @ step(g, out, row: row, column: column - 1)
    out @ step(g, out, row: row, column: column + 1)
    return out

function step(g: Grid, out: [i64], row: i64, column: i64) -> [i64]
    if !inside(g, row: row, column: column)
        return out
    index = index_of(g, row: row, column: column)

    if !is_open(g, index)
        return out
    return out.push(index)

test "an index is a row and a column, both ways"
    g = read("S.\n.E\n").must()
    assert index_of(g, row: 1, column: 0) == 2
    assert row_of(g, 2) == 1
    assert column_of(g, 3) == 1
    assert at(g, 0) == START
    assert at(g, 3) == GOAL

test "a maze must be a rectangle with one start and one goal"
    assert read("S.\n.E\n").must().width == 2
    assert read("S.\n.E.\n").is_err()
    assert read("").is_err()
    assert read("SE\nS.\n").is_err()
    assert read("S.\n..\n").is_err()
    assert read("E.\n..\n").is_err()

test "the neighbours of a square stop at the walls and at the edges"
    g = read("S#\n.E\n").must()
    assert neighbours(g, 0) == [2]
    assert neighbours(g, 2) == [0, 3]
    assert neighbours(g, 3) == [2]

# Breadth-first search, and the shortest path it found.
#
# Breadth-first rather than depth-first because the question is *how short*, and
# a queue answers it while a stack does not. The queue is an array with a **head
# index** rather than something that removes from the front: removing element 0
# copies the whole array under value semantics, so a queue that shrinks is
# quadratic in the number of squares and one that only grows is not.
#
# `came` does two jobs, and doing both with one map is what keeps the loop
# honest: it is the visited set (a key exists) and the way back (its value). A
# separate `visited` could disagree with it, and the disagreement would be a
# solver that walks in circles.

use grid

## Error codes
#
# One `constant` per code, so a typo is `error[unknown_name]` here rather
# than a comparison that is quietly false forever (panel 034 R4).

constant ERR_NO_PATH: str
    "no_path"

function solve(g: grid.Grid) -> [i64]?
    start = grid.locate(g, grid.START)?
    goal = grid.locate(g, grid.GOAL)?
    came: {i64: i64} @= {}
    came[start] @ start
    queue: [i64] @= [start]
    head: i64 @= 0

    while head < queue.len()
        here = queue[head]
        head @ head + 1

        if here == goal
            return ok(walk_back(came, start: start, goal: goal))

        for next in grid.neighbours(g, here)
            if came[next].is_err()
                came[next] @ here
                queue @ queue.push(next)

    return fail(code: ERR_NO_PATH, msg: "no way from the start to the goal")

# The path, start first. It is built backwards from the goal and turned round
# once, because following `came` is the only direction that map can be read in.
function walk_back(came: {i64: i64}, start: i64, goal: i64) -> [i64]
    backwards: [i64] @= [goal]
    at: i64 @= goal

    while at != start
        at @ came[at].must()
        backwards @ backwards.push(at)

    return reversed(backwards)

function reversed(xs: [i64]) -> [i64]
    out: [i64] @= []

    for i in range(from: 0, to: xs.len())
        out @ out.push(xs[xs.len() - 1 - i])

    return out

# How many steps the path takes — one fewer than the squares it visits.
function steps(path: [i64]) -> i64
    return path.len() - 1

# Whether every step of a path is a legal move: adjacent, open, and inside. The
# solver is believed by nothing; this is what the tests ask.
function is_walkable(g: grid.Grid, path: [i64]) -> bool
    if path.len() == 0
        return false

    for i in range(from: 1, to: path.len())
        if !contains(grid.neighbours(g, path[i - 1]), path[i])
            return false

    return true

function contains(known: [i64], one: i64) -> bool
    for each in known
        if each == one
            return true

    return false

test "the shortest way through an open room is the straight one"
    g = grid.read("S..\n...\n..E\n").must()
    path = solve(g).must()
    assert steps(path) == 4
    assert is_walkable(g, path)
    assert path[0] == 0
    assert path[path.len() - 1] == 8

test "a wall makes the way round it longer"
    g = grid.read("S.#\n.#.\n..E\n").must()
    path = solve(g).must()
    assert steps(path) == 4
    assert is_walkable(g, path)

test "a maze with no way through says so instead of guessing"
    walled = grid.read("S#E\n###\n...\n").must()
    boxed = grid.read("S.#\n..#\n##E\n").must()
    assert solve(walled).is_err()
    assert solve(boxed).is_err()

test "the start and the goal may be the same square's neighbours"
    g = grid.read("SE\n..\n").must()
    assert steps(solve(g).must()) == 1

test "reversed does what its name says, including for nothing"
    assert reversed([1, 2, 3]) == [3, 2, 1]
    assert reversed([]) == []
    assert reversed([7]) == [7]