24
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ In your example input/output shouldn't 1 2 3 4 return 0 1? \$\endgroup\$ – Gaffi Mar 21 '12 at 14:57
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ugoren Mar 21 '12 at 17:23
  • \$\begingroup\$ How slow will it be allowed to work? \$\endgroup\$ – ceased to turn counterclockwis Mar 21 '12 at 18:24
  • \$\begingroup\$ @Gaffi - Absolutely right - fixed \$\endgroup\$ – lochok Mar 21 '12 at 20:04
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – ugoren Mar 22 '12 at 5:33
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Blazer Mar 22 '12 at 7:23
  • \$\begingroup\$ 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. \$\endgroup\$ – ugoren Mar 22 '12 at 17:29
  • \$\begingroup\$ 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' \$\endgroup\$ – Blazer Mar 22 '12 at 18:18
  • \$\begingroup\$ @Blazer. What are the test cases that caused this output? \$\endgroup\$ – Steven Rumbalski Mar 22 '12 at 18:33
  • \$\begingroup\$ @Blazer: 4 0 is four white pegs. I think you have the scoring reversed. \$\endgroup\$ – Steven Rumbalski Mar 22 '12 at 18:45
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does it guarantee a correct guess in 6 moves? \$\endgroup\$ – ugoren Mar 22 '12 at 14:13
  • \$\begingroup\$ 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! \$\endgroup\$ – ceased to turn counterclockwis Mar 22 '12 at 15:16
5
\$\begingroup\$

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

PC DOS, 8088 assembly, 800 bytes

As a follow-on to my previous post and per the suggestion of @Rogem, I'm submitting the solution to which I was referring. This was written with the goal of speed in mind, not shortest character count, so this is not a golfed entry.

This does fully implement Knuth's Mastermind algorithm, so based on his proof this will solve a 6/4 board (6 colors, 4 pegs) in five or fewer moves.

        TITLE MMSOLVE
        DOSSEG
        .MODEL SMALL
        .STACK 100H

MAJVER  EQU '1'                 ; this version
MINVER  EQU '1'

COLS    EQU 6                   ; game play possible colors
PATT    EQU 4                   ; game play secret pattern length
GUES    EQU 6                   ; game play number of guesses

CLRS    EQU 'A'                 ; first pattern character
;CLRS   EQU '1'                 ; first pattern character
HNTS    EQU 'xo-'               ; three hint chars: black, white and none
;HNTS   EQU 'BW.'               ; hint chars: black, white and none

x   =   COLS                    ; calculate exponent (MASM has no built-in exponent macro)
        REPT PATT - 1
x   =   x * COLS
SSZ     EQU x                   ; SSZ EQU COLS ^ PATT
        ENDM

; simple implementation of integer-key-based array
AARY_SZ EQU 28                  ; length of array
AARY    STRUC
KEY     DW  AARY_SZ DUP(?)
VAL     DW  AARY_SZ DUP(?)
LEN     DW  0
AARY    ENDS

; clear a key-based array
; mangles AX, DI
AARY_CLEAR  MACRO AARR
            LOCAL SZARR
SZARR = (LENGTH AARR.VAL-LENGTH AARR.KEY)
        PUSH CX
        ;CLD                        ; scan forward for key
        MOV  AX, 0FFFFH             ; write FFFFH's to keys
        MOV  CX, SZARR / 2
        LEA  DI, AARR.KEY
        REP  STOSW
        XOR  AX, AX                 ; write 0's to values
        MOV  CX, (SZARR / 2) + 1    ; also clear LEN variable
        LEA  DI, AARR.VAL
        REP  STOSW
        POP  CX
        ENDM

; set a value in key-based array
AARY_SET    MACRO   AARR, KEY, VAL
            LOCAL   KEY_EXISTS, SZARR, SZELE
SZARR = (LENGTH AARR.VAL-LENGTH AARR.KEY)
SZELE = TYPE AARR.KEY           
        LEA  DI, AARR.KEY       ; SCASW looks for AX in ES:DI (it will advance DI)
        MOV  CX, AARR.LEN       ; only look array's length
        CMP  CX, 1              ; reset ZF
        IFDIFI <KEY>,<AX>       ; skip next MOV if KEY is AX
        MOV  AX, KEY            ; (2) search for value in KEY
        ENDIF
        REPNE SCASW             ; look for key in AX in array
        JZ   KEY_EXISTS         ; if REPNE ends with ZF, value was found
