Tripos 2022 Paper 1 Question 1 — Worked Solution

Question: A single-player word-guessing game. The player guesses a letter c and position i. Response: Green (correct letter, correct position), Amber (correct letter, wrong position), or Black (not in word). No repeated letters in the target word.

Given types and helper:

type word = char list
type guess = char * int
type guesses = guess list
val prune_guesses : guesses -> guesses

prune_guesses removes all but the most recent guess for each character.

(a) mapi and lookfor [4 marks]

mapi:

let rec mapi f l =
  let rec go i = function
    | [] -> []
    | x :: xs -> f i x :: go (i + 1) xs
  in
  go 0 l

Explanation: mapi is like map but the function f also receives the element’s index (starting from 0). We use a helper function go with an accumulating index parameter. Each recursive step applies f i x and increments the index. This is O(n) time.

lookfor:

let rec lookfor y = function
  | [] -> None
  | (a, b) :: rest ->
      if b = y then Some a
      else lookfor y rest

Explanation: lookfor y l searches l for a pair (a, b) where b = y. If found, returns Some a; otherwise None. This is a linear search, O(n) time. The type is val lookfor : 'a -> ('b * 'a) list -> 'b option.

(b) respond function [8 marks]

Write respond : word -> guesses -> responses that gives feedback about game progress.

Solution:

type response = Green of int | Amber of int | Black of char
type responses = response list

let respond target guesses =
  let pruned = prune_guesses guesses in
  mapi (fun i c ->
    match lookfor c pruned with
    | None -> Black c
    | Some pos ->
        if pos = i then Green i
        else Amber i
  ) target

Explanation: First we prune the guesses to keep only the most recent guess per character. Then we use mapi to iterate over the target word with positions. For each character c at position i in the target:

• If the character was never guessed (lookfor returns None), the response is Black c — the player doesn’t know this letter yet.
• If the player guessed this character at position i, the response is Green i — correct letter in the correct position.
• If the player guessed this character at some other position, the response is Amber i — the letter is in the word but at a different position.

The responses type captures the three possible outcomes. This is O(n × m) where n is word length and m is the number of guesses (since lookfor does linear search).

(c)(i) create_game with turn limit [6 marks]

Define create_game : word -> (guess -> responses) that returns a function g usable for at most six tries, then raises Out_of_turns.

Solution:

exception Out_of_turns

let create_game target =
  let guesses = ref [] in
  let turns = ref 0 in
  fun (c, pos) ->
    if !turns >= 6 then raise Out_of_turns
    else begin
      turns := !turns + 1;
      guesses := (c, pos) :: !guesses;
      respond target !guesses
    end

Explanation: We use two mutable references: guesses accumulates the guess history (most recent first, matching the guesses type convention), and turns counts how many tries have been made. The returned closure:

1. Checks if six turns have been used — if so, raises Out_of_turns.
2. Increments the turn counter.
3. Prepends the new guess to the guesses list.
4. Calls respond with the updated guesses.

The closure captures the mutable references, so each call to g updates the same internal state. This is the private-state pattern from Lecture 11 (analogous to makeAccount). The function remains purely functional in its interface — the caller only sees a function from guess to responses.

(c)(ii) Example usage [2 marks]

let g = create_game ['a'; 'p'; 'p'; 'l'; 'e']

(* Try 1: guess 'a' at position 0 *)
g ('a', 0)
(* Result: [Green 0; Black 'p'; Black 'p'; Black 'l'; Black 'e'] *)

(* Try 2: guess 'p' at position 1 *)
g ('p', 1)
(* Result: [Green 0; Green 1; Amber 2; Black 'l'; Black 'e'] *)
(* Note: position 2 shows Amber because 'p' is at position 1 but also at position 2 *)

(* Try 3: guess 'x' at position 0 *)
g ('x', 0)
(* Result: [Green 0; Green 1; Amber 2; Black 'l'; Black 'e'] *)
(* No new information about 'x' since it's not in the word *)

After 6 tries, further calls to g raise Out_of_turns.