Download code

Jump to: navigation, search

Back to Dijkstra's_algorithm_(Inform_7)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

dijkstra.inform7

  1 [ The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Dijkstra's_algorithm_(Inform_7)?oldid=19116
 14 ]
 15 
 16 "Dijkstra's Algorithm" by Dave
 17 
 18 A node is a kind of thing.
 19 Contact relates nodes to each other.
 20 The verb to contact (he contacts, they contact, he contacted, it is contacted, he is contacting) implies the contact relation.
 21 The current node is a node that varies.
 22 
 23 A node can be found, examined, or unreached.
 24 A node has a number called the total distance.  
 25 Definition: a node is near if its total distance is 10 or less.
 26 
 27 Following relates various nodes to one node (called the precedent).
 28 The verb to follow (he follows, they follow, he followed, it is followed, he is following) implies the following relation.
 29 Every turn: run Dijkstra's algorithm.
 30 
 31 To run Dijkstra's algorithm:
 32 	initialize Dijkstra's algorithm from the current node;
 33 	while some of the nodes are examined begin;
 34 		continue Dijkstra's algorithm;
 35 	end while.
 36 	
 37 To initialize Dijkstra's algorithm from (n - a node):
 38 	clear the state;
 39 	now n is examined;
 40 	change the total distance of n to 0.
 41 	
 42 To continue Dijkstra's algorithm:
 43 	let n be the nearest examined node;
 44 	now n is found;
 45 	repeat with m running through the nodes contacting n begin;
 46 		examine m from n;
 47 	end repeat.
 48 
 49 To examine (m - a found node) from (n - a node): now m is found.
 50 
 51 To examine (m - an unreached node) from (n - a node):
 52 	now m is examined;
 53 	change the total distance of m to the extension of n to m;
 54 	now m follows n.
 55 	
 56 To examine (m - an examined node) from (n - a node):
 57 	let d be the extension of n to m;
 58 	if the total distance of m > d begin;
 59 		change the total distance of m to d;
 60 		now m follows n;
 61 	end if.
 62 To clear the state:
 63 	repeat with m running through nodes begin;
 64 		now m is unreached;
 65 		now m does not follow anything;
 66 	end repeat;
 67 
 68 To decide what number is the extension of (n - a node) to (m - a node):
 69 	decide on the total distance of n + the distance between m and n.
 70 Barcelona, Geneve, Lausanne, London, Marseille, Narbonne, Oxford, Paris, and Toulouse are nodes.
 71 
 72 Table of Intercity Distances
 73 src	dst	distance
 74 Barcelona	Narbonne	250
 75 Geneve	Lausanne	64
 76 Geneve	Marseille	260
 77 Geneve	Narbonne	550
 78 Geneve	Paris	540
 79 Geneve	Toulouse	700
 80 Lausanne	Paris	536
 81 London	Oxford	95
 82 London	Paris	440
 83 Marseille	Narbonne	260
 84 Narbonne	Toulouse	150
 85 Paris	Toulouse	680
 86 
 87 To decide what number is the distance between (n - a node) and (m - a node):
 88 	repeat through the Table of Intercity Distances begin;
 89 		if the src entry is n and the dst entry is m, decide on the distance entry;
 90 		if the src entry is m and the dst entry is n, decide on the distance entry;
 91 	end repeat.
 92 	
 93 Definition: a node is initial if it is the current node.
 94 To slide the marker from (n - an initial node):
 95 	say "You take the marker from [n] and slide it".
 96 To slide the marker from (n - a node):
 97 	slide the marker from the precedent of n;
 98 	say " to [n]".
 99 To slide the marker to (n - a node):
100 	slide the marker from the precedent of n;
101 	say ", winding up at [n].".
102 		
103 planning is an action applying to one visible thing.
104 understand "[a node]" as planning.
105 check planning:
106 	if the current node is the noun, say "The marker is already at [the current node]." instead.
107 carry out planning: 
108 	slide the marker to the noun;
109 	change the current node to the noun.	
110 	
111 The Map Room is a room.
112 "You are looking at a roadmap centered on the south of France[line break]Say 'relations' to examine the current graph state[line break]Say 'city name' to plan a trip from [the current node].". 
113 The marker and the roadmap are scenery in the Map Room.
114 
115 When play begins:
116 	repeat through the Table of Intercity Distances begin;
117 		now the src entry contacts the dst entry;
118 		now the dst entry contacts the src entry;
119 	end repeat;
120 	repeat with n running through the nodes begin;
121 		move n to the Map Room;
122 	end repeat;
123 	change the current node to Barcelona;
124 	run Dijkstra's algorithm.
125 	
126 Test me with "barcelona/lausanne/barcelona/paris/marseille"


hijacker
hijacker
hijacker
hijacker