TweetFollow Us on Twitter

Apr 00 Challenge

Volume Number: 16 (2000)
Issue Number: 4
Column Tag: Programmer's Challenge

Programmer's Challenge

by Bob Boonstra, Westford, MA

Text Compression

This month, we've got some very important messages to send. But we're not living in a world of free bandwidth. In fact, bandwidth in our Challenge world is very expensive, so expensive that we're asking you to compress our messages and save us a few bytes.

The prototype for the code you should write is:

void * /* yourStorage */ InitCompression(void);

long /* compressedLength */ CompressText(
  char *inputText,        /* text to be compressed */
  long numInputChars,     /* length of inputText in bytes */
  char *compressedText,   /* return compressedText here */
  const void *yourStorage /* storage returned by InitCompression */
);

long /* expandedLength */ ExpandText(
  char *compressedText,   /* encoded text to be expanded */
  long compressedLength,  /* length of encoded text in bytes */
  char *expandedText,     /* return expanded text here */
  const void *yourStorage /* storage returned by InitCompression */
);

void TermCompression(
  void *yourStorage       /* storage returned by InitCompression */
);

For this Challenge, you need to provide the four routines indicated above. Your InitCompression and TermCompression routines will be called only once each, at the beginning of the test and at the end of the test, respectively. InitCompression should allocate and return a block of yourStorage where you initialize any information needed by your compression and expansion routines. That storage will be passed back to you unchanged each time you are asked to compress or decompress text. TermCompression will be called at the end of the test and should deallocate the block of yourStorage to avoid a memory leak.

In between the calls to InitCompression and TermCompression, the test code will make multiple calls to CompressText and ExpandText with different inputText values. CompressText should process the inputText, populate the compressedText, and return the number of bytes in the result. ExpandText does the opposite, processing the compressedText, converting it to expandedText, and returning the number of bytes of the original text. Multiple CompressText and ExpandText calls will occur with varying inputText and compressedText, in any order, with the obvious constraint that text must be encoded before it can be decoded.

The inputText may contain any character between 0x00 and 0x7F, inclusive. As a practical matter, the inputText will be drawn from paragraphs of English-language text, computer programs in C, C++, and Pascal, and html pages.

All text-specific information needed to decode the compressedText must be stored in the compressedText itself. Any text-independent decoding information may be stored in yourStorage or in static storage within your program. No text-specific encoding information may be stored in yourStorage or in static variables.

The winner will be the solution that correctly compresses the inputText into the least costly compressedText, where cost is a function of length and execution time. Specifically, each inputText will have a cost equal to theCompressedLength of the corresponding compressedText, plus a penalty of 10% for each 100 milliseconds required to do the encoding and decoding.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 5 environment. Solutions may be coded in C, C++, or Pascal. Solutions in Java will also be accepted, but Java entries must be accompanied by a test driver that uses the interface provided in the problem statement.

Three Months Ago Winner

Congratulations to Sebastian Maurer for winning the January, 2000, Triangle Peg Challenge. The Peg Challenge required entries to solve variously sized games of peg solitaire, a game where pegs are arranged in holes on a triangle board. The objective of the game is to repeatedly jump one peg over an adjacent one, removing the jumped peg each time, with the intent of removing as many pegs as possible. In our Challenge, scoring counted 1000 penalty points for each peg left on the board, plus one penalty point for each millisecond of execution time. Sebastian did not submit the fastest entry - in fact, he ranked third in speed - but it played the Peg game significantly better than the other solutions, resulting in a better overall score.

I evaluated the Pegs entries using 14 test cases, ranging from 5 pegs to 100 pegs on a side. Nine of the test cases were missing only one peg, one of the large puzzles was missing 50 pegs, with the remainder missing a small number of pegs. Sebastian's entry left fewer pegs on the board than the second place solution in 12 of 14 test cases, and fewer than the third place solution in 10 of 14 cases. Sebastian's entry won in all of the test cases involving larger puzzles.

Sebastian's code is rather sparsely commented. The work is done in his Search routine, which iteratively tries valid moves, backtracks when it cannot find a valid move, and saves the best solution found so far. In looking at the code for the top entries, it wasn't obvious why Sebastian's solution did so much better than the others. The entries did use different logic to prune the search and trade execution time against search depth; perhaps those differences explain the performance variation.

