Download code

From LiteratePrograms

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 [ Copyright (c) 2010 the authors listed at the following URL, and/or
  2 the authors of referenced articles or incorporated external code:
  3 http://en.literateprograms.org/Dijkstra's_algorithm_(Inform_7)?action=history&offset=20070723002244
  4 
  5 Permission is hereby granted, free of charge, to any person obtaining
  6 a copy of this software and associated documentation files (the
  7 "Software"), to deal in the Software without restriction, including
  8 without limitation the rights to use, copy, modify, merge, publish,
  9 distribute, sublicense, and/or sell copies of the Software, and to
 10 permit persons to whom the Software is furnished to do so, subject to
 11 the following conditions:
 12 
 13 The above copyright notice and this permission notice shall be
 14 included in all copies or substantial portions of the Software.
 15 
 16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 19 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 20 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 21 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 22 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 23 
 24 Retrieved from: http://en.literateprograms.org/Dijkstra's_algorithm_(Inform_7)?oldid=10731
 25 ]
 26 
 27 "Dijkstra's Algorithm" by Dave
 28 
 29 A node is a kind of thing.
 30 Contact relates nodes to each other.
 31 The verb to contact (he contacts, they contact, he contacted, it is contacted, he is contacting) implies the contact relation.
 32 
 33 The current node is a node that varies.
 34 
 35 A node can be found, examined, or unreached.
 36 A node has a number called the total distance.  
 37 Definition: a node is near if its total distance is 10 or less.
 38 
 39 Following relates various nodes to one node (called the precedent).
 40 The verb to follow (he follows, they follow, he followed, it is followed, he is following) implies the following relation.
 41 
 42 Every turn: run Dijkstra's algorithm.
 43 
 44 To run Dijkstra's algorithm:
 45 	initialize Dijkstra's algorithm from the current node;
 46 	while some of the nodes are examined begin;
 47 		continue Dijkstra's algorithm;
 48 	end while.
 49 	
 50 To initialize Dijkstra's algorithm from (n - a node):
 51 	clear the state;
 52 	now n is examined;
 53 	change the total distance of n to 0.
 54 	
 55 To continue Dijkstra's algorithm:
 56 	let n be the nearest examined node;
 57 	now n is found;
 58 	repeat with m running through the nodes contacting n begin;
 59 		examine m from n;
 60 	end repeat.
 61 
 62 To examine (m - a found node) from (n - a node): now m is found.
 63 
 64 To examine (m - an unreached node) from (n - a node):
 65 	now m is examined;
 66 	change the total distance of m to the extension of n to m;
 67 	now m follows n.
 68 	
 69 To examine (m - an examined node) from (n - a node):
 70 	let d be the extension of n to m;
 71 	if the total distance of m > d begin;
 72 		change the total distance of m to d;
 73 		now m follows n;
 74 	end if.
 75 
 76 To clear the state:
 77 	repeat with m running through nodes begin;
 78 		now m is unreached;
 79 		now m does not follow anything;
 80 	end repeat;
 81 
 82 To decide what number is the extension of (n - a node) to (m - a node):
 83 	decide on the total distance of n + the distance between m and n.
 84 
 85 Barcelona, Geneve, Lausanne, London, Marseille, Narbonne, Oxford, Paris, and Toulouse are nodes.
 86 
 87 Table of Intercity Distances
 88 src	dst	distance
 89 Barcelona	Narbonne	250
 90 Geneve	Lausanne	64
 91 Geneve	Marseille	260
 92 Geneve	Narbonne	550
 93 Geneve	Paris	540
 94 Geneve	Toulouse	700
 95 Lausanne	Paris	536
 96 London	Oxford	95
 97 London	Paris	440
 98 Marseille	Narbonne	260
 99 Narbonne	Toulouse	150
100 Paris	Toulouse	680
101 
102 To decide what number is the distance between (n - a node) and (m - a node):
103 	repeat through the Table of Intercity Distances begin;
104 		if the src entry is n and the dst entry is m, decide on the distance entry;
105 		if the src entry is m and the dst entry is n, decide on the distance entry;
106 	end repeat.
107 	
108 
109 Definition: a node is initial if it is the current node.
110 To slide the marker from (n - an initial node):
111 	say "You take the marker from [n] and slide it".
112 To slide the marker from (n - a node):
113 	slide the marker from the precedent of n;
114 	say " to [n]".
115 To slide the marker to (n - a node):
116 	slide the marker from the precedent of n;
117 	say ", winding up at [n].".
118 		
119 planning is an action applying to one visible thing.
120 understand "[a node]" as planning.
121 check planning:
122 	if the current node is the noun, say "The marker is already at [the current node]." instead.
123 carry out planning: 
124 	slide the marker to the noun;
125 	change the current node to the noun.
126 	
127 	
128 The Map Room is a room.
129 "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].". 
130 The marker and the roadmap are scenery in the Map Room.
131 
132 When play begins:
133 	repeat through the Table of Intercity Distances begin;
134 		now the src entry contacts the dst entry;
135 		now the dst entry contacts the src entry;
136 	end repeat;
137 	repeat with n running through the nodes begin;
138 		move n to the Map Room;
139 	end repeat;
140 	change the current node to Barcelona;
141 	run Dijkstra's algorithm.
142 	
143 Test me with "barcelona/lausanne/barcelona/paris/marseille"
144


Retrieved from "http://en.literateprograms.org/Special:Downloadcode"
Views
Personal tools