Safe Haskell	None
Language	Haskell2010

Game.Mastermind

Synopsis

data Eval = Eval Int Int
evaluate :: Enum a => [a] -> [a] -> Eval
matching :: (C set, Enum a) => EnumSet a -> [a] -> Eval -> set a
matchingSimple :: Enum a => EnumSet a -> [a] -> Int -> [[EnumSet a]]
randomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> set a -> State g (Maybe [a])
mixedRandomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> set a -> State g (Maybe [a])
scanningRandomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> EnumSet a -> [([a], Eval)] -> set a -> State g (Maybe [a])
separatingRandomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> EnumSet a -> set a -> State g (Maybe [a])
partitionSizes :: Enum a => EnumSet a -> [a] -> [(Eval, Integer)]
mainSimple :: T Char -> Int -> IO ()
mainRandom :: T Char -> Int -> IO ()
main :: IO ()
propBestSeparatingCode :: (C set, Enum a) => Int -> set a -> T [] [a] -> Bool

Documentation

data Eval Source #

Constructors

Eval Int Int

Instances

Instances details

Show Eval Source #
Instance details Defined in Game.Mastermind Methods showsPrec :: Int -> Eval -> ShowS # show :: Eval -> String # showList :: [Eval] -> ShowS #
Eq Eval Source #
Instance details Defined in Game.Mastermind Methods (==) :: Eval -> Eval -> Bool # (/=) :: Eval -> Eval -> Bool #
Ord Eval Source #
Instance details Defined in Game.Mastermind Methods compare :: Eval -> Eval -> Ordering # (<) :: Eval -> Eval -> Bool # (<=) :: Eval -> Eval -> Bool # (>) :: Eval -> Eval -> Bool # (>=) :: Eval -> Eval -> Bool # max :: Eval -> Eval -> Eval # min :: Eval -> Eval -> Eval #

evaluate :: Enum a => [a] -> [a] -> Eval Source #

Given the code and a guess, compute the evaluation.

\(CodePair secret attempt) -> MM.evaluate secret attempt == MM.evaluate attempt secret

matching :: (C set, Enum a) => EnumSet a -> [a] -> Eval -> set a Source #

Given a code and an according evaluation, compute the set of possible codes.

The Game.Mastermind game consists of collecting pairs of codes and their evaluations. The searched code is in the intersection of all corresponding code sets.

>>> filter ((MM.Eval 2 0 ==) . MM.evaluate "aabbb") $ replicateM 5 ['a'..'c']
["aaaaa","aaaac","aaaca","aaacc","aacaa","aacac","aacca","aaccc","acbcc","accbc","acccb","cabcc","cacbc","caccb","ccbbc","ccbcb","cccbb"]
>>> CodeSet.flatten (MM.matching (EnumSet.fromList ['a'..'c']) "aabbb" (Eval 2 0) :: CodeSetTree.T Char)
["aaaaa","aaaac","aaaca","aaacc","aacaa","aacac","aacca","aaccc","acbcc","accbc","acccb","cabcc","cacbc","caccb","ccbbc","ccbcb","cccbb"]

\(CodePair secret attempt) -> CodeSetTree.member secret $ MM.matching alphabet attempt (MM.evaluate secret attempt)

\(CodePair secret attempt) -> forAllEval secret $ \eval -> (eval == MM.evaluate secret attempt) == CodeSetTree.member secret (MM.matching alphabet attempt eval)

\(Code attempt) -> forAllEval attempt $ \eval0 -> forAllEval attempt $ \eval1 -> eval0 == eval1 || CodeSetTree.null (compose2 CodeSetTree.intersection (MM.matching alphabet attempt) eval0 eval1)

\(Code attempt) -> forAllEval attempt $ \eval -> all ((eval ==) . MM.evaluate attempt) $ take 100 $ CodeSet.flatten $ (MM.matching alphabet attempt eval :: CodeSetInt)

\(Code attempt) -> forAllEval attempt $ \eval -> let set :: CodeSetInt; set = MM.matching alphabet attempt eval in map (CodeSet.select set) [0 .. min 100 (CodeSet.size set) - 1] == take 100 (CodeSet.flatten set)

TestMM.intersections

TestMM.solve

matchingSimple :: Enum a => EnumSet a -> [a] -> Int -> [[EnumSet a]] Source #

A variant of the game: It is only possible to specify number of symbols at right places.

The results of matching and matchingSimple cannot be compared.

randomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> set a -> State g (Maybe [a]) Source #

mixedRandomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> set a -> State g (Maybe [a]) Source #

In the beginning we simply choose a random code from the set of possible codes. In the end, when the set becomes small, then we compare different alternatives.

scanningRandomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> EnumSet a -> [([a], Eval)] -> set a -> State g (Maybe [a]) Source #

This strategy starts with scanning the alphabet. That is, we test sets of different symbols we did not try so far. The idea is to sort out unused symbols early. This is especially useful when the alphabet is large, i.e. its size is some multiples of the code width.

We stop scanning when we are sure to have seen all characters of the secret code. E.g.:

vicx
alsn   o
mfgt   o
hjqw
edpz   oo
bkru   - we already know, that these cannot be in the secret code

We use the Choice data type for tracking the number of symbols that we can minimally use from the ones we have already tried. The order of applying mergeChoice matters, but I see no easy way to find a good order or to make it robust against re-ordering.

If the user tells us that all symbols in a code are used, then the scanning phase ends immediately. This happens automatically according to our way of processing Choices.

separatingRandomizedAttempt :: (C set, RandomGen g, Enum a) => Int -> EnumSet a -> set a -> State g (Maybe [a]) Source #

In the beginning we choose codes that separate reasonably well, based on heuristics. At the end, when the set becomes small, we do a brute-force search for an optimally separating code.

partitionSizes :: Enum a => EnumSet a -> [a] -> [(Eval, Integer)] Source #

A more precise test would be to check that for different numbers of rightPlace and rightSymbol the codesets are disjoint and their union is the set of all possible codes. To this end we need a union with simplification or a subset test.

\(Code attempt) -> fromIntegral (EnumSet.size alphabet) ^ length attempt == sum (map snd (MM.partitionSizes alphabet attempt))

mainSimple :: T Char -> Int -> IO () Source #

mainRandom :: T Char -> Int -> IO () Source #

main :: IO () Source #

propBestSeparatingCode :: (C set, Enum a) => Int -> set a -> T [] [a] -> Bool Source #