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

Macs Fan Control 1.5.14 - Monitor and co...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
VueScan 9.7.96 - Scanner software with a...
VueScan is a scanning program that works with most high-quality flatbed and film scanners to produce scans that have excellent color fidelity and color balance. VueScan is easy to use, and has... Read more
FileMaker Pro 19.6.1 - Quickly build cus...
FileMaker Pro is the tool you use to create a custom app. You also use FileMaker Pro to access your app on a computer. Start by importing data from a spreadsheet or using a built-in Starter app to... Read more
Duet 3.1.0.0 - Use your iPad as an exter...
Duet is the first app that allows you to use your iDevice as an extra display for your Mac using the Lightning or 30-pin cable. Note: This app requires a iOS companion app. Release notes were... Read more
Firefox 107.0.1 - Fast, safe Web browser...
Firefox offers a fast, safe Web browsing experience. Browse quickly, securely, and effortlessly. With its industry-leading features, Firefox is the choice of Web development professionals and casual... Read more
War Thunder 2.21.1.91 - Multiplayer war...
In War Thunder, aircraft, attack helicopters, ground forces and naval ships collaborate in realistic competitive battles. You can choose from over 1,500 vehicles and an extensive variety of combat... Read more
Numbers 12.2.1 - Apple's spreadshee...
With Apple Numbers, sophisticated spreadsheets are just the start. The whole sheet is your canvas. Just add dramatic interactive charts, tables, and images that paint a revealing picture of your data... Read more
DEVONthink Pro 3.8.7 - Knowledge base, i...
DEVONthink is DEVONtechnologies' document and information management solution. It supports a large variety of file formats and stores them in a database enhanced by artificial intelligence (AI). Many... Read more
Drive Genius 6.2.3 - $79.00
Drive Genius features a comprehensive Malware Scan. Automate your malware protection. Protect your investment from any threat. The Malware Scan is part of the automated DrivePulse utility. DrivePulse... Read more
VLC Media Player 3.0.18 - Popular multim...
VLC Media Player is a highly portable multimedia player for various audio and video formats (MPEG-1, MPEG-2, MPEG-4, DivX, MP3, OGG, ...) as well as DVDs, VCDs, and various streaming protocols. It... Read more

Latest Forum Discussions

See All

