TweetFollow Us on Twitter

Jun 01 Programmers Challenge

Volume Number: 17 (2001)
Issue Number: 06
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

Dots

You have probably played the game Dots before, although perhaps not in quite some time. My memory of the game dates back to childhood, when we played it in the car while on some long trip. Greg Sadetsky suggested that Dots might make an interesting Challenge, and he wins two Challenge points for that suggestion.

The game starts with a piece of paper with a rectangular grid of NxN dots. The game proceeds with two players alternating turns connecting adjacent dots with a line. Two dots are adjacent if they are in the same row and in adjacent columns, or in the same column and in adjacent rows. The object of the game is to take possession of more squares than does your opponent. Each time a player connects dots that form the fourth edge of a square, the player takes possession of that square. A line can complete zero, one, or two squares. When a player completes one or more squares, s/he is entitled to make another move, and to continue making additional moves as long as a square is completed with each move. The game continues until every square has been formed.

The prototype for the code you should write is:

typedef struct Dot {
   short row;      /* row number of dot, 0..boardSize-1 */
   short col;      /* column number of dot, 0..boardSize-1 */
} Dot;

typedef struct DotLine {
   Dot dot1;      /* first dot of a line */
   Dot dot2;      /* second dot of a line */
   /*   legal lines are formed by dots in the same row, in adjacent columns, or in the same column 
   in adjacent rows */
} DotLine;         

void InitDots(
   short boardSize,      /* number of dots per row/col in board */
   Boolean playFirst,    /* true if you play first, false of opponent plays first */
   WindowPtr dotWindow   /* color window where you should draw game results */
);

void OpponentMove(
const DotLine opponentLine   /* line formed by your opponent on previous move */
);

short /* number of lines generated   */ PlayDots(
   DotLine yourLines[]         /* return the lines you form here */
);

void TermDots(void);      /* return any storage you allocated */

Play begins with a call to your InitDots routine, where you are given the size of the game board (boardSize), an indicator of who plays first (playFirst), and a pointer to a CWindow (passed as a WindowPtr because that’s what most toolbox routines expect). In that window, you will be required to display the progress of the game as it proceeds.

When it is your turn to move, your PlayDots routine will be called. Your code should select the most advantageous move and return it in yourLines[0]. If that move forms a square, you can select an additional move, store it in yourLines[1], and continue as long as squares are formed. PlayDots should return the number of moves you made during your turn.

After your opponent has played, your OpponentMove routine will be called one or more times, once for each move made by your opponent. The move will be provided in the opponentLine parameter, for use in display and in updating your data structures.

After each of your moves, and after notification of each opponent move, you should display the move and the updated game state in the dotWindow. The window should also display the number of squares completed by each player. The details of the display are left to you, as long as the display is correct.

When all of the squares have been formed, your TermDots routine will be called. You should deallocate any dynamically allocated memory and perform any other cleanup required.

The winner will be determined by a round-robin or other fair tournament played with multiple board sizes. Scoring is based on minimizing your point total, calculated as the number of squares that your opponent occupies, plus a penalty of 1% for each millisecond your solution takes to execute.

The Challenge prize will be divided between the overall winner and the best scoring entry from a contestant that has not won the Challenge recently.

This will be a native PowerPC Challenge, using the CodeWarrior Pro 6 environment. Solutions may be coded in C, C++, or Pascal.

Three Months Ago Winner

Congratulations to Claes Wihlborg for winning the March DragSort Challenge. The object of this Challenge was to sort a list by dragging items from one position to another, minimizing the cumulative distance that the drag cursor traveled while moving to pick up an item and while dragging it to its new position. Four of the five entries I received sorted my test cases correctly, and three of the four used the same basic algorithm. Claes’ entry, however, did so much more efficiently than the others, earning him the Challenge win.

The winning solution moves down the list and picks up the first out-of-order item, dragging it in the same direction and dropping it before the next in-order item. It then continues scanning the list in the same direction, picking up the next out-of-order item and dropping it were it belongs. When it reaches the end of the list, it reverses direction and does the same thing moving backward. It continues to move up and down the list until all of the items are in the correct order. A straightforward and efficient solution.

I evaluated the entries using six test cases using lists ranging up to 6500 elements. Since the problem was based on a hypothetical Usenet application, most of the test cases were based on lists that were ordered correctly except for some relatively small percentage of the list items.

As the best-placing entry from someone who has not won a Challenge in the past two years, Randy Boring wins a share of this month’s Challenge prize. You don’t need to defeat the Challenge points leaders to claim a part of the prize, so enter the Challenge and win Developer Depot credits!

The table below lists, for each of the solutions submitted, the number of penalty points earned by each entry, the total time in milliseconds, and the number of select and drag position moves used to sort the test cases. It also lists the code size, data size, and programming language used for each entry. 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.

