Tag Archives: Puzzle

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

It was my Friday lunch break, and since I wanted get a problem with a recent online order corrected before the weekend, I called the merchant’s 800 number.  After a long hold time, I finally got a representative on the phone who, horror of horrors, was a mathematics PhD working a call center job.  As I cranked up the phone volume, she told me she was swamped with calls and the correction I needed was going to take awhile.  She’d prefer I just go away.

“Can you call back later?” she asked.
“Sure. When?”
“In a while.”
“How long?”
“A while.”
“Can you give me an idea?” I asked.
“Tell ya’ what.  Calculate pi using the Leibniz formula to nine correct digits.  Use the basic algorithm with no series accelerations or transforms.  Do it 10 times.  When you’re done, call me back.”
“OK,” I mumbled and hung up.

What to do?  The coding part was easy, and there are even Leibniz implementations all over the net.  But nine correct digits would take good big number support and a billion iterations of basic Leibniz.  Ten successive runs of that would go well past the end of my lunch break.

Fortunately, I have a quad core machine, had seen first-hand the benefits of threading things such as this, and even wrote about it just yesterday.  So I wrapped some threads around a basic implementation, ran it, and called back.  Problem solved.

You never know when you, too, might have a math PhD on the other end of a customer service call.  So to help you prepare for that, I invite you to this exercise:

Write code to do ten threaded runs of the basic Leibniz formula to calculate pi to nine correct digits (one billion iterations) in significantly less time than ten successive runs.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop this single-threaded Ruby implementation.

Last Week’s Fragment – Solution

This week, we complete a genetic algorithm solution to our recent pet store problem:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15, cats cost $1, and mice are 25 cents each.  Finish implementing our genetic algorithm solution by doing the natural selection and termination.

Natural selection can be done simply by sorting the current population by fitness and taking the top N individuals, like so:

     /**
      * Compare fitness levels for sorting.
      */
     public function compareFitness($purchase1, $purchase2) {
         if ($purchase1->getFitness() == $purchase2->getFitness())
             return 0;
         return ($purchase1->getFitness() > $purchase2->getFitness()) ? -1 : 1;
     }
 
     /**
      * Select a subset of the given population for breeding a new generation.
      * Return this subset ordered by the most fit first.
      */
     public static function select($population, $size) {
         usort($population, array('PetPurchase', 'compareFitness'));
         return array_slice($population, 0, $size);
     }

And we terminate by breeding until we either find a perfect fit or hit a generation cap:

     /**
      * Find the most fit solution by breeding the given number of generations,
      * each with the specified population size.
      * Return an array with the most fit and the number of generations created.
      */
     public static function findMostFit($generations, $populationSize) {
         $population = self::createPopulation($populationSize);
         $mostFit = new PetPurchase();
         for ($i=0; $i<$generations; $i++) {
             $population = self::select($population, $populationSize);
             if ($population[0]->getFitness() > $mostFit->getFitness())
                 $mostFit = $population[0];
             if ($mostFit->getFitness() == 100)
                 break;
             $population = self::breed($population);
         }
         return array($mostFit, $i);
      }

My completed PetPurchase class is here.  I also coded a Ruby version here.  Here’s an example run:

      $result = PetPurchase::findMostFit(20000, 30);
      $result[0]->printMe();
      echo $result[1].' generations';

With a result:

Dogs Cats Mice Count Cost Fitness
3 41 56 100 100.000 100.000

1510 generations

As in this case, genetic algorithms often aren’t the fastest or most efficient way to get a result.  They’re really a (slightly) directed random walk, and they’re not good for well-understood solutions that don’t justify the overhead of a genetic approach.  But for cases where fitness is well-understood but the solution isn’t, genetic algorithms can be a valuable tool.

Hopefully this simple example clearly demonstrates the evolutionary programming approach behind cool things like BoxCar 2D.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

This week, we’ll wrap up our genetic algorithm solution to our recent pet store problem:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15, cats cost $1, and mice are 25 cents each.  Finish implementing our genetic algorithm solution by doing the natural selection and termination.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop my current PetPurchase class; I put in placeholders for the next steps.

Last Week’s Fragment – Solution

Last week we continued our genetic algorithm solution to our recent pet store problem:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15, cats cost $1, and mice are 25 cents each.  Continue implementing our genetic algorithm solution.  Write code to create an initial generation (random population) of PetPurchases and create (“breed”) subsequent generations by crossover and, if desired, mutation.

We can create the initial population by adding these methods:

     /**
      * Generate a random set of counts, within reasonable constraints.
      */
     public function randomize() {
         $this->setDogCount(rand(1,6));
         $this->setCatCount(rand(1,85));
         $this->setMouseCount(rand(1,336));        
     }
     /**
      * Create a population of the given size with random individuals.
      */
     public static function createPopulation($size) {
         $population = array();
         for ($i=0; $i<$size; $i++) {
             $purchase = new PetPurchase();
             $purchase->randomize();
             array_push($population, $purchase);
         }
         return $population;
      }

And combination and mutation is done with these new methods:

     /**
      * Set my attributes from those of my parents.
      * This is also known as breeding, crossover, or recombination.
      */
     public function combine($dad, $mom) {
         $this->setDogCount(rand(0,1) == 0 ?
                             $dad->getDogCount() : $mom->getDogCount());
         $this->setCatCount(rand(0,1) == 0 ?
                             $dad->getCatCount() : $mom->getCatCount());
         $this->setMouseCount(rand(0,1) == 0 ?
                               $dad->getMouseCount() : $mom->getMouseCount());
      }
 
      /**
       * Mutate my attributes so that I'm not an exact clone of my parents.
       */
      public function mutate() {
          $this->setDogCount(rand(0,2) == 0 ?
                              rand(1,6) : $this->getDogCount());
          $this->setCatCount(rand(0,2) == 0 ?
                              rand(1,85) : $this->getCatCount());
          $this->setMouseCount(rand(0,2) == 0 ?
                              rand(1,336) : $this->getMouseCount());
      }

