Sunday, March 1, 2009

hrrmm...these puzzles are apuzzlin' me

So I was perusing the xkcd blag and came across this little puzzle (which was taken from LispClub.com).
Sue and Bob take turns rolling a 6-sided die. Once either person rolls a 6, the game is over. Sue rolls first. If she doesn’t roll a 6, Bob rolls the die; if he doesn’t roll a 6, Sue rolls again. They continue taking turns until one of them rolls a 6.

Bob rolls a 6 before Sue.

What is the probability Bob rolled the 6 on his second turn?
In the blag comment section, there was a lot of confusion over the wording. Personally, I read it as, "what is the probability of Bob winning the second roll?" In other words, what are the odds of Bob rolling a 6. If it is read like that, then most will probably guess 1/6. Makes sense; there are 6 sides to a dice and you have 1/6 chances of rolling the 6.

However, when you read it carefully and think about it, it's really asking for the probability of Bob winning on the second turn. Now, it's not as simple (to me anyways) and I get all sorts of confused. A commenter named Ian posted a lengthy description of the solution. The mathematics wasn't entirely clear to me, but makes kind of sense (very little to be honest). But math isn't my strong suit. Brute forcing is :D I decided to take Rotheral's approach in the comment section and write my own simulation. Granted, I created this the quickest way possible, and it's using java.util.Random, which from what I can remember isn't always the bestest of best random functions. But for all intents and purposes, it'll work just fine.

Here's the code (forgive the crudeness of how it's edited. I haven't figured out how to make blogger display code):

import java.util.Random;
public class RollOfDie {
  public static void main(String[] args) {
  Random rand = new Random();
    int bobRollCount = 0;
    int sueRollCount = 0;
    int sueWonRound2 = 0;
    int bobWonRound2 = 0;
    //loop for 1E8 games, that's 100,000,000
    for(int i = 0; i &lt 1E8; i++){
      //keep track of the turn
      int turnCount = 0;
      int roll = 0;
      //keep rolling until we hit 6
      while(roll != 6){
        roll = rand.nextInt(6) + 1;
        turnCount++;  
      }
      //even numbered turns are Sue's
      if(turnCount%2 == 0){
        sueRollCount++;
      //odd are Bob's
      }else{
        bobRollCount++;
      }

      //turnCount 2 and 3 are the second turn
      if(turnCount == 2){
        sueWonRound2++;
      }else if (turnCount == 3){
        bobWonRound2++;
    }
  }

  System.out.println("Bob won " + bobRollCount + " games");
  System.out.println("Bob won " + bobWonRound2 + " games on the 2nd round");
  System.out.println("Probability that Bob rolled a 6 on his second turn: " +
                      bobWonRound2 + "/" + bobRollCount + " = "
                      +((double)bobWonRound2/(double)bobRollCount));
  }
}

So as you can see, it's relatively straight forward. Just roll the dice until 6 is reached and then check if the turn was on the second turn (in this case, turnCount 2 or 3). I could have made it to run a few times and then take the average each running, but I felt that running 1E08 games was probably enough. That's 100,000,000 games. 

While I am convinced by the outcome of my result - it matches the ~21% others have reported, I'm not confident in the mathematics. There's a lot going over my head.

Regardless, I had fun making this little demo program. Maybe I should have tried making it in Haskell :D

Weezle-Wuzzle...again

So it's been another month since I've posted. I've done very little programming from home. I did work on my AI project some, but then, as was the case for my AI class, I got stuck trying to make my little bots turn and find their target properly and wouldn't you know it, I just stopped. I just cannot see where the problem is. UGH! So frustrating!

For a while, I sat down and tried to design a new system for this AI thing, but I'm unsure how to go about the design. What I need to do is just sit down and design it. Maybe even take out some of my books from my classes and read up (again) on how to properly design something. But then again, I need to make myself some clear cut goals.

This reminds me of this blog I came across some time ago. Looking at it, I'm fairly certain I have done 3 of the 7 items listed here.

So, how will I break this bad habit? Honestly, I'm not sure. I don't have a clear goal as to what I want or what I want to achieve. I also don't have a clear plan of any sorts to achieve any kind of goal. And then of course there's the motivation. I code all day at work, but don't find the energy to do so at home. It's one big cascading problem.

I've read that joining an open source project is a good way to get programming. Maybe I'll search around for something like that. But seriously, I need to sit my ass down and plan out my AI thing.

FOCUS FOCUS FOCUS