The Critical Line: Volume 5

For those not familiar with the game, it is a 2 player board game where one player selects a 4-digit code using only the digits 1 to 6 (in the board game, six colours are used instead of digits but for simplicity, we’ll work with digits here), and the other player has to try and guess the code within a certain number of guesses. Repetition of digits is allowed and after each guess, the code-maker will score the guess (and hence reveal some information about the code) via the use of black and white pegs.

The number of black pegs is the number of positions in which the code and the guess exactly match – i.e. same digit in same position. The number of white pegs is the number of digits (excluding those digits that earned a black peg) that match another digit in the code (excluding those that have already given a black peg or a white peg) but are in the wrong order. The score is given simply as a total number of black pegs and a total number of white pegs. So if the score is 1 black, 0 white, we don’t know if it is the first, second, third or fourth digit that match.

For example:
Code is 4135, Guess is 1234. This will score 1 black peg (the third position matches) and 2 white pegs (the first and second position of the guess exist in the code, but in other positions).
Code is 3622, Guess is 2242. This will score 1 black peg (final positon) and 1 white peg (one of the 2’s guessed in position 1 and 2 are in the code in position 3).
Code is 3622, Guess is 2222. This will score 2 black pegs, and 0 white pegs.

In the standard board game, the player guessing receives up to 12 guesses to correctly guess the code. It has been proven in many places on the internet that this is more than enough, and with an efficient algorithm the code can usually be guessed in no more than 6 guesses. My challenge here takes a slightly different approach.

The challenge

For each of these parts, assume that the code is randomly selected from a uniform distribution of the 1296 (6*6*6*6) possible options. There are three parts to the challenge, and they increase in order of difficulty. Although it may not look like it at first, Part 1 can be solved quite reasonably without the aid of a computer.

Part 1. Let’s say you only get a maximum of two guesses and your objective is to win the game (i.e. score 4 black pegs) as often as possible within those two guesses. You will receive the black peg / white peg score of your first guess before you make your second guess. What should your first guess be, and what are your odds of winning the game?

Part 2. The same situation as Part 1, except now you get three guesses instead of two. However, you must nominate your second guess BEFORE you receive the score of your first guess. You will then receive the score of each of the first two guesses before making your third guess. What should your first two guesses be to maximise your chances, and what are your odds of winning the game?

Part 3. As per Part 2, except this time you do receive the score of the first guess before making your second guess. What is the optimal strategy (if you can write it concisely) and what are your odds of winning the game?

The Critical Line Vol.4 Solution

There were 3 correct submissions to last month’s puzzle. Congratulations to Mike Fowlds, Andrew Parker, and Will Turvey. The winner this month, in my subjective opinion, was Mike Fowlds.

A Peculiar Process 
Start with any string of (lowercase) letters. Create a new string by following this process: remove the first letter of the string. For every remaining letter of the string: if that letter is ‘z’, do nothing. Otherwise, insert after that letter, the subsequent letter of the alphabet.
For example, starting with the string ‘brazen’, after one iteration the string becomes ‘rsabzefno’, after applying the process again it becomes ‘stabbczeffgnoop’.
Demonstrate that given any finite length string, repeating this process will eventually result in the empty string.

Solution
As you may expect, there is nothing particularly special about our 26-letter alphabet. We can generalise this problem to an alphabet of any size. Let $$A_n = \{ a_n, a_{n-1}, \dots, a_1\}$$ be an alphabet of $$n \ge 1$$ letters. Given any string on $$A_n$$, the peculiar process will remove the first letter of the string and after every subsequent letter, $$a_{i}$$, will insert $$a_{i-1}$$ unless $$i=1$$. We proceed by induction on the number of letters in the alphabet.

Base Case: If $$n=1$$ then our string is only a sequence of $$a_1$$. The process only removes the first letter of the string which reduces it to the empty string.

Inductive Step: Suppose the proposition is true for an alphabet of size $$k-1$$ and consider any string $$\sigma$$ from the alphabet $$A_k$$. Observe that no $$a_i$$ with $$i>k$$ will ever appear, nor will any new $$a_k$$ appear as a result of applying the process to $$\sigma$$. Now, the prefix of $$\sigma$$ before the first $$a_k$$ (or to the end of the string, whichever is first), will be from an alphabet of $$k-1$$ letters, which will reduce to the empty string by the inductive assumption. In the next iteration the leading $$a_k$$ will be removed, which reduces the total number of letters $$a_k$$ in the string. It follows by induction that $$\sigma$$ will eventually be reduced to the empty string $$\square$$

Further reading here.

CPD: Actuaries Institute Members can claim two CPD points for every hour of reading articles on Actuaries Digital.