NEW_KEY:
        MOV  WORD PTR [DI], AX  ; otherwise, create key
        ADD  DI, SZELE          ; if key was found it will be advanced by WORD size so need to be consistent
        INC  AARR.LEN           ; array length grown by 1
KEY_EXISTS:
        MOV  WORD PTR [DI][SZARR-SZELE], VAL
        ENDM

; increment integer value in key-based array
; destroys AX, CX and DI
AARY_INC    MACRO   AARR, KEY
            LOCAL   KEY_EXISTS, SZARR, SZELE, NEW_KEY
SZARR = (LENGTH AARR.VAL-LENGTH AARR.KEY)
SZELE = TYPE AARR.KEY
        LEA  DI, AARR.KEY       ; (2+EA) SCASW looks for AX in ES:DI (it will advance DI)
        MOV  CX, AARR.LEN       ; (12+EA) only look array's length
        CMP  CX, 1              ; (4) reset ZF
        IFDIFI <KEY>,<AX>       ; skip next MOV if KEY is AX
        MOV  AX, KEY            ; (2) search for KEY
        ENDIF
        REPNE SCASW             ; (9+19n) look for key in AX in array
        JZ   KEY_EXISTS         ; (4/16) if REPNE ends with ZF, value was found
NEW_KEY:
        MOV  WORD PTR [DI], AX  ; (13+EA) otherwise, create key
        ADD  DI, SZELE          ; (13+EA) if key was found it will be advanced by WORD size so need to be consistent
        INC  AARR.LEN           ; (23+EA) array length grown by 1
KEY_EXISTS:
        INC  WORD PTR [DI][SZARR-SZELE] ; (23+EA)
        ENDM

; clear array of BYTE
; Input: ARR: address of array start, BVAL value to fill
; mangles AX, CX, DI
CLR_ARRB MACRO ARR, BVAL
        CLD                     ; [2]
        MOV  AL, BVAL           ; [2] (if reg)
        XOR  CH, CH             ; [3]
        MOV  CL, LENGTH ARR     ; [4]
        LEA  DI, ARR            ; [2+EA]
        REP  STOSB              ; [9+10n]
        ENDM

; calculate exponent
; Input: Unsigned BYTE: FACTOR and EXP
; AX = pow(FACTOR, EXP)
POWER   MACRO   FACTOR, EXP
        LOCAL   AGAIN, GOTZERO
        PUSH CX
        PUSH BX
        XOR  CH, CH
        MOV  CL, EXP            ; Exponent is count for loop
        XOR  BX, BX
        MOV  AX, 1              ; Multiply by 1 first time
        JCXZ GOTZERO            ; Get out if exponent is zero
        MOV  BL, FACTOR
AGAIN:  MUL  BX                 ; Multiply until done
        LOOP AGAIN
GOTZERO:
        POP  BX
        POP  CX
        ENDM                    ; result in AX

; return larger of values A and B into A
; Note: one must be a register
; A = max(A, B)
MAX     MACRO   A, B
        LOCAL   END_MAX
    CMP  A, B
    JGE  END_MAX        ; if B less than A, do nothing (answer is A)
    MOV  A, B
END_MAX:
        ENDM            ; result is in A

; return smaller of values A and B into A
; Note: one must be a register
; A = min(A, B)
; timing: 9/19 (19 if A <= B, 9 if B < A)
MIN     MACRO   A, B
        LOCAL   END_MIN
    CMP  A, B           ; (3)
    JLE  END_MIN        ; (4/16) if A <= B, do nothing (answer is already in A)
    MOV  A, B           ; (2)
END_MIN:
        ENDM            ; result is in A

; unsigned return smaller of values A and B into A
; if there is a change then: X = Y
; Note: one must be a register
; A = min(A, B)
UKMIN   MACRO   A, B, X, Y
        LOCAL   END_MIN
    CMP  A, B
    JC   END_MIN        ; if B less than A, do nothing (answer is A)
    MOV  A, B
    MOV  X, Y
END_MIN:
        ENDM            ; result is in A

        .DATA?
S2      DW  SSZ/2+1 DUP(?)      ; array of remaining possible values of S
S2LN    DW  ?                   ; count of S2 array
P_WC    DB  COLS DUP(?)         ; array count pattern guess white peg
G_WC    DB  COLS DUP(?)         ; array count player guess white peg
H       AARY <>                 ; used to tabulate next guess in second pass

        .DATA
