# Solving Mastermind in 6 or less moves

Your goal is to write a program that will solve any Mastermind puzzle in 6 or less moves.

### Background

Mastermind is a board game. The goal of the game is to exactly guess the combination (colours and order) of 4 coloured pegs hidden by the other player. When a guess is made, the other player responds with between 0 and 4 white and or red pegs. A red peg is where the colour and location are correct. A white peg is where the colour is represented in the remaining pieces, but is in the incorrect location. If there are duplicate colours in the guess, there will only be one peg awarded per corresponding colour in the secret. (So - if the secret contained 1 Blue, and the guess had 2 blues with one in the correct location, there would be one red peg given). There are 6 different colors, and duplicates may be used.

So for instance, a game might go as follows: (Assuming the solution is Red Green Green Blue)

1:  Blue Purple Black Green - 2 white pegs
2:  Green Red Black Blue    - 2 white pegs, 1 red peg
3:  Green Green Green Blue  - 3 red pegs
4:  Red Green Green Blue    - 4 red pegs


The rules are expanded on Wikipedia

### Requirements

• The program must read from stdin, and write to stdout
• I will be using numbers for simplicity instead of colors. The combination to guess will be 4 numbers between 1 and 6
• They must output their guesses as a series of 4 space separated numbers from 1 to 6 concluding with a newline. For instance:

1 5 2 2 \n

• The program will subsequently receive as input after its guess 2 integers between 0 and 4 separated by a space and concluding with a newline. The first will be the amount of white pegs, the second the amount of red pegs.

• On an input of "0 4" (4 red pegs), the program must terminate
• The program must be able to solve any puzzle in less then 6 turns (your program giving output, followed by the response input is 1 turn). There is no bonus (due to complexity of proof) for being able to solve it in less.
• The solution must be completely internal and included in the source. Standard Libraries only are permitted. The solution may therefore not rely on any other files (such as dictionaries), or the internet.

### Example Input/Output

> is your programs output
< is the responding input
Solution is 1 5 6 6

> 1 2 3 4
< 0 1
> 4 1 6 6
< 1 2
> 1 6 5 6
< 2 2
> 1 5 6 6
< 0 4


### Scoring

• This is pure and simple Code Golf. The shortest solution in bytes wins.

This is my first Code Golf question. My apologies if I have done something wrong, but I've attempted as well as possible to ensure that there is absolutely no ambiguity, and prevent as much rules lawyering as possible. If I have been ambiguous or unclear, please feel free to ask questions.

