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

Tunnelblick 3.7.4b - GUI for OpenVPN.
Tunnelblick is a free, open source graphic user interface for OpenVPN on OS X. It provides easy control of OpenVPN client and/or server connections. It comes as a ready-to-use application with all... Read more
Carbon Copy Cloner 5.0.5 - Easy-to-use b...
Carbon Copy Cloner backups are better than ordinary backups. Suppose the unthinkable happens while you're under deadline to finish a project: your Mac is unresponsive and all you hear is an ominous,... Read more
Postbox 5.0.22 - Powerful and flexible e...
Postbox is a new email application that helps you organize your work life and get stuff done. It has all the elegance and simplicity of Apple Mail, but with more power and flexibility to manage even... Read more
Ortelius 2.0.8 - Vector drawing app espe...
Ortelius is a full-featured vector drawing application especially for map design. Draw directly with features such as roads, rivers, coastlines, buildings, symbols and contours. Ortelius is known for... Read more
Bartender 3.0.32 - Organize your menu-ba...
Bartender lets you organize your menu-bar apps by hiding them, rearranging them, or moving them to Bartender's Bar. You can display the full menu bar, set options to have menu-bar items show in the... Read more
Adobe Animate CC 2018 18.0.1.115 - Anima...
Animate CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2018 (was Flash CC) lets you... Read more
Adobe Lightroom Classic CC 7.1 - Import,...
Adobe Lightroom is available as part of Adobe Creative Cloud for as little as $9.99/month bundled with Photoshop CC as part of the photography package. Lightroom 6 is also available for purchase as a... Read more
ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
ExpanDrive 6.1.8 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
DiskCatalogMaker 7.2.7 - Catalog your di...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast Finder-like intuitive look and feel Super-fast search algorithm Can compress catalog data for... Read more

Latest Forum Discussions

See All

Amazing Katamari Damacy guide - beginner...
Amazing Katamari Damacy brings the bizarro world of the original games to mobile and shifts them into an endless format that's just as addictive as the PlayStation entries. Your goal is still to roll as much random stuff as you possibly can, though... | Read more »
Portal Knights guide - crafting tips and...
In Portal Knights, you're only as strong as the items you have at your disposal. This sandbox adventure is all about crafting and building up the next big thing. Whether you're an avid explorer or collector, crafting will likely play a large part... | Read more »
The best deals on the App Store this wee...
A new week means new discounts on the App Store. This week's deals run the gamut of action-adventure titles, puzzle games, and one of the best narrative adventure series out there. If you're looking to fill out your mobile gaming library on a... | Read more »
What you need to know about Animal Cross...
We hope you've been hard at work on collecting all of those holiday items in Animal Crossing: Pocket Camp, because you're about to get a whole new list of fun things to do as the game receives its first big update sometime soon. There are a lot of... | Read more »
Reigns: Her Majesty guide - how to use e...
Ruling a kingdom isn't easy--doubly so for a queen whose every decision is questioned by the other factions seeking a slice of power. Reigns: Her Majesty builds on the original game's swipey tactics, adding items that you can use to move the story... | Read more »
The best new games we played this week -...
Friday has crept up on us once again, so it's time to honor the best new games we've played over the past few days. This past week was a pretty exciting one, with the debut of lots of beautiful new indies and some familiar faces returning to the... | Read more »
Portal Knights guide- beginner tips and...
Portal Knights is finally making the jump to iOS and Android, and it's already climbing the ranks to become the next big MMO experience on mobile. This sprawling sandbox game will let you pursue any adventure you wish, whether you want to sling... | Read more »
Reigns: Her Majesty guide - how to swipe...
Reigns: Her Majesty is storming the App Store this week, bringing more tinder-esque kingdom building to eager players everywhere. If you've played the original Reigns, you'll know that leading a kingdom is never easy. It's a careful balancing act... | Read more »
Getting Over It (Games)
Getting Over It 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: A game I madeFor a certain kind of person To hurt them. • Climb up an enormous mountain with nothing but a hammer and a pot.•... | Read more »
Reigns: Her Majesty (Games)
Reigns: Her Majesty 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: | Read more »

Price Scanner via MacPrices.net

Apple Watch Series 2, Certified Refurbished,...
Apple has Certified Refurbished Apple Watch Nike+ Series 2s, 42mm Space Gray Aluminum Case with Anthracite/Black Nike Sport Bands, available for $249 (38mm) or $279 (42mm). The 38mm model was out of... Read more
Apple offers Certified Refurbished 2016 12″ R...
Apple has Certified Refurbished 2016 12″ Retina MacBooks available starting at $949. Apple will include a standard one-year warranty with each MacBook, and shipping is free. The following... Read more
B&H drops price on 13″ 256GB MacBook Air...
B&H has the 13″ 1.8GHz/256GB Apple MacBook Air (MQD42LL/A) now on sale for $1079 including free shipping plus NY & NJ sales tax only. Their price is $120 off MSRP, and it’s the lowest price... Read more
Holiday sale: 9″ iPads starting at $299, take...
MacMall has 9″ WiFi iPads on sale for $30 off including free shipping: – 9″ 32GB WiFi iPad: $299 – 9″ 128GB WiFi iPad: $399 Read more
Green Monday deal: 15″ 2.8GHz MacBook Pro on...
B&H Photo has the 15″ 2.8GHz Space Gray MacBook Pro on sale for $250 off MSRP for today only as part of their Green Monday/Holiday sale. Shipping is free, and B&H charges sales tax for NY... Read more
Green Monday sale: B&H offers 12″ Apple i...
B&H Photo has 12″ iPad Pros on sale for up to $150 off MSRP as part of their Green Monday/Holiday sale. Shipping is free, and B&H charges sales tax in NY & NJ only: – 12″ 64GB WiFi iPad... Read more
Holiday deal: 21″ and 27″ Apple iMacs on sale...
MacMall has 2017 21″ and 27″ Apple iMacs on sale for up to $200 off MSRP. Shipping is free: – 21″ 2.3GHz iMac: $999 $100 off MSRP – 21″ 3.0GHz iMac: $1199 $100 off MSRP – 21″ 3.4GHz iMac: $1379 $120... Read more
Holiday deal: Apple Mac minis for up to $150...
MacMall has Mac minis on sale for up to $100 off MSRP, each including free shipping: – 1.4GHz Mac mini: $399 $100 off MSRP – 2.6GHz Mac mini: $599 $100 off MSRP – 2.8GHz Mac mini: $949 $50 off MSRP... Read more
Beats by Dr. Dre – BeatsX Earphones on sale f...
Best Buy has BeatsX Earphones on sale for $109, $40 off, on their online store. Sale price for online orders only. Choose free store pickup, if available, or choose free shipping. Read more
10″ 64GB WiFi Apple iPad Pros on sale for $59...
MacMall has 10.5″ 64GB Apple iPad Pros on sale for $599 including free shipping. That’s $50 off MSRP and among the lowest prices available for these iPads from any Apple reseller. Read more

Jobs Board

QA Automation Engineer, *Apple* Pay - Apple...
# QA Automation Engineer, Apple Pay Job Number: 113202642 Santa Clara Valley, California, United States Posted: 11-Dec-2017 Weekly Hours: 40.00 **Job Summary** At Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, 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
*Apple* Retail - Multiple Positions - Apple,...
Job Description:SalesSpecialist - Retail Customer Service and SalesTransform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*Apple* Information Security - Security Data...
# Apple Information Security - Security Data Analyst Job Number: 113119545 Austin, Texas, United States Posted: 10-Nov-2017 Weekly Hours: 40.00 **Job Summary** This Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.