S       DW  SSZ/2+1 DUP(101H)   ; BYTE (boolean only) for each possible pattern as flag
CH_HNTS DB  HNTS                                        ; hints in memory for individual display
ST_PMT  DB  'Score [',HNTS,']? $'                       ; prompt for hints
ST_FAIL DB  0DH,0AH,'Incorrect game play or scoring.$'  ; invalid hints provided (game over)
ST_WELC DB  'Mastermind Solver v',MAJVER,'.',MINVER     ; welcome greeting
        DB  '  ',COLS+'0',' colors'
        DB  ' (',CLRS,'-',CLRS+COLS-1,'), '
        DB  PATT+'0',' pegs.  ',0DH,0AH,0DH,0AH,'$'
ST_CALC DB  'Calculating: $'                            ; shown while calculating

        .CODE

START:
    MOV  AX, @DATA          ; load DATA segment location
    MOV  DS, AX             ;   into DS register
    MOV  ES, AX             ;   into ES register

    MOV  AH, 09H            ; display welcome message
    LEA  DX, ST_WELC
    INT  21H

    CALL INIT_GUESS         ; generate the initial guess into DX
    MOV  AX, SSZ            ; number of remaining solutions (all in this case) into AX
    MOV  CX, GUES           ; loop max number of allowed guesses

PLAY_LOOP:
    PUSH AX                 ; save count of remaining solutions
    MOV  AX, GUES+1         ; display guess counter, using CX loop counter
    SUB  AX, CX
    CALL OUTDEC
    MOV  AX, DX             ; next solution from NEXT_GUESS/INIT_GUESS is in DX
    CALL TAB
    CALL PR_SEQ             ; display formatted guess in AX
    CALL TAB
    POP  AX                 ; restore count of solutions remaining
    CALL OUTDEC             ; display count of remaining solutions
    CALL TAB
    CALL GET_HINTS          ; prompt player for hints, put into BX
    CALL NL
    CMP  BX, 4              ; if score was four hints game is over
    JE   GAME_SHOW_SEQ
    CALL NEXT_GUESS         ; DX = prev guess, BX = hints from DX; ret DX = next guess, AX = guess remain count
    CMP  AX, 1              ; if only one solution remains, it is the correct one
    JE   GAME_DONE
    CMP  AX, 0              ; if no solutions, hint responses were given inaccurately
    JE   SCORE_FAIL
    LOOP PLAY_LOOP

SCORE_FAIL: 
    MOV  AH, 09H            ; no possible solutions from hints provided - print error message
    LEA  DX, ST_FAIL
    INT  21H    
    JMP  SHORT EXIT

GAME_DONE:                  ; completed because only one valid solution was found
    MOV  AX, GUES+2         ; display last guess counter, using CX loop counter
    SUB  AX, CX
    CALL OUTDEC

GAME_SHOW_SEQ:              ; completed because score was all black
    CALL TAB
    MOV  AX, DX             ; the only solution is in DX
    CALL PR_SEQ             ; display formatted guess in AX
    CALL NL

EXIT:                       ; exit to DOS
    MOV  AX, 4C00H          ; DOS 2.0+ - terminate with return code 0
    INT  21H                ; execute

; Function:
;       Print formatted pattern sequence
; Inputs:
;       Sequence in AX
; Outputs:
;       Formatted pattern to screen
; Preserves AX, CX
PR_SEQ PROC                 ; print formatted guess in AX
    PUSH AX                 ; save original sequence
    PUSH BX
    PUSH CX                 ; save to preserve any currently running LOOPs
    PUSH DX

BEGIN_PR_SEQ:
    MOV  CX, PATT           ; count number of digits in pattern
    MOV  BX, COLS           ; number of colors/digits as divisor in BX

PR_COL_LOOP:
    XOR  DX, DX             ; zero DX ( will never have a 32 bit quotient )
    DIV  BX                 ; DX:AX = quot (use AX for next loop), DX = mod
    ADD  DL, CLRS           ; add index to first char in sequence
    PUSH DX                 ; save char to stack to display in reverse below
    LOOP PR_COL_LOOP
                            ; display reversed
    MOV  CL, PATT           ; reset loop for display
    MOV  AH, 02H            ; display char function

