# Solve 4x4 Mastermind in exactly 5 steps

## Background

Mastermind is a game of code-breaking for two players. One of the players is codemaker (Alice) and the other is codebreaker (Bob).

4x4 means that the player should guess the length-4 sequence made of four alphabets (say RGBY). The hidden sequence may have duplicate letters, so there are $$\4^4 = 256\$$ possibilities in total.

At the start of the game, Alice sets up a hidden code, which Bob should guess correctly within a set number of turns. At each turn, Bob presents a guess, and Alice tells Bob how many of the positions are correct, and how many of the letters are correct but at a wrong position. For example, if the hidden code is RRYG and Bob guessed BRGY:

          Code: R R Y G
Guess: B R G Y
Correct: R(2nd-2nd)
Wrong position: Y(3rd-4th), G(4th-3rd)


Then Alice tells Bob the two counts 1, 2. (Note that the first R in the code does not contribute to the counts because the second R in the guess was already consumed as Correct.) Bob repeats the guess with different sequences, until the guess is identical to the code (getting 4, 0) or he runs out of turns.

## Challenge

The Dream World mastermind solver features four specific guesses so that the unique answer can be derived from their outcomes in all cases. The guesses are as follows:

1. R G G R
2. B B R R
3. Y Y G R
4. G B B Y


Given the outcomes of the four combinations above (four pairs of integers), output the unique hidden code.

You can assume the input is valid and the answer exists. You can choose to output any four distinct values (numbers/characters) in place of RGBY.

Standard rules apply. The shortest code in bytes wins.

NB: Fetching the results from the linked website is a standard loophole, and therefore forbidden.

## Test cases

Each pair in the input represents (correct, misplaced). Note that the answer can be one of the four predefined guesses (generating a (4, 0) in the input).

(2, 0), (2, 0), (1, 0), (0, 0) => R R R R
(2, 1), (1, 0), (1, 2), (1, 1) => G G Y R
(0, 2), (0, 2), (0, 3), (1, 2) => G R Y B
(2, 0), (0, 0), (2, 0), (0, 2) => Y G G G
(1, 1), (4, 0), (1, 0), (1, 1) => B B R R

• How flexible is the input format? May we take each pair as a 2-digit integer? – Arnauld Oct 5 '20 at 9:50
• @Arnauld Length-2 strings are OK, 2-digit numbers are not. – Bubbler Oct 5 '20 at 15:15
• @JCRM "Missing letters" means the hidden combination may contain zero copies of some letter, like RGGR which contains zero B's. There are no blanks in any hidden combination, and all positions must be one of four letters. – Bubbler Oct 6 '20 at 9:31
• Is taking input “transposed” as two lists of 4 numbers (# correct for each guess / # misplaced for each guess) okay? – Lynn Oct 7 '20 at 18:24
• @Lynn That's fine. – Bubbler Oct 8 '20 at 7:27

# 05AB1E, 3833 32 bytes

-6 bytes thanks to Kevin Cruijssen!

For each possible output this generates the input and selects the matching one. Colors are encoded as B=0, G=1, R=2, Y=3.

3Ý4ãʒU•˜ÐÐÛ•4в4äεœεX-0¢}¬Dràα‚}Q


Try it online!

Commented:

3Ý4ã              # Generate all possible outputs
3Ý                # range [0 .. 3]
4и              # to the 4th cartesian power

ʒU ... Q          # filter the possible outputs
#   where the following equals the input
#   and assign the current output to variable X

•˜ÐÐÛ•4в4ä        # encode the 4 guesses
•˜ÐÐÛ•            # compressed integer 2517300803
4в          # convert to base 4:
#   [2,1,1,2,0,0,2,2,3,3,1,2,1,0,0,3]
4ä        # split into 4 groups:
#   [2,1,1,2],[0,0,2,2],[3,3,1,2],[1,0,0,3]

εœεX-0¢}¬Dràα‚}   # compute the score for each guess
ε             }   # map over the guesses ...
œ                #   take all permutations
#     the first will be the original guess
ε    }          #   map over the permuations ...
X-             #     subtract the current output
0¢           #     count the 0's
¬         #   get the head without popping
#     this is number of correct positions (c)
D        #   duplicate it       => c, c, [...]
r       #   reverse the stack  => [...], c, c
à      #   take the maximum
#     this is number of correct colors,
#     correct and misplaced (c+m)
#                      => c+m, c, c
α     #   absolut difference => |c-(c+m)|, c = m, c
‚    #   pair up     => [c, m]

