A-Maze-ingly Retro Route Puzzle
This is a JSON variant of the problem described by this blog post.
Write a program that will output a valid route one could follow to collect all specified items within a map. The map is a json description of set of rooms with allowed path and contained object.
Exercise starts with an input of:
- json reppresentation of map
- starting room
- list of object to collect
Room type allowed fields
id: Integer
name: String
north: Integer //referring to a connected room
south: Integer //referring to a connected room
west: Integer //referring to a connected room
east: Integer //referring to a connected room
objects: List //of Objects
Object type allowed fields
name: String //Object Name
Map
{
"rooms": [
{ "id": 1, "name": "Hallway", "north": 2, "objects": [] },
{ "id": 2, "name": "Dining Room", "south": 1, "west": 3, "east": 4, "objects": [] },
{ "id": 3, "name": "Kitchen","east":2, "objects": [ { "name": "Knife" } ] },
{ "id": 4, "name": "Sun Room","west":2, "objects": [ { "name": "Potted Plant" } ] }
]
}Input
Start Room ID = 2
Objects To Collect = Knife, Potted Plant
Output
| ID | Room | Object collected |
|---|---|---|
| 0 | Dining Room | None |
| 1 | Hallway | None |
| 2 | Dining Room | None |
| 3 | Kitchen | Knife |
| 2 | Dining Room | None |
| 4 | Sun Room | Potted Plant |
- TDD approach.
- Build a Docker container with runnable code inside so that we can mount a volume in it and test on different maps.
To build a runnable jar:
mvn clean package
To build a runnable docker image:
mvn clean package docker:build
Example:
java -jar target/retro-route-puzzle-<version>.jar -m map.json -r 2 -i "Knife" "Potted Plant"
Example using Docker:
docker run -v `pwd`:`pwd` -w `pwd` retro-route-puzzle -m map.json -r 2 -i "Knife" "Potted Plant"
The search algorithm is a greedy multi step graph visit, where each step uses Breadth First Search or Depth First Search. In either case the complexity is O(R) where R is the number of rooms, but in general BFS should result in shorter routes.