The table below lists, for each of the solutions submitted, the overall score, the execution time in microseconds, and the total number of pegs left on the board for all of our test cases. It also indicates the code size, data size, and programming language used by each solution. Two entries did not complete all of the test cases and are listed last. As usual, the number in parentheses after the entrant's name is the total number of Challenge points earned in all Challenges prior to this one.

NameScoreTime (µsecs)Pegs LeftCode SizeData SizeLang
Sebastian Maurer (77)20224644646419764852162C
Andrew Downs (2)3623988109883613187220C
Willeke Rieken (61)3727672146723713302056C++
Randy Boring (112)11211715476714107357308132096C++
M. L.N/AN/A2648218C
J. C.N/AN/A108281021C++

Top Contestants

Listed here are the Top Contestants for the Programmer's Challenge, including everyone who has accumulated 10 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month's entrants.

RankNamePoints
1.Munter, Ernst227
2.Saxton, Tom139
3.Maurer, Sebastian87
4.Rieken, Willeke48
5.Boring, Randy43
6.Heithcock, JG43
7.Shearer, Rob43
8.Taylor, Jonathan24
9.Brown, Pat20
10.Downs, Andrew12
11.Jones, Dennis12
12.Hart, Alan11
13.Duga, Brady10
14.Hewett, Kevin10
15.Murphy, ACC10
16.Selengut, Jared10
17.Strout, Joe10
18.Varilly, Patrick10

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

1st place20 points
2nd place10 points
3rd place7 points
4th place4 points
5th place2 points
finding bug2 points
suggesting Challenge2 points

Here is Sebastian's winning Triangle Peg solution:

Pegs.c
Copyright © 2000 Sebastian Maurer

#include "Pegs.h"
#include "Memory.h"
#include "Timer.h"

#include <stdio.h>

const int kNumTries = 1000;
const UInt32 kStopTime = 500000;
  // in microseconds

const int kNumDirections = 6;
enum {kIllegal = 0, kFull, kEmpty};

char** gGrid;
PegJump *gCurrentJumps;
PegJump *gBestJumps;
int gBestScore;
UnsignedWide gLastImprovement;
unsigned short *gDirection;
short gDeltaRow[kNumDirections];
short gDeltaCol[kNumDirections];

static UInt32 WideDiff(UnsignedWide m1, UnsignedWide m2)
{
  UnsignedWide m;
  m.lo = m2.lo - m1.lo;
  m.hi = m2.hi - m1.hi;
  if (m1.lo > m2.lo)
    m.hi -= 1;
  return m.lo;
}

static void PrintBoard(int triangleSize) {
  for(int r = 0; r < triangleSize; r++) {
    for(int c = - triangleSize; c <= triangleSize; c++)
    {
      switch (gGrid[r][c]) {
        case kIllegal: printf(" "); break;
        case kFull: printf("X"); break;
        case kEmpty: printf("."); break;
        default: printf("?");
      }
    }
    printf("\n");
  }
  printf("\n");
}

AllocateGrid
//////
// Memory allocation for the 2D grid
static char **AllocateGrid(
  int xMin, int xMax,
  int yMin, int yMax)
{
  int i, j;
  int nx = xMax - xMin + 1;
  int ny = yMax - yMin + 1;
  char **array;
  Ptr p;
  int rowSize;

  array = (char **) NewPtr((Size)(nx * sizeof(char*)));
  if (array == 0)
    return 0;
  
  array -= xMin;
  p = NewPtr((Size)(nx * ny * sizeof(char)));
  if (p == 0)
    return 0;
  p -= yMin * sizeof(char);
  rowSize = (int)(ny * sizeof(char));
  for(i = xMin; i <= xMax; i++) {
    array[i] = (char*) p;
    p += rowSize;
  }

  for(i = xMin; i <= xMax; i++)
    for(j = yMin; j <= yMax; j++)
      array[i][j] = 0;

  return array;
}

DeallocateGrid
static void DeallocateGrid(
  char **array, long xMin, long yMin)
{
  DisposePtr((Ptr) (array[xMin] + yMin));
  DisposePtr((Ptr) (array + xMin));
}

FillGrid
//////
// Fill the grid with the initial configuration
static void FillGrid(
  short size,
  short numInitialPegs,
  TrianglePegPosition initialPegPositions[]
) {
  for(int r = -2; r < size + 2; r++)
    for(int c = - size - 2; c <= size + 2; c++)
      gGrid[r][c] = kIllegal;

  for(int r = 0; r < size; r++)
    for(int c = - r; c <= r; c += 2)
      gGrid[r][c] = kEmpty;
  
  for(int p = 0; p < numInitialPegs; p++) {
    int row = initialPegPositions[p].row;
    int col = initialPegPositions[p].col;
    gGrid[row][col] = kFull;
  }
}