Name Points Time(msecs) Moves
Claes Wihlborg (29) 29026776 180 29026284
Ernst Munter (721) 29026987 706 29026284
Randy Boring (135) 29027737 1456 29026284
Marco Aiello 84384025 4600 84379428
R. O. Incorrect N/A
Name Code Size Data Size Lang
Claes Wihlborg 704 8 C++
Ernst Munter 2380 80 C++
Randy Boring 2212 145 C++
Marco Aiello 1416 28 C++
R. O. 43432 6120 C++

Top Contestants ...

Listed here are the Top Contestants for the Programmer’s Challenge, including everyone who has accumulated 20 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, the number of wins over the past 24 months, and the total number of career Challenge points.

Rank Name Points Wins(24 mo) Total Points(24 mo)
1. Munter, Ernst 294 11 731
2. Rieken, Willeke 87 3 134
3. Saxton, Tom 76 2 185
4. Maurer, Sebastian 68 2 108
5. Taylor, Jonathan 56 2 56
6. Shearer, Rob 55 1 62
7. Wihlborg, Claes 49 2 49

... and the Top Contestants Looking for a Recent Win

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

Rank Name Points(24 mo) Total Points
8. Boring, Randy 39 142
9. Jones, Dennis 12 22
10. Sadetsky, Gregory 12 14
11. Downs, Andrew 12 12
12. Day, Mark 10 30
13. Duga, Brady 10 10
14. Fazekas, Miklos 10 10
15. Flowers, Sue 10 10
16. Strout, Joe 10 10
17. Nicolle, Ludovic 7 55
18. Hala, Ladislav 7 7
19. Miller, Mike 7 7
20. Schotsman, Jan 7 7
21. Widyatama, Yudhi 7 7
22. Heithcock, JG 6 43

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 place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

Here is Claes’ winning DragSort solution:

DragSort.cp
Copyright © 2001
Claes Wihlborg

/*
      The program takes a very simple approach and implements
      bubblesort with alternating sort directions.
*/

#include “DragSort.h”

//—————————————————————————————————- DragSort

long /* numMoves */ DragSort(
   long itemsToSort[],   /* array of items to be sorted */
   long numItemsToSort,  /* number of itemsToSort */
   long startPosition,   /* item initially selected */
   Move sortMoves[]      /* store Moves that sort the array here */
)
{
   Move *nextMove = sortMoves;
   
   long temp, temp2;
   
   long *p, *oldp, *pMin, *pMax, *newMin, *newMax;
         
   pMin = itemsToSort;
   pMax = itemsToSort + numItemsToSort - 1;

// If strartpos <> 0, sweep down

   p = itemsToSort + startPosition;
   while( p > pMin )
   {
      oldp = p—;
      
      if( (temp = *oldp) < *p )
      {
         nextMove->selectPosition = oldp - itemsToSort;
         do
         {
            *oldp = *p;
            oldp = p—;
         }
         while( (p >= pMin) && (temp < *p ) );
         nextMove++->dragToPosition =  oldp - itemsToSort;
         *oldp = temp;
      }
   }
   
// 1:st iteration: sweep once up and once down.
// this iteration puts at least the smallest and the biggest items in place. 

   newMax = 0;
   newMin = 0;
   
   p = pMin;
   while( p < pMax ) //sweep up
   {
      oldp = p++;
      
      if( (temp = *oldp) > (temp2 = *p) )
      {
         nextMove->selectPosition = oldp - itemsToSort;
         do
         {
            *oldp = temp2;
            oldp = p++;
         }
         while( (p <= pMax) && (temp > (temp2 = *p)) );
         nextMove++->dragToPosition =  oldp - itemsToSort;
         *oldp = temp;
         newMax = oldp;
      }
   }
   
   if( !newMax ) return nextMove - sortMoves;
        // no more items in wrong order
   
   pMax = newMax - 1;
   p = pMax;
   while( p > pMin ) //sweep down
   {
      oldp = p—;
      
      if( (temp = *oldp) < (temp2 = *p) )
      {
         nextMove->selectPosition = oldp - itemsToSort;
         do
         {
            *oldp = temp2;
            oldp = p—;
         }
         while( (p >= pMin) && (temp < (temp2 = *p)) );
         nextMove++->dragToPosition =  oldp - itemsToSort;
         *oldp = temp;
         newMin = oldp;
      }
   }
   
   if( !newMin ) return nextMove - sortMoves;
        // no more items in wrong order
   pMin = newMin + 1;

   do //main loop: sweep once up and once down for every iteration
   {
      newMax = 0;
      newMin = 0;
      
      p = pMin;
      
      while( p < pMax ) //sweep up
      {
         oldp = p++;
         
         if( (temp = *oldp) > (temp2 = *p) )
         {
            nextMove->selectPosition = oldp - itemsToSort;
            do
            {
               *oldp = temp2;
               oldp = p++;
            }
            while( temp > (temp2 = *p) );
                //simpler condition as biggest element in correct place
            nextMove++->dragToPosition =  oldp -  itemsToSort;
            *oldp = temp;
            newMax = oldp;
         }
      }
      
      if( !newMax ) break;  // no more items in wrong order
      
      pMax = newMax - 1;
      p = pMax;
      
      while( p > pMin ) //sweep down
      {
         oldp = p—;
         
         if( (temp = *oldp) < (temp2 = *p) )
         {
            nextMove->selectPosition = oldp - itemsToSort;
            do
            {
               *oldp = temp2;
               oldp = p—;
            }
            while( temp < (temp2 = *p) );
                   //simpler condition as smallest element in correct place
            nextMove++->dragToPosition =  oldp - itemsToSort;
            *oldp = temp;
            newMin = oldp;
         }
      }
      
      pMin = newMin + 1;
   }
   while( newMin );

   return nextMove - sortMoves;
}
 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Keynote 10.2 - Apple's presentation...
