Falca's Cave
Project 2 dropped our hero, Falca, into a square cave guarded by a dragon. Falca must collect every treasure (up to three) and leave by the exit, and may only pass the dragon once holding the sword.
My 2019 file for this project survived. The “As submitted” mode is a line-by-line TypeScript port of it, checked against the Python on 230 seeded caves (220 of them random). Flip to “Spec-correct” to see what changes when its bugs are fixed.
- build_cave()
- check_path()
- shortest_path()
- optimal_path()
A line-by-line port of my 2019 file, bugs included. Here the dragon only guards its own square.
The input: data
The cave
The first cave from the 2019 file. Grab the sword, pass the dragon, collect the treasure: 23 moves.
Click or drag to paint. Click a feature again with its own tool to remove it.
- Falca
- route
The four functions
Run the code
The fewest moves from the entrance to the exit that collect every treasure, fetching the sword only if it helps. The search is uniform-cost over the interesting squares, with shortest_path as the cost of each leg.
As submitted (2019)
23 moves
Spec-correct
23
- 1to the sword (3, 3)+6
- 2to the dragon (0, 2) armed+8
- 3to the treasure (1, 3) armed+2
- 4to the exit (2, 1) armed+7
>>> optimal_path(data) 23
Priority queue: 12 entries popped
| cost | treasure left | sword | waypoints |
|---|---|---|---|
| 6 | 1 | 1 | (0, 0) → (3, 3) |
| 9 | 1 | 1 | (0, 0) → (3, 3) → (2, 1) |
| 14 | 1 | 1 | (0, 0) → (3, 3) → (0, 2) |
| 14 | 1 | 1 | (0, 0) → (3, 3) → (2, 1) → (0, 2) |
| 16 | 0 | 1 | (0, 0) → (3, 3) → (0, 2) → (1, 3) |
| 16 | 0 | 1 | (0, 0) → (3, 3) → (1, 3) |
| 16 | 0 | 1 | (0, 0) → (3, 3) → (2, 1) → (0, 2) → (1, 3) |
| 16 | 0 | 1 | (0, 0) → (3, 3) → (2, 1) → (1, 3) |
| 18 | 0 | 1 | (0, 0) → (3, 3) → (1, 3) → (0, 2) |
| 18 | 0 | 1 | (0, 0) → (3, 3) → (2, 1) → (1, 3) → (0, 2) |
| 19 | 1 | 1 | (0, 0) → (3, 3) → (0, 2) → (2, 1) |
| 23 | 0 | 1 | (0, 0) → (3, 3) → (0, 2) → (1, 3) → (2, 1) |
Code review, six years late
What my 2019 code got wrong
It printed 23 and 14 on the two sample caves, which is all I checked at the time. Replaying it on hundreds of caves turned up these quirks. The presets under “Where the two versions differ” show each one.
The original file is kept unchanged in the repository, which is private for now (DR-003).
The dragon's reach
The task says Falca may not enter the dragon's square or any of the eight around it without the sword. My shortest_path only blocks the dragon's own square, so routes brush right past it.
Fetching the sword
optimal_path decides Falca is armed before walking to the sword, so the leg that fetches it may already walk past the dragon.
No treasure, no search
With no treasure in the cave, optimal_path returns the direct entrance-to-exit distance straight away, even when the dragon blocks it and the sword would open another route.
A crash when walled in
If nothing can be reached from the entrance, the priority queue runs dry and queue.pop(0) raises IndexError.
Picky build_cave
build_cave rejects any cave without a 'walls' key, yet never checks for features that share a square or sit outside the grid.
Generous check_path
Treasure is only counted when the cave has both a dragon and a sword, and walking off the edge is noticed one move late.
Parity: scripts/generate_parity_fixtures.py runs the unmodified 2019 file on 230 seeded caves (2 samples, 8 hand-made, 220 random) through build_cave, check_path, shortest_path and optimal_path, crashes included, and the TypeScript port must match every answer.