Simplified Mastermind
Cambridge Computer Science Tripos Part IA -- 2020 -- Paper 1, Question 2
In this exercise, we will develop a game engine to play a simplified version of the game of Mastermind.
In simplified Mastermind, player A selects a list of n colours among 3 possible colours: Red, Green and Blue (e.g., [Red; Red; Green; Blue] if n = 4). Player B has to guess player A's list by proposing lists of colours in sequence. Every time player B proposes a list, she gets feedback in the form of a number x -- the number of colours that are in the correct position.
For example, if player A's list is [Red; Red; Green; Blue] and player B guessed [Red; Green; Green; Red], then x = 2 (the first Red and the Green are at the right positions).
We will use the following type throughout:
type colour = Red | Green | Blue
exception SizeMismatchPart (a): Feedback function
Given two colour lists, write a function feedback that counts how many positions have matching colours. The first argument a is player A's list, and the second b is player B's guess. Raise SizeMismatch if the lengths don't match.
let feedback (a : colour list) (b : colour list) : int = failwith "TODO"let () =
let check a b expected =
let got = feedback a b in
Printf.printf "feedback => %d %s\n" got
(if got = expected then "(correct)" else "(WRONG)");
assert (got = expected)
in
check [Red; Red; Green; Blue] [Red; Green; Green; Red] 2;
check [Red; Green; Blue] [Red; Green; Blue] 3;
check [Red; Red; Red] [Blue; Blue; Blue] 0;
check [Red; Green; Blue] [Blue; Red; Green] 0;
print_endline "All tests passed!"Part (b): Using currying
Using currying, define a test function that takes a list proposed by player B and returns x. This function should assume that player A's list is [Blue; Green; Red].
let test : colour list -> int = failwith "TODO"let () =
let check guess expected =
let got = test guess in
Printf.printf "test => %d %s\n" got
(if got = expected then "(correct)" else "(WRONG)");
assert (got = expected)
in
check [Blue; Green; Red] 3;
check [Red; Green; Blue] 1;
check [Blue; Blue; Blue] 1;
print_endline "All tests passed!"Part (c): Type of test
What is the type of test in Part (b)?
Think about this, then check by evaluating:
testPart (d): Generating all colour lists
Write a function generate_lists that generates all possible colour lists of a given length n.
Tip: generate_lists 2 should output 32 = 9 lists.
let rec generate_lists (n : int) : colour list list = failwith "TODO"let () =
let check n expected =
let got = List.length (generate_lists n) in
Printf.printf "generate_lists %d: %d lists %s\n" n got
(if got = expected then "(correct)" else "(WRONG)");
assert (got = expected)
in
check 1 3;
check 2 9;
check 3 27;
print_endline "All tests passed!"Part (e): Finding valid lists
Given a colour list guess by player B and feedback x, write a function valid_lists that returns all possible lists that player A could have chosen (i.e. all lists that would produce the given feedback for the given guess).
let valid_lists (b : colour list) (x : int) : colour list list =
failwith "TODO"let () =
(* If B guesses [Red; Green; Blue] and gets feedback 3,
the only valid list is [Red; Green; Blue] itself *)
let v = valid_lists [Red; Green; Blue] 3 in
Printf.printf "valid_lists [R;G;B] 3: %d list(s) %s\n"
(List.length v)
(if List.length v = 1 then "(correct)" else "(WRONG)");
assert (List.length v = 1);
(* If B guesses [Red; Red; Red] and gets feedback 0,
no position can be Red: should be 2^3 = 8 lists *)
let v2 = valid_lists [Red; Red; Red] 0 in
Printf.printf "valid_lists [R;R;R] 0: %d list(s) %s\n"
(List.length v2)
(if List.length v2 = 8 then "(correct)" else "(WRONG)");
assert (List.length v2 = 8);
print_endline "All tests passed!"