Letters on dice problem
        |
The letters-on-dice puzzle
During the first year of my degree, I was lucky enough to be studying Pascal and to be a cocky sod. Therefore, when we were handed a sheet with a bunch of questions on, and we only had to do one, I automatically gravitated to the hardest. God knows why.
The problem
Take four dice and the 26 letters of the alphabet. Remove the letters Q and Z, then stick the rest of the letters on the dice at random. Now, throw the dice and make four-letter words with the letters you roll.
Given a list of four-letter words made with a particular set of dice, write a computer program to solve the puzzle, deducing which letters are on which dice.
The sample list of words supplied with the problem was:
sale fens axes wars hear crab veil gays duck spey brow rack char pugh tare duct pile joys ripe
General strategies
There are a quite a few different ways to approach this problem. Several of these are outlined below.
The first, and perhaps most obvious, is to exploit the following logical facts:
- If two words have three letters in common, the odd letters in each case must be on the same dice.
- If two letters are on the same dice, then new words can be added to the word list by substituting one for the other throughout the existing wordlist.
This leads to a simple approach to the problem: look throughout the word list, examining each possible pairing of words for cases where only one letter is different, and thus gradually fill in the dice arrangement. However, this method is quite laborious to complete by hand, and rather tricky to encode; the problem is that the words are best handled as sets, but under Pascal this does not permit direct access to the components, which is also required. It means that to encode this algorithm, some fancy footwork is necessary to handle the data structures necessary.
A second method is to start with a 24x24 array of booleans, all initially true, representing the possible connections between letters. So, for example, if row 1 has elements 2, 4 and 6 only set to true, that represents the letter A sharing a dice with the letters B,D and F.
With this structure, loop over all the words and eliminate as appropriate; for example, for the word AXES, set the array elements corresponding to (A,X), (A,E), (A,S), (X,E), and so on to false.
A sample program using this algorithm was written; however, it does not make full use of the information in the wordlist and so if the wordlist is too short - as in the example considered below - then a solution cannot be reached.
The third method that I considered was as follows: Choose a root word - more on this later - and allocate this word’s four letters to the dice 1-4. Run through the wordlist and replace each occurrence of these letters by the corresponding dice number. eg. Choose 'sale' as the root word; then 'sale' become '1234' and 'axes' becomes 'ax24'.
Then, apply the following constraints until the problem is solved:
- Any word in the word list which consists of only one letter with three digits means that letter must be on the dice that isn’t represented, eg. '1x24' means x must be on dice 3. This change can then be applied to all the rest of the words in the wordlist.
- If a word in wordlist has some numbers and some letters, then the letters can't be on the dice that are listed there eg. 'ax24' means that neither 'a' nor 'x' can be present on dice 2 or 4.
- Initially, each letter can appear on any die. If, through successive application of (2), the number of possible dice for any one letter is reduced to 1, it follows that the letter must be on that dice. Again, this change can then be applied throughout the wordlist.
This algorithm has also been coded; unlike the second algorithm listed earlier, this one produces an answer, subject to one caveat: the initial, root word.
If the root word is chosen well, then the algorithm produces a solution. 'Well' in this context means it should be the word in the word list which contains the most frequency letters in the world list as a whole. Consider the example runs; this algorithm can solve the puzzle as completely as possible if 'sale' is the root word but not is 'fens' is the root. Although it is not considered here in any detail, it would be possible to automate this process by counting letter frequencies assigning a score to each word based on whether or not it contains several frequent letters. The program below is naive to these details and simply takes the first word in the word list as the root word.
Notes on implementaion
Primary data structures consist of two arrays, one called dice which holds the information for what dice holds what letters (24x4 array), and one called words which simply holds the word list in an array of strings.
The main bulk of the program is executed by a repeat...until loop which uses a boolean flag, called StateHasChanged, as it’s escape condition. This flag is initially set to false at the beginning of each iteration of the loop and then set to true if any data has been changed; in this way, the program senses if no more deduction can be made and quits.
The three constraints are applied as three procedures, CheckNumberOfDigits, EliminatePossibilities and CheckLetterAssignments, which correspond to the three constraints above. During each loop, CheckNumberOfDigits and EliminatePossibilities are run once for each word in the word list, and the finally CheckLetterAssignments is run to 'clean up' after EliminatePossibilities.
Most of the rest of the code consists of small support routines to these procedures. The most important of these is Propagate; given the information that a certain position in a given word is on a particular dice, it spreads this information throughout the wordlist.
Note that both of the programs presented here have a 'verbose' switch, which here takes the form of a booelan value set in the first line of the main program code. If verbose is on, the program prints more information about it’s inner workings; this is particularly useful for the second program, as it allows the program’s logical workings to be read as a debugging aid.
A solution
program solution;
(* an attempt to solve the letters-on-dice puzzle *)
const MAXWORDS=25; (* max. number of words in a wordlist as Pascal has
no dynamic array sizing *)
(* I'm going to be lazy and use global variables *)
var dice:array[1..25,1..4] of integer;
(* use -1 to indicate a letter is not on a dice, 0 to indicate
it might be, and 1 to indicate it is *)
words:array[1..MAXWORDS] of string;
i,j,k,l:integer;
verbose,StateHasChanged:boolean;
Function IntToChar (I : integer) : char;
(* RETURN THE VALUE OF THE INTEGER I AS A CHARACTER-TYPE *)
Var S : string;
begin
Str (I,S);
IntToChar:=S[1];
end;
procedure read_wordlist;
var WordListFile:text;
i:integer; (* loop variable *)
begin
assign(WordListFile,'words.txt');
reset(WordListFile);
i:=1;
repeat
for j:=1 to 4 do
read(WordListFile,words[i,j]);
i:=i+1;
readln(WordListFile);
until ((i=MAXWORDS) or (EOF(WordListFile)));
end;
procedure propagate(word_no,position,value:integer);
(* Throughout the data space, this procedure sets all occurrences
of the letter in words[word_no,position] to (value) *)
var i,j:integer;
ch:string;
begin
ch:=words[word_no,position];
words[word_no,position]:=IntToChar(value);
if (verbose) then writeln('Setting ',ch,' to be ',value);
for i:=1 to MAXWORDS do
for j:=1 to 4 do
if (words[i,j]=ch) then words[i,j]:=IntToChar(value);
for j:=1 to 4 do
if (j=value) then dice[(ord(ch[1])-ord('a')+1),j]:=1
else dice[(ord(ch[1])-ord('a')+1),j]:=-1;
StateHasChanged:=true;
end;
procedure CheckNumberOfDigits(word_no:integer);
(* calculate the number of digits in a specified word in wordlist,
and act appropriately if there are only three *)
var num,i,posn,value:integer;
begin
num:=0;
value:=0;
for i:=1 to 4
do
if ((words[word_no,i]>='0') and (words[word_no,i]<='9')) then
begin
num:=num+1;
value:=value+(ord(words[word_no,i])-ord('0'));
end
else posn:=i;
if (verbose) then writeln('Processing ',words[word_no,1],words[word_no,2],
words[word_no,3],words[word_no,4],' which has ',num,' number(s)');
if (num=3) then
propagate(word_no,posn,(10-value));
end;
function IsDigit(test:char):boolean;
var i:integer;
begin
if ((test>='0') and (test<='9')) then IsDigit:=true
else IsDigit:=false;
end;
procedure EliminatePossibilities(word_no:integer);
(* This procedure does stuff like :
A word is "1A2B", and so it follows that neither A nor B
can be on dice 1 or 2 *)
var digit:array[1..4] of integer;
ch:array[1..4] of char;
num,i,j:integer;
null:word;
begin
for i:=1 to 4 do
begin
digit[i]:=99 ; ch[i]:='*';
end;
for i:=1 to 4 do
if (IsDigit(words[word_no,i])) then
val(words[word_no,i],digit[i],null)
else ch[i]:=words[word_no,i];
for i:=1 to 4 do
if (digit[i]<99) then
for j:=1 to 4 do
begin
if ((ch[j]<>'*') and (dice[(ord(ch[j])-ord('a')+1),digit[i]]<>-1)) then
begin
dice[(ord(ch[j])-ord('a')+1),digit[i]]:=-1;
StateHasChanged:=true;
if (verbose) then writeln('Looks like ',ch[j],
' can''t be on dice ',digit[i]);
end;
end;
end;
procedure CheckLetterAssignments(null);
(* If EliminatePossibilites has managed to remove
all bar 1 of the possible dice for
and given letter, then this procedure sets the
letter to the remaining possibility *)
var i,j,k,l,sum:integer;
begin
for i:=1 to 25 do
begin
sum:=0;
for j:=1 to 4 do
sum:=sum+dice[i,j];
if (sum=-3) then
(* for the letter correspoding to i,
we can now identify the correct die... *)
for j:=1 to 4 do
if (dice[i,j]=0) then
begin
if (verbose) then writeln('Setting ',chr(i+ord('A')-1),' to ',j);
for k:=1 to MAXWORDS do
for l:=1 to 4 do
if (words[k,l]=chr(i+ord('a')-1)) then propagate (k,l,j);
end;
end;
end;
begin
verbose:=true;
for i:=1 to 25 do
for j:=1 to 4 do
if (i<>17) then dice[i,j]:=0 else dice[i,j]:=-1;
read_wordlist;
if (verbose) then for i:=1 to MAXWORDS do
begin
if (words[i,1]<>'') then for j:=1 to 4 do write(words[i,j]);
writeln();
end;
writeln('Using first word "',words[1,1],words[1,2],
words[1,3],words[1,4],'" as root word');
propagate(1,1,1);
propagate(1,2,2);
propagate(1,3,3);
propagate(1,4,4);
repeat
StateHasChanged:=false;
for j:=1 to MAXWORDS do
begin
CheckNumberOfDigits(j);
EliminatePossibilities(j);
end;
CheckLetterAssignments(i);
if (verbose) then
begin
writeln('Current state of play:');
for k:=1 to 25 do
begin
write(chr(ord('A')+k-1),': ');
for l:=1 to 4 do
case dice[k,l] of
-1 : write (' ');
0 : write ('.');
1 : write ('*');
end;
writeln();
end;
end;
until (StateHasChanged=false);
if (verbose) then for i:=1 to MAXWORDS do
begin
if (words[i,1]<>'') then for j:=1 to 4 do write(words[i,j]);
writeln();
end;
writeln('The solution is:');
writeln('================');
for i:=1 to 4 do
begin
write ('Dice ',i,': ');
for j:=1 to 25 do
if (dice[j,i]=1) then write(chr(j+ord('A')-1));
writeln;
end;
end.
Program output
sale
fens
axes
wars
hear
crab
veil
gays
duck
spey
brow
rack
char
pugh
tare
duct
pile
joys
ripe
Using first word "sale" as root word
Setting s to be 1
Setting a to be 2
Setting l to be 3
Setting e to be 4
Processing 1234 which has 4 number(s)
Processing f4n1 which has 2 number(s)
Looks like f can't be on dice 4
Looks like n can't be on dice 4
Looks like f can't be on dice 1
Looks like n can't be on dice 1
Processing 2x41 which has 3 number(s)
Setting x to be 3
Processing w2r1 which has 2 number(s)
Looks like w can't be on dice 2
Looks like r can't be on dice 2
Looks like w can't be on dice 1
Looks like r can't be on dice 1
Processing h42r which has 2 number(s)
Looks like h can't be on dice 4
Looks like r can't be on dice 4
Looks like h can't be on dice 2
Processing cr2b which has 1 number(s)
Looks like c can't be on dice 2
Looks like b can't be on dice 2
Processing v4i3 which has 2 number(s)
Looks like v can't be on dice 4
Looks like i can't be on dice 4
Looks like v can't be on dice 3
Looks like i can't be on dice 3
Processing g2y1 which has 2 number(s)
Looks like g can't be on dice 2
Looks like y can't be on dice 2
Looks like g can't be on dice 1
Looks like y can't be on dice 1
Processing duck which has 0 number(s)
Processing 1p4y which has 2 number(s)
Looks like p can't be on dice 1
Looks like p can't be on dice 4
Looks like y can't be on dice 4
Processing brow which has 0 number(s)
Processing r2ck which has 1 number(s)
Looks like k can't be on dice 2
Processing ch2r which has 1 number(s)
Processing pugh which has 0 number(s)
Processing t2r4 which has 2 number(s)
Looks like t can't be on dice 2
Looks like t can't be on dice 4
Processing duct which has 0 number(s)
Processing pi34 which has 2 number(s)
Looks like p can't be on dice 3
Processing joy1 which has 1 number(s)
Looks like j can't be on dice 1
Looks like o can't be on dice 1
Processing rip4 which has 1 number(s)
Setting P to 2
Setting R to 3
Setting Y to 3
Current state of play:
A: *
B: . ..
C: . ..
D: ....
E: *
F: ..
G: ..
H: . .
I: ..
J: ...
K: . ..
L: *
M: ....
N: ..
O: ...
P: *
Q:
R: *
S: *
T: . .
U: ....
V: ..
W: ..
X: *
Y: *
Processing 1234 which has 4 number(s)
Processing f4n1 which has 2 number(s)
Processing 2341 which has 4 number(s)
Processing w231 which has 3 number(s)
Setting w to be 4
Processing h423 which has 3 number(s)
Setting h to be 1
Processing c32b which has 2 number(s)
Looks like c can't be on dice 3
Looks like b can't be on dice 3
Processing v4i3 which has 2 number(s)
Processing g231 which has 3 number(s)
Setting g to be 4
Processing duck which has 0 number(s)
Processing 1243 which has 4 number(s)
Processing b3o4 which has 2 number(s)
Looks like o can't be on dice 3
Looks like b can't be on dice 4
Looks like o can't be on dice 4
Processing 32ck which has 2 number(s)
Looks like k can't be on dice 3
Processing c123 which has 3 number(s)
Setting c to be 4
Processing 2u41 which has 3 number(s)
Setting u to be 3
Processing t234 which has 3 number(s)
Setting t to be 1
Processing d341 which has 3 number(s)
Setting d to be 2
Processing 2i34 which has 3 number(s)
Setting i to be 1
Processing jo31 which has 2 number(s)
Looks like j can't be on dice 3
Setting B to 1
Setting O to 2
Current state of play:
A: *
B: *
C: *
D: *
E: *
F: ..
G: *
H: *
I: *
J: . .
K: . .
L: *
M: ....
N: ..
O: *
P: *
Q:
R: *
S: *
T: *
U: *
V: ..
W: *
X: *
Y: *
Processing 1234 which has 4 number(s)
Processing f4n1 which has 2 number(s)
Processing 2341 which has 4 number(s)
Processing 4231 which has 4 number(s)
Processing 1423 which has 4 number(s)
Processing 4321 which has 4 number(s)
Processing v413 which has 3 number(s)
Setting v to be 2
Processing 4231 which has 4 number(s)
Processing 234k which has 3 number(s)
Setting k to be 1
Processing 1243 which has 4 number(s)
Processing 1324 which has 4 number(s)
Processing 3241 which has 4 number(s)
Processing 4123 which has 4 number(s)
Processing 2341 which has 4 number(s)
Processing 1234 which has 4 number(s)
Processing 2341 which has 4 number(s)
Processing 2134 which has 4 number(s)
Processing j231 which has 3 number(s)
Setting j to be 4
Processing 3124 which has 4 number(s)
Current state of play:
A: *
B: *
C: *
D: *
E: *
F: ..
G: *
H: *
I: *
J: *
K: *
L: *
M: ....
N: ..
O: *
P: *
Q:
R: *
S: *
T: *
U: *
V: *
W: *
X: *
Y: *
Processing 1234 which has 4 number(s)
Processing f4n1 which has 2 number(s)
Processing 2341 which has 4 number(s)
Processing 4231 which has 4 number(s)
Processing 1423 which has 4 number(s)
Processing 4321 which has 4 number(s)
Processing 2413 which has 4 number(s)
Processing 4231 which has 4 number(s)
Processing 2341 which has 4 number(s)
Processing 1243 which has 4 number(s)
Processing 1324 which has 4 number(s)
Processing 3241 which has 4 number(s)
Processing 4123 which has 4 number(s)
Processing 2341 which has 4 number(s)
Processing 1234 which has 4 number(s)
Processing 2341 which has 4 number(s)
Processing 2134 which has 4 number(s)
Processing 4231 which has 4 number(s)
Processing 3124 which has 4 number(s)
Current state of play:
A: *
B: *
C: *
D: *
E: *
F: ..
G: *
H: *
I: *
J: *
K: *
L: *
M: ....
N: ..
O: *
P: *
Q:
R: *
S: *
T: *
U: *
V: *
W: *
X: *
Y: *
1234
f4n1
2341
4231
1423
4321
2413
4231
2341
1243
1324
3241
4123
2341
1234
2341
2134
4231
3124
The solution is:
================
Dice 1: BHIKST
Dice 2: ADOPV
Dice 3: LRUXY
Dice 4: CEGJW
Note the words given do not yield a unique solution; the letters F and N can be on either dice 2 or dice 4, or dice 4 and dice 2 respectively; also, M can be on any of dice 2,3 or 4. However, as F and N are on dice 2 and 4 it follows M must be on 3. The program can't solve for that part, unfotunately...