HFST: Einstein's Puzzle

This page shows how to use HFST command line tools to solve a riddle in a similar way as Beesley & Karttunen have done with the XFST tools. We advise the reader to go through the riddle and its solution before reading this page. The solution given on this page can also be executed with a single script.

We use a similar kind of formalism for representing a row of houses as Beesley & Karttunen. The character | is a separator between houses and spaces are added between words and separators for better readability. An example of a row of houses:

red Englishman tea Dunhill fish | blue German water BlueMaster dogs | yellow Dane bier Prince birds | green Norwegian coffee PallMall cats | white Swede milk Blend horses

We first define two pi star transducers used in constraint transducers to match any symbol. One accepts any number of symbols inside a house, i.e. the separator character | is not included. The other accepts any number of any sign, i.e. it can be used to match strings between two or more houses. We use the tool hfst-txt2fst to create those transducers.

# matches all symbols
echo "0 0 @_IDENTITY_SYMBOL_@ @_IDENTITY_SYMBOL_@
0" | hfst-txt2fst -f $FORMAT > pi.hfst

# matches all symbols except "|"
echo "0 0 @_IDENTITY_SYMBOL_@ @_IDENTITY_SYMBOL_@
0 1 | |
0" | hfst-txt2fst -f $FORMAT > pi_house.hfst

# The possible values of a house color (spaces are added for better readability)
echo -e "blue \ngreen \nred \nwhite \nyellow " | hfst-strings2fst -f $FORMAT -j > Color.hfst

# The possible values of nationality
echo -e "Dane \nEnglishman \nGerman \nSwede \nNorwegian " | hfst-strings2fst -f $FORMAT -j > Nationality.hfst

# The possible values of a drink
echo -e "bier \ncoffee \nmilk \ntea \nwater " | hfst-strings2fst -f $FORMAT -j > Drink.hfst

# The possible values of cigarettes
echo -e "Blend \nBlueMaster \nDunhill \nPallMall \nPrince " | hfst-strings2fst -f $FORMAT -j > Cigarette.hfst

# The possible values of animals
echo -e "birds \ncats \ndogs \nfish \nhorses " | hfst-strings2fst -f $FORMAT -j > Pet.hfst

# Convert all strings into transducers
for i in blue green red white yellow \
Dane Englishman German Swede Norwegian \
bier coffee milk tea water \
Blend BlueMaster Dunhill PallMall Prince \
birds cats dogs fish horses; \
do 
  echo $i" " | hfst-strings2fst -f $FORMAT > $i.hfst
done

# Separator character (spaces are included for better readability)
echo "| " | hfst-strings2fst -f $FORMAT > HouseSeparator.hfst

# House contains the consecutive values "ColorNationalityDrinkCigarettePet"
echo "" | hfst-strings2fst -f $FORMAT > House.hfst
for i in Color Nationality Drink Cigarette Pet; 
do 
  hfst-concatenate House.hfst $i.hfst > TMP
  mv TMP House.hfst
done

# Houses is "House| House| House| House| House"
hfst-concatenate House.hfst HouseSeparator.hfst | hfst-repeat -f 4 -t 4 > Houses.hfst
hfst-concatenate Houses.hfst House.hfst > TMP
mv TMP Houses.hfst

Now we create the constraint transducers. First we create two constraints and test if they work correctly.

# 1. The Englishman lives in the red house.
# Since color and nationality are adjacent, it is enough to accept all strings that contain "red Englishman"
echo "red Englishman" | 
hfst-strings2fst -f $FORMAT |  # "red Englishman"
hfst-concatenate -1 pi.hfst |  # .* "red Englishman"
hfst-concatenate -2 pi.hfst > C1.hfst  # .* "red Englishman" .*

If the constraint works, the following command

hfst-conjunct Houses.hfst C1.hfst | hfst-fst2strings -r 50 | grep -v "red Englishman"

should print no lines.

# 2. The Swede keeps dogs.
# Now we must match the string between Swede and dog inside the same house.
echo "Swede" | 
hfst-strings2fst -f $FORMAT |  # "Swede"
hfst-concatenate pi_house.hfst > TMP;  # "Swede" .*
echo "dogs" | 
hfst-strings2fst -f $FORMAT |  # "dogs"
hfst-concatenate -1 TMP |  # "Swede" .* "dogs"
hfst-concatenate -1 pi.hfst |  # .* "Swede" .* "dogs"
hfst-concatenate -2 pi.hfst > C2.hfst  # .* "Swede" .* "dogs" .*