SaveSolution
//////
// Store the current best solution
static void SaveSolution(int numMoves) {
  gBestScore = numMoves;

  for(int m = 0; m < numMoves; m++) {
    gBestJumps[m].from.row =
      gCurrentJumps[m].from.row;
    gBestJumps[m].from.col =
      gCurrentJumps[m].from.col;
    gBestJumps[m].to.row =
      gCurrentJumps[m].to.row;
    gBestJumps[m].to.col =
      gCurrentJumps[m].to.col;
  }
    
}

Try
//////
// Perform a move if it is legal, and return true
// If the move is illegal, return false
// I assume position (r,c) already contains a peg
static bool Try(int move, int r, int c, int dir)
{
  int dr = gDeltaRow[dir];
  int dc = gDeltaCol[dir];

  if ((gGrid[r + dr][c + dc] == kFull) &&
    (gGrid[r + 2 * dr][c + 2 * dc] == kEmpty))
  {
    gDirection[move] = dir;
      
    gCurrentJumps[move].from.row = r;
    gCurrentJumps[move].from.col = c;
    
    gCurrentJumps[move].to.row = r + 2 * dr;
    gCurrentJumps[move].to.col = c + 2 * dc;
    
    gGrid[r][c] = kEmpty;
    gGrid[r + dr][c + dc] = kEmpty;
    gGrid[r + 2 * dr][c + 2 * dc] = kFull;

    return true;
  }
  else
    return false;
}

UndoMove
//////
// Undo a move by restoring the grid
static inline void UndoMove(int row, int col, int dir) {
  int dr = gDeltaRow[dir];
  int dc = gDeltaCol[dir];

  gGrid[row][col] = kFull;
  gGrid[row + dr][col + dc] = kFull;
  gGrid[row + 2 * dr][col + 2 * dc] = kEmpty;
}

Search
//////
// This is where the search is done
static void Search(
  int numInitialPegs,
  int triangleSize
) {

  UnsignedWide now;
  int move, row, col, dir;
  bool abort = false;
  bool haveASolution = false;
  
  int numTries = 0;

  row = 0;
  col = 0;
  dir = -1;
  move = 0;

  do {
  
    // find the next valid move
    do {
      dir++;
      if (dir >= kNumDirections) {
        dir = 0;
        col++;
        if (col == row + 1) {
          row++;
          col = - row;
        }
      }
    } while ((row < triangleSize) &&
           ((gGrid[row][col] == kEmpty) ||
            !Try(move, row, col, dir)));
  
    if (row < triangleSize) {
      // we just made a valid move
      // start work on the next move
      
      move++;

      row = 0;
      col = 0;
      dir = 0;
    } else { // we reached a dead end
      
      // see if this is a better solution
      if (move > gBestScore) {
        SaveSolution(move);
        haveASolution = true;

        if (move + 1 == numInitialPegs)
          abort = true;

        Microseconds(&now);

        gLastImprovement = now;
      }
      
      // backtrack
      move-;
      
      if (move >= 0) {
        row = gCurrentJumps[move].from.row;
        col = gCurrentJumps[move].from.col;
        dir = gDirection[move];
        UndoMove(row, col, dir);        
      }
      
    }
    
    if (haveASolution) {
      // if we already reached a dead end once,
      // don't waste time searching more
    
      numTries++;
      if (numTries == kNumTries) {
        numTries = 0;
        Microseconds(&now);
        if (WideDiff(gLastImprovement, now) >
            kStopTime)
        {
          abort = true;
        }
      }
    }

  } while (!abort && (move >= 0));
}