• In your example input/output shouldn't 1 2 3 4 return 0 1? – Gaffi Mar 21 '12 at 14:57
• And in the example text, shouldn't "Green Green Green Blue" give a white peg as well (for the first Green)? EDIT - Wikipedia clarifies that no white should be given, as you wrote. But I think the white/black rules should be explicitly stated in the question. – ugoren Mar 21 '12 at 17:23
• How slow will it be allowed to work? – ceased to turn counterclockwis Mar 21 '12 at 18:24
• @Gaffi - Absolutely right - fixed – lochok Mar 21 '12 at 20:04
• The rules for white pegs are not stated here. Suppose you chose 1234 and I guess 5611. Both my 1s are the right color in the wrong place, so from the way you stated the rules I'd say I get 2 whites. But no - Wikipedia says it's 1 white. The incorrect method is also easier to program (but Steven Rumbalski correctly implemented Wikipedia's rules). – ugoren Mar 22 '12 at 5:33

# Python 2 Python 3, 359 365 338 chars

from itertools import*
from collections import*
m=h=set(product(*['123456']*4))
def f(g,k):b=sum(x==y for x,y in zip(g,k));return'%s %s'%(sum(min(g.count(c),k.count(c))for c in set(g))-b,b)
while len(m)>1:g=min(h,key=lambda g:max(Counter(f(g,k)for k in m).values()));print(*g);s=input();m=set(x for x in m if s==f(g,x))
print(*(m.pop()))


Funny, it took me many edits to realize I had a five character variable name.

I do not like the long imports. It feels like I should be able to implement a replacement for collections.Counter that would save the import.

I also do not like the print(*(m.pop())) at the end. It feels like it should disappear into the while loop, but I can't find a way to do it without making it longer.

• TypeError: join() takes exactly one argument (2 given) on return j(sum(min(g.count(c),k.count(c))for c in set(g))-b,b). also, sum() returns an int, while j (str.join) should take an iterable – Blazer Mar 22 '12 at 7:23
• My loop structure gets rid of the final print, and I think it's slightly shorter. It also matches the requested behavior better (stopping on "4 0" rather than when you know the answer). And len(m)>1==m[1:]. Import is indeed annoying - from a,b import * would have been nice. – ugoren Mar 22 '12 at 17:29
• this program seems to exit whenever it feels it's right. one time I ran it and it stopped at 5 guesses, it wasn't correct. the next time it stopped at 4 guesses and it was correct, but I didn't even input 4 0 yet, which is in the objective criteria, and other times it will exit with an exception: print(*(m.pop())) KeyError: 'pop from an empty set' – Blazer Mar 22 '12 at 18:18
• @Blazer. What are the test cases that caused this output? – Steven Rumbalski Mar 22 '12 at 18:33
• @Blazer: 4 0 is four white pegs. I think you have the scoring reversed. – Steven Rumbalski Mar 22 '12 at 18:45

## Haskell, 317 304

q[0,4]_=error""
q[n,m]l=(\s->all(==4-m)[g s,n+g(u(foldr((u((.drop 1).(++)).).break.(==)))$unzip s)]).c(u(/=)).zip l u=uncurry;m=map;g=length;c=filter f a=[head.c(($(zipWith q(take n a)$f a)).all.flip($)).sequence$replicate 4[1..6]|n<-[0..]] main=interact$unlines.m(unwords.m show).f.m(m read.words).lines


I love writing purely functional interactive programs! But of course this style has certain limitations: it terminates now with an error, but you didn't specify that this is not ok. I'd need to refactor the whole thing into the IO monad to get a non-error exit.

• Does it guarantee a correct guess in 6 moves? – ugoren Mar 22 '12 at 14:13
• Uh. I thought it was (works for the OP's example and other solutions), but exhaustive testing shows that it sometimes needs 7 guesses. I shall have to work on this yet! – ceased to turn counterclockwis Mar 22 '12 at 15:16

## Python, 385 357 chars, Solves in 5 moves

The more I change it, it grows more and more like Steven Rumbalski's... The main difference is that he works with strings rather than integers.
Implemented Knuth's algorithm (correctly now, I hope).
Borrowed the scoring function from Steven Rumbalski.
It takes a long time to generate the first guess, gets better later.
Hard-coding it (g=len(A)==1296 and [1,1,2,2] or ...) makes life easier if you want to test it.
I don't count 4 newlines+tab pairs, which can be replaced by semicolons.

from collections import*
from itertools import*
a=B=A=list(product(*[range(1,7)]*4))
r=lambda g,k:(sum(x==y for x,y in zip(g,k)),sum(min(g.count(c),k.count(c))for c in set(g)))
while a!=4:
g=A[1:]and min(B,key=lambda x:max(Counter(r(x,i)for i in A).values()))or A
print"%d "*4%tuple(g)
b,a=map(int,raw_input().split())
A=[x for x in A if r(g,x)==(a,a+b)]

• "%d "*4%tuple(g) – gnibbler Mar 22 '12 at 9:08
• from collections import* – gnibbler Mar 22 '12 at 9:09
• a,b=map(int,raw_input()) – gnibbler Mar 22 '12 at 9:11
• product(*[range(1,7)]*4) – gnibbler Mar 22 '12 at 9:17
• Counter(r(x,i)for i in A).values() – gnibbler Mar 22 '12 at 9:20