We can test the two constraints with the command

hfst-conjunct C1.hfst C2.hfst | hfst-conjunct Houses.hfst | hfst-minimize | hfst-fst2strings -r 10 > houses;
cat houses | wc -l > N1  # number of lines in total
grep "red Englishman" houses | wc -l > N2  # number of lines that contain "red Englishman"
grep "Swede[^|]*dogs" houses | wc -l > N3  # number of lines that contain a house inhabited by a Swede that keeps dogs
diff N1 N2 && diff N2 N3 && echo "TEST OK"

which should print the text "TEST OK".

Next we construct the rest of the constraint transducers in a similar way as done by Beesley & Karttunen.

# 3. The Dane drinks tea
hfst-concatenate Dane.hfst tea.hfst | hfst-concatenate -1 pi.hfst | hfst-concatenate -2 pi.hfst > C3.hfst 

# 4. The green house is just to the left of the white one
hfst-concatenate green.hfst pi_house.hfst | hfst-concatenate HouseSeparator.hfst | hfst-concatenate white.hfst | \
hfst-concatenate -1 pi.hfst | hfst-concatenate -2 pi.hfst > C4.hfst

# 5. The owner of the green house drinks coffee
hfst-concatenate green.hfst pi_house.hfst | hfst-concatenate coffee.hfst | hfst-concatenate -1 pi.hfst | hfst-concatenate -2 pi.hfst > C5.hfst

# 6. The Pall Mall smoker keeps birds
hfst-concatenate PallMall.hfst birds.hfst | hfst-concatenate -1 pi.hfst | hfst-concatenate -2 pi.hfst > C6.hfst

# 7. The owner of the yellow house smokes Dunhills
hfst-concatenate yellow.hfst pi_house.hfst | hfst-concatenate Dunhill.hfst | hfst-concatenate -1 pi.hfst | hfst-concatenate -2 pi.hfst > C7.hfst

# 8. The man in the center house drinks milk
echo "" | hfst-strings2fst -f $FORMAT > C8.hfst
for i in pi_house.hfst HouseSeparator.hfst pi_house.hfst HouseSeparator.hfst pi_house.hfst milk.hfst pi_house.hfst HouseSeparator.hfst pi_house.hfst HouseSeparator.hfst pi_house.hfst; \
do  hfst-concatenate C8.hfst $i > TMP; mv TMP C8.hfst ; done  

# 9. The Norwegian lives in the first house
hfst-concatenate pi_house.hfst Norwegian.hfst | hfst-concatenate pi.hfst > C9.hfst

# 10. The Blend smoker has a neighbor who keeps cats
echo "" | hfst-strings2fst -f $FORMAT > C10_1.hfst
for i in pi.hfst Blend.hfst Pet.hfst HouseSeparator.hfst pi_house.hfst cats.hfst pi.hfst; \
do  hfst-concatenate C10_1.hfst $i > TMP; mv TMP C10_1.hfst;  done
echo "" | hfst-strings2fst -f $FORMAT > C10_2.hfst
for i in pi.hfst cats.hfst pi_house.hfst HouseSeparator.hfst pi_house.hfst Blend.hfst pi.hfst; \
do  hfst-concatenate C10_2.hfst $i > TMP; mv TMP C10_2.hfst;  done
hfst-disjunct C10_1.hfst C10_2.hfst | hfst-minimize > C10.hfst

# 11. The man who keeps horses lives next to the Dunhill smoker
echo "" | hfst-strings2fst -f $FORMAT > C11_1.hfst
for i in pi.hfst horses.hfst HouseSeparator.hfst pi_house.hfst Dunhill.hfst pi.hfst; \
do hfst-concatenate C11_1.hfst $i > TMP; mv TMP C11_1.hfst;  done
echo "" | hfst-strings2fst -f $FORMAT > C11_2.hfst
for i in pi.hfst Dunhill.hfst pi_house.hfst HouseSeparator.hfst pi_house.hfst horses.hfst pi.hfst; \
do hfst-concatenate C11_2.hfst $i > TMP; mv TMP C11_2.hfst;  done
hfst-disjunct C11_1.hfst C11_2.hfst | hfst-minimize > C11.hfst