There are the many possible ways to go about this; breeding techniques can be quite different, but still result in a population that contains a correct (best fit) solution.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

This week, we continue our genetic algorithm solution to our recent pet store problem:

Write code to create an initial generation (random population) of PetPurchases and create (“breed”) subsequent generations by crossover and, if desired, mutation. We’ll finish by doing the natural selection and termination next week.

To play along, post your code as a comment or send it via email.  If you’d like, you can build atop my initial PetPurchase class; I put in placeholders for the next steps.

Last Week’s Fragment – Solution

Genetic algorithms have received new attention lately with interesting things like BoxCar 2D.  So with last week’s puzzle, we began looking at a genetic algorithm approach to solving a recent Friday Fragment:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Start implementing a genetic algorithm solution – determine how to encode candidate solutions (individuals) and code the fitness function.

We could encode candidate solutions using a simple associative array with the number of dogs, cats, and mice, but I decided to create a class (PetPurchase) and use instance variables, like so:

     class PetPurchase {
         private $dogCount, $catCount, $mouseCount;

Here’s a very simple fitness function I wrote – a method on PetPurchase.  There are many possible answers.

     public function getFitness() {

         // There must be at least one of each animal:
         if ($this->getDogCount() == 0 ||
             $this->getCatCount() == 0 ||
             $this->getMouseCount() == 0)
              return 0;

         $countError = abs(100 - $this->getTotalCount());
         $amountError = abs(100 - $this->getTotalCost());

         if ($countError > 50 || $amountError > 50)
             return 0;
         else
             return 100 - ($countError + $amountError);
     }

For the rest of this initial code, see http://derekwilliams.us/fragments/PetPurchase1.php.txt.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Genetic algorithms have received new attention lately with interesting things like BoxCar 2D.  And while some of the research around them may seem mysterious, the basic approach is quite simple.  Let’s revisit a recent Friday Fragment and apply evolutionary techniques to solve it:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Start implementing a genetic algorithm solution – determine how to encode candidate solutions (individuals) and code the fitness function.

To play along, post your code as a comment or send it via email.  You can refer back to Joe’s conventional programming solution if you’d like; the point here is to re-structure it into a genetic algorithm in order to learn this approach first-hand.

Last Week’s Fragment – Solution

Last week’s puzzle continued our team ranking system based on win/loss records and strength of schedule (SOS):

Write code to calculate the RPI (Ratings Percentage Index) for a set of teams using the basic Wikipedia calculation.  Present the teams ordered by RPI.

I updated my PHP Team class (now TeamRPI) to calculate RPI and sort the results. Here are the changes:

     public function computeRPI() {
         ... // (code up to here is the same as last week)
         $this->setRPI((0.25 * $this->getWinPercent())
                         + (0.5 * $or) + (0.25 * $oor));
     }
     public static function sortByRPI() {
         usort(self::$allTeams, array('TeamRPI', 'compareRPI'));
     }
     public function compareRPI($team1, $team2) {
        if ($team1->getRPI() == $team2->getRPI())
           return 0;
        return ($team1->getRPI() > $team2->getRPI()) ? -1 : 1;
     }

While at it, I improved performance by using an associative array:

     private static function addTeam($team) {
        self::$allTeams[$team->getName()] = $team;
     }
     public static function getTeam($name) {
         return self::$allTeams[$name];
     }

You can run this at  http://derekwilliams.us/fragments/rpi.html, which also includes links to the source code and 2010 NCAA Football data.

Here are the top 15 RPI rankings it calculates from this data, which is similar to other pure RPI rankings.

Rank Name Record Win % RPI
1 Auburn 14-0-0 1.000 0.694
2 LSU 11-2-0 0.846 0.660
3 Oklahoma 12-2-0 0.857 0.652
4 Arkansas 10-3-0 0.769 0.646
5 Alabama 10-3-0 0.769 0.638
6 Texas A&M 9-4-0 0.692 0.633
7 Stanford 12-1-0 0.923 0.632
8 TCU 13-0-0 1.000 0.631
9 Missouri 10-3-0 0.769 0.629
10 Ohio St. 12-1-0 0.923 0.628
11 Oregon 12-1-0 0.923 0.627
12 Michigan St. 11-2-0 0.846 0.622
13 Boise St. 12-1-0 0.923 0.621
14 Oklahoma St. 11-2-0 0.846 0.620
15 Florida St. 10-4-0 0.714 0.616

This shows some interesting things when compared to polls and other ranking systems, such as one reason why TCU is moving to the Big East.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Let’s continue our team ranking system based on win/loss records and strength of schedule (SOS):

Write code to calculate the RPI (Ratings Percentage Index) for a set of teams using the basic Wikipedia calculation.  Present the teams ordered by RPI.

To play along, post your code or URL as a comment, or send it via email.  If you’d like, you can build atop last week’s code and data.

Last Week’s Fragment – Solution

Last week’s puzzle introduced us to strength of schedule calculations for NCAA teams, or any team for that matter:

Write code to find the strength of schedule (SOS) for your favorite team using the basic Wikipedia calculation.  Start with a simple list of wins and losses, parse the results, and calculate the ratio.  For extra insight, compare it to other teams played.

I wrote a basic PHP Team class to parse the results, house the records and opponents, and calculate strength of schedule.  Here’s the gist of it:

   public function computeStrengthOfSchedule() {
      foreach ($this->getOpponents() as $opponent) {
          if (!is_null($team = self::getTeam($opponent))) {
              $opponentWins += $team->getWins();
              $opponentGames += $team->getWins() + $team->getLosses();
              foreach ($team->getOpponents() as $opponentOpponent) {
                  if (!is_null($team2 = self::getTeam($opponentOpponent))) {
                       $opponentOpponentWins += $team2->getWins();
                       $opponentOpponentGames += $team2->getWins() + $team2->getLosses();
                  }
              }
          }
      }
      if ($opponentGames > 0)
          $or = $opponentWins / $opponentGames;
      if ($opponentOpponentGames > 0)
          $oor = $opponentOpponentWins / $opponentOpponentGames;
      $this->setStrengthOfSchedule(((2*$or) + $oor)/3);
 }

You can run this at  http://derekwilliams.us/fragments/sos.html, which also includes links to the source code and 2010 NCAA Football data.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

The NFL has honed parity to the point where “any given Sunday” should be the new slogan.  But that’s far from the case for the NCAA.  In this era of “buy games” and weak conferences, strength of schedule (SOS) is as important as win-loss record for NCAA play.  Want to know where your team really stands?  Then, yes, look at their win/loss record, but also look at their SOS ranking.

We calculated tournament graph power rankings in a recent Friday Fragment.  For the next couple of weeks, we’ll look at ranking by record and schedule strength.  So let’s get started:

Write code to find the strength of schedule (SOS) for your favorite team using the basic Wikipedia calculation.  Start with a simple list of wins and losses, parse the results, and calculate the ratio.  For extra insight, compare it to other teams played.

To play along, post your code or URL as a comment, or send it via email.

Last Week’s Fragment – Solution

Last week, we asked for a code fragment to avoid the time-consuming substitution work required to solve a recent Car Talk Puzzler:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Determine the equations and write code to solve them.

Joel Odom pointed out that this is a form of the classic Knapsack problem.  Indeed it is, as we’re optimizing money spent and number of animals purchased.  Fortunately, the $100 and 100 item bounds keep it in (fast) polynomial time.  Joe Richardson gave us a solution in C#:

   int d,c,m, max=100, amount=100, i=0;
   for (d=1;d<=max && 15*d<=amount;d++)  {
       for (c=1;(c<=max-d) && (15*d+c<=amount);c++)   {
           for (m=1;(m<=max-c-d) && (15*d + c + .25*m<=amount);m++) {
               i++;
               if ((d+c+m == max) && (15*d + c + .25*m == amount))
                   Console.WriteLine("Dogs: " + d + " Cats: " + c + " Mice: " +m);
           }
       }
   }
   Console.WriteLine("Iterations: " + i );

This gives us 3 dogs, 41 cats, and 56 mice, lickety-split.  On the follow-up Car Talk episode, Ray and Tom talked about how they spent hours on this puzzle: Tom stayed up until 3 am without an answer, and Ray spent a lot of time just plugging in numbers. That’s the beauty of this code fragment: let the computer do the time-consuming work!

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Equations are a perfect fit for programming.  A small fragment of code can help you quickly compute a result, particularly when substitution or Monte Carlo methods are required: you can save time by letting the computer do the “plugging in.”

A recent Car Talk Puzzler required simultaneous equations with some trial and error.  Let’s write code to let the computer do the time-consuming substitution work for us:

You’re given $100 and told to spend it all purchasing exactly 100 animals at the pet store, buying at least one of each animal.  Dogs cost $15.  Cats cost $1, and mice are 25 cents each.  Determine the equations and write code to solve them.

To play along, post your code as a comment or send it via email.

Last Week’s Fragment – Solution

In celebration of the NFL postseason, last week’s challenge was to complete our basic our team ranking system:

Write code to use a tournament matrix (built from win/loss records) to compute power rankings for a set of teams.

To do this, we load up the matrix from win/loss records (I used scores from ProFootball-Fans.com), square it and add it to itself (M + M2), and then add across the rows.  I offered my initial tournament matrix class to do the math and get started.

To complete this, we add methods to our TournamentMatrix class to parse the scores (parseScores) and compute the powers (computePowers).  My updated class is here as TournamentMatrix2.php.  Calling it from a web page is straightforward:

<?php
    require 'TournamentMatrix2.php';
    if (isset($_POST['submit'])) {
        doTourney($_POST['scores']);
    }

    function doTourney($scores) {
        $matrix = new TournamentMatrix2();
        $matrix->parseScores($scores);
        $matrix->computePowers();
        show_powers($matrix->getPowers());
    }
?>

The calling code is in rankings.php.  You can run my code from http://derekwilliams.us/fragments/tourney.html.  Paste in your own scores, or use my NFL regular season scores at http://derekwilliams.us/fragments/nflscores.txt.  For this NFL data, you’ll see that the top 10 power rankings are:

Rank Team Power
1 Patriots 91
2 Falcons 85
3 Jets 84
4 Ravens 79
5 Chiefs 77
6 Bears 76
7 Saints 74
8 Giants 71
9 Steelers 69
10 Eagles 69

Pretty much what you’d expect (the Packers are #13).  If only the playoffs had cooperated.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

In celebration of the NFL playoffs, we continue our team ranking system.  It’s time to implement our tournament matrix:

Write code to use a tournament matrix (built from win/loss records) to compute power rankings for a set of teams.

As described below, you load up the matrix, square it and add it to itself (M + M2), and then add across the rows.  To play along, provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop the simple tournament matrix class I started.

Last Week’s Fragment – Solution

Last week’s challenge was to propose a fragment of design, not code for ranking teams based on win/loss records.  I suggested using a dominance-directed graph (a.k.a., tournament graph):

Propose an algorithm to use a tournament graph to compute power rankings.  Start with simple list of wins and losses (Team A beat Team B, Team B beat Team C, etc.) and propose a way to rank the teams.

You start by creating a matrix (two-dimensional array) from the win-loss results and assign a zero or one to each cell: one if the row-wise team beat the team in that column; otherwise, zero.  You then compute the powers of each vertex (in the matrix-represented graph) using the formula M + M2 (add the matrix to the result of squaring itself).  From the resulting matrix, sum each row to get the power of each team.  There’s a nice, brief description at the bottom of this page: http://aix1.uottawa.ca/~jkhoury/graph.htm.

The benefit of this approach is it considers “transitive wins:” if Team A beats Team B and Team B beats Team C, Team A gets some credit over Team C, even if they never played.  The downside is that football isn’t always transitive.

So finish the code and plug in some records.  Let’s see how our power matrix compares to reality.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

It’s NFL wildcard weekend, and analysts are all over the place in their predictions.  It’s clear who the top NFL teams are (Falcons, Pats), but less clear for teams with fewer wins, and when comparing teams that haven’t played each other in awhile.  There’s no RPI for football, but a dominance-directed graph (a.k.a., tournament graph) can provide some basic rankings.  Over the next two weeks, we’ll see if we can build such a ranking system.  Let’s start with the approach:

Propose an algorithm to use a tournament graph to compute power rankings.  Start with simple list of wins and losses (Team A beat Team B, Team B beat Team C, etc.) and propose a way to rank the teams.

To play along, write a description of the solution or pseudo code and post it as a comment or send it via email.  To avoid “spoilers”, simply don’t expand comments for this post.

Last Week’s Fragment – Solution

Last week’s puzzle continued with our new year’s calendar programming:

Write code to print out a month’s calendar given a month and year.

There are many implementations already available (including C code for the unix cal utility), but this was an opportunity to work it out for yourself.  I coded a Q&D web implementation in PHP; here’s the gist:

   STATIC $day_names = array('Sun', 'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat');
   $days_in_month = date('t', mktime(0, 0, 0, $month, 1, $year));
   $day = 1 - date('w', mktime(0, 0, 0, $month, 1, $year));
   echo '<table border="1">';
   for ($i=0; $i<7; $i++) {
      echo '<tr border="1">';
      for ($j=0; $j<7; $j++) {
         if ($i==0)
            printf('<td border="1"><b>%s</b></td>', $day_names[$j]);
         else {
            printf('<td border="1">%s</td>',
                     ($day > 0 && $day <= $days_in_month) ? $day : '&nbsp;');
            $day++;
         }
      }
      echo '</tr>';
   }
   echo '</table><p>&nbsp;</p>';

I used the classic PHP date function tricks to get the days in month and starting day of week.  It’s running at http://derekwilliams.us/fragments/cal.php and the complete source code is here.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

If you coded last week’s fragment under Linux, you could check your results by running cal month year.  The unix cal utility formats calendars based on the current date or a given date.  So let’s continue our new year’s programming along those lines:

Write code to print out a month’s calendar given a month and year.

To play along, post the code for the solution as a comment or send it via email.  You can built atop last week’s solution to determine the starting day of week.  There are likely many implementations already available (including C code for the unix utility), but this is a good opportunity to try new languages or techniques.

Last Week’s Fragment – Solution

With our round of game programming, our code solutions had grown a bit larger than mere fragments.  So last week’s puzzle returned to something short and sweet, as Friday Fragments marked Christmas Eve and New Year’s Eve:

Write code to calculate the day of week (Sunday through Saturday) for a given date.  Remember to account for leap years.

This is something of a classic math puzzle, and it’s not too tough to do the calculation mentally.  Many languages have a library function for this, but calling that would be cheating.  Perhaps the simplest approach is to implement Zeller’s Congruence in the language of your choice, overcoming numeric conversions.  I coded it in newly-explored Gosu:

   uses java.lang.Math
   var month=12;   var day=31;    var year=2011;  // Your date here
   var dayNames = {"Sun", "Mon", "Tue", "Wed", "Thu", "Fri", "Sat" }

   // Shift the year to start in March, split the year components:
   if (month<3) { month += 10; year--; }
   else         { month -= 2; }
   var shortYear = year % 100
   var century = (year / 100)

   // Zeller's: W = (k + floor(2.6m - 0.2) - 2C + Y + floor(Y/4) + floor(C/4)) mod 7
   var dayOfWeek = ((day +
                      Math.floor((2.6 * month) - 0.2) - (2 * century) +
                      shortYear + Math.floor(shortYear/4) + Math.floor(century/4)) % 7) as int
   print(dayNames[dayOfWeek])

 

Have a happy 1-1-11!

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

This year has Friday Fragments marking Christmas Eve and New Year’s Eve.  With that and another year change in mind, let’s do a simple calendar-related puzzle:

Write code to calculate the day of week (Sunday through Saturday) for a given date.  Remember to account for leap years.

To play along, post the code for the solution as a comment or send it via email.

Last Week’s Fragment – Solution

With last week’s puzzle, we conclude our round of game programming:

Upgrade your game (rock-paper-scissorstic-tac-toe, or Reversi, your choice) to use async (AJAX-style) calls and updates, rather than postbacks. Use any frameworks you’d like, or just plain old Javascript.

My Reversi solution is at http://derekwilliams.us/bots/reversi/reversiajax.php.  I used jQuery for the AJAX (get) calls, and ported much of playreversi.php and reversimove.php to Javascript.  Here’s the gist of it:

  var url = "http://derekwilliams.us/bots/reversi";  // Your bot here
  var board = "...........................OX..." +
              "...XO...........................";

  function userMove(row, col) {
    var index = (row*8) + col;
    var play = board.substr(0, index) + "X" + board.substr(index + 1);
    board = updateBoard(board, play);
    if (board.indexOf(".") >= 0)
      callBot();
    else
      showBoard();
  }

  function callBot() {
    var fullUrl = url + "?board=" + board + "&piece=O";
    $.get(fullUrl, "", function(play) { botReturn(play) }, "text");
  }

  function botReturn(play) {
    board = updateBoard(board, play);
    showBoard();
  }

  function showBoard() {
    var boardTable = document.getElementById("boardTable");
    for (var row=0; row<8; row++)
      for (var col=0; col<8; col++) {
        var piece = board.charAt((row*8)+col);
        var cellContents = "<img src='" + imageForPiece(piece) + "'>";
        if (piece == "." && canPlay(board, "X", (row*8)+col))
          cellContents = "<a href='javascript:userMove(" + row + "," + col + ")'>"
                                                           + cellContents + "</a>";
          boardTable.rows[row].cells[col].innerHTML = cellContents;
        }
  }

To see the helper functions, view the Javascript source. I continue to call my reversi web service bot; you can substitute your own at the “Your bot here” line.

By moving most of the behavior to the client, I greatly simplified the server-side PHP code (see the reversiajax.php source code).  You can view all our games and bots at http://derekwilliams.us/bots.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Let’s bring our games into the modern era.  You’ll notice in my solutions that every play causes a full redraw of the page.  That’s so very 1990s, so let’s fix it:

Upgrade your game (rock-paper-scissorstic-tac-toe, or Reversi, your choice) to use async (AJAX-style) calls and updates, rather than postbacks. Use any frameworks you’d like, or just plain old Javascript.

To play along, provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop the games, bots, and/or source code at http://derekwilliams.us/bots.

Last Week’s Fragment – Solution

Last’s week’s puzzle returned to our Reversi game:

Write code to let man compete against machine (a game bot) in Reversi.  Present the game board on a web page, let the human player make the next move, and then call the game bot for its move.  Continue this until one side wins.

My solution is at http://derekwilliams.us/bots/reversi/playreversi.php.  I built it from last week’s code and called our Reversi bot unmodified.  Here it is:

<?php
  require('reversimove.php');
  $url = 'http://derekwilliams.us/bots/reversi/';  // Your bot here

  // Set up the session.  If this is a new game, show the initial board:
  session_start();
  if (!isset($_SESSION['board']) || !isset($_REQUEST['row'])) {
    $board = str_repeat('.',64);
    $board[27]='O'; $board[28]='X';
    $board[35]='X'; $board[36]='O';
    $_SESSION['board'] = $board;
    exit(show_board($board));
  }

  // Get the board, add Xs (the human's) move, and score it:
  $play = $board = $_SESSION['board'];
  $play[($_REQUEST['row'] * 8 ) + $_REQUEST['col']] = 'X';
  $board = update_board($board, $play);
  if (substr_count($board, '.') == 0) {
    unset($_SESSION['board']);
    exit(show_board($board));
  }

  // Call the web service bot to get its (O's) move and score it:
  $play = file_get_contents($url.'?board='.$board.'&piece=O');
  $board = update_board($board, $play);
  show_board($board);
  $_SESSION['board'] = $board;

  function show_board($board) {
    STATIC $images = array( 'X' => 'black.jpg', 'O' => 'white.jpg', '.' => 'green.jpg');
    $scores = array('.' => 0, 'X' => 0, 'O' => 0);
    echo '<table border="1">';
    for ($i=0; $i<8; $i++) {
      echo '<tr border="1">';
      for ($j=0; $j<8; $j++) {
        $piece = $board[($i*8)+$j];
        $scores[$piece]++;
        if ($piece == '.' && can_play($board, 'X', ($i*8)+$j))
          printf('<td border="1"><a href="playreversi.php?row=%d&col=%d"><img src="%s"></td></a>',
                   $i, $j, $images[$piece]);
        else
          printf('<td border="1"><img src="%s"></td>', $images[$piece]);
      }
      echo '</tr>';
    }
    printf('</table><p>X: %d, O: %d.&nbsp;<a href="playreversi.php">Start Over</a></p>',
               $scores['X'], $scores['O']);
  }
?>

To keep it simple, there’s not a lot of error handling.  If you haven’t already done so, try coding your own bot, plug it in at the “Your bot here” line, and compete against it.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

With this week’s solution, we now have code to match man against machine in tic-tac-toe.  Let’s do that for our Reversi game:

Write code to let man compete against machine (a game bot) in Reversi.  Present the game board on a web page, let the human player make the next move, and then call the game bot for its move.  Continue this until one side wins.

To play along, provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop the games, bots, and/or source code at http://derekwilliams.us/bots.

Last Week’s Fragment – Solution

With last week’s puzzle, we returned to our game bots to let us humans play along:

Write code to let man compete against machine (a game bot) in rock-paper-scissors, tic-tac-toe, or Reversi (your choice).  Present the game board on a web page, let the human player make the next move, and then call the game bot for its move.  Continue this until one side wins.

I wrote a basic tic-tac-toe solution, available at http://derekwilliams.us/bots/tictactoe/playttt.php.  I deliberately built it from prior code (like scorettt) and called our tic-tac-toe bot unmodified.  Here’s the PHP code, with more commenting this time:

<?php
 $url = 'http://derekwilliams.us/bots/tictactoe';  // Your bot here

 // Set up the session.  If this is a new game, show the initial board:
 session_start();
 if (!isset($_SESSION['board'])) {
   $_SESSION['board'] = '         ';
   exit(show_board($_SESSION['board']));
 }

 // Get the board, add X's (the human's) move, and score it:
 $board = $_SESSION['board'];
 $board[($_REQUEST['row'] * 3) + $_REQUEST['col']] = 'X';
 if (!is_null($result = score_board($board, 'X')))
   game_over($board, $result);

 // Call the web service bot to get its (O's) move and score it:
 $board = file_get_contents($url.'?board=|'.rawurlencode($board).'|');
 $board = substr($board, 1, 9);
 if (!is_null($result = score_board($board, 'O')))
   game_over($board, $result);

 // No-one has won yet.  Show the board & keep playing:
 show_board($board);
 $_SESSION['board'] = $board;

 // Helper functions:

   function score_board($board, $turn) {

     STATIC $wins = array( array(0,1,2), array(3,4,5), array(6,7,8),
                           array(0,3,6), array(1,4,7), array(2,5,8),
                           array(0,4,8), array(2,4,6) );

     for ($i=0; $i<8; $i++) {
       for ($j=0, $piececount=0; $j<3; $j++) {
         if ($board[$wins[$i][$j]] == $turn)
           $piececount++;
       }
       if ($piececount == 3)
         return $turn.' wins!';
       elseif (substr_count($board, ' ') == 0)
         return 'Tie!';
     }
   }

   function show_board($board) {
     STATIC $images = array( 'X' => 'x.jpg', 'O' => 'o.jpg', ' ' => 'space.jpg');
     echo '<table border="1">';
     for ($i=0; $i<3; $i++) {
       echo '<tr border="1">';
       for ($j=0; $j<3; $j++) {
         $piece = $board[($i*3)+$j];
         if ($piece == ' ')
           printf('<td border="1"><a href="playttt.php?row=%d&col=%d"><img src="%s"></td></a>',
                    $i, $j, $images[$piece]);
         else
           printf('<td border="1"><img src="%s"></td>', $images[$piece]);
       }
       echo '</tr>';
    }
    echo '</table><p>&nbsp;</p>';
   }

   function game_over($board, $result) {
     show_board($board);
     unset($_SESSION['board']);
     exit(printf('<p><b>%s</b></p><a href="playttt.php">Start Over</a>', $result));
   }
?>

To keep it simple, there’s not a lot of error handling.  Also, you’ll notice that our prior tic-tac-toe bot (the O player) isn’t very good at it.  If you haven’t already done so, try coding your own bot, plug it in at the “Your bot here” line, and compete against it.  Perhaps you could upgrade the wins map. Then maybe your record will be as good as the NFC-leading Falcons.  10-2 – Rise Up!

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

After last week’s commemorative fragment, we’ll resume our game bots.  Let’s make our bots more interesting by letting us play instead of just watching:

Write code to let man compete against machine (a game bot) in rock-paper-scissors, tic-tac-toe, or Reversi (your choice).  Present the game board on a web page, let the human player make the next move, and then call the game bot for its move.  Continue this until one side wins.

To play along, provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop the bots and/or source code at http://derekwilliams.us/bots.

Last Week’s Fragment – Solution

Last week’s puzzle was another cryptogram:

OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

I offered a hint (“try some googling”) and a short-cut (“just offer suggestions on how to go about solving it”).  And for good reason: this is a somewhat famous unsolved cryptogram.  It’s Part 4 of Kryptos, Jim Sanborn’s sculpture at the CIA headquarters. I posted it last week in celebration of its 20th anniversary, and the recent release of a new clue.

Many experts and other sorts have worked on solving Part 4, in search of fame or just a good challenge.  I think it utilizes a one-time pad or a long key, perhaps along with the Vigenere Table found on the sculpture.  The key or pad may be located on-site; for example in the underground utility tunnel.  Time will tell.

If you think you can crack it, don’t just tell me: send your solution to Sanborn for verification.

If you’re just interested in Sanborn’s work, check out photos online.  The CIA Kryptos sculpture is now closed to visitors, but you can visit Sanborn’s other sculptures, such as The Cyrillic Projector and Adam Smith’s Spinning Top at UNC Charlotte.  Just don’t show up at his home.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Having finished a series of game bots, we’ll have a Thanksgiving change of pace and do another cryptogram.  Crack the following cipher:

OBKR
UOXOGHULBSOLIFBBWFLRVQQPRNGKSSO
TWTQSJQSSEKZZWATJKLUDIAWINFBNYP
VTTMZFPKWGDKZXTJCDIGKUHUAUEKCAR

You can provide the solution or just offer suggestions on how to go about solving it.  For example, I can’t solve it, but based on its background (try some googling), I have ideas about how it might be solved.  To “play along,” post your response as a comment or send it via email.

Last Week’s Fragment – Solution

Last week’s puzzle was to code a simple Reversi competition:

Write code to call competing Reversi bots, flip pieces, and score the results.

Here’s a solution in PHP.  

<?php
  require('reversimove.php);
  $urls[0] = 'http://derekwilliams.us/bots/reversi';
  $urls[1] = $urls[0];  // Your bot here
  $pieces = array('X', 'O');
  $board = str_repeat('.',64);
  $board[27]='O'; $board[28]='X';
  $board[35]='X'; $board[36]='O';
  $player = 0;

  for ($i=0; $i<64; $i++) {;
    $play = file_get_contents($urls[$player].'?board='.$board.'&piece='.$pieces[$player]);
    $board = update_board($board, $play);
    show_board($board);
    $player = $player == 0 ? 1 : 0;
  }

  function show_board($board) {
    $scores = array('.' => 0, 'X' => 0, 'O' => 0);
    echo '<table border="1">';
    for ($i=0; $i<8; $i++) {
      echo '<tr border="1">';
      for ($j=0; $j<8; $j++) {
        $piece = $board[($i*8)+$j];
        $scores[$piece]++;
        echo '<td border="1">'.$piece.'&nbsp;</td>';
      }
      echo '</tr>';
    }
    echo '</table><p>&nbsp;</p>';
    printf("<p>X: %d, O: %d</p>", $scores['X'], $scores['O']);
    if ($scores['.'] == 0)
      exit(printf("<p>%s wins!</p>", $scores['X'] > $scores['O'] ? 'X' : 0));
  }
?>

You can run this solution and other bots from the links at http://derekwilliams.us/bots.  This page also includes full source code, including helper functions.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Even T-Rex likes to code games that play themselves, so let’s continue with our Reversi “game bot:”

Write code to call competing Reversi bots, flip pieces, and score the results.  If you’d like, you can build atop the solution we used for tic-tac-toe.

To “play along,” provide either the URL or the code for the solution. You can post it as a comment or send it via email.

Last Week’s Fragment – Solution

Last week’s puzzle was to start a Reversi (a.k.a., Othello) “bot:”

Code a simple REST web service to start playing Reversi.  It should accept a 64-character string representing the current 8×8 “game board” with dot (empty space), X (black), or O (white) in each position (starting from the top left, going left-to-right and down).  It should return a 64-character string with your next move added.   Don’t worry about turning pieces yet, just find the next best move.

Here’s a simple solution in PHP, with room for improvement.  To start playing, pass it ?board=………………………OX……XO………………………&piece=X.

<?php
  if (!ereg('^[XO.]{64}$', $board=$_REQUEST['board']))
    die(str_repeat('X',64));
  if (!ereg('^[XO]$', $mypiece=$_REQUEST['piece']))
    die(str_repeat('.',64));

  if (!is_null($result = find_move($board, $mypiece)))
    exit($result);
  else
    exit($board);

  function find_move($board, $piece) {

    STATIC $plays = array( 0, 7, 56, 63,                  // outer corners
                           2, 5, 16, 23, 40, 47, 58, 61,  // A-squares
                           3, 4, 24, 32, 31, 39, 59, 60,  // B-squares
                          18, 21, 42, 45,                 // inner corners
                          19, 20, 26, 29, 34, 37, 43, 44, // inner sides
                          10, 11, 12, 13, 17, 22, 25, 30, // mid sides
                          33, 38, 41, 46, 50, 51, 52, 53,
                           1, 6, 8, 15, 48, 55, 57, 62,   // C-squares
                           9, 14, 49, 54 );               // X-squares              

    foreach ($plays as $play)
      if ($board[$play] == '.' && can_play($board, $piece, $play)) {
        $board[$play] = $piece;
        return $board;
      }
    return null;
  }
?>

Of course, there are much smarter ways to code Reversi, such as applying common strategies and running look-ahead scenarios, but that’d be more than a fragment.  Years ago, a coworker wrote one for VisualWorks (still in the Cincom Public Repository), and there’s a well-documented implementation at lurgee.net.  If you’re up for coding a smarter version behind the service interface, give it a shot.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Let’s do another “game bot” – this time, Othello (a.k.a., Reversi):

Code a simple REST web service to start playing Reversi.  It should accept a 64-character string representing the current 8×8 “game board” with dot (empty space), X (black), or O (white) in each position (starting from the top left, going left-to-right and down).  It should return a 64-character string with your next move added.   Don’t worry about turning pieces yet, just find the next best move.  We’ll work on flipping pieces in next week’s fragment.

To “play along,” provide either the URL or the code for the solution. You can post it as a comment or send it via email.

Last Week’s Fragment – Solution

Last week’s puzzle continued with our a tic-tac-toe “bot”:

Write code to score the results of calling two tic-tac-toe web services playing each other.  Check for wins, ties, and illegal moves.

Here’s a solution with my bot competing against itself (not surprisingly, it ends in a tie).  Of course, it still places a lot of trust in the bots to behave, but we’re keeping things simple here.

<?php
  $urls[0] = 'http://derekwilliams.us/bots/tictactoe';
  $urls[1] = $urls[0];  // Your bot here
  $board = '         ';
  $turn = 'X';

  for ($round=0; $round<5; $round++) {
    for ($i=0; $i<2; $i++) {
      $board = file_get_contents($urls[$i].'?board=|'.rawurlencode($board).'|');
      $board = substr($board, 1, 9);
      show_board($board);
      if (!is_null($result = score_board($board, $round, $turn)))
        exit(show_result($result));
      elseif ($round==4)
        exit(show_result('Tie'));
      $turn = $turn == 'X' ? 'O' : 'X';
    }
  }

  function score_board($board, $round, $turn) {
    STATIC $wins = array( array(0,1,2), array(3,4,5), array(6,7,8),
                          array(0,3,6), array(1,4,7), array(2,5,8),
                          array(0,4,8), array(2,4,6) );

     if (substr_count($board, $turn) != $round + 1)
       return 'Wrong number of '.$turn.'s';
     for ($i=0; $i<8; $i++) {
       for ($j=0, $piececount=0; $j<3; $j++) {
         if ($board[$wins[$i][$j]] == $turn)
           $piececount++;
       }
       if ($piececount == 3)
         return $turn.' wins!';
     }
   }

   function show_board($board) {
     echo '<table border="1">';
     for ($i=0; $i<3; $i++) {
       echo '<tr border="1">';
       for ($j=0; $j<3; $j++)
         echo '<td border="1">'.$board[($i*3)+$j].'&nbsp;</td>';
       echo '</tr>';
     }
     echo '</table><p>&nbsp;</p>';
   }

   function show_result($result) {
     return printf('<p><b>%s</b></p>', $result);
   }
?>

You can run this solution and the bots themselves from the links at http://derekwilliams.us/bots.

Stephen told me of a tic-tac-toe bot he wrote, but, alas, I forgot the full URL.  I’ll try to post it along with next week’s puzzle.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

We’ll continue in our tic-tac-toe “game bot” vein with the next step:

Write code to score the results of calling two tic-tac-toe web services playing each other.  Check for wins, ties, and illegal moves.

To “play along,” provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop results from our last Friday Fragment.

Last Week’s Fragment – Solution

Last week’s puzzle was a tic-tac-toe “bot”:

Code a simple REST web service to play tic-tac-toe.  It should accept a nine-character string representing the current “game board” with space, X, or O in each position (starting from the top left, going left-to-right and down).  It should return a nine-character string with your next move added.

Here’s my Q&D, brute-force solution in PHP, with room for improvement.  I added vertical bar wrappers to preserve spaces on the GET request, so pass it ?board=|         | to start.

<?php

   if (!ereg('^\|{1}[XO ]{9}\|{1}$', $board=$_REQUEST['board']))
     die('|XXXXXXXXX|');
   $board = substr($board, 1, 9);
   $mypiece = (substr_count($board, ' ') & 1) ? 'X' : 'O';

   // The best move is with two plays and one space to win or block.
   // The rest is not much better than random.
   for ($plays=2; $plays>=0; $plays--)
     for ($spaces=1; $spaces<4-$plays; $spaces++)
       if (!is_null($result = find_move($board, $mypiece, $spaces, $plays)))
         exit('|'.$result.'|');

   die('|OOOOOOOOO|');

   function find_move($board, $piece, $spaces, $plays) {

     $wins = array( array(0,1,2), array(3,4,5), array(6,7,8),
                    array(0,3,6), array(1,4,7), array(2,5,8),
                    array(0,4,8), array(2,4,6) );

     for ($i=0; $i<8; $i++) {
       $win=$wins[$i];
       for ($j=0, $mycount=0, $spacecount=0; $j<3; $j++) {
         if ($board[$win[$j]] == $piece)
           $mycount++;
         elseif ($board[$win[$j]] == ' ') {
           $spacecount++;
           $spaceplace = $j;
         }
       }
       $opponentcount = 3 - $mycount - $spacecount;

       if ($spacecount == $spaces) {
         if ($mycount == $plays) {              // win
           $board[$win[$spaceplace]] = $piece;
           return $board;
         } elseif ($opponentcount == $plays) {  // block
           $board[$win[$spaceplace]] = $piece;
           return $board;
         }
       }
     }
     return null;
   }
?>

Can you write a tic-tac-toe bot that’ll beat it?

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

Let’s do another game bot: this time, just a bit more sophisticated than randomly answering rock, paper, or scissors:

Code a simple REST web service to play tic-tac-toe.  It should accept a nine-character string representing the current “game board” with space, X, or O in each position (starting from the top left, going left-to-right and down).  It should return a nine-character string with your next move added.

For example, the game board at left is represented by the string ”  O X OX “.  X goes first; if you receive all spaces (empty board), go first with X.  Otherwise, take the next move: if you receive an even number of Xs and O’s, replace a space with an X; if you receive an odd number of plays, replace a space with an O.  And no cheating: if you do anything other than take the next legal move, you lose.

This is your chance to have a computer play your games for you.  Can you code something that plays as wisely as you would?

To “play along,” provide either the URL or the code for the solution. You can post it as a comment or send it via email.  We’ll have the submitted services compete in some “bot wars.”

Last Week’s Fragment – Solution

Last week’s puzzle continued with our simple RPS game:

Write code to score the results of calling rock, paper, scissors (RPS) web services.  Remember, rock beats scissors, scissors beat paper, and paper beats rock.  And bombs and dynamite don’t count.

Here’s another simple solution in PHP – my bot facing off against Spencer’s:

    <?php
      $winners = array("rock" => "paper", "paper" => "scissors", "scissors" => "rock");
      $url1 = 'http://derekwilliams.us/bots/rps';
      $url2 = 'http://ninjatricks.net/rps.php';
      $result1 = file_get_contents($url1);
      $result2 = file_get_contents($url2);
      printf("1: %s   2: %s\n", $result1, $result2);

      if ($result1 == $result2)
        echo "Tie";
      elseif ($result1 == $winners[$result2])
        echo "#1 wins!";
      elseif ($result2 == $winners[$result1])
        echo "#2 wins!";
      else
        echo "No winner.  Someone's misbehaving.";
    ?>

Again, it’s a bit oversimplified, but does the job.

Now you’re ready for your first “bot war”: see how your RPS bot competes with mine at http://derekwilliams.us/bots/rps.

The Friday Fragment

It’s Friday, and time again for the Friday Fragment: our weekly programming-related puzzle.

This Week’s Fragment

This week, we’ll take another step in our web service “bot wars:”

Write code to score the results of calling rock, paper, scissors web services.  Remember, rock beats scissors, scissors beat paper, and paper beats rock.  And bombs and dynamite don’t count.

To “play along”, provide either the URL or the code for the solution. You can post it as a comment or send it via email.  If you’d like, you can build atop results from our last Friday Fragment.

Last Week’s Fragment – Solution

Last week’s puzzle continued along our simple web service vein with the flip-side: calling a web service.

Write code to call your rock, paper, scissors web service and keep counts of how many times each is returned.

Here’s a really simple solution in PHP:

    <?php
      $counts = array("rock" => 0, "paper" => 0, "scissors" => 0);
      $url = 'http://derekwilliams.us/bots/rps';
      for ($i=0; $i<100; $i++)
        $counts[file_get_contents($url)]++;
      print_r($counts);
    ?>

 

It’s a bit oversimplified (e.g., no error handling), but does the job.