RoomDoorKey.adoc

Maze with locked doors

In this gist model of the maze, you can reach room D by following the path A→B→C→A, picking up the key for room D in room B. However it is not possible to reach room F, since the key to room F is in room E, and the key to room E is in room D, and there is no way back from room D to room A, so room E is inaccessible. (Finding the HIDDEN door from room D to room C would make this possible.)

Is it possible to create queries which take into account the keys that can be picked up on the way? For example:

• Is it possible to get from room X to room Y?

• What are all the paths that lead from room A to room Z?

• I’m in room N with these keys. Have I come to a dead end?

• What keys do I need to get from the Library to the Conservatory?

CREATE INDEX ON :Room(name);
CREATE (a:Room {name:'A'})
     , (b:Room {name:'B'})
     , (c:Room {name:'C'})
     , (d:Room {name:'D'})
     , (e:Room {name:'E'})
     , (f:Room {name:'F'})
     , (a)-[ab:DOOR]->(b)
     , (a)-[ad:DOOR {key: 'B'}]->(d)
     , (a)-[ae:DOOR {key: 'D'}]->(e)
     , (b)-[bc:DOOR]->(c)
     , (c)-[ca:DOOR]->(a)
     , (e)-[ed:DOOR]->(d)
     , (d)-[df:DOOR {key: 'E'}]->(f)
     , (d)-[dc:HIDDEN]->(c)
RETURN a,b,c,d,e,f;

// find the two rooms and all paths between them
MATCH path = (:Room {name:"A"})-[:DOOR*0..]->(:Room {name:"D"})
// take path, keys and doors as collections
WITH path, EXTRACT(room IN nodes(path) | COALESCE(room.key,-1)) AS keys, rels(path) AS doors
// condition for all doors
// either no lock or the lock-number is in the collection of keys collected so far
WHERE ALL(idx IN RANGE(0,size(doors)-1) WHERE NOT doors[idx].key OR doors[idx].key IN keys[0..idx])
// return the path(s)
RETURN path;