28
\$\begingroup\$

You probably know the game mastermind:

The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time. Let's call those colors A through H, so possible solutions could be ABCD or BCHD.

Each time you place a guess, the game master will respond with two information: how many slots you got right, and how many colors you got right but in the wrong place.

Some examples:

If the code is ABCD
and your guess is ACHB
the response 12: the color A is correctly placed, the two colors B&C are in the wrong place.

Code is ABCD
you guess EFGH
response is 00

Code is ABCD
you guess ABCD
response is 40

A full representation would be:
ABCD04,DCBA40
or
ABCD00,EFGH22,EFHG13,HFGE40

A partial game does not contain the final solution, 
nor necessarily enough data to define a unique solution.
ABCD00,EFGH22,EFHG13

An example for an invalid partial game would be:
ABCD03,EFGH02: This would require that 5 colors are present

In essence, all games that cannot have a solution are invalid. The gamemaster made a mistake.

Your task

Never trust a game master. Your task is to write a program that takes a partial or full game description and validates whether such a game state is possible.

  • Expect that no game description is longer than 8 attempts.
  • Expect that the gamemaster can make a mistake on the very first turn, e.g. ABCD41
  • The player can make an "invalid" guess to gain further information, e.g. AAAA to check if there is an A at all. Such a game is still valid, you only evaluate the gamemaster's responses. In such a case, exact hit takes precedence over near-misses, for code ABCD it's AAAA10, not AAAA14.
  • You can format the input and output in whatever way you see fit, including replacing the colors by digits etc.
  • Any pre-generated hashtable counts towards the total number of bytes.
  • You know the loophole thing.

The shortest code wins.

Additional test cases:

 - ABCD11,ACEG02,HGFE11,CCCC10,CDGH01 => valid
 - ABCD01,EFGH03,CGGH11,HGFE21 => valid
 - ABCD22,EFGH01,ACDE11 => invalid
 - ABCD02,EFGH01,AABB21,AEDH30 => invalid
 - ABCD03,DCBA02 => invalid 
 - ABCD32 => invalid

You can generate any number of valid cases by playing the game. Invalid solutions are hard to come up with. If you find invalid combinations that first slipped through your code, please comment it below for your fellow golfers.

Bonus: Bonus points if you come up with a solution that uses a significantly different approach than generating and traversing all possible permutations.

\$\endgroup\$
12
  • 3
    \$\begingroup\$ Welcome to the site. Nice first challenge. Can we have a test case that includes CGCC (Code Golf & Coding Challenges) just for the fun of it :-) \$\endgroup\$
    – ElPedro
    Aug 11, 2020 at 14:14
  • \$\begingroup\$ @ElPedro I'd suggest CGCC02,GAGA02,CAFE12 => valid. \$\endgroup\$
    – Arnauld
    Aug 11, 2020 at 15:59
  • \$\begingroup\$ A general question - am I supposed to accept an answer? And if so, how long shall I wait? \$\endgroup\$ Aug 13, 2020 at 7:26
  • 1
    \$\begingroup\$ @Veskah; Good point. I didn't explicitly define it. Though in most implementations it would be 0,1, I would stick with the negated example: "for code ABCD it's AAAA10, not AAAA14." So it 's 0,3 . \$\endgroup\$ Aug 13, 2020 at 17:12
  • 2
    \$\begingroup\$ @Veskah: As this is my first challenge and I clearly oversaw this issue, I will just accept both versions. It's an edge-case not worth sinking anything. \$\endgroup\$ Aug 13, 2020 at 18:14

4 Answers 4

16
\$\begingroup\$

JavaScript (ES6),  116 112  107 bytes

Expects an array of entries in the following format: [[a,b,c,d], "XY"], where a to d are integers in [0..7], X is the number of correct digits and Y is the number of near-misses.

Returns 0 or 1.

f=(a,n)=>n>>12?0:!a.some(([a,x])=>!a.every(o=(d,i)=>o[x-=d^(v=n>>i*3&7)?a.includes(v):10,v]^=1)|x)|f(a,-~n)

Try it online!

Commented

f = (                     // f is a recursive function taking:
  a,                      //   a[] = input
  n                       //   n = 12-bit counter, initially undefined, to
) =>                      //       describe all possible codes
n >> 12 ?                 // if n = 4096:
  0                       //   stop the recursion
