Counterfeit Monkey — 199 of 292

Book 2 - Hashing

[ While it is possible to do the object comparisons for this game entirely in Inform 7 native code, doing so becomes very computationally expensive, especially for ambitious tools such as the anagramming gun: we are manipulating indexed text and lists multiple times for each of hundreds of objects.

So to get around this, we start the game by caching information about each object in a way that allows us to filter later what comparisons we're going to need to make.

For each object, we assign a code that is a bitmap indicating which letters of the alphabet appear in that object. (Not how many times those letters appear or in what order or even how many letters there are -- so BED and BEDE would have the same hash code, as would ABED and BEAD, and so on. Moreover, bitwise comparisons allow us to and/or these lists of letters so that we can see that BEND with N removed does have the same letters as BED, all without having to manipulate any indexed text.)

The point of this is to be able to rapidly eliminate the majority of comparisons without ever having to do the more expensive analysis of specific letters.

Thanks to Graham Nelson for technical assistance on this. ]

A thing has a number called the hash code.

A room has a number called the hash code.

When play begins (this is the initialize hash codes rule):

repeat with item running through things which are not facts:

let T be indexed text;

let T be "[item]";

now the item is unseen;

now the hash code of the item is letter-hash of T;

repeat with item running through rooms:

let T be indexed text;

let T be "[item]";

now the hash code of the item is letter-hash of T.

To reset hash code of (item - a thing):

let T be indexed text;

let T be "[item]";

now the hash code of the item is letter-hash of T.

To say (N - number) as letter-hash:

(- ShowLetterHash({N}); -).

To decide which number is the letter-hash of (T - indexed text):

(- LetterHash({T}) -).

To decide which number is (X - number) with (Y - number) added:

(- ({X} | {Y}) -).

To decide which number is (X - number) with (Y - number) removed:

(- ({X} & (~{Y})) -).

To demonstrate letter-hash of (T - indexed text):

say "The hash of <[T]> is [letter-hash of T as letter-hash].";

[When play begins:

demonstrate letter-hash of "bed";

demonstrate letter-hash of "bede";

demonstrate letter-hash of "temptress";

demonstrate letter-hash of "empress";

let t be the letter-hash of "temptress";

let r be the letter-hash of "t";

say "temptress with t removed: [t with r removed as letter-hash]."; ]

Include (-

[ LetterHash T i n c d b m;

n = IT_CharacterLength(T);

for (i=0: i<n: i++) {

d = -1;

c = BlkValueRead(T, i);

if ((c >= 'a') && (c <= 'z')) d = c-'a';

if ((c >= 'A') && (c <= 'Z')) d = c-'A';

if (d >= 0) {

b = 1;

while (d > 0) { d--; b = b*2; }

m = m | b;

}

}

return m;

];

[ ShowLetterHash h i b;

for (i=0, b=1; i<26; i++, b=b*2) {

if (h&b) print "1"; else print "0";

}

];

-);