Easily create gorgeous presentations with the all-new Keynote, featuring powerful yet easy-to-use tools and dazzling effects that will make you a very hard act to follow. The Theme Chooser lets you... Read more
Apple Pages 10.2 - Apple's word pro...
Apple Pages is a powerful word processor that gives you everything you need to create documents that look beautiful. And read beautifully. It lets you work seamlessly between Mac and iOS devices, and... Read more
Safari Technology Preview 14.0.1 - The n...
Safari Technology Preview contains the most recent additions and improvements to WebKit and the latest advances in Safari web technologies. And once installed, you will receive notifications of... Read more
TeamViewer 15.10.5 - Establish remote co...
TeamViewer gives you remote control of any computer or Mac over the Internet within seconds, or can be used for online meetings. Find out why more than 200 million users trust TeamViewer! Free for... Read more
Toast Titanium 19 - The ultimate media t...
Roxio Toast Titanium, the leading DVD burner for Mac, makes burning even better, adding Roxio Secure Burn to protect your files on disc and USB in Mac- or Windows-compatible formats. Get more style... Read more
MacCleanse 9.0 - $29.95
MacCleanse is the product of thousands of hours of intense research and development. It meticulously scans all of the nooks and crannies of a computer for unnecessary junk that can take up huge... Read more
MacPilot 12.0 - $15.96
MacPilot gives you the power of UNIX and the simplicity of Macintosh, which means a phenomenal amount of untapped power in your hands! Use MacPilot to unlock over 1,200 features, and access them all... Read more
NetNewsWire 5.1 - RSS and Atom news read...
NetNewsWire is the best way to keep up with the sites and authors you read most regularly. Let NetNewsWire pull down the latest articles, and read them in a distraction-free and Mac-like way. Native... Read more
FontExplorer X Pro 7.1.3 - Font manageme...
FontExplorer X Pro is optimized for professional use; it's the solution that gives you the power you need to manage all your fonts. Now you can more easily manage, activate and organize your... Read more
DiskCatalogMaker 8.2.5 - 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

