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

MacFamilyTree 8.2.1 - Create and explore...
MacFamilyTree gives genealogy a facelift: modern, interactive, convenient and fast. Explore your family tree and your family history in a way generations of chroniclers before you would have loved.... Read more
Spotify 1.0.57.474. - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
VOX 2.8.26 - Music player that supports...
VOX just sounds better! The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all audio formats you should ever need.... Read more
beaTunes 5.0.1 - Organize your music col...
beaTunes is a full-featured music player and organizational tool for music collections. How well organized is your music library? Are your artists always spelled the same way? Any R.E.M. vs REM?... Read more
LibreOffice 5.3.4.2 - Free, open-source...
LibreOffice is an office suite (word processor, spreadsheet, presentations, drawing tool) compatible with other major office suites. The Document Foundation is coordinating development and... Read more
Sparkle Pro 2.2 - $79.99
Sparkle Pro will change your mind if you thought building websites wasn't for you. Sparkle is the intuitive site builder that lets you create sites for your online portfolio, team or band pages, or... Read more
calibre 3.1.1 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
calibre 3.1.1 - Complete e-book library...
Calibre is a complete e-book library manager. Organize your collection, convert your books to multiple formats, and sync with all of your devices. Let Calibre be your multi-tasking digital librarian... Read more
Sparkle Pro 2.2 - $79.99
Sparkle Pro will change your mind if you thought building websites wasn't for you. Sparkle is the intuitive site builder that lets you create sites for your online portfolio, team or band pages, or... Read more
Spotify 1.0.57.474. - Stream music, crea...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more

Latest Forum Discussions

See All

This War of Mine gets a new ending and m...
This War of Mine just got a big new update, featuring free DLC that adds a new ending to the game, among other exciting changes. The update is celebrating the game's two-year release anniversary. Apart from the new ending, which will be quite... | Read more »
Summon eight new heroes in Fire Emblem H...
Nintendo keeps coming at us with Fire Emblem Heroes updates, and it doesn't look like that trend is stopping anytime soon. The folks behind the game have just announced the new War of the Clerics Voting Gauntlet, expected to start next Tuesday. [... | Read more »
The best deals on the App Store this wee...
iOS publishers are pulling out all the stops this week -- there's a huge number of seriously great games at discounted prices this week. Let's not waste any time and get right down to business. [Read more] | Read more »
The House of da Vinci (Games)
The House of da Vinci 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Enter The House of Da Vinci, a new must-try 3D puzzle adventure game. Solve mechanical puzzles, discover hidden... | Read more »
Solve the disappearance of history’s gre...
Blue Brain Games invites you to indulge in an immersive hands-on 3D puzzle adventure in similar vein to The Room series, with its debut release The House of Da Vinci. Set during the historic period of the Italian Renaissance (when Leonardo himself... | Read more »
Age of Rivals (Games)
Age of Rivals 3.3 Device: iOS Universal Category: Games Price: $.99, Version: 3.3 (iTunes) Description: Deep civilization-building strategy in a fast-paced card game! | Read more »
Panthera Frontier (Games)
Panthera Frontier 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »
Angry Birds Evolution beginner's gu...
Angry Birds changes things up a fair bit in its latest iteration, Angry Birds Evolution. The familiar sling-shot physics mechanics are still there, but the game now features team-based gameplay, RPG elements, and a new top-down view. With all of... | Read more »
Sega Forever is for the retro game fans
Sega is launching a new retro games service titled Sega Forever, in a move that's sure to delight games enthusiasts with a bit of nostalgia. Sega's releasing five classic games for free. The titles include Sonic the Hedgehog, Phantasy Star II,... | Read more »
The Little Acre (Games)
The Little Acre 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

ABBYY TextGrabber 6 for iOS Implements Instan...
ABBYY has announced the release of TextGrabber 6.0.0, an important feature update to the company’s productivity app developed for iOS and Android devices. TextGrabber 6.0 now offers Real-Time... Read more
vPhone, First Smartphone That Can’t Be Lost,...
Austin, Texas based Hypori has introduced the vPhone, a virtual smartphone that affords every business user the benefits of separate work and personal phones, conveniently delivered on a single... Read more
Save this weekend with 2016 refurbished MacBo...
Apple has dropped prices on Certified Refurbished 2016 15″ and 13″ MacBook Pros by as much as $590 off original MSRP. An Apple one-year warranty is included with each model, and shipping is free: -... Read more
New 27-inch 3.4GHz iMac on sale for $1699, sa...
MacMall has the new 2017 27″ 3.4GHz iMac (MNE92LL/A) in stock and on sale for $1699 including free shipping. Their price is $100 off MSRP. Read more
Clearance 2016 MacBook Pros available for up...
B&H Photo has clearance 2016 13″ and 15″ MacBook Pros in stock today and on sale for up to $400 off original MSRP. Shipping is free, and B&H charges NY & NJ sales tax only: - 15″ 2.7GHz... Read more
Apple Ranks 9th In comScore Top 50 U.S. Digit...
comScore, Inc. has released its monthly ranking of U.S. online activity at the top digital media properties for May 2017 based on data from comScore Media Metrix Multi-Platform. * Entity has... Read more
10.5-inch iPad Pros available for up to $20 o...
B&H Photo has the new 2017 10.5″ iPad Pros available for up to $20 off MSRP including free shipping plus NY & NJ sales tax only: - 64GB iPad Pro WiFi: $649 - 256GB iPad Pro WiFi: $749 - 512GB... Read more
Three Off-The-Beaten-Track iOS Apps That Dese...
One of the great things about using iPads and iPhones is the vast selection of apps available for most anything you want or need to do. The three outlined in this article have been in my core app... Read more
Apple No. 1 Spot In Gartner Top 100 Vendors i...
Gartner, Inc. has unveiled the top global 100 vendors in IT in 2016 based on their revenue across IT (excluding communication services) and component market segments. In the Gartner Global Top 100:... Read more
Clearance iMacs available for up to $300 off...
B&H Photo has clearance 21″ and 27″ Apple iMacs available starting at $949, each including free shipping plus NY & NJ sales tax only: - 27″ 3.3GHz iMac 5K: $1999 $300 off original MSRP - 27″... Read more

Jobs Board

*Apple* News Product Marketing Mgr., Publish...
…organizational consensus on strategy and vision for publisher tools, authoring, and Apple News Format.Carries this strategy and vision across the organization to Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Security Data Analyst - *Apple* Information...
…data sources need to be collected to allow Information Security to better protect Apple employees and customers from a wide range of threats.Act as the subject matter Read more
Lead *Apple* Solutions Consultant - Apple I...
…integrity, and trust.Success Metrics/Key Performance Indicators:Quantitative* Year over Year growth in Apple Product and Beyond the Box sales in the assigned Point of Read more
*Apple* Solutions Consultant till v%u00E5r...
…ethics, integrity, and trust.Success Metrics/Key Performance Indicators:QuantitativeYear over Year growth in Apple Product and Beyond the Box sales in the assigned Point Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.