PR_COL_DISP:
    POP  DX                 ; display "color" char
    INT  21H
    MOV  DL, ' '            ; display space
    INT  21H
    LOOP PR_COL_DISP

    POP  DX
    POP  CX
    POP  BX
    POP  AX
    RET

PR_SEQ ENDP

; Function:
;       Score two sequences and calculate hint pegs
; Inputs:
;       Variables:
;       BX (P1): Secret Pattern 
;       DX (G1): Player guess
; Outputs:
;       AX: AL = black pegs, AH = white pegs
; Mangles: DI, BP
CALC_SCORE PROC
    PUSH CX                 ; (15)
    PUSH DX                 ; (15)
    PUSH SI                 ; (15)

CMP_CLEAR:                  ; clear all working variables
    XOR  CX, CX             ; (3)
    CLR_ARRB G_WC, CL       ; (22 + EA + (10 * COLS))
    CLR_ARRB P_WC, CL       ; (22 + EA + (10 * COLS))

SCORE_BLACK:
    MOV  AX, DX             ; (2)
    MOV  SI, BX             ; (2)
    MOV  BX, COLS           ; (4) number of colors/digits as divisor in BX
    MOV  CL, PATT           ; (4) loop number of possible colors

LOOP_BLACK:
    XOR  DX, DX             ; (3) divide guess
    DIV  BX                 ; (144-162 yowch) DX AX = quot (use AX for next loop), DX = mod
    MOV  BP, DX             ; (2) save modulo of guess in BP
    MOV  DI, DX             ; (2)
    INC  G_WC[DI]           ; (23+EA) increment count at index DX in Guess White Count array
    XCHG AX, SI             ; (3) switch AX to pattern

    XOR  DX, DX             ; (3) divide pattern    
    DIV  BX                 ; (144-162) DX AX = quot (use AX for next loop), DX = mod
    MOV  DI, DX             ; (2) increment count at index DX in Pattern White Count array
    INC  P_WC[DI]           ; (23+EA)
    XCHG AX, SI             ; (3) switch AX back to guess

    CMP  DX, BP             ; (3) check if guess and pattern have same modulo
    JNE  END_LOOP_BLACK     ; (4/16)
    INC  CH                 ; (3) if so, this is a black peg

END_LOOP_BLACK:
    DEC  CL                 ; (3)
    TEST CL, CL             ; (3) if CL > 0
    JNZ  LOOP_BLACK         ; (4/16)

SCORE_WHITE:
    XOR  AX, AX             ; (3) AH = count of black and white pegs combined
    MOV  DI, COLS           ; (4) loop and count all score pegs in G_WC and P_WC    

LOOP_WHITE:
    MOV  BL, G_WC[DI-1]     ; (12+EA) put GUESS in BL
    MOV  BH, P_WC[DI-1]     ; (12+EA) put PATT in BH
    MIN  BL, BH             ; (9/19) add min of BL and BH
    ADD  AH, BL             ; (3) to count of white and black (AH)
    DEC  DI                 ; (3)
    TEST DI, DI             ; (3) if DI > 0
    JNZ  LOOP_WHITE         ; (4/16) if 0, jump to end

SCORE_RESULT:
    MOV  AL, CH             ; (2) AL/CH = black pegs, AH = black + white
    SUB  AH, AL             ; (3) AL = black pegs, AH = white pegs

SCORE_END:
    POP SI                  ; (12)
    POP DX                  ; (12)
    POP CX                  ; (12)
    RET

CALC_SCORE ENDP

; Generate initial guess:
;   Half of the first color and half of the second color
;   If odd number, the extra is the second color
;   Example: A A B B B
; Output: DX: initial guess
; Mangles BL, CX
INIT_GUESS PROC
    PUSH AX
    XOR  DX, DX
    MOV  CX, PATT / 2 + ( PATT AND 1 )  ; loop half of number of pegs rounded up
IG_START_LOOP:
    MOV  BL, CL             ; adjust to 0 based loop
    DEC  BL
    PUSH DX
    POWER COLS, BL          ; AX = pow(FACTOR, EXP)
    POP  DX
    ADD  DX, AX
    LOOP IG_START_LOOP
    POP  AX
    RET
INIT_GUESS ENDP

