13
\$\begingroup\$

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
\$\endgroup\$
  • 3
    \$\begingroup\$ How flexible is the input format? May we take each pair as a 2-digit integer? \$\endgroup\$ – Arnauld Oct 5 at 9:50
  • 1
    \$\begingroup\$ @Arnauld Length-2 strings are OK, 2-digit numbers are not. \$\endgroup\$ – Bubbler Oct 5 at 15:15
  • \$\begingroup\$ @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. \$\endgroup\$ – Bubbler Oct 6 at 9:31
  • \$\begingroup\$ Is taking input “transposed” as two lists of 4 numbers (# correct for each guess / # misplaced for each guess) okay? \$\endgroup\$ – Lynn Oct 7 at 18:24
  • \$\begingroup\$ @Lynn That's fine. \$\endgroup\$ – Bubbler Oct 8 at 7:27
4
\$\begingroup\$

05AB1E, 38 33 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]
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ и4.Æ can be ã for -3 \$\endgroup\$ – Kevin Cruijssen Oct 5 at 9:49
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Oct 5 at 9:50
  • 1
    \$\begingroup\$ @KevinCruijssen thanks a lot. Now I can use filter instead of find first, since ã doesn't produce duplicates. \$\endgroup\$ – ovs Oct 5 at 9:55
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Oct 5 at 9:58
  • \$\begingroup\$ @KevinCruijssen working with a stack is confusing at times :/. Now fixed. \$\endgroup\$ – ovs Oct 5 at 10:03
2
\$\begingroup\$

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:
                      ʋ      -   last four links as a dyad:
            Œ!               -     all permutations (of the board in question)
              =              -     equals? (vectorises across the boards & test-board)
               §             -     sums
                     Ʋ       -     last four links as a monad:
                Ḣ            -       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
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ @ovs thanks! I if shorten it your way, the lambda does not seem to save any more bytes. Am I missing something? \$\endgroup\$ – Jitse Oct 5 at 9:26
  • \$\begingroup\$ 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 :). \$\endgroup\$ – ovs Oct 5 at 9:32
  • \$\begingroup\$ @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. \$\endgroup\$ – Jitse Oct 5 at 9:35
  • \$\begingroup\$ Here is some pre-3.8 inline assignment ;). \$\endgroup\$ – ovs Oct 5 at 9:40
  • \$\begingroup\$ @ovs Good find, thanks! \$\endgroup\$ – Jitse Oct 5 at 9:41
1
\$\begingroup\$

Charcoal, 53 bytes

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

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:

ΦE²⁵⁶⭆⁴﹪÷ιX⁴λ⁴

Filter through all possible 4-digit codes.

⁼Iθ

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

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

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

×⁹ΣEι⁼§λξν

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

ΣE⁴⌊⟦№ιIν№λIν

... the sum of matching and mismatching digits.

58 bytes to output using RYGB:

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

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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[]
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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)
]
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.