Re: Mastermind algorithm

Daniel Tuijnman wrote:
>>As I anticipate being unable to decipher any of the winning solutions,
>>I'd be much obliged if some of you better-than-median folks would post
>>an ungolfed Alternate solution illustrating your approach.
> 
> 
> Ungolfing is a bit hard, I guess. But some time ago, someone on this
> list proposed that every time someone explained his/her solution, so
> here it goes.
> 
> #!/usr/bin/perl -pl
> @;=grep{$'./[6-9]/eq(($x=$`)^$_)=~y/ //.$".grep$x=~s/$_//,/./g}/ /%1x4..5x4,@;}{$_=pop@
> 
> The basic idea is to make a list of all candidate solutions, and for each
> input line to filter out only those candidate solutions that satisfy
> that input line.
> 
> The list of candidate solutions is stored in array @;. For each input
> line, a full list of new candidates is generated, and together with the
> list in @;, fed into the big grep{...} expression. Thus, the last
> element(s) in @; have satisfied all input lines, and after all input is
> processed,
>     $_=pop@
> gives the only viable solution.
> 
> The expression / /%1x4..5x4 generates all 4-digit (0-5) strings, plus
> some strings containing digits 6-9, so those must be weeded out yet.
> As a "side-effect", the expression splits the input line in two:
> $` containing the 4-digit string, and $' containing the number of black
> pegs, a space, plus the total number of pegs.
> 
> Within the grep, these peg numbers are calculated for the candidate
> solution:
> a) (($x=$`)^$_) xors character-wise the candidate solution with the
>    input line; if a digit is on the right spot, this xor yields a
>    NUL character, which are counted by the y///.
> b) grep$x=~s/$_//,/./g counts the total number of pegs. For each digit
>    in the candidate, the s/// looks if it occurs in the input line
>    string ($x, which is a copy of $`) and removes it, so digits are not
>    counted doubly.
> These two numbers are string-concatenated with a space ($") in between,
> and the resulting string string-compared with the results from the input
> line ($').
> 
> Finally, to weed out those candidates containing digits 6-9, $' is
> concatenated with /[6-9]/: the latter expression yields the empty string
> if no such digits occur, else string "1".
> 	
> Hope this helps!
> 	
Thanks very much for the explanation.  I can't believe I missed the exclusive
or resulting in nulls idea even after I was experimenting with the bitwise ops.

One clarification that might help anyone else reading is how you generated
all the combinations without using glob"{0,1,2,3,4,5}"x4 like Roy and I did:
/ /%1x4..5x4
# result of / / always matches so it returns 1
1%1x4..5x4
# 1%1 is 0
0x4..5x4
# The repetition op forces the result into string context so it's really:
"0000".."5555"
-- 
     _.,-*~`^'~*-,._ Danny Rathjens _.,-*~`^'~*-,._
"Believe nothing, O monks, merely because you have been told it ...  or because
 it is traditional, or because you yourselves have imagined it." -- Gautama Buddha