; Calculate next guess based on results of previous one
; Input:
;   - BX: last score
;   - DX: last guess
; Output:
;   - AX: number of remaining solutions
;   - DX: next guess
NEXT_GUESS PROC
    PUSH BP                 ; save BP just because we're nice
    PUSH CX
    LEA  DI, S              ; load S BYTE array for SCASB
    MOV  S2LN, 0            ; reset S2 array
    MOV  CX, SSZ            ; iterate through all possible patterns
    CLD                     ; always scan forward for keys in SCAS

ELIM_LOOP:
    XOR  AX, AX             ; search for non-0's
    REPE SCASB              ; Find non-AL byte starting at ES:[DI]
    JZ   END_ELIM_LOOP      ; end loop if reached end of S
    PUSH BX                 ; save last guess result
    MOV  BX, CX             ; move sequence number into BX for CALC_SCORE
    XCHG SI, DI             ; save DI
    CALL CALC_SCORE         ; compare the sequence in BX and DX (previous guess), result in AX
    XCHG SI, DI             ; restore DI
    POP  BX                 ; restore last guess result
    CMP  AX, BX             ; compare this result to last guess
    JE   ELIM_PUSH_S2       ; keep it as a possibility if score result is the same
    MOV  BYTE PTR [DI-1], 0 ; eliminate this as a possible correct answer
    JMP  ELIM_LOOP