SolvePegTriangle
short /* number of moves */ SolvePegTriangle (
  short triangleSize,
    /* number of rows in triangle to solve */
  short numInitialPegs,
    /* number of pegs in starting puzzle position */
  TrianglePegPosition initialPegPositions[],
    /* peg locations in starting puzzle position */
  PegJump pegJumps[]
    /* return peg moves that solve the puzzle here,
       in sequence */

) {
  // prepare, allocate, initialize structures
  gDeltaRow[0] = -1; gDeltaCol[0] = -1;
  gDeltaRow[1] = -1; gDeltaCol[1] = +1;
  gDeltaRow[2] = 0; gDeltaCol[2] = -2;
  gDeltaRow[3] = 0; gDeltaCol[3] = +2;
  gDeltaRow[4] = +1; gDeltaCol[4] = -1;
  gDeltaRow[5] = +1; gDeltaCol[5] = +1;
  
  gGrid =
    AllocateGrid(-2, triangleSize + 2,
      - triangleSize - 2, triangleSize + 2);
  if (gGrid == 0)
    return 0;
  
  gDirection = (unsigned short*)
    NewPtr(numInitialPegs * sizeof(unsigned short));
  if (gDirection == 0)
    return 0;
  
  gCurrentJumps = (PegJump*)
    NewPtr(numInitialPegs * sizeof(PegJump));
  if (gCurrentJumps == 0)
    return 0;

  gBestJumps = pegJumps;

  Microseconds(&gLastImprovement);
  gBestScore = 0;

  FillGrid(triangleSize, numInitialPegs,
       initialPegPositions);

  // do the work
  Search(numInitialPegs, triangleSize);

  // clean up
  DeallocateGrid(gGrid, -2, - triangleSize - 2);
  DisposePtr((Ptr)gDirection);
  DisposePtr((Ptr)gCurrentJumps);

  return gBestScore;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

BBEdit 11.6.1 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
ScreenFlow 6.1 - Create screen recording...
ScreenFlow is powerful, easy-to-use screencasting software for the Mac. With ScreenFlow you can record the contents of your entire monitor while also capturing your video camera, microphone and your... Read more
Microsoft Office 2016 15.25 - Popular pr...
Microsoft Office 2016 - Unmistakably Office, designed for Mac. The new versions of Word, Excel, PowerPoint, Outlook and OneNote provide the best of both worlds for Mac users - the familiar Office... Read more
FileZilla 3.21.0 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.21.0: Fixed Vulnerabilities Fixed a string format... Read more
Fantastical 2.2.5 - Create calendar even...
Fantastical 2 is the Mac calendar you'll actually enjoy using. Creating an event with Fantastical is quick, easy, and fun: Open Fantastical with a single click or keystroke Type in your event... Read more
The Hit List 1.1.26 - Advanced reminder...
The Hit List manages the daily chaos of your modern life. It's easy to learn - it's as easy as making lists. And it's powerful enough to let you plan, then forget, then act when the time is right.... Read more
Typinator 6.10 - Speedy and reliable tex...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
EtreCheck 3.0.2 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more
FileZilla 3.21.0 - Fast and reliable FTP...
FileZilla (ported from Windows) is a fast and reliable FTP client and server with lots of useful features and an intuitive interface. Version 3.21.0: Fixed Vulnerabilities Fixed a string format... Read more
EtreCheck 3.0.2 - For troubleshooting yo...
EtreCheck is an app that displays the important details of your system configuration and allow you to copy that information to the Clipboard. It is meant to be used with Apple Support Communities to... Read more

Dungeon Warfare (Games)
Dungeon Warfare 1.0 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0 (iTunes) Description: Dungeon Warfare is a challenging tower defense game where you become a dungeon lord to defend your dungeon against greedy... | Read more »
Solitairica (Games)
Solitairica 1.0.7 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.7 (iTunes) Description: Solitairica takes RPG combat and challenging rogue-like progression to a fresh new place—the world of solitaire! | Read more »
Bowmasters tips, tricks and hints
At least for this writer, archery was one of the more pleasant surprises of the 2016 Rio Olympics. As opposed to target shooting with guns, which was dreadfully boring, watching people shoot arrows at targets was pretty darn cool. [Read more] | Read more »
Best apps for watching live TV
The Olympics have come and gone, leaving nearly everyone in a temporary state of "What the heck am I going to watch on TV right now?" Besides old reruns of Golden Girls, but that goes without saying. [Read more] | Read more »
What is Flip Diving, and why has it take...
Move over Pokemon GO. There's a new king in town, and it's "the world's #1 cliff diving game." [Read more] | Read more »
5 places where Pokemon GO is still numbe...
In the U.S., the bloom is off the Pokemon Go rose ever so slightly. It's still doing great, sitting atop the top grossing chart as it has for some time, but it's no longer among the top 10 free apps in downloads, possibly because darn near... | Read more »
Madden NFL Mobile: How defense has chang...
Saying that defense is not a priority in Madden NFL Mobile is a bit of an understatement. In asynchronous head-to-head play, you don't take control of your defenders at all, as the AI manages them while your opponent plays offense. When it's your... | Read more »
Feed Hawk (News)
Feed Hawk 1.0.1 Device: iOS Universal Category: News Price: $2.99, Version: 1.0.1 (iTunes) Description: Feed Hawk makes it easy to subscribe to the RSS feed of the website you are visiting. From within Safari, simply open a share... | Read more »
Reigns character guide: Who's who i...
Know your foes. Keep your friends close, but your enemies closer. And there are probably some other cliches that would apply to your perilous spot on the throne in Reigns as well. [Read more] | Read more »
Match 3 puzzler Small Lime is now availa...
Set to hit Android and IOS on the 17th August, Small Lime is the newest match 3 mobile game, and hopes to throw something a little different into the mix. If you love match 3 puzzles, but are tired of the same old ideas being re-hashed again and... | Read more »

Price Scanner via MacPrices.net

12-inch Retina MacBooks on sale for up to $10...
Amazon has 2016 12″ Apple Retina MacBooks on sale for $100 off MSRP. Shipping is free: - 12″ 1.1GHz Space Gray Retina MacBook: $1199 $100 off MSRP - 12″ 1.1GHz Silver Retina MacBook: $1224.99 $75 off... Read more
13-inch 2.5GHz MacBook Pro (Apple refurbished...
Apple has Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.5GHz MacBook Pros... Read more
21-inch iMacs on sale for up to $120 off MSRP
B&H Photo has 21″ iMacs on sale for up to $120 off MSRP including free shipping plus NY sales tax only: - 21″ 3.1GHz iMac 4K: $1379 $120 off MSRP - 21″ 2.8GHz iMac: $1199.99 $100 off MSRP - 21″ 1... Read more
Typinator 6.10 comes with 50 improvements – G...
Ergonis Software today announced release of Typinator 6.10, a new version of their text expander utility for macOS. Typinator 6.10 comes with 50 improvements, including new features, compatibility... Read more
Taxi Sim 2016 Puts Users Behind the Wheel in...
Ovilex Soft today announces Taxi Sim 2016, an update to their ultra-realistic 3D driving simulator app for iOS and Android devices — literally a global event what with the company’s nearly 450,000... Read more
11-inch 1.6GHz/128GB MacBook Air on sale for...
Amazon has the current-generation 11″ 1.6GHz/128GB MacBook Air (sku MJVM2LL/A) on sale for $788 for a limited time. Their price is $111 off MSRP, and it’s the lowest price available for this model. Read more
Apple refurbished Mac minis available for up...
Apple has Certified Refurbished Mac minis available starting at $419. Apple’s one-year warranty is included with each mini, and shipping is free: - 1.4GHz Mac mini: $419 $80 off MSRP - 2.6GHz Mac... Read more
Apple refurbished 13-inch Retina MacBook Pros...
Apple has Certified Refurbished 13″ Retina MacBook Pros available for up to $270 off the cost of new models. An Apple one-year warranty is included with each model, and shipping is free: - 13″ 2.7GHz... Read more
12-inch 32GB and 128GB WiFi iPad Pros on sale...
B&H Photo has 12″ 32GB & 128GB WiFi Apple iPad Pros on sale for up to $70 off MSRP, each including free shipping. B&H charges sales tax in NY only: - 12″ Space Gray 32GB WiFi iPad Pro: $... Read more
Apple refurbished 11-inch MacBook Airs availa...
Apple has Certified Refurbished 11″ MacBook Airs (the latest models), available for up to $170 off the cost of new models. An Apple one-year warranty is included with each MacBook, and shipping is... Read more

Jobs Board

*Apple* Retail - Multiple Positions Germanto...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Professional Learning Specialist - A...
# Apple Professional Learning Specialist Job Number: 51234379 Portland, Maine, Maine, United States Posted: Aug. 18, 2016 Weekly Hours: 40.00 **Job Summary** The Read more
Lead *Apple* Solutions Consultant - Apple (...
# Lead Apple Solutions Consultant Job Number: 51218465 Richmond, VA, Virginia, United States Posted: Aug. 18, 2016 Weekly Hours: 40.00 **Job Summary** The Lead ASC Read more
*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 51218534 Pleasant Hill, California, United States Posted: Aug. 18, 2016 Weekly Hours: 40.00 **Job Summary** As an Apple Read more
*Apple* Retail - Multiple Positions Chestnut...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.