generate_plotter.py

#!/usr/bin/env python3
"""Generate a Littleman solution for the Plotter problem."""

from __future__ import annotations

from dataclasses import dataclass


TOP = 50
RIGHT_WALL = 168
RIGHT_TURN = 166
TERMINAL_COLUMN = 167
LEFT_TURN = 1
LOOP_RETURN = 3
ROUND_RETURN = 5

BANDS = {
    "IN": 12,
    "ERR": 24,
    "DY": 36,
    "SX": 48,
    "CX": 60,
    "DX": 72,
    "SY": 84,
    "CY": 96,
    "P": 108,
    "DATA": 120,
    "Q": 132,
    "SWAP": 144,
    "ADDR": 156,
}

MEMORIES = ("ERR", "DY", "SX", "CX", "DX", "SY", "CY", "P", "Q")

# A becomes sign(z), with zero treated as positive.  This is sufficient for
# Bresenham because the step in an equal coordinate is never taken.
SIGN = "M`63`W}M+M1W+"

# A becomes 1 when z >= 0 and 0 otherwise.
GE_ZERO = "M`63`W}NM1-"

# A becomes 1 when z != 0 and 0 otherwise.
NOT_EQUAL_ZERO = "MN|M`63`W}N"


@dataclass(frozen=True)
class Access:
    start: int
    code: str


def access(kind: str, name: str) -> Access:
    band = BANDS[name]
    if kind == "read":
        return Access(band - 1, "0sr")
    if kind == "write":
        return Access(band - 2, "M1sWs")
    if kind == "input":
        return Access(band, "r")
    if kind == "send":
        return Access(band, "s")
    raise ValueError(f"unknown access kind: {kind}")


class LaneCompiler:
    def __init__(self) -> None:
        self.lanes: list[list[str]] = []
        self.cursor = 7
        self.new_lane()

    def new_lane(self) -> None:
        if self.lanes and not any(ch != " " for ch in self.lanes[-1]):
            return
        self.lanes.append([" "] * (RIGHT_WALL + 1))
        self.cursor = 7

    def put(self, x: int, code: str) -> None:
        if x < 1 or x + len(code) > RIGHT_TURN:
            raise ValueError(f"instruction does not fit at {x}: {code!r}")
        lane = self.lanes[-1]
        for offset, ch in enumerate(code):
            pos = x + offset
            if lane[pos] != " ":
                raise ValueError(f"lane collision at x={pos}: {lane[pos]!r} vs {ch!r}")
            lane[pos] = ch
        self.cursor = x + len(code)

    def plain(self, code: str) -> None:
        if self.cursor + len(code) > RIGHT_TURN:
            self.new_lane()
        self.put(self.cursor, code)

    def do(self, kind: str, name: str) -> None:
        op = access(kind, name)
        if op.start < self.cursor:
            self.new_lane()
        self.put(op.start, op.code)

    def read(self, name: str) -> None:
        self.do("read", name)

    def write(self, name: str) -> None:
        self.do("write", name)

    def input(self) -> None:
        self.do("input", "IN")

    def send(self, name: str) -> None:
        self.do("send", name)


