wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Mastermind Puzzles (6 Colours)
        
(Message started by: daemonturk on Feb 21st, 2009, 4:12am)
Title: Mastermind Puzzles (6 Colours)
Post by daemonturk on Feb 21st, 2009, 4:12am
You may need to familiarize yourself with the game of Mastermind (Logic/Deduction type boardgame).

http://en.wikipedia.org/wiki/Mastermind_(board_game)

I'm not sure if this belongs in pure math, but I need help.

MARKERS:
W = Correct colour, Wrong Position
B = Correct colour, Correct Position
(Becareful with the rules about corresponding markers with duplicate pegs)
Colours: 6

1. If the first guess is BBCC, and the feedback is WWW, how many remaining possible combinations are there?

2. If the first guess is BBCG, and the feedback is WWBB, how many remaining possible combinations are there?

3. If the first guess is BCGR, and the feedback is WWWB, how many remaining possible combinations are there?

4. First Guess: BCGR, Feedback: WWBB, Remaining Possible Combinations: ?

Please help me find the answers to all these questions, and if possible, explain how you solved them.

To help you guys further, I will put an example question and answer.

Example Question and Solution

First Guess: BBBC, Feedback: B

Solution:
If we assume Black is the one in the correct position, the other three colours MUST be wrong entirely because there was no 'W's in the feedback. Hence, the other 3 slots can be any of 4 colours (because they can't be Black or Cyan).
So we end up with (3 x 4^3) because there were 3 Blacks.

If we assume Cyan is correct in position, the first 3 slots are entirely wrong, and hence could be any of the 5 colours (for black is wrong). Hence, 5^3.

The total possible combinations remaining out of the total 1296, is (3 x 4^3) + 5^3 = 317.

Thanks a lot guys!
Title: Re: Mastermind Puzzles (6 Colours)
Post by tohuvabohu on Feb 21st, 2009, 1:03pm
1. If the first guess is BBCC, and the feedback is WWW, how many remaining possible combinations are there?

Possibilities: swap bb with cc, then replace any peg with one of the 4 other colors.
?CBB 4
C?BB 4
CC?B 4
CCB? 4

2. If the first guess is BBCG, and the feedback is WWBB, how many remaining possible combinations are there?

Possibilities: every possible swap of two pegs except swapping the two B’s
BBGC
CBBG
GBCB
BCBG
BGCB

3. If the first guess is BCGR, and the feedback is WWWB, how many remaining possible combinations are there?

Possibilities: two rotations possible for each of 4 choices of the one stationary peg
BGRC
BRCG
GCRB
RCBG
CRGB
RBGC
CGBR
GBCR

4. First Guess: BCGR, Feedback: WWBB, Remaining Possible Combinations: ?

Possibilities: every possible swap of two pegs
CBGR
GCBR
RCGB
BGCR
BRGC
BCRG
Title: Re: Mastermind Puzzles (6 Colours)
Post by daemonturk on Feb 21st, 2009, 6:43pm
Very nice.

How about:

First Guess: BBCG, Feedback: WWW

(Challenging)
Title: Re: Mastermind Puzzles (6 Colours)
Post by towr on Feb 22nd, 2009, 8:25am
It's fairly easy to write a small program to give you the result. And since 64 isn't that much, you don't even need to take a smart approach to it. Just running through all possible sequences and checking which match works.


Code:
<script>
function match(p, g, ccwp, ccrp)
{
 var i,j,s,t;
 s = (p[0]==g[0]) + (p[1]==g[1]) + (p[2]==g[2]) + (p[3]==g[3]);
 p.sort(); g.sort();

 i=j=t=0;  
 while(i < 4 && j < 4)
 {
   if(p[i]==g[j])
     i++, j++, t++;
   else if(p[i]<g[j])
     i++;
   else
     j++;
 }

 return (t==ccwp+ccrp) && (s==ccrp);
}


function run(guess, ccwp, ccrp)
{
 var col = ["B", "C", "G", "R", "Y", "M"]; /* ? */
 var cnt=0;
 for(a=0; a<6; a++)
   for(b=0; b<6; b++)
     for(c=0; c<6; c++)
       for(d=0; d<6; d++)
       {
          if(match([a,b,c,d], guess, ccwp, ccrp))
          {
            document.write(col[a] + col[b] + col[c] + col[d] + "<br>");
            cnt++;
          }
       }
 document.write(cnt+"<br>");
}

function start(guess_string, result_string)
{
 var cols={};
 cols["B"] = 0;  cols["C"] = 1;  cols["G"] = 2;  cols["R"] = 3;  cols["Y"] = 4;  cols["M"] = 5;

 var guess;
 guess=[cols[guess_string[0]],cols[guess_string[1]],cols[guess_string[2]],cols[guess_string[3]]];
 
 var ccwp=0, ccrp=0;
 for(i=0; i < result_string.length; i++)
 {
   if (result_string[i] == "B") ccrp++;
   if (result_string[i] == "W") ccwp++;
 }  

 run(guess, ccwp, ccrp);
}

start("BBCC", "WWW");
start("BBCG", "WWBB");
start("BCGR", "WWWB");
start("BCGR", "WWBB");
start("BBBC", "B");
start("BBCG", "WWW");

document.close();
</script>


It gives 44 for the last one.
Title: Re: Mastermind Puzzles (6 Colours)
Post by daemonturk on Feb 22nd, 2009, 8:27am
44 is correct, but I'm not familiar with this language, is it C#? It would be good if I had a logical solution too  :-/
Title: Re: Mastermind Puzzles (6 Colours)
Post by towr on Feb 22nd, 2009, 8:43am

on 02/22/09 at 08:27:32, daemonturk wrote:
44 is correct, but I'm not familiar with this language, is it C#? It would be good if I had a logical solution too  :-/
It's javascript. (So it can just run in your browser; which I find convenient since I'm using it anyway).