:                         // else:
  !a.some(([a, x]) =>     //   for each entry [a, x, y] in a[], with a[] =
                          //   guess, x = correct digits and near-misses:
    !a.every(o =          //     we use the object o to keep track of the
                          //     digits that were already extracted from n,
                          //     in order to discard invalid codes
      (d, i) =>           //     for each value d at position i in a[]:
      o[                  //
        x -=              //       update x:
          d ^ (           //         compare d with ...
            v =           //         ... v which is defined as ...
              n >> i * 3  //         ... the next 3-bit digit extracted from n
              & 7         //
          ) ?             //         if d is not equal to v, decrement x if ...
            a.includes(v) //           ... v appears elsewhere in a[]
          :               //         else:
            10,           //           subtract 10 from x
        v                 //       actual index in o to ...
      ] ^= 1              //       ... mark this digit as used; or yield 0
                          //       and exit every() if it was already used
    )                     //     end of every(); the iteration fails if it's
    | x                   //     falsy or x is not equal to 0
  )                       //   end of some()
  | f(a, -~n)             //   do a recursive call with n + 1
\$\endgroup\$
2
  • 10
    \$\begingroup\$ Scholars will be studying how this works for years to come. \$\endgroup\$
    – 640KB
    Aug 11, 2020 at 19:01
  • \$\begingroup\$ 106 \$\endgroup\$
    – l4m2
    Jan 25, 2022 at 16:15
7
\$\begingroup\$

Charcoal, 47 bytes

⊙EX⁸¦⁴E⁴§α﹪÷ιX⁸λ⁸∧⬤ι⁼№ιλ¹⬤θ⁼I…⮌λ²ΣEι∨⁼ν§λξ∧№λνχ

Try it online! Link is to verbose version of code. Brute-force, but only takes a second or so on TIO. Outputs a Charcoal boolean, i.e. - for truthy, nothing for falsy. Explanation:

⊙EX⁸¦⁴E⁴§α﹪÷ιX⁸λ⁸

Generate all possible codes including duplicates, and see if any of them satisfies the following.

∧⬤ι⁼№ιλ¹

Check that the code contains no duplicates, and...

⬤θ

... check whether all of the guesses satisfy the following.

⁼I…⮌λ²

Get the result of the guess and check that it equals the following.

ΣEι

Map over each character of the code.

∨⁼ν§λξ

Check whether it's an exact match.

∧№λνχ

Check whether it's misplaced.

60 46 44-byte version for a version that allows duplicates in the code:

⊙EX⁸¦⁴E⁴§α﹪÷ιX⁸λ⁸⬤θ⁼Σλ⁺×⁹ΣEι⁼ν§λξΣEα⌊⟦№ιν№λν

Try it online! Link is to verbose version of code. Brute-force, so takes a few seconds on TIO for falsy cases. Outputs a Charcoal boolean, i.e. - for truthy, nothing for falsy. Explanation:

⊙EX⁸¦⁴E⁴§α﹪÷ιX⁸λ⁸

Generate all possible codes including duplicates, and see if any of them satisfies the following.

⬤θ

Check whether all of the guesses satisfy the following.

⁼Σλ⁺

Extract the result of the guess (when passed a string which contains non-digits, Sum looks for embedded integer(s) and takes their sum rather than their digital sum) and check that it equals the sum of the following:

×⁹ΣEι⁼ν§λξ

Count 9 for each exact match.

ΣEα⌊⟦№ιν№λν

Count each match (whether exact or misplaced).

Edit: I had inadvertently calculated 4⁸ instead of 8⁴, so the code was taking 16 times longer than it needed to.

\$\endgroup\$
3
\$\begingroup\$

Python3, 304 140 bytes

lambda l:any(all(sum((x in t)+9*(x==y)for x,y in zip(p,t))==int(t[4:])for t in l)for p in permutations('ABCDEFGH',4))
from itertools import*

Lambda expecting input in the form of an array. Try it online!

Or 156 bytes as a full python program with textual input/output:

from itertools import*
l=input()
print(any(all(sum((x in t)+9*(x==y)for x,y in zip(p,t))==int(t[4:])for t in l.split())for p in permutations('ABCDEFGH',4)))

(try it online)

Could save 2 bytes by replacing 'ABCDEFGH' with range(8), but then input should be in the form 012311,024602,765411,222210,236701.