def compile_controller() -> tuple[list[list[str]], int, int, int]:
    c = LaneCompiler()

    # Load x0, y0, x1, y1.  P, Q, CX, and CY are temporary input registers.
    for target in ("P", "Q", "CX", "CY"):
        c.input()
        c.write(target)

    # sx = sign(x1 - x0)
    c.read("P")
    c.plain("M")
    c.read("CX")
    c.plain("-" + SIGN)
    c.write("SX")

    # dx = (x1 - x0) * sx = abs(x1 - x0)
    c.read("P")
    c.plain("M")
    c.read("CX")
    c.plain("-M")
    c.read("SX")
    c.plain("*")
    c.write("DX")

    # sy = sign(y1 - y0)
    c.read("Q")
    c.plain("M")
    c.read("CY")
    c.plain("-" + SIGN)
    c.write("SY")

    # dy = -(y1 - y0) * sy = -abs(y1 - y0)
    c.read("Q")
    c.plain("M")
    c.read("CY")
    c.plain("-M")
    c.read("SY")
    c.plain("*N")
    c.write("DY")

    # Store 32*sy, because P is the row-major display address.
    c.read("SY")
    c.plain("M`32`*")
    c.write("SY")

    # P = 32*y0 + x0
    c.read("Q")
    c.plain("M`32`*M")
    c.read("P")
    c.plain("+")
    c.write("P")

    # Q = 32*y1 + x1
    c.read("CY")
    c.plain("M`32`*M")
    c.read("CX")
    c.plain("+")
    c.write("Q")

    # err = dx + dy
    c.read("DY")
    c.plain("M")
    c.read("DX")
    c.plain("+")
    c.write("ERR")

    c.new_lane()
    loop_start = len(c.lanes) - 1

    # Plot P.  ADDR deliberately travels one whole lane before DATA, so the
    # cursor is positioned before color 15 can reach the display.
    c.read("P")
    c.plain("M")
    c.send("ADDR")
    c.new_lane()
    c.plain("`15`")
    c.send("DATA")
    c.plain("WM")
    c.read("Q")
    c.plain("-" + NOT_EQUAL_ZERO)
    branch_lane = len(c.lanes) - 1

    # cx = (2*err >= dy)
    c.new_lane()
    c.read("ERR")
    c.plain("M+M")
    c.read("DY")
    c.plain("N+" + GE_ZERO)
    c.write("CX")

    # cy = (2*err <= dx), equivalently dx - 2*err >= 0.
    c.read("ERR")
    c.plain("M+M")
    c.read("DX")
    c.plain("-" + GE_ZERO)
    c.write("CY")

    # err += dy*cx
    c.read("DY")
    c.plain("M")
    c.read("CX")
    c.plain("*M")
    c.read("ERR")
    c.plain("+")

    # Store that partial value while computing dx*cy.
    c.write("ERR")
    c.read("DX")
    c.plain("M")
    c.read("CY")
    c.plain("*M")
    c.read("ERR")
    c.plain("+")

    # Store the completed error and advance P by sx*cx.
    c.write("ERR")
    c.read("SX")
    c.plain("M")
    c.read("CX")
    c.plain("*M")
    c.read("P")
    c.plain("+")
    c.write("P")

    # Advance P by (32*sy)*cy.
    c.read("SY")
    c.plain("M")
    c.read("CY")
    c.plain("*M")
    c.read("P")
    c.plain("+")
    c.write("P")

    final_lane = len(c.lanes) - 1
    return c.lanes, loop_start, branch_lane, final_lane


def set_cell(grid: list[list[str]], x: int, y: int, ch: str) -> None:
    if ch == " ":
        return
    old = grid[y][x]
    if old != " " and old != ch:
        raise ValueError(f"grid collision at ({x}, {y}): {old!r} vs {ch!r}")
    grid[y][x] = ch


def draw_room(
    grid: list[list[str]],
    left: int,
    top: int,
    interior_rows: list[str],
    *,
    vertical_wall: str = "|",
    horizontal_wall: str = "-",
) -> None:
    width = len(interior_rows[0])
    if any(len(row) != width for row in interior_rows):
        raise ValueError("ragged room")
    right = left + width + 1
    bottom = top + len(interior_rows) + 1
    set_cell(grid, left, top, "+")
    set_cell(grid, right, top, "+")
    set_cell(grid, left, bottom, "+")
    set_cell(grid, right, bottom, "+")
    for x in range(left + 1, right):
        set_cell(grid, x, top, horizontal_wall)
        set_cell(grid, x, bottom, horizontal_wall)
    for y in range(top + 1, bottom):
        set_cell(grid, left, y, vertical_wall)
        set_cell(grid, right, y, vertical_wall)
    for row_index, row in enumerate(interior_rows, start=top + 1):
        for col_index, ch in enumerate(row, start=left + 1):
            set_cell(grid, col_index, row_index, ch)