‘Genshin Impact’ Version 3.3 Pre-Install...
Following the reveal of the release date and more for Genshin Impact (Free) version 3.3 ‘All Senses Clear, All Existence Void’, HoYoverse showcased the Genius Invokation TCG that arrives this week in the update. | Read more »
TouchArcade Game of the Week: ‘Sling Min...
The world of PC games has always blown my mind because there’s just SO MUCH stuff out there that it’s not uncommon at all for there to be a game that’s well-liked and well-reviewed, and seemingly quite popular with a solid fanbase, and have it be... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 2nd, 2022. So, today turned out a little quieter than the usual Friday. It was so quiet, in fact, that I decided to pen a few reviews. The Knight Witch, Railbound, and Donut... | Read more »
Blue Archive reveals its latest event st...
Nexon has announced the new update for Blue Archive, under the name of An Unconcealed Heart. Featuring a battle between two academies, the story will follow a group struggling to gain recognition, and will bring three new students to recruit. [... | Read more »
Dead Cells+ Is Out Now on Apple Arcade a...
Following the major update for Dead Cells on iOS and Android a few days ago, Playdigious has brought Dead Cells+ () to Apple Arcade. As an App Store Great, Dead Cells+ includes all prior paid DLC and content updates. It also has exclusive mobile... | Read more »
SwitchArcade Round-Up: ‘Romancing SaGa’,...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 1st, 2022. Wow, December. We’re already at the last month of the year? Phew. I have a lot of work to finish in the next few weeks. As for today, we’ve got a little news, a... | Read more »
‘Railbound’ Update Now Available Adding...
One of our favorite puzzlers released this year is Railbound from Afterburn Games, which hit in early September and earned our Game of the Week recognition for being an absolutely ace logic puzzler. The goal is to place rail pieces down in order to... | Read more »
The Seven Deadly Sins: Grand Cross celeb...
Netmarble Corporation has pulled out all the stops to celebrate the 3 and a half year anniversary of The Seven Deadly Sins: Grand Cross. The Grand Cross 3.5th Year Anniversary the Ultimate One, a rather wordy title, brings with it a brand new... | Read more »
‘Skullgirls Mobile’ Major Update 5.2 Out...
Developer Hidden Variable pushed out a major update for Skullgirls Mobile (Free) a few hours ago. The version 5.2 update brings in Black Dahlia (before the console and PC game), Retakes, XP Treats, free gifts, and more. Since launch, Skullgirls... | Read more »
Out Now: ‘Disgaea 4’, ‘Romancing SaGa: M...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »

Price Scanner via MacPrices.net

Holiday Sale: Apple AirPods Pro for only $199...
Amazon has new 2022 AirPods Pro in stock and on sale for $199.99 shipped as part of their Holiday sale. Their price is $50 off Apple’s MSRP, equaling their Black Friday price, and it’s the lowest... Read more
New Holiday Sale: Apple retailers are offerin...
Several Apple retailers lowered prices on 10.9″ iPad Airs overnight to lows of $100 off MSRP starting at $499. Their prices are the lowest available for iPad Airs anywhere this Holiday season right... Read more
New Holiday sale at Amazon: Take $50 off Appl...
Amazon has Apple’s new 10th-generation iPads in stock and on sale, for the first time, for $50 off MSRP starting at only $399. Their discount applies to all models and all colors. With the discount,... Read more
Holiday Sale: Get an 8.3″ Apple iPad mini for...
Sams Club has 10.9″ 64GB iPad minis on Holiday sale for $80-$100 off MSRP through December 7, 2022. With their discount, prices start at $399 — the cheapest price for a new iPad mini from any of the... Read more
Sams Club Holiday December Event sale: Apple...
Apple AirPods Max headphones are on sale at Sams Club for $110 off MSRP ($439) as part of their December Event sale, ending on December 7, 2022, valid for all colors. Sale price for online orders... Read more
Apple’s 10.2″ 64GB 9th-generation iPads are o...
Sams Club has 9th-generation 64GB iPads on Holiday sale for $60 off MSRP through December 7, 2022. With their discount, prices start at $259 — the cheapest price for a new iPad from any of the Apple... Read more
11″ 128GB WiFi M2 iPad Pro on sale for $749,...
B&H Photo has the new 11″ 128GB WiFi M2-powered iPad Pro (in Space Gray or Silver) on Holiday sale for $749 including free 1-2 day shipping to most US addresses. Their price is $50 off MSRP and... Read more
Find the best Holiday sale price on an iPad u...
We’ve updated our iPad Price Trackers with the latest information on the new 10th-generation iPads, M2-powered iPad Pros, M1 iPad Airs, iPad minis, and 9th generation iPads from Apple’s authorized... Read more
Apple retailers are offering $100-$150 Holida...
Apple retailers have posted their most-recent Holiday sale prices on 13″ MacBook Airs. Take up to $150 off MSRP on M2-powered Airs with these sales with prices starting at only $1099. Free shipping... Read more
Holiday Sale: Apple’s 14″ MacBook Pros with M...
B&H Photo is offering $200-$300 discounts on Apple’s 14″ MacBook Pros with M1 Pro CPUs as part of their Holiday 2022 sale, with prices starting at $1799. Free 1-2 day shipping is available to... Read more

Jobs Board

Support Technician II - *Apple* Support - O...
…problems and acting as a liaison between customers and resolving groups. As an Apple Technical Specialist, you will be supporting many of our popular Apple Read more
*Apple* Electronic Repair Technician - PlanI...
…a highly motivated individual to join our Production Department as an Apple Electronic Repair Technician. The computer repair technician will diagnose, assemble, Read more
Lead Developer - *Apple* tvOS - Rumble (Uni...
…earnings, and positive sentiment About the role: We are looking for a Lead Apple tvOS Developer to join our application engineering team to expand our video centric Read more
Tier 1 Endpoint Engineer - *Apple* - Red Ri...
…Desk on site, at our Client's location, with a focus on support to Apple products. This position will handle technical support requests directly from customers and Read more
Product Manager II - *Apple* - DISH (United...
…you will be doing We seek an ambitious, data-driven thinker to assist the Apple Product Development team as our new Retail Wireless division continues to grow and Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.