Inform 7 Home Page / Documentation
§21.11. Variations: arrays, logs, queues, stacks, sets, sieves and rings
Lists are highly adaptable, and many other collection-like constructions can be made using them. This section introduces no new material, but simply suggests some of the variations which are possible.
1. The traditional computing term array means a list of values accessed by their entry numbers, often used in mathematical computations. The difference between an array and a list is mostly one of attitude, but usually arrays are fixed in length whereas lists can expand or contract.
2. A log is a list which records the most recently arrived values, but does not allow itself to grow indefinitely. In the following, which remembers the seven most recently taken items, new values arrive at the end while old ones eventually disappear from the front:
The most-recently-taken list is a list of objects that varies.
Carry out taking something (called the item):
truncate the most-recently-taken list to the last 6 entries;
add the item to the most-recently-taken list.
After taking:
say "Taken. (So, your recent acquisitions: [most-recently-taken list].)"
Note that the most-recently-taken list begins play as the empty list, grows as the first few items are taken, but then stabilises at length 7 thereafter. If we need to remember recent history, but only recent history, then a log is better than a list which can grow indefinitely, because there is no risk of speed reduction or memory exhaustion in a very long story.
3. A queue is a list of values which are waiting for attention. New values join at the back, while those being dealt with are removed from the front (whereupon the whole queue moves up one). An empty queue means that nobody is waiting for attention: but there is, in principle, no upper limit to the size of a queue, as anyone who has tried to make a couchette reservation at Roma Termini will know.
Queues typically form when two independent processes are at work, but going at different or variable speeds. An empty queue looks just like any other list:
The queue is a list of objects that varies.
(Invariably people, in what follows, but we'll make it a "list of objects" to allow for other possibilities too.) Once we identify a "new customer", we can join him to the queue thus:
add the new customer to the queue;
The process of serving the customers needs to make sure there is actually somebody waiting in the queue before it does anything:
Every turn when the number of entries in the queue is not 0:
let the next customer be entry 1 of the queue;
say "[The next customer] is served and leaves.";
remove entry 1 from the queue.
Of course queues can also be constructed which empty from other positions, rather than the front: or we could make what computer scientists sometimes call a deque, a "double-ended queue" where new values arrive at both ends.
4. A stack is like a queue except that values arrive at, and are removed from, the same end. Stacks are slightly faster if the active end is the back rather than the front, though this will only be noticeable if they grow quite large.
To put a value V onto a stack S (which is known as "pushing") is simple:
add V to S;
And to remove a value from the top of the stack (which is known as "pulling"):
let N be the number of entries in S;
let V be entry N of S;
remove entry N from S;
Note that the middle line, accessing entry N, will fail if N = 0, that is, if the stack is empty: Inform's list routines will produce a run-time problem message.
Stacks are useful if some long-term process is constantly being interrupted by newer and more urgent demands, but they can also be used in planning. If a character has a long-term goal, which needs various short-term goals to be achieved along the way, then a stack can represent the goals currently being pursued. The top of the stack represents what the character is trying to achieve now. If the character realises that it needs to achieve something else first, we put that new goal onto the top of the stack, and it becomes the new current goal. When the character completes a task, it can be removed, and we can go back to trying to finish whatever is now on top. When the stack is empty, the character has achieved the original goal.
5. Notoriously, set has 464 distinct meanings in the Oxford English Dictionary, making it the single most ambiguous word in the language. Here we mean not the home of a badger or the Egyptian god of the desert, but the mathematical sense: a collection of values (sometimes called "elements") without duplicates, and which is normally written in brace notation and in some natural order for the reader's convenience.
The trick here is to maintain the principle that, at all times, our list is sorted in order and contains no duplicates. To provide an example, we start with two sets of numbers:
let S be {2, 4, 8, 16, 32, 64};
let T be {2, 4, 6, 10};
Here we add an element to T:
add 8 to T, if absent; sort T;
The "if absent" clause ensures that no duplicate can occur, and by sorting T afterwards, we maintain the principle that a set must remain in order - so T is now {2, 4, 6, 8, 10}, not {2, 4, 6, 10, 8}. (Inform's sorting algorithm is fast on nearly-sorted lists, so frequent sorting is not as inefficient as it might look.)
We next take the union of T and S, that is, the set containing everything which is in either or both:
let U be S; add T to U, if absent; sort U;
This makes U = {2, 4, 6, 8, 10, 16, 32, 64}, and once again no duplicates occur and we preserve the sorting. The intersection of T and S, the set of elements in both of them, is a little trickier:
let I be T;
repeat with the element running through T:
if the element is not listed in S, remove the element from I.
(Faster methods could be devised which exploit the sortedness of T and S, but are not worth it for shortish lists.) This produces I = {2, 4, 8}. Lastly, we can form the set difference, consisting of those elements which are in S but not in T:
let D be S; remove T from D, if present;
Here, as with intersection, since all we do is to strike out unwanted elements, the surviving ones remain in order and there is no need to sort when we are finished. This produces D = {16, 32, 64}.
6. A sieve is used to make a complicated choice where there are many constraints, by ruling out impossible cases to see what is left. The term derives from the kitchen utensil (for sieving fine grains of flour), but via the name of the "sieve of Eratosthenes", an ancient Greek method for determining the prime numbers.
Using a sieve is much like using a set, and the difference is mainly one of outlook - we are interested in what does not belong, rather than what does.
7. A ring is not so much a row of values, more a circle, with the last and first entries thought of as adjacent. One position is usually thought of as special, and is the place where new items are added: this may as well be entry 1. For instance, to add "new item" to the ring:
add the item at entry 1 in the ring;
To set "item" to the frontmost value and extract it from the ring:
let the item be entry 1 of the ring;
remove entry 1 from the ring;
And we can rotate the ring in either direction, making a different entry the new entry 1 and therefore the new frontmost value:
rotate the ring;
rotate the ring backwards;
A last note to conclude the chapter on lists. Lists, like almost all other values in Inform, can be passed to phrases as parameters. However, note that they are genuine values, not what some programming languages call "references" or "pointers". So the following:
To mess with (L - a list of numbers):
add 7 to L, if absent.
does nothing, in practice. If given a list, it adds 7 to the list, but then throws it away again, so the longer list is never seen; it's exactly like
To mess with (N - a number):
now N is 3.
which can never affect anything other than its own temporary value "N", which expires almost immediately in any case.
If we want a phrase which changes a list in a useful way and gives it back to us, we need a phrase which both takes in and gives back:
To decide which list of numbers is the extended (L - a list of numbers):
add 7 to L, if absent;
decide on L.
And then, for example -
the extended { 2, 4, 6 };
produces:
{ 2, 4, 6, 7 }
|
|
 ExampleCircle of Misery
Retrieving items from an airport luggage carousel is such fun, how can we resist simulating it, using a list as a ring buffer?
|
|
The only point we need to be careful about is that the carousel is simulated twice over, in the following text: once in the built-in way that objects are inside other objects, so that the luggage items are objects contained in the carousel object; but then again by the "circle of misery" list, a ring buffer keeping track of what order things are in. We need to be careful that these two records do not fall out of synchrony: anything put into the carousel must be added to the list, anything taken out must be removed. (In fact we forbid things to be added, for simplicity's sake.)
"Circle Of Misery"
Luggage item is a kind of thing. The blue golf bag, the leopardskin suitcase, the green rucksack and the Lufthansa shoulder-bag are luggage items.
Heathrow Baggage Claim is a room. The carousel is a container in Heathrow. "The luggage carousel, a scaly rubbered ring, does for the roundabout what Heathrow Airport does for the dream of flight: that is, turns the purest magic into the essence of boredom, only with extra stress. [if the number of entries in the circle of misery is 0]For once it stands idle. Perhaps it's broken.[otherwise]The baggage approaching you now: [the circle of misery with indefinite articles]."
The circle of misery is a list of objects that varies.
When play begins:
now all the luggage items are in the carousel;
add the list of luggage items to the circle of misery.
The list "circle of misery" is our ring, in which entry 1 is considered to be the position of whichever bag is currently frontmost. And here it goes, round and round:
Every turn when the number of entries in the circle of misery is not 0:
rotate the circle of misery;
let the bag be entry 1 of the circle of misery;
say "The carousel trundles on, bringing [a bag] to within reach."
After taking a luggage item (called the bag):
remove the bag from the circle of misery, if present;
say "Taken."
Before doing something with a luggage item (called the bag) which is in the carousel:
if the bag is not entry 1 of the circle of misery, say "[The bag] is maddeningly out of range. You'll have to wait for it to come round." instead.
Instead of inserting something into the carousel, say "In recent years, the authorities have tended to frown upon depositing bags in random places at airports."
Test me with "get suitcase / get suitcase / get suitcase / get suitcase / look / get golf bag / look / get golf bag".
|
|
ExampleEyes, Fingers, Toes
A safe with a multi-number combination, meant to be dialed over multiple turns, is implemented using a log of the last three numbers dialed. The log can then be compared to the safe's correct combination.
|
|
It is not difficult to implement a safe which can be set to a single number to open; but a more common scenario in the real world is for the safe to open on a sequence of numbers when they have been dialed in the right order.
For IF, this means that we have to keep running track of the last N digits the player has dialed, dropping the first digit and adding a new one to the end each time the player re-dials the safe. This is a perfect occasion for lists:
"Eyes, Fingers, Toes"
The Addams Wine Cellar is a room. It contains a closed lockable locked container called a safe.
The safe has a list of numbers called the current combination.
The safe has a list of numbers called the true combination. The true combination of the safe is {2, 10, 11}.
Understand "set [something] to [a number]" as setting it numerically to. Setting it numerically to is an action applying to one thing and one number.
Instead of examining the safe:
if the number of entries in the current combination of the safe is 0,
say "You haven't dialed the safe to any combination yet.";
otherwise say "You have dialed the safe to [the current combination of the safe].".
Check setting something numerically to (this is the block setting numerically rule):
say "[The noun] cannot be set."
Instead of setting the safe numerically to the number understood:
truncate the current combination of the safe to the last 2 entries;
add the number understood to the current combination of the safe;
if the safe is locked and the current combination of the safe is the true combination of the safe:
say "You dial [the number understood], and [the safe] gives a joyous CLICK.";
now the safe is unlocked;
otherwise if safe is unlocked and the safe is closed and the current combination of the safe is not the true combination of the safe:
say "You spin the dial, and [the safe] snicks locked.";
now the safe is locked;
otherwise:
say "You dial [the number understood] on the safe."
Test me with "x safe / set safe to 10 / x safe / set safe to 29 / x safe / set safe to 2 / x safe / set safe to 10 / x safe / set safe to 11 / open safe / set safe to 14 / close safe / set safe to 15 / open safe".
Fibonacci (a posthumous nickname) spread Arabic mathematical learning across Europe in the 13th century, and it's curious that his name lives on only for a single sequence.
"The Fibonacci Sequence"
Pisa is a room. Leonardo Fibonacci is a man in Pisa. "The modest Italian mathematician, Leonardo Fibonacci (1170-1250), beams at you."
Sequencing is an action applying to one number. Understand "sequence [number]" as sequencing.
Instead of sequencing, say "You make a feeble attempt, sketching in the sand, but it goes nowhere. Leonardo is sympathetic. 'Often goes wrong for me, too, actually. I didn't even invent the thing - the ancient Indians knew about it first.'"
Persuasion rule for asking Leonardo to try sequencing: persuasion succeeds.
Report Leonardo sequencing:
let N be the number understood;
say "Leonardo scratches his head and makes self-deprecating remarks, before coming up with [the first N terms of the Fibonacci sequence]."
An array need not be fixed in length, as the following example shows:
To decide what list of numbers is the first (F - a number) terms of the Fibonacci sequence:
let the Fibonacci sequence be {1, 1};
let N be 3;
while N < F:
let the last term be entry (N - 1) of the Fibonacci sequence;
let the penultimate term be entry (N - 2) of the Fibonacci sequence;
let the next term be the last term plus the penultimate term;
add the next term to the Fibonacci sequence;
increment N;
decide on the Fibonacci sequence.
Test me with "sequence 20 / leonardo, sequence 20".
The result of "the first 20 terms of the Fibonacci sequence" is "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584 and 4181". This is a sequence which has a knack of turning up in odd places - it was found in the 1970s to be related to the rings of florets in a sunflower, for instance - and here it is in a book about interactive fiction.
|
|
ExampleI Didn't Come All The Way From Great Portland Street
In this fiendishly difficult puzzle, which may perhaps owe some inspiration to a certain BBC Radio panel game (1967-), a list is used as a set of actions to help enforce the rule that the player must keep going for ten turns without hesitation, repetition, or deviating from the subject on the card.
|
|
There is very little to this, in fact. The tricky rule to enforce is Repetition: the player is forbidden to repeat any previously tried action. We keep track of this by keeping a set of past actions, which for want of a better term is called the "tally". All we need to do is:
if the current action is listed in the tally, challenge for "Repetition of [the current action]!";
otherwise add the current action to the tally.
Note that the tally can never contain duplicates, and that when, at the end of the round, we print it out, we sort it first - this makes a more natural-looking sentence. (Sorting a list of actions uses the natural order for actions: compare the sequence on the Actions page of the Index.) The full text, then, is:
"I Didn't Come All The Way From Great Portland Street"
The Paris Theatre is a room. An instrument is a kind of thing. The violin, the tuba, the xylophone and the triangle are instruments. The violin is inside the case. The tuba, the xylophone, the radish, the case, the bust of Nicholas Parsons, the purple felt hat and the triangle are in the Paris Theatre.
The Round is a scene. The Round begins when play begins. The Round ends when the turn count is 10.
The tally is a list of stored actions that varies.
When the Round begins:
say "'And the subject on the card is... musical instruments. Will you carry out for us something to do with that, please, for ten turns starting - now!'"
When the Round ends:
sort the tally;
say "Phweeep![paragraph break]'So, when the whistle goes ten turns are up, you get a point for acting when the whistle blows, and in that round you entertained us by [the tally], and you also get a bonus point for keeping going until the whistle went.'";
end the story finally.
To challenge for (infraction - text):
say "Bzzzzt! 'And [one of]Clement Freud[or]Derek Nimmo[or]Kenneth Williams[or]Peter Jones[at random] has challenged.'[paragraph break]'[infraction]'[paragraph break]'Well, as it's your first time playing the game, and the audience was enjoying your contribution so much, I will disallow the challenge, you have [10 minus the turn count] turn[s] left on musical instruments, starting... now!"
Before doing something:
if the current action is listed in the tally, challenge for "Repetition of [the current action]!" instead;
otherwise add the current action to the tally;
if waiting, challenge for "Hesitation!" instead;
if not looking and not waiting and the noun is not an instrument and the second noun is not an instrument, challenge for "Deviation!" instead.
Test me with "look / wait / examine bust / take tuba / get triangle / hit xylophone / get tuba / examine tuba / get violin".
(The Paris Theatre in Lower Regent Street, London, was for many years the home of BBC radio panel games.)
First, to set the scene:
"Lugubrious Pete's Delicatessen"
The Supermarket is west of the Delicatessen Counter. Lugubrious Pete is in the Delicatessen. "Lugubrious Pete, dolefully slicing meats and cheeses, serves at the counter." Alice, Beth, Gemma, Delia, and Eliza are women in the Supermarket.
The deli queue is a list of objects that varies.
Two processes compete here: one that fills the queue, the other which will empty it. The first process is the one which brings shoppers in to the counter, joining the back of the queue, which is where "add ... to ..." puts new entries by default:
Every turn when a woman is in the Supermarket and a random chance of 2 in 3 succeeds (this is the customer arriving rule):
let the customer be a random woman in the Supermarket;
now the customer is in the Delicatessen;
if the player is in the Supermarket, say "[The customer] walks into the Delicatessen.";
if the player is in the Delicatessen, say "[The customer] comes in from the Supermarket, and [if the number of entries in the deli queue is 0]can't believe her luck. The counter is free![otherwise]resignedly queues behind [the deli queue].";
add the customer to the deli queue.
The competing process is the one which serves shoppers and thus gets rid of them again: unfortunately, it is slower. But Pete is fair if inefficient, and serves the customers in strict order of arrival. Each served customer is removed from the front of the list, and the others therefore all move up a place.
Every turn when the number of entries in the deli queue is not 0 and a random chance of 1 in 3 succeeds (this is the customer being served rule):
let the customer be entry 1 of the deli queue;
if the player is in the Delicatessen, say "Pete gives a droopy expression as he serves [customer], who nevertheless brightens and leaves.";
if the player is in the Supermarket, say "[customer] emerges cheerfully from the Delicatessen Counter, and goes about her regular shopping.";
now the customer is in the Supermarket;
remove entry 1 from the deli queue.
Instead of waiting in the Delicatessen when the number of entries in the deli queue is not 0, say "Time passes, for [deli queue] quite as much as for yourself."
Test me with "wait / wait / wait / east / wait / wait / wait / wait / wait".
That completes the example, but here is a variation to show that queues need not empty from the front. The Deli already looks a pretty sexist establishment, with the customers all being women, but it is about to get a whole lot worse:
Modesty is a kind of value. The modesties are positively prim, buttoned up, modest, flirty, revealing and downright immodest. Every woman has a modesty. Alice is positively prim. Beth is downright immodest. Gemma is modest. Delia is flirty. Eliza is revealing.
We could then rewrite the service rule like so:
Every turn when the number of entries in the deli queue is not 0 and a random chance of 1 in 3 succeeds (this is the customer being served rule):
let Pete's preference be the deli queue;
sort Pete's preference in reverse modesty order;
let the customer be entry 1 of Pete's preference;
let the first in line be entry 1 of the deli queue;
if the player is in the Delicatessen, say "[if the customer is the first in line]Pete gives a droopy expression as he serves [the customer], who nevertheless brightens and leaves.[otherwise]Outrageously, Pete scans the queue, notices [the customer] in her [modesty of the customer] clothes, and serves her next, while [the first in line] glares at him.";
if the player is in the Supermarket, say "[The customer] emerges cheerfully from the Delicatessen Counter, and goes about her regular shopping.";
now the customer is in the Supermarket;
remove the customer from the deli queue.
It is now heartbreakingly difficult for Alice to obtain her sliced chorizo sausage.
In the words of Wikipedia: "Eratosthenes of Cyrene (Greek Eρατοσθένης; 276 BC-194 BC) was a Greek mathematician, poet, athlete, geographer and astronomer." In the words of Tom Lehrer: "It's people like that who make you realise how little you've achieved in life."
A prime number is a number greater than 1 which is not a multiple of anything, so we can find the primes by starting with all the numbers and sieving out all the multiples of 2, then all the multiples of 3, and so on. Here we make our sieve of the unacceptable numbers (the "composite" or non-prime ones) first, then form a list of all the numbers, then sieve out the composites: what are left must be the primes.
"Sieve of Eratosthenes"
Alexandria is a room. Eratosthenes is a man in Alexandria. "The haughty Greek mathematician, Eratosthenes, glowers at you."
Sieving is an action applying to one number. Understand "sieve [number]" as sieving.
Instead of sieving, say "You make a feeble attempt, sketching in the sand, but it goes nowhere. Eratosthenes smirks. 'I expect your friends call you gamma, then?'"
Persuasion rule for asking Eratosthenes to try sieving: persuasion succeeds.
Report Eratosthenes sieving:
let N be the number understood;
let the composites be a list of numbers;
let I be 2;
while I times I is at most N:
if I is not listed in the composites:
let J be I times 2;
while J is at most N:
add J to the composites, if absent;
increase J by I;
increment I;
sort the composites;
let the primes be a list of numbers;
repeat with P running from 2 to N:
add P to the primes;
remove the composites from the primes;
say "Eratosthenes sketches lines in the sand with the air of much practice. 'The primes up to [N] are [the primes]. The composites are [the composites].'"
Test me with "sieve 10 / eratosthenes, sieve 100".
While this could all be done more efficiently with an array, that's only because what we are sieving are numbers: sieving is a technique which can be used for non-numerical decisions, too.
Suppose the player's mother is supposed to be cleaning the living room, but she can be interrupted by the need to pick up things the player has dropped. New tasks are added to the end of her "current plan" list; every turn, she attempts to do whatever is the last entry on that list.
"Your Mother Doesn't Work Here"
A person has a list of stored actions called the current plan.
Every turn:
repeat with culprit running through people who are not the player:
if the number of entries in current plan of the culprit is greater than 0:
let N be the number of entries in the current plan of the culprit;
try entry N of the current plan of the culprit;
remove entry N from the current plan of the culprit.
The Living Room is a room. It contains a somewhat muddy Persian rug. Your mother is a woman in the Living Room.
West of the Living Room is the Kitchen.
Instead of your mother rubbing the rug:
say "Your mother scrubs the stained areas of the rug, muttering to herself."
Instead of taking something:
say "Nah, Mom'll get that."
Report your mother taking something:
say "Your mother picks up [the noun][one of], sighing deeply[or], jaw tight[or], with assorted comments on your manners[or]; to judge from her comments, she is also indulging in a pleasant fantasy about Swiss boarding schools[stopping]." instead.
When play begins:
add mother going west to the current plan of mother;
add mother rubbing the rug to the current plan of mother.
Every turn:
if mother is not in the Living Room, end the story finally.
Carry out dropping something:
add mother taking the noun to the current plan of mother.
The player carries some dirty socks, some dirty shoes, a dirty hat, a pair of dirty trousers, and a backpack.
Test me with "drop socks / z / drop shoes / drop hat / drop all / z / z".
As goal-seeking goes, this is fairly rudimentary; "Boston Cream" provides an alternative (and slightly more sophisticated approach), but for really complex goal-seeking characters, it is probably best to turn to the character extensions designed for Inform.