• и4.Æ can be ã for -3 – Kevin Cruijssen Oct 5 '20 at 9:49
• Also, the ©® can be UX (or VY), and then you can remove the I at the IQ, since it will use the input implicitly for another -1. – Kevin Cruijssen Oct 5 '20 at 9:50
• @KevinCruijssen thanks a lot. Now I can use filter instead of find first, since ã doesn't produce duplicates. – ovs Oct 5 '20 at 9:55
• Also, a small error in your explanation. After the triple swap it's c, c+m, c. The explanation after the Duplicate and Subtract are correct, though. – Kevin Cruijssen Oct 5 '20 at 9:58
• @KevinCruijssen working with a stack is confusing at times :/. Now fixed. – ovs Oct 5 '20 at 10:03

# Jelly,  29  28 bytes

4ṗð“ßƙṫl‘ị⁸Œ!=§Ḣ,Ṁạ\ƲʋþZiị⁸


A monadic Link accepting a list of four lists of two integers (the [correct, misplaced] pairs in order) which yields a list of four integers (where 1,2,3,4 map to R,G,B,Y respectively).

Try it online! (footer remaps back to the letters representing the colours.)

### How?

4ṗð“ßƙṫl‘ị⁸Œ!=§Ḣ,Ṁạ\ƲʋþZiị⁸ - Link: scores
4ṗ                          - 4 Cartesian power 4 -> all boards
ð                         - start a new dyadic chain f(boards, scores)
“ßƙṫl‘                   - code-page indices = [21, 161, 245, 108]
⁸                 - chain's left argument, boards
ị                  - index into -> the four test-boards
þ     - make a table of:
Œ!               -     all permutations (of the board in question)
=              -     equals? (vectorises across the boards & test-board)
§             -     sums
Ḣ            -       head -> total correctly placed
Ṁ          -       maximum -> total that could be correct by permuting
,           -       pair
\        -       cumulative reduce by:
ạ         -         absolute difference -> [correct, misplaced]
Z    - transpose
i   - first index of (scores) in (that)
⁸ - chain's left argument, boards
ị  - index into


# Python 3, 171 bytes

def f(s,a=0):b='%04i'%a;return([(w,sum(min(b.count(x),t.count(x))for x in{*t})-w)for t in('0110','2200','3310','1223')for w in[sum(map(str.__eq__,b,t))]]==s)*b or f(s,a+1)


Try it online!

-22 bytes thanks to ovs

Recursive function to test all possible combinations and find the matching input.

sum(map(str.__eq__,b,t)) finds the number of correct positions for each combination.

sum(min(b.count(x),t.count(x))for x in{*t}) finds the sum of the correct and misplaced positions. The number of misplaced positions is found by subtracting the number of correct positions.

Uses 0, 1, 2, 3 for R, G, B, Y, respectively.

• @ovs thanks! I if shorten it your way, the lambda does not seem to save any more bytes. Am I missing something? – Jitse Oct 5 '20 at 9:26
• In the original approach this saved more bytes, but Q=lambda*x:sum(map(str.__eq__,*x)) gets you to 185. This looks much better without itertools :). – ovs Oct 5 '20 at 9:32
• @ovs Ah yes, I forgot about the starred arguments, thanks. And indeed, itertools rarely makes anything look nicer :p I had considered switching to 3.8, but I like to avoid the walrus operator where I can. Just a personal preference. – Jitse Oct 5 '20 at 9:35
• Here is some pre-3.8 inline assignment ;). – ovs Oct 5 '20 at 9:40
• @ovs Good find, thanks! – Jitse Oct 5 '20 at 9:41

# Charcoal, 53 bytes

ΦＥ²⁵⁶⭆⁴﹪÷ιＸ⁴λ⁴⁼ＩθＥ⪪”)“∧.r⁹1”⁴⁺×⁹ΣＥι⁼§λξνΣＥ⁴⌊⟦№ιＩν№λＩν


Try it online! Link is to verbose version of code. Takes input as four strings containing pairs of digits in match mismatch order. Output uses digits 0-3 for the colours RYGB. Uses brute force. Explanation:

ΦＥ²⁵⁶⭆⁴﹪÷ιＸ⁴λ⁴


Filter through all possible 4-digit codes.

⁼Ｉθ


Convert the input pairs of digits to integers and compare with the result of...

Ｅ⪪”)“∧.r⁹1”⁴⁺


... checking the score of each of the patterns in the compressed string 0220330011202331 by taking the sum of...

×⁹ΣＥι⁼§λξν


... nine times the number of matching digits and...

ΣＥ⁴⌊⟦№ιＩν№λＩν


... the sum of matching and mismatching digits.

58 bytes to output using RYGB:

ΦＥ²⁵⁶⭆⁴§RYGB÷ιＸ⁴λ⁼ＩθＥ⪪”{⊞‴⊗⁵÷∧p<8'”⁴⁺×⁹ΣＥι⁼§λξνΣＥα⌊⟦№ιν№λν


Try it online! Link is to verbose version of code.

# JavaScript (ES6),  169 ... 160  153 bytes

Expects an array of 2-character strings "CM" with C = correct, M = misplaced. Returns an array of integers, with 0123 = RGBY.

f=(a,n)=>a.some((c,i)=>(g=n=>A=a.map(_=>4*(n/=4)&3))(n,b=g(3911125524>>>i*8)).map((v,k)=>c-=v^b[k]?b.some((w,j)=>v-w|v==A[j]?0:b[j]|=4):10)|c)?f(a,-~n):A


Try it online!

### How?

We generate all possible boards A[] and test them against the guesses b[] which are extracted from the 32-bit integer 3911125524 as follows:

3911125524 = 0xE91F0A14

0x14 = 00 01 01 00 -> R G G R
0x0A = 00 00 10 10 -> R R B B
0x1F = 00 01 11 11 -> R G Y Y
0xE9 = 11 10 10 01 -> Y B B G


We decrement the expected outcome c when a 'misplaced' digit is found and subtract 10 from c when a 'correct' digit is found. We stop when we have c = 0 for all guesses.

### Commented

f = (a, n) =>                // a[] = input array, n = counter
a.some((c, i) =>           // for each entry c at position i in a[]:
( g = n =>               //   g is a helper function turning a byte n
A = a.map(_ =>         //   into an array of 4 2-bit values
4 * (n /= 4) & 3     //   by isolating the 2 least significant bits
)                      //   and dividing by 4 between each iteration
)(                       //
n,                     //   invoke g with n to create the board A[]
b = g(                 //   invoke g with a byte extracted from ...
3911125524 >>> i * 8 //   ... this 32-bit integer ...
)                      //   ... to create the i-th guess b[]
)                        //
.map((v, k) =>           //   for each value v at position k in A[]:
c -=                   //     update c:
v ^ b[k] ?           //       if v is not equal to b[k]:
b.some((w, j) =>   //         decrement c if there's some w at position j
v - w |          //         in b[] such that v = w and v is not equal
v == A[j] ?      //         to A[j] (i.e. A[j] is not 'correct'),
0              //         in which case ...
:                //
b[j] |= 4      //         ... we invalidate b[j] by OR'ing it with 4
)                  //
:                    //       else:
10                 //         subtract 10 from c
)                        //   end of map()
| c                      //   yield a truthy value if c is ≠ 0
) ?                        // end of some(); if truthy:
f(a, -~n)                //   failure: do a recursive call with n + 1
:                          // else:
A                        //   success: return A[]


# R, 194 bytes

function(r,a=apply,~=table,g=matrix(762201603%/%4^(15:0)%%4,4))(p=expand.grid(rep(list(t<-0:3),4)))[a(p,1,function(y)all(a(g,1,function(h)c(z<-sum(y==h),sum(pmin(~c(t,y),~c(t,h))-1)-z))==r)),]


Try it online!

Uses the integers 0,1,2,3 to indicate R,G,B,Y.

How? (commented and de-golfed gode)

solve_mastermind=
function(r,                             # get responses r as 8-element vector
a=apply,                              # a = alias to apply() function (not used in de-golfed code here)
~=table,                            # ~ = alias to table() function (not used in de-golfed code here)
g=matrix(762201603%/%4^(15:0)%%4,4))  # g = matrix of guesses, compressed as a base-4 integer,
#     and decompressed here using DIV powers-of-4 MOD 4
(p=expand.grid(rep(list(0:3),4)))       # p = all possible permutations of codes (a 256 x 4 matrix)
[                                       # Select & return the correct row from p:
apply(p,1,function(y)                  # apply this function to all rows of p:
all( ... )==r                         # return true if all these values are equal to the elements of r:
apply(g,1,function(h)               # apply this function to all rows of g (that is, each of the 4 guesses):
c(                                  # return a 2-element vector, consisting of:
z<-sum(y==h),                     # 1. z = sum of elements of this code (y) that are equal to elements of this guess (h)
#     so: correct position + correct colour
sum(                              # 2. the sum of ...
pmin(                           #     the minima of ...
table(c(0:3,y)),              #      the count of the digits 0..3 in this code (y), +1
#       (the table() function counts the number of each type of instance.
#       However, we aren't sure that all of the digits will be present, and
#       absent digits would normally be uncounted (instead of counted as zero).
#       So we join the series 0..3 to y before counting the digits.
table(c(0:3,h)))              #      and the count of the digits 0..3 in this guess (h), +1
-1)           #     minus one (to account for the digits that we added)
-z)                               #    minus the number of correct position + correct colour
)==r)),                             # (see above)
]
`