I'll have to think a bit more about a logical solution.
Title: Re: Mastermind Puzzles (6 Colours)
Post by tohuvabohu on Feb 22nd, 2009, 12:09pm
If there are two B’s, and a fourth color then it’s either
C?BB 3
?CBB 3
G?BB 3
?GBB 3

If there are two B’s and G or C is repeated then it’s
CCBB
GGBB

If there is one B and a fourth color, then it’s
CGB? 3
CG?B 3
C?GB 3
?CGB 3
GCB? 3
GC?B 3
G?BC 3
?GBC 3

If there is one B, and C or G is repeated, then it’s
CGBC
GCBC
GGBC
CGGB
CCGB
GCGB
Title: Re: Mastermind Puzzles (6 Colours)
Post by daemonturk on Feb 22nd, 2009, 11:14pm
Thanks, tohuvabohu ;D

@towr: Your code is impressive, but I'm not familiar with javascript to appreciate it =(
Title: Re: Mastermind Puzzles (6 Colours)
Post by towr on Feb 23rd, 2009, 12:25am

on 02/22/09 at 23:14:12, daemonturk wrote:
@towr: Your code is impressive, but I'm not familiar with javascript to appreciate it =(
It's really not that impressive. It just loops through all 64 possible colour sequences and picks the one that fit the guess+result. If you were familiar with javascript, you probably wouldn't appreciate it any better ;)
Most pieces would work the same in java, C, C++, and similar languages though.
Title: Re: Mastermind Puzzles (6 Colours)
Post by Aryabhatta on Mar 14th, 2009, 11:34am
Can we move this out of putnam section?
Title: Re: Mastermind Puzzles (6 Colours)
Post by daemonturk on Mar 14th, 2009, 9:03pm
It belongs here, its a conditional probability game.
Title: Re: Mastermind Puzzles (6 Colours)
Post by Eigenray on Mar 15th, 2009, 6:09am
Well, it was in Putnam, until somebody moved it.  Maybe I should have said something, but I thought it would be obvious.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board