def build_program() -> str:
    lanes, loop_start, branch_lane, final_lane = compile_controller()
    lane_count = len(lanes)
    commit_local_y = 2 * lane_count + 1
    controller_bottom = TOP + commit_local_y + 1
    grid = [[" "] * (RIGHT_WALL + 1) for _ in range(controller_bottom + 1)]

    # Central controller room.
    set_cell(grid, 0, TOP, "+")
    set_cell(grid, RIGHT_WALL, TOP, "+")
    set_cell(grid, 0, controller_bottom, "+")
    set_cell(grid, RIGHT_WALL, controller_bottom, "+")
    for x in range(1, RIGHT_WALL):
        set_cell(grid, x, TOP, "-")
        set_cell(grid, x, controller_bottom, "-")
    for y in range(TOP + 1, controller_bottom):
        set_cell(grid, 0, y, "|")
        set_cell(grid, RIGHT_WALL, y, "|")

    for index, lane in enumerate(lanes):
        access_y = TOP + 1 + 2 * index
        return_y = access_y + 1
        for x, ch in enumerate(lane):
            set_cell(grid, x, access_y, ch)
        set_cell(grid, LEFT_TURN, access_y, "@" if index == 0 else ">")
        set_cell(grid, RIGHT_TURN, access_y, "v")
        set_cell(grid, RIGHT_TURN, return_y, "<")
        set_cell(grid, LEFT_TURN, return_y, "v")

    first_y = TOP + 1
    loop_y = TOP + 1 + 2 * loop_start
    branch_y = TOP + 1 + 2 * branch_lane
    final_return_y = TOP + 2 + 2 * final_lane
    commit_y = TOP + commit_local_y

    # Separate northbound columns return to the next round or next pixel.
    set_cell(grid, ROUND_RETURN, first_y, ">")
    set_cell(grid, LOOP_RETURN, loop_y, ">")

    # Positive means P != Q and takes the normal computation path.  Zero
    # continues into a private downward column and skips directly to commit.
    grid[branch_y][RIGHT_TURN] = "X"
    set_cell(grid, TERMINAL_COLUMN, branch_y, "v")

    # The final computation lane returns to the plot lane instead of falling
    # through into another copy of the loop body.
    grid[final_return_y][LEFT_TURN] = " "
    set_cell(grid, LOOP_RETURN, final_return_y, "^")

    # Commit a clearing swap (0), then wait for the next round's input.
    set_cell(grid, TERMINAL_COLUMN, commit_y, "<")
    set_cell(grid, BANDS["SWAP"] + 1, commit_y, "0")
    set_cell(grid, BANDS["SWAP"], commit_y, "s")
    set_cell(grid, ROUND_RETURN, commit_y, "^")

    # Nine mutable register rooms.
    memory_rows = [
        "@M>rXWsWv",
        "    r    ",
        "    M    ",
        "  ^ <   <",
    ]
    for name in MEMORIES:
        band = BANDS[name]
        draw_room(grid, band - 5, 42, memory_rows)
        # Controller -> register command/data.
        set_cell(grid, band, 49, "^")
        set_cell(grid, band, 48, "^")
        # Register -> controller response.
        set_cell(grid, band + 2, 48, "v")
        set_cell(grid, band + 2, 49, "v")

    # Input room and its sole outgoing pipe.
    draw_room(grid, BANDS["IN"] - 1, 45, ["I"])
    set_cell(grid, BANDS["IN"], 48, "v")
    set_cell(grid, BANDS["IN"], 49, "v")

    # One 32x24 LM-75 display.
    display_left = BANDS["DATA"] + 2
    display_top = 5
    draw_room(
        grid,
        display_left,
        display_top,
        [" " * 32 for _ in range(24)],
        vertical_wall=":",
        horizontal_wall="=",
    )

    # DATA: up the left side, then directly into the display.
    set_cell(grid, BANDS["DATA"], 49, "^")
    for y in range(16, 49):
        set_cell(grid, BANDS["DATA"], y, "|")
    set_cell(grid, BANDS["DATA"], 15, ">")
    set_cell(grid, BANDS["DATA"] + 1, 15, ">")

    # SWAP: straight into the display's bottom edge.
    set_cell(grid, BANDS["SWAP"], 49, "^")
    for y in range(32, 49):
        set_cell(grid, BANDS["SWAP"], y, "|")
    set_cell(grid, BANDS["SWAP"], 31, "^")

    # ADDR: go around the right side and enter through the top.
    set_cell(grid, BANDS["ADDR"], 49, "^")
    for y in range(4, 49):
        set_cell(grid, BANDS["ADDR"], y, "|")
    set_cell(grid, BANDS["ADDR"], 3, "<")
    for x in range(BANDS["SWAP"] + 1, BANDS["ADDR"]):
        set_cell(grid, x, 3, "-")
    set_cell(grid, BANDS["SWAP"], 3, "v")
    set_cell(grid, BANDS["SWAP"], 4, "v")

    lines = ["".join(row).rstrip() for row in grid]
    while lines and not lines[0]:
        lines.pop(0)
    while lines and not lines[-1]:
        lines.pop()
    return "\n".join(lines) + "\n"


if __name__ == "__main__":
    program = build_program()
    with open("plotter.txt", "w", encoding="ascii", newline="\n") as output:
        output.write(program)
    print(f"wrote plotter.txt ({max(map(len, program.splitlines()))}x{len(program.splitlines())})")