Solving Mastermind in 6 or less moves

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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[0]
    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)]