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.

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!

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 + M²), 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:

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

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 + M²), 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 + M² (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.

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-scissors, tic-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.

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!

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.

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.

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?