Maze Runner: Level Service

Maze Runner: Level Service

You've joined the tools team for Labyrinth, a grid puzzle game. Level designers draw levels as ASCII maps in the level editor, and the level service behind it validates them, finds the fewest-steps solution, and draws that solution as an overlay. This sprint you'll fix two bug reports and then build the new cell types design has asked for.

Codebase

• maze/glyphs.py: what each map character means, plus entry_cost for terrain.
• maze/grid.py: Grid (positions are (row, col)), DIRECTIONS order, parse_level validation.
• maze/rules.py: movement rules the solver consults for every move (the extension point for new cells).
• maze/search.py: breadth-first fewest-steps solver.
• maze/terrain.py: placeholder for the cost-aware planner (not implemented).
• maze/render.py: draws a path over a level for the editor overlay.
• maze/generator.py: deterministic procedural levels (seeded LCG). Known-good.
• maze/service.py: LevelService, which stores levels by id and caches solutions per id.
• maze/api.py: the run(operations) entrypoint and the operation dispatcher.
• tests/: the existing unit tests. tests/test_solver.py::test_open_room and tests/test_render.py::test_render_marks_path_and_keeps_markers fail today.

How your code is run

run(operations: list[list]) -> list creates a fresh LevelService, applies each operation in order, and returns exactly one output per operation. Errors are returned as strings, never raised.

Any other operation name returns "error: unknown operation '<name>'".

Glyphs today: # wall, . floor, S start, E exit, 1-9 terrain (walkable, see Part 4). A move goes one cell up, right, down or left; walls can't be entered; leaving the map is impossible.

Validation runs in this order and the first failure is returned as "error: <reason>":

1. empty level (no rows, or the first row is empty)
2. rows have different lengths
3. unknown glyph '<ch>' at row <r>, col <c> (the first one in row-major order)
4. expected exactly one S
5. expected exactly one E

A failed load or generate leaves any existing level with that id untouched. A successful one replaces it.

Tie-break. When several paths have the fewest steps, path (and so render) uses the one whose move sequence comes first when moves are compared one at a time with up < right < down < left. The existing BFS already gets this by exploring neighbours in DIRECTIONS order; keep it.

Worked example

[["load", "intro", ["S.#", "...", "#.E"]], ["solve", "intro"], ["path", "intro"], ["render", "intro"]]

returns

["ok", 4, [[0,0],[0,1],[1,1],[1,2],[2,2]], ["S*#", ".**", "#.E"]]

Four routes take 4 steps; right, down, right, down sorts first. Today render returns ["**#", ".**", "#.*"].

Part 1: Bug reports from level design

Goal: fix these reported problems without changing anything else.

1. "When the solution is drawn in the editor, the S and E markers disappear." render must draw * on every path cell except S and E, which always keep their glyph, even if the path crosses them more than once. Whatever else is under the path (floor, terrain, and the new cells from later parts) becomes *.
2. "The solver says there is no path through big open levels that are obviously solvable." An empty 8x8 room with S and E in opposite corners is reported as null instead of 14. solve/path must be correct for any level up to 300x300.
3. "After I re-upload a level under the same id, solve sometimes gives the old level's answer." After a successful load or generate, every query on that id must reflect the new level.

Part 2: One-way gates

Goal: support the gate cells > < ^ v.

1. The loader accepts the four gate glyphs.
2. A gate can only be entered by a move in the direction its arrow points: > by a move right, < by a move left, ^ by a move up, v by a move down.
3. Leaving a gate is unrestricted (any direction, subject to the normal rules for the cell you enter).
4. A gate counts as one step like any other cell. The tie-break is unchanged.

Example

[["load", "oneway", ["S<..E", ".###.", "....."]], ["solve", "oneway"], ["load", "short", ["S>.E"]], ["solve", "short"]]

returns ["ok", 8, "ok", 3]: in oneway the < can't be entered by moving right, so the route goes around the bottom (down, down, right x4, up, up).

Part 3: Keys and doors

Goal: support keys a b c d and their doors A B C D.

1. The loader accepts the eight glyphs. A level may hold at most one key of each letter; a second one is the validation error duplicate key '<k>', naming the key whose second copy comes first in row-major order. This check runs after the S and E checks. A door whose key isn't in the level is allowed (it can just never be opened).
2. You start with no keys. Stepping onto a key cell picks that key up for the rest of the walk. The key cell stays walkable.
3. A door can be entered only while holding the key of the same letter (a opens A). Doors never lock again.
4. The fewest-steps path may now revisit cells (including S) after collecting a key. path lists every position in walk order, and the walk ends the first time it reaches E.
5. Gates (Part 2) still apply, and the tie-break rule is unchanged.

Example

[["load", "k", ["S.a", "#A#", "#E#"]], ["solve", "k"], ["path", "k"], ["render", "k"]]

returns ["ok", 5, [[0,0],[0,1],[0,2],[0,1],[1,1],[2,1]], ["S**", "#*#", "#E#"]]: walk right twice to get a, step back, then go down through A to E.

Part 4: Cheapest route over terrain (stretch)

Goal: add the cheapest operation.

1. ["cheapest", level_id] returns the minimum total cost of a walk from S to E as an int, null if E is unreachable, or "error: unknown level".
2. Each move costs the entry cost of the cell moved onto: a terrain digit costs its value, and every other walkable cell (., E, S, gates, keys, doors) costs 1. Standing on S at the start is free. This is glyphs.entry_cost.
3. Walls, gates, keys and doors work exactly as in Parts 2-3.
4. solve is unchanged: it still counts steps and ignores terrain.
5. Scale: tests generate levels up to 80 cells on a side and run several solve and cheapest queries in one call, all under the runner's 5-second limit for the whole suite. Scanning every state to find the next cheapest one, or enumerating whole paths, is too slow.

Example

[["load", "t", ["S9E", "1#1", "111"]], ["solve", "t"], ["cheapest", "t"]]

returns ["ok", 2, 6]: the 2-step route costs 9 + 1 = 10, and the 6-step detour around the wall costs 6.

Notes

• glyphs.py constants, generator.py and the Grid helpers are known-good. The bugs are elsewhere.
• Use the AI assistant freely, but check what it changes against the rules above.
• Later parts must not break earlier ones. Hidden tests re-check earlier behaviour.
• Parts 1-3 is a strong result. Part 4 is a stretch.