History of edits: move r=[0,1,2,3] outside of function and remove [] to save 3 bytes; remove () around return value to save 2 bytes; replace def f(p,t): with lambda p,t: to save about 8 bytes; replace [...].count(True) with sum(...) to save 5+3=8 bytes; remove intermediary variable m to save 5 bytes; use := in a much better way to get rid of the nested lambda and the awkward (,,)[-1] and save 26 bytes; @Arnauld fixed a mistake with the rules of mastermind and golfed it down to 221 bytes; @Arnauld did some magic with the booleans and ints to golf it to 185; replace for i in range(4) with for x,y in zip(p,t) to save 7 bytes; save 10 bytes by replacing (lambda l:...)(input()) with l=input() ...; @Arnauld saves 8 bytes by replacing t.count(x)and 1+9*(x==y) with (x in t)+9*(x==y) (which is also easier to understand in my opinion) plus 3 bytes by requiring whitespace-separated input to replace .split(',') with .split(), @Arnauld saves 1 byte by replacing import itertools as i with from itertools import*; @Arnauld removed 16 bytes by making it a lambda instead of a full python program

Less compact, more readable version

import itertools as i

r=0,1,2,3
def f(p,t):
    correct = [p[i]==t[i] for i in r]
    misplaced = [t.count(p[i]) and not correct[i] for i in r]
    return sum(correct) * 10 + sum(misplaced) == int(t[4:])

def z(line):
    return any(all(f(p,t) for t in line.split(',')) for p in i.permutations('ABCDEFGH',4))

print(z(input()))
  • f(p,t) is True if combination p passes test t. p is a size-4 array which might not contain duplicates (eg ABCD). t is a size-6 array which might contain duplicates (eg CCCC10).
  • z(line) is True if there exists at least one legal combination p which passes all tests t; tests are described by the comma-separated string line.
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Nice first answer! The challenge explicitly allows to replace letters with digits, so your alternate input format should be fine. \$\endgroup\$
    – Arnauld
    Aug 12, 2020 at 17:12
  • \$\begingroup\$ Thanks for the feedback! Sacrificing the input format for two bytes might be worth it if the code was shorter, but is too high a sacrifice for 2 bytes out of 249! About the failure on CGCC02,GAGA02,CAFE12: it returns False. Should it return True instead? CGCC01 means no C is correctly placed, but 1 or 2 C are misplaced. Yet there are three C. Shouldn't all three of them be misplaced? If the program should return True, then I fear the issue might be with my understanding of mastermind, rather than with the code implementation of my logic. \$\endgroup\$
    – Stef
    Aug 13, 2020 at 12:00
  • 1
    \$\begingroup\$ 157 bytes (now expecting a space-separated list). \$\endgroup\$
    – Arnauld
    Aug 13, 2020 at 13:58
  • 1
    \$\begingroup\$ Or 140 bytes with a lambda taking a list. \$\endgroup\$
    – Arnauld
    Aug 13, 2020 at 14:09
  • 1
    \$\begingroup\$ The default rule for code-golf is program or function. BTW, it's pretty standard to include a Try it online! link in your answer so that it can be easily tested. \$\endgroup\$
    – Arnauld
    Aug 13, 2020 at 14:42
2
\$\begingroup\$

R + gtools, 130 125 bytes

function(l)any(apply(permutations(8,4),1,function(c)all(sapply(l,function(g)g[[2]]==c(x<-sum(c==el(g)),sum(c%in%el(g))-x)))))

Try it online!

Colours are represented by digits 1..8. Returns 'TRUE' for valid games and 'FALSE' for invalid gamemaster responses.

Commented:

mastermind_check=function(l)            # l=list of lists of [guess,response]
 any(                                   # do any of...
  apply(permutations(8,4),1,            # all possible codes...
   function(c)all(                      # produce all valid responses for...
    sapply(l,                           # every [guess,response] pair...
     function(g)                        # using this function to define valid response:
      all(g[[2]]==c(                    # - both of these must be the same:
        x<-sum(c==el(g)),               #   - response[1] == sum of correct cols in correct pos
        sum(c%in%el(g))-x               #   - response[2] == sum of correct cols in any pos
      )                                 #                    minus response[1]
)))))                                   # ...?

R, 114 bytes

function(l){while(T)T=!all(y<-sample(1:8,4),sapply(l,function(g)g[[2]]==c(x<-sum(y==el(g)),sum(y%in%el(g))-x)));1}

Try it online!

Stochastic function that checks random codes until it finds one that could satisfy the gamemaster responses, at which point it halts and returns 1.
Halting is assured in finite time for all valid gamemaster responses.
If gamemaster response is invalid, function never halts.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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