ELIM_PUSH_S2:
    MOV  SI, S2LN           ; build array of only possible choices (to minimize memory access below)
    SHL  SI, 1              ; multiply array index by 2 (since it's a WORD)
    MOV  S2[SI], CX         ; push to end of S2 array 
    INC  S2LN               ; array size increased by one
    JMP  ELIM_LOOP

END_ELIM_LOOP:
    MOV  BX, 0FFFFH         ; BX is best, lowest score
    XOR  BP, BP             ; BP is best guess candidate
    CALL COUNT_SOLS         ; AX = number of remaining solutions, DX = lowest solution
    PUSH AX                 ; save to be returned at end of this proc
    CMP  AX, 1              ; check if there's one or no remaining solution(s)
    JLE  DONE_NEXT_GUESS    ; 1 or 0 remaining, return with AX

KNUTH_START:
    MOV  CX, SSZ            ; start Knuth pass 2 loop

KNUTH_LOOP_1:
    CALL CLEAR_H            ; clear hint array (using macro makes jump too large :( )
    PUSH CX                 ; (15) save outer loop counter
    PUSH BP                 ; (15) save BP for inner loop
    PUSH BX                 ; (15) save BX, contains current best, lowest score
    LEA  SI, S2             ; (2+EA) pointer to S2 for LODSW loop start
    MOV  DX, CX             ; (2) pattern to compare with CALC_SCORE inner loop below
    MOV  CX, S2LN           ; (12+EA) start Knuth pass 2 inner loop
    DEC  DX                 ; (3) convert one-based loop counter to zero-based guess number

KNUTH_LOOP_2:               ; ** this loop is run COUNT_SOLS * ( COLS ^ PATT ) times
    LODSW                   ; (16) load guess from S2 (SI) into AX
    MOV  BX, AX             ; (3) move to BX for CALC_SCORE
    CALL CALC_SCORE         ; compare the sequence in BX and DX, return AX
    XCHG CX, BP             ; (4) save CX current loop position (ARRAY_INC mangles it)
    AARY_INC H, AX          ; increment the results of CALC_SCORE
    XCHG CX, BP             ; (4) restore CX
    LOOP KNUTH_LOOP_2       ; (5/17)

END_KNUTH_LOOP_2:
    POP  BX                 ; restore BX - current lowest score
    POP  BP                 ; restore BP - best guess candidate
    MOV  CX, H.LEN          ; tabulate the largest value in H
    INC  CX                 ; size + 1 so SCASW will always read the last value
    LEA  DI, H.VAL          ; point to values of H hint array
    XOR  AX, AX             ; end when found occurance of this
    XOR  DX, DX             ; DX contains current max value (0)

TAB_H_LOOP:
    REPE SCASW              ; read until a non-initialized value (0) has been found
    JZ   END_TAB_H_LOOP     ; have reached end of array
    MOV  SI, WORD PTR[DI-2] ; otherwise, a value has been found
    MAX  DX, SI             ; DX = max(DX, SI)
    JMP  SHORT TAB_H_LOOP

END_TAB_H_LOOP:
    POP  CX                 ; restore outer loop 1 counter
                            ; "prefer" values in S - "lower score by .5"
    MOV  SI, SSZ            ; values in S are stored highest first,
    SUB  SI, CX             ;   so reverse array index
    SHL  DX, 1              ; double the score
    OR   DL, 1              ; add one
    SUB  DL, BYTE PTR S[SI] ; subtract one if in S (giving it a better score)
    UKMIN BX, DX, BP, CX    ; BX = min(BX, DX) (unsigned)
                            ; if BX is changed then BP = CX
    CMP  CL, 00H            ; progress display update every 256 iterations
    JNE  END_LOOP_1B
    CALL PR_COUNT

END_LOOP_1B:
    LOOP KNUTH_LOOP_1
    MOV  DX, BP             ; BP is the next guess (1-based index)
    DEC  DX                 ; convert to 0-based index

DONE_NEXT_GUESS:
    POP AX                  ; previously saved count of remaining solutions
    POP CX  
    POP BP
    RET

NEXT_GUESS ENDP

; this only exists otherwise jumps in NEXT_GUESS would be too far
CLEAR_H PROC
    AARY_CLEAR H
    RET
CLEAR_H ENDP

; shows simple progress count
PR_COUNT PROC
    PUSH AX
    PUSH BX
    PUSH DX
    MOV  DL, 0DH        ; CR only
    MOV  AH, 02H        ; display char function
    INT  21H
    MOV  AH, 09H 
    LEA  DX, ST_CALC    ; display "Calculating" string
    INT  21H
    MOV  AX, SSZ
    SUB  AX, CX
    MOV  BX, 100
    MUL  BX
    MOV  BX, SSZ
    DIV  BX
    CALL OUTDEC
    MOV  AH, 02H        ; display char function
    MOV  DL, '%'
    INT  21H
    MOV  DL, 0DH        ; CR only
    INT  21H
    POP  DX
    POP  BX
    POP  AX
    RET
PR_COUNT ENDP

; Count the number of remaining possible solutions (non-zero values in S)
; Input:    S: start of array of WORDs
;           SSZ: size of array of WORDs
; Output:   AX: count of solutions
;           DX: final solution number (use if this is the correct guess)
COUNT_SOLS PROC
    PUSH DI
    PUSH CX
    PUSH BX
    MOV  CX, SSZ            ; start loop
    LEA  DI, S              ; base address of WORD data array
    XOR  BX, BX             ; BX contains count of still valid solutions

COUNT_SOLS_LOOP:
    XOR  AX, AX             ; AL = 0, search for BYTE other than this
    REPE SCASB              ; Find non-AL byte starting at ES:[DI]
    JZ   END_CS_LOOP        ; check if end of search
    INC  BX                 ; count it as a still possible solution
    MOV  DX, CX             ; save last (lowest index) guess in DX
    JMP  COUNT_SOLS_LOOP

END_CS_LOOP:
    MOV  AX, BX             ; put final count in AX
    POP  BX                 ; restore BX, CX, DI to original condition
    POP  CX
    POP  DI
    RET

COUNT_SOLS ENDP

; Prompt player and get a hints result
; Inputs:
;       Hints from player console
; Outputs:
;       Hints in BX
; Preserves AX, CX, DX
GET_HINTS PROC
    PUSH AX
    PUSH CX
    PUSH DX

    MOV  BX, 0EEAAH         ; sentinel value to check for end of stack
    PUSH BX                 ; input values saved to stack (to facilitate backspace)
    XOR  CX, CX

GET_HINTS_PROMPT:
    MOV  AH, 9              ; display prompt string
    LEA  DX, ST_PMT
    INT  21H
    MOV  CL, PATT           ; loop to get the number of digits in pattern

GET_HINTS_LOOP:
    MOV  AH, 8              ; DOS 21H - get single char with no echo
    INT  21H                ; character is in AL
    CMP  CL, 0              ; check if the number of digits has been met
    JE   CHK_BRK            ; if so, only valid char is a Enter, break or backspace

CHK_BK:
    MOV  AH, CH_HNTS        ; look for black 'x'
    CMP  AL, AH
    JNE  CHK_WH             ; if not check for white
    MOV  BX, 1
    PUSH BX
    JMP  SHORT VALID_CHAR

CHK_WH:
    MOV  AH, CH_HNTS+1      ; look for white 'o'
    CMP  AL, AH
    JNE  CHK_NONE
    MOV  BX, 100H
    PUSH BX
    JMP  SHORT VALID_CHAR   ; if not check for white

CHK_NONE:
    MOV  AH, CH_HNTS+2      ; treat a '-' as no result
    CMP  AL, AH
    JE   SHORT VALID_CHAR   ; if not check for control chars

CHK_BRK:                    
    CMP  AL, 3              ; check if Ctrl-C, return to DOS
    JNE  GH_CHK_CR
    MOV  AX, 4C00H          ; DOS 2.0+ - terminate with return code 0
    INT  21H                ; execute

GH_CHK_CR:
    CMP  AL, 0DH            ; is it a CR (13)?
    JE   GET_SEQ_LOOP_DONE  ; if so, end the input loop

CHK_BS:                     
    CMP  AL, 8              ; check for backspace
    JNE  END_GET_SEQ_LOOP   ; if not, restart loop (last valid option)

    CMP  CL, PATT           ; this is a backspace, so make sure this is not the first
    JGE  END_GET_SEQ_LOOP   ; if no chars yet, nothing to backspace so restart loop

DISP_BS:
    MOV  AH, 2              ; erase previous char
    MOV  DL, 8              ; backspace
    INT  21H
    MOV  DL, ' '            ; erase char (will advance cursor)
    INT  21H
    MOV  DL, 8              ; backspace again
    INT  21H
    INC  CL
    POP  AX
    JMP  SHORT END_GET_SEQ_LOOP

VALID_CHAR:                 ; valid char has been found

DISP_CHR:                   ; display it
    MOV  DL, AL
    MOV  AH, 2
    INT  21H
    DEC  CL

END_GET_SEQ_LOOP:
    JMP  GET_HINTS_LOOP

GET_SEQ_LOOP_DONE:
    MOV  CL, PATT+1         ; loop and calculate seq # (include sentinel value)
    XOR  AX, AX             ; zero out accumulator

CALC_SEQ:
    POP  DX                 ; get value
    CMP  DX, 0EEAAH         ; first value is a 0EEAAH which means done
    JE   END_CAL_HINTS
    ADD  AX, DX
    LOOP CALC_SEQ

END_CAL_HINTS:
    MOV  BX, AX
    POP  DX
    POP  CX
    POP  AX
    RET

GET_HINTS ENDP

; Print AX as a signed decimal integer
; Inputs:
;       Hints from player console
OUTDEC  PROC
        PUSH    AX              ; save registers
        PUSH    BX
        PUSH    CX
        PUSH    DX
        XOR     CX,CX           ; CX counts digits                 
        MOV     BX,10D          ; BX has divisor
@REPEAT1:
        XOR     DX,DX           ; prepare high part of dividend  
        DIV     BX              ; AX = quotient, DX = remainder
        PUSH    DX              ; save remainder on stack
        INC     CX              ; count = count + 1
        OR      AX,AX           ; quotient = 0?
        JNE     @REPEAT1        ; no, keep going
        MOV     AH,2            ; print char fcn
@PRINT_LOOP:
        POP     DX              ;digit in DL
        OR      DL,30H          ;convert to character
        INT     21H             ;print digit
        LOOP    @PRINT_LOOP     ;loop until done
        POP     DX              ;restore registers
        POP     CX
        POP     BX
        POP     AX
        RET
OUTDEC  ENDP

; convenience PROC's for display
; display a new line (CRLF)
NL PROC
    PUSH AX
    PUSH DX
    MOV  AH, 02H    ; display char function
    MOV  DL, 0DH
    INT  21H
    MOV  DL, 0AH
    INT  21H
    POP  DX
    POP  AX
    RET
NL ENDP

; display a tab
TAB PROC
    PUSH DX
    PUSH AX
    MOV  DL, 9      ; move tab char to display into DL
    MOV  AH, 02H    ; display char function
    INT  21H
    POP  AX
    POP  DX
    RET
TAB ENDP

END START

Implementation

My design requirement for this was that it should solve in a reasonable amount of time on the smallest IBM PC configuration -- an IBM PC 5150, Intel 8088 CPU (4.77MHz), PC DOS 2.0 and 48KB of RAM. On this configuration, depending on the number of initial eliminations, the first guess will take between 30 seconds to 2 1/2 minutes (realize of course, the 8088 is a circa-1979 chip capable of approx 0.33 MIPS). On a 386-class machine, it's a few seconds and on a 486+, it's nearly instant.

On a 6/4 board the first guess requires approx. 3.4 million (2*(colors ^ pegs) ^ 2) integer division operations, which on the 8088 are quite slow (even by then standards!). On a 5/5 board, it's almost 10 million. The 6/4 version runs entirely in 4KB of RAM and 5/5 requires 8KB.

Obviously in machine code, there are no associative or variable-length arrays, aggregate counting functions, or lambda function-based minimax, so all of that had to be hand rolled (hence the 800 byte program size).

UI Notes

Since this wasn't written for this challenge the UI does not follow the above examples. I used A-F for pegs (instead of 1-6) and "x" and "o" representing black and white pegs. To input two black pegs and one white peg you'd put in "xxo" (more similar to the actual board game).

You can change these characters in the EQU section at the top, and I've commented out examples of using the ones in the problem spec. Also, you can change the number of possible colors and pegs at assembly time as well. As the 8088 is a 16 bit CPU, colors ^ pegs must be less than 65,536 (however, that would require 2 * 2^32 division operations on an 8088 so I wouldn't recommend it).

Output

Here are some example runs on the PC (all of these solved in four guesses):

enter image description here

Try it!

Here are links to download the assembled executable.

  • MMS64.EXE - solver a 6/4 (6 colors, 4 pegs), 1,296 possible solutions
  • MMS55.EXE - solver a 5/5 (5 colors, 5 pegs), 3,125 possible solutions -- (not proven to be solvable in five or fewer moves)
\$\endgroup\$
1
\$\begingroup\$

Congratulations @ugoren on doing this so succinctly. I've implemented this algorithm before and not nearly as briefly or elegantly.

I believe however that there is one small part of the Knuth algorithm not implemented (my first time I missed it too), which is the "From the set of guesses with the maximum score, select one as the next guess, choosing a member of S whenever possible". So prefer a solution that is in S over one that isn't, even if it's not the one with the least numeric value.

An example case:

1 1 2 2
0 1
1 3 4 4
2 0
3 1 3 5
0 1
1 6 3 2*

At which point, the minimax set would be:

[('1', '6', '3', '2'), ('3', '4', '2', '1'), ('3', '4', '2', '3'), ('3', '4', '2', '6'), ('3', '4', '6', '3'), ('3', '4', '6', '5'), ('4', '1', '3', '2'), ('4', '2', '3', '2'), ('4', '3', '3', '2'), ('5', '6', '3', '2'), ('6', '1', '3', '2'), ('6', '5', '3', '2')]

And your A ("members of S") contains the following:

[('3', '4', '2', '6'), ('3', '4', '6', '2'), ('4', '1', '6', '6'), ('4', '4', '2', '5'), ('4', '6', '3', '2'), ('6', '4', '3', '2')]

The only value in the minimax set that is in A is 3 4 2 6, which is the one Knuth's algorithm would choose over 1 6 3 2.

With this, I believe your submission will be provable to solve in 5 or less. Obviously the code golf rules state 6 or less and the challenge was not specifically to be Knuth-complete. However without it (the other Python implementation for example is not), Knuth's proof alone cannot be used to guarantee rule compliance.

(just realized this was from 2012, sorry for the resurrect!)

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! FWIW, "resurrecting" or "necro-posting" is actually encouraged here. However, it looks like this would fit better as a comment to this post than as an answer. If you have 50 or more reputation points (you currently don't), you can comment on other peoples' posts. \$\endgroup\$ – Erik the Outgolfer Dec 20 '18 at 19:14
  • \$\begingroup\$ Also, the 'code' in 'codegolf' stands for 'show your code'; your answer would be greatly enhanced by an implementation in your favorite programming language, no matter whether that's COBOL, Scala or Minecraft! \$\endgroup\$ – Rogem Dec 22 '18 at 20:40
  • \$\begingroup\$ @Rogem very good point. My implementation was done in x86 assembly, designed to be fast, not golfed. I will post it though! \$\endgroup\$ – gwaugh Feb 14 at 16:43
  • \$\begingroup\$ @gwaugh Then you should check out the x86 tips thread \$\endgroup\$ – Rogem Feb 15 at 9:58

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.