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 } deriving (Functor, Applicative, Monad) newtype GodQuestion a = GodQuestion { unGodQuestion :: GodM a } deriving (Functor, Applicative, Monad)
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
Back