Home

# Modeling 'The Hardest Logic Puzzle Ever' in Haskell

22 August 2015

I recently stumbled upon "The Hardest Logic Puzzle Ever" on Wikipedia. I'm not that into the logic puzzles, neither I intended to solve it; but I have thought that it'd be fun to try representing the question and the possible answers in it.

The puzzle is defined as follows:

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

It immediately looks like we can write a DSL where you can ask a god a question, receive their answers as Da or Ja and compose an algorithm to determine the identity of the gods. And we will even be able to check our solutions via QuickCheck!

Just to catch your interest, here is how we'll be able to write the solution to the puzzle on our DSL:

-- | https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever#The_solution
solution :: THLPE (GodType, GodType, GodType)
solution = do
r1 <- askTo GodB $ifIAsked GodB (godType GodA <&> (== RandomGod)) <&> (== Ja) let notRandomGod = case r1 of Ja -> GodC Da -> GodA r2 <- askTo notRandomGod$
ifIAsked notRandomGod (godType notRandomGod <&> (== FalseGod)) <&> (== Ja)
let notRandomGodType = case r2 of Ja -> FalseGod
Da -> TrueGod

r3 <- askTo notRandomGod $ifIAsked notRandomGod (godType GodB <&> (== RandomGod)) <&> (== Ja) let randomGod = case (r3, notRandomGod) of (Ja, _) -> GodB (Da, GodA) -> GodC (Da, GodC) -> GodA let f n = if | randomGod == n -> RandomGod | notRandomGod == n -> notRandomGodType | otherwise -> if notRandomGodType == TrueGod then FalseGod else TrueGod return$ (f GodA, f GodB, f GodC)

where (<&>) = flip fmap


If you look at the Wikipedia link on the comment, you can see that this code is the word-by-word translation of the solution on the page.

Here are the imports I'll use through the program:

import           Control.Monad.Trans.RWS (RWS, ask, runRWS, state, tell)
import           Data.Bool               (bool)
import           Data.List               (permutations)
import           Data.Monoid             ((<>))
import           System.Random           (StdGen, getStdRandom, mkStdGen,
random)
import           Test.QuickCheck         (Arbitrary, arbitrary, elements)


I started by defining the core types:

data GodAnswer
= Da
| Ja
deriving (Show, Eq, Enum)

data GodType
= TrueGod
| FalseGod
| RandomGod
deriving (Show, Eq, Enum)

data GodName
= GodA
| GodB
| GodC
deriving (Show, Eq, Enum)


And we have some starting conditions per game; the gods identities and the meanings of Da and Ja:

data THLPESetting
= THLPESetting { _godA      :: GodType
, _godB      :: GodType
, _godC      :: GodType
, _translate :: Bool -> GodAnswer
}


At first, my plan was simply using a Reader THLPESetting to carry the THLPESetting around the algorithm. But I came onto some obstacles:

• The Random's behavior required a State to give different answers on each question

• I wanted to hide the game state from the users

• Since gods are omniscient, they should know the game state(the other gods types) too.

The latter two points required two different Monad's, one for carrying the game state between questions(which forbids access to game state), and one for questions we ask to a god(which has access to game state).

So, I defined the following types:

type GodM a = RWS THLPESetting () StdGen a

newtype THLPE a = THLPE { unTHLPE :: GodM a }

newtype GodQuestion a = GodQuestion { unGodQuestion :: GodM a }


Note: The deriving clauses need {-# LANGUAGE GeneralizedNewtypeDeriving #-}.

After that, I defined godType accessor:

godTypeI :: GodName -> GodM GodType
godTypeI GodA = _godA <$> ask godTypeI GodB = _godB <$> ask
godTypeI GodC = _godC <$> ask godType :: GodName -> GodQuestion GodType godType = GodQuestion . godTypeI  As you can see, there is no GodName -> THLPE GodType, that means only gods will know the types of the other gods. godTypeI is only defined for internal use(askTo function below) and won't get exported. And we have two methods for interacting with gods: askTo :: GodName -> GodQuestion Bool -> THLPE GodAnswer askTo n (GodQuestion q) = THLPE$ do
tell 1
t <- godTypeI n
translate <- _translate <$> ask translate <$> case t of
TrueGod   -> q
FalseGod  -> not <$> q RandomGod -> state random ifIAsked :: GodName -> GodQuestion Bool -> GodQuestion GodAnswer ifIAsked n = GodQuestion . unTHLPE . askTo n  We're almost finished. The only thing left is the function to interpret our DSL and return if our answer is correct: runTHLPE :: StdGen -> THLPESetting -> THLPE (GodType, GodType, GodType) -> (Bool, (StdGen, Int)) runTHLPE gen set (THLPE r) = let (ans, s, w) = runRWS r set gen in (ans == (_godA set, _godB set, _godC set), (s, getSum w)) runTHLPE' :: THLPESetting -> THLPE (GodType, GodType, GodType) -> IO Bool runTHLPE' s g = getStdRandom$ \gen -> runTHLPE gen s g


That's everything we need to run the solution!

λ> runTHLPE (THLPESetting TrueGod RandomGod FalseGod (bool Da Ja)) solution
True
λ> runTHLPE (THLPESetting FalseGod TrueGod RandomGod (bool Ja Da)) solution
True
λ> runTHLPE (THLPESetting FalseGod TrueGod RandomGod (bool Ja Da)) solution
True


Everything looks okay, but lets test it a little more thoroughly with QuickCheck:

data THLPESetting
= THLPESetting { _godA      :: GodType
, _godB      :: GodType
, _godC      :: GodType
, _translate :: Bool -> GodAnswer
}

instance Show THLPESetting where
show (THLPESetting{..})
= "THLPESetting { " <> show _godA <>
", " <> show _godB <>
", " <> show _godC <>
", (\\case True  -> " <> show (_translate True) <>
"; False -> " <> show (_translate False) <>
")}"

instance Arbitrary THLPESetting where
arbitrary = do
[a, b, c] <- elements $permutations [TrueGod, FalseGod, RandomGod] tr <- elements$ [bool Ja Da, bool Da Ja]
return $THLPESetting a b c tr instance Arbitrary StdGen where arbitrary = mkStdGen <$> arbitrary


Now we can quickCheck it:

λ> :m +Test.QuickCheck
λ> quickCheck (\g s -> fst \$ runTHLPE g s solution)
+++ OK, passed 100 tests.


That's all!

If you want to tinker with it, the source is at: https://gist.github.com/utdemir/1268418421a2ed9ea5f0a57ab0e88551

Home
© Utku Demir, 2015-2023. Source: github.com/utdemir/utdemir.com.