A Year of Apple Arcade: The Good, The Ba...
Apple Arcade has persisted for just over a year at this point, and although that means I've been busy ranking and re-ranking every game on the service for just about as long, I haven't done much reflection on the service as a whole. [Read more] | Read more »
Animal Restaurant anniversary event team...
Animal idle simulator Animal Restaurant is celebrating its first-year anniversary with a crossover event with popular YouTube series Aaron’s Animals. [Read more] | Read more »
Raziel: Dungeon Arena is a hack 'n...
Raziel: Dungeon Arena is available now on mobile and will appeal to fans of both comic books and old school dungeon crawlers. Not only will you hack 'n' slash your way through mobs of enemies but there's also fully-narrated animated comic to enjoy... | Read more »
Steam Link Spotlight - Hades
Steam Link Spotlight is a feature where we look at PC games that play exceptionally well using the Steam Link app. Our last entry was on Disco Elysium. Read about how it plays using Steam Link over here. | Read more »
Microsoft has acquired ZeniMax Media and...
In the latest of a series of blockbuster moves, Microsoft has now acquired Zenimax Media and its subsidiary, Bethesda Softworks, for $7.5 billion. [Read more] | Read more »
Infinity Mechs is an upcoming idle game...
Indie developer SkullStar studio has announced an upcoming idle mech game called Infinity Mechs. It draws inspiration from the mobile game Iron Saga and has been officially licensed by Game Duchy. It's set to launch for both iOS and Android on... | Read more »
PUBG Mobile Lite's latest update se...
PUBG Mobile Lite, the streamlined version of the popular battle royale that's designed to work on less powerful devices, sees the return of a popular game variant today, Survive Till Dawn mode. It arrives as part of the 0.19.0 content update. [... | Read more »
Matchy Catch, Jyamma Games’ new hyper-ca...
Matchy Catch is a new hyper-casual puzzler from Jyamma Games, the Italian studio behind the Pong-inspired puzzle-adventure Hi-Ball Rush. It’s only the developer’s second game for iOS and Android devices, but it promises to be every bit as fun and... | Read more »
Among Us! Imposter Guide - How to be a s...
Among Us! continues to be getting a lot of play in these parts, and since our first guide we've learned a thing or two about the game. This is especially true regarding the imposter role, as its a relatively rare opportunity that we've now put... | Read more »
Paladin's Story is an upcoming fant...
Paladin's Story is an upcoming fantasy RPG with an off-kilter sense of humour that's heading for iOS and Android. It will officially launch for both on September 16th though the game is already available on Google Play in Early Access. [Read more... | Read more »

Price Scanner via MacPrices.net

Today on Woot: Apple refurbished 16″ MacBook...
Amazon-owned Woot has Apple refurbished 16″ MacBook Pros available today for up to $605 off the cost of new models. Shipping is free for Prime members: – 16″ 6-Core MacBook Pros: $1874.99 $525 off... Read more
Apple offers last year’s iMacs for as little...
Apple has dropped prices on last year’s 21″ iMacs, Certified Refurbished, by up to $240 off the original cost of new models. Apple’s one-year warranty is standard, shipping is free, and each iMac... Read more
Get last year’s 32GB iPad for only $279 today...
Amazon has dropped prices on clearance 2019 Silver 32GB WiFi Apple iPads by $50 to $279 shipped. That’s the cheapest price available for a new 10.2″ iPad from any Apple reseller. Act now if you’re... Read more
New Apple Watch Series 6 and SE models now on...
Amazon is the first Apple reseller to offer the new Apple Watch Series 6 and Apple Watch SE models at discounted sale prices. These are the same Watches sold by Apple in their retail and online... Read more
The cheapest Macs are back in stock today at...
Apple has restocked clearance, previous-generation, Certified Refurbished Mac minis starting at only $599. Each mini comes with free shipping plus Apple’s standard one-year warranty. These are the... Read more
Sale! Amazon has 2020 13″ 2.0GHz MacBook Pros...
Amazon has 2020 13″ MacBook Pros with 10th generation Intel CPUs back in stock on sale again today for $150-$200 off Apple’s MSRP. Shipping is free. Be sure to purchase the MacBook Pro from Amazon,... Read more
Base 13″ 1.4GHz Apple MacBook Pros on sale fo...
Apple reseller Expercom is offering a $65-$75 discount on new 2020 13″ 1.4GHz MacBook Pros, depending on configuration. Shipping is free. Expercom estimates shipping in 3-5 days, as stock of Apple’s... Read more
Price drop! Get a 44mm Apple Watch Series 5 G...
Amazon has dropped their price on the 44mm Apple Watch Series 5 GPS + Cellular by $100 to $429 shipped. That’s $100 off Apple’s original MSRP for this model. For the latest prices and sales, see our... Read more
Verizon offers $200 discount on new Apple Wat...
Verizon will take up to $200 off the purchase of a new GPS + Cellular Apple Watch Series 6 or Apple Watch SE with select trade-in and the purchase of a new iPhone with service. The fine print: “Get... Read more
Verizon offers $250 discount on new 8th gener...
Verizon will take up to $250 off the price of an 8th generation 2020 Apple Cellular iPad with select trade-ins and a new iPhone purchase. Plus get Apple News+ free for 6 months. The fine print: “Save... Read more

Jobs Board

Security Officer ($23.00/Hourly) - *Apple*...
**Security Officer \($23\.00/Hourly\) \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated Read more
Product Manager, *Apple* Commercial Sales -...
Product Manager, Apple Commercial Sales Austin, TX, US Requisition Number:77652 As an Apple Product Manager for the Commercial Sales team at Insight, you Read more
Security Officer ($23.00/Hourly) - *Apple*...
**Security Officer \($23\.00/Hourly\) \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated Read more
Security Officer ($23.00/Hourly) - *Apple*...
**Security Officer \($23\.00/Hourly\) \- Apple Store** **Description** About NMS Built on a culture of safety and integrity, NMSdelivers award\-winning, integrated Read more
Platform - Workplace Eng - *Apple* Enterpri...
MORE ABOUT THIS JOB We are looking for an Apple Platform Engineer who will bring a unique engineering skill set, support, clarity, organization and above all else, Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.