# 12. The man who smokes Blue Masters drinks bier.
echo "" | hfst-strings2fst -f $FORMAT > C12.hfst
for i in pi.hfst bier.hfst BlueMaster.hfst pi.hfst; \
do hfst-concatenate C12.hfst $i > TMP; mv TMP C12.hfst;  done

# 13. The German smokes Prince
echo "" | hfst-strings2fst -f $FORMAT > C13.hfst
for i in pi.hfst German.hfst Drink.hfst Prince.hfst pi.hfst; \
do hfst-concatenate C13.hfst $i > TMP; mv TMP C13.hfst;  done

# 14. The Norwegian lives next to the blue house
echo "" | hfst-strings2fst -f $FORMAT > C14_1.hfst
for i in pi.hfst Norwegian.hfst pi_house.hfst HouseSeparator.hfst blue.hfst pi.hfst; \
do hfst-concatenate C14_1.hfst $i > TMP; mv TMP C14_1.hfst;  done
echo "" | hfst-strings2fst -f $FORMAT > C14_2.hfst
for i in pi.hfst blue.hfst pi_house.hfst HouseSeparator.hfst Color.hfst Norwegian.hfst pi.hfst; \
do hfst-concatenate C14_2.hfst $i > TMP; mv TMP C14_2.hfst;  done
hfst-disjunct C14_1.hfst C14_2.hfst | hfst-minimize > C14.hfst

# 15. The Blend smoker has a neighbor who drinks water
echo "" | hfst-strings2fst -f $FORMAT > C15_1.hfst
for i in pi.hfst Blend.hfst Pet.hfst HouseSeparator.hfst pi_house.hfst water.hfst pi.hfst; \
do hfst-concatenate C15_1.hfst $i > TMP; mv TMP C15_1.hfst;  done
echo "" | hfst-strings2fst -f $FORMAT > C15_2.hfst
for i in pi.hfst water.hfst pi_house.hfst HouseSeparator.hfst pi_house.hfst Blend.hfst pi.hfst; \
do hfst-concatenate C15_2.hfst $i > TMP; mv TMP C15_2.hfst;  done
hfst-disjunct C15_1.hfst C15_2.hfst | hfst-minimize > C15.hfst

Let's minimize the constraint transducers to carry out conjunction more efficiently:

for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15;
do
  hfst-minimize C$i.hfst > TMP;
  mv TMP C$i.hfst;
done

Let's conjunct Houses.hfst with the constraints one by one. We can also print the constraint number and the number of states in the intermediate result.

cp Houses.hfst Result.hfst; 
for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15;
do 
  # echo $i; 
  hfst-conjunct Result.hfst C$i.hfst | hfst-minimize > TMP; 
  mv TMP Result.hfst;  
  # hfst-summarize Result.hfst | grep "# of states"; 
done

The command hfst-fst2strings Result.hfst gives us five possible solutions:

yellow Norwegian water Dunhill cats | blue Dane tea Blend horses | red Englishman milk PallMall birds | green German coffee Prince horses | white Swede bier BlueMaster dogs
yellow Norwegian water Dunhill cats | blue Dane tea Blend horses | red Englishman milk PallMall birds | green German coffee Prince cats | white Swede bier BlueMaster dogs
yellow Norwegian water Dunhill cats | blue Dane tea Blend horses | red Englishman milk PallMall birds | green German coffee Prince birds | white Swede bier BlueMaster dogs
yellow Norwegian water Dunhill cats | blue Dane tea Blend horses | red Englishman milk PallMall birds | green German coffee Prince dogs | white Swede bier BlueMaster dogs
yellow Norwegian water Dunhill cats | blue Dane tea Blend horses | red Englishman milk PallMall birds | green German coffee Prince fish | white Swede bier BlueMaster dogs

One missing constraint is that someone keeps fish, as indicated by the original question "Who keeps the fish?". We can make the constraint easily by filtering the previous output with the command grep "fish:

yellow Norwegian water Dunhill cats | blue Dane tea Blend horses | red Englishman milk PallMall birds | green German coffee Prince fish | white Swede bier BlueMaster dogs

So, it is the German who keeps the fish.


-- ErikAxelson - 2011-08-29