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

pwSafe 4.1 - Secure password management...
pwSafe provides simple and secure password management across devices and computers. pwSafe uses iCloud to keep your password databases backed-up and synced between Macs and iOS devices. It is... Read more
Kodi 15.0.rc1 - Powerful media center to...
Kodi (was XBMC) is an award-winning free and open-source (GPL) software media player and entertainment hub that can be installed on Linux, OS X, Windows, iOS, and Android, featuring a 10-foot user... Read more
Coda 2.5.11 - One-window Web development...
Coda is a powerful Web editor that puts everything in one place. An editor. Terminal. CSS. Files. With Coda 2, we went beyond expectations. With loads of new, much-requested features, a few surprises... Read more
Bookends 12.5.7 - Reference management a...
Bookends is a full-featured bibliography/reference and information-management system for students and professionals. Access the power of Bookends directly from Mellel, Nisus Writer Pro, or MS Word (... Read more
Maya 2016 - Professional 3D modeling and...
Maya is an award-winning software and powerful, integrated 3D modeling, animation, visual effects, and rendering solution. Because Maya is based on an open architecture, all your work can be scripted... Read more
RapidWeaver 6.2.3 - Create template-base...
RapidWeaver is a next-generation Web design application to help you easily create professional-looking Web sites in minutes. No knowledge of complex code is required, RapidWeaver will take care of... Read more
MacFamilyTree 7.5.2 - Create and explore...
MacFamilyTree gives genealogy a facelift: it's modern, interactive, incredibly fast, and easy to use. We're convinced that generations of chroniclers would have loved to trade in their genealogy... Read more
Paragraphs 1.0.1 - Writing tool just for...
Paragraphs is an app just for writers. It was built for one thing and one thing only: writing. It gives you everything you need to create brilliant prose and does away with the rest. Everything in... Read more
BlueStacks App Player 0.9.21 - Run Andro...
BlueStacks App Player lets you run your Android apps fast and fullscreen on your Mac. Version 0.9.21: Note: Now requires OS X 10.8 or later running on a 64-bit Intel processor. Initial stable... Read more
Tweetbot 2.0.2 - Popular Twitter client....
Tweetbot is a full-featured OS X Twitter client with a lot of personality. Whether it's the meticulously-crafted interface, sounds and animation, or features like multiple timelines and column views... Read more

Rage of Bahamut is Giving Almost All of...
The App Store isn't what it used to be back in 2012, so it's not unexpected to see some games changing their structures with the times. Now we can add Rage of Bahamut to that list with the recent announcement that the game is severely cutting back... | Read more »
Adventures of Pip (Games)
Adventures of Pip 1.0 Device: iOS iPhone Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ** ONE WEEK ONLY — 66% OFF! *** “Adventures of Pip is a delightful little platformer full of charm, challenge and impeccable... | Read more »
Divide By Sheep - Tips, Tricks, and Stre...
Who would have thought splitting up sheep could be so involved? Anyone who’s played Divide by Sheep, that’s who! While we’re not about to give you complete solutions to everything (because that’s just cheating), we will happily give you some... | Read more »
NaturalMotion and Zynga Have Started Tea...
An official sequel to 2012's CSR Racing is officially on the way, with Zynga and NaturalMotion releasing a short teaser trailer to get everyone excited. Well, as excited as one can get from a trailer with no gameplay footage, anyway. [Read more] | Read more »
Grab a Friend and Pick up Overkill 3, Be...
Overkill 3 is a pretty enjoyable third-person shooter that was sort of begging for some online multiplayer. Fortunately the begging can stop, because its newest update has added an online co-op mode. [Read more] | Read more »
Scanner Pro's Newest Update Adds Au...
Scanner Pro is one of the most popular document scanning apps on iOS, thanks in no small part to its near-constant updates, I'm sure. Now we're up to update number six, and it adds some pretty handy new features. [Read more] | Read more »
Heroki (Games)
Heroki 1.0 Device: iOS Universal Category: Games Price: $7.99, Version: 1.0 (iTunes) Description: CLEAR THE SKIES FOR A NEW HERO!The peaceful sky village of Levantia is in danger! The dastardly Dr. N. Forchin and his accomplice,... | Read more »
Wars of the Roses (Games)
Wars of the Roses 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: | Read more »
TapMon Battle (Games)
TapMon Battle 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: It's time to battle!Tap! Tap! Tap! Try tap a egg to hatch a Tapmon!Do a battle with another tapmons using your hatched tapmons! *... | Read more »
Alchemic Dungeons (Games)
Alchemic Dungeons 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: ### Release Event! ### 2.99$->0.99$ for limited time! ### Roguelike Role Playing Game! ### Alchemic Dungeons is roguelike... | Read more »

Price Scanner via MacPrices.net

Canon PIXMA MG3620 Wireless Inkjet All-in-One...
Canon U.S.A., Inc. has announced the PIXMA MG3620 Wireless (1) Inkjet All-in-One (AIO) printer for high-quality photo and document printing. Built with convenience in mind for the everyday home user... Read more
July 4th Holiday Weekend 13-inch MacBook Pro...
Save up to $150 on the purchase of a new 2015 13″ Retina MacBook Pro at the following resellers this weekend. Shipping is free with each model: 2.7GHz/128GB MSRP $1299 2.7GHz/... Read more
27-inch 3.5GHz 5K iMac on sale for $2149, sav...
Best Buy has the 27″ 3.5GHz 5K iMac on sale for $2149.99. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary. Their price is $... Read more
Apple now offering refurbished 2015 11-inch...
The Apple Store is now offering Apple Certified Refurbished 2015 11″ MacBook Airs as well as 13″ MacBook Airs (the latest models), available for up to $180 off the cost of new models. An Apple one-... Read more
15-inch 2.5GHz Retina MacBook Pro on sale for...
Amazon.com has the 15″ 2.5GHz Retina MacBook Pro on sale for $2274 including free shipping. Their price is $225 off MSRP, and it’s the lowest price available for this model. Read more
Finally Safe To Upgrade To Yosemite’?
The reason I’ve held back from upgrading my MacBook Air from OS X 10.9 Mavericks to 10.10 Yosemite for nearly a year isn’t just procrastination. Among other bugs reported, there have been persistent... Read more
Logo Pop Free Vector Logo Design App For OS X...
128bit Technologies has released of Logo Pop Free 1.2 for Mac OS X, a vector based, full-fledged, logo design app available exclusively on the Mac App Store for the agreeable price of absolutely free... Read more
21-inch 1.4GHz iMac on sale for $999, save $1...
B&H Photo has new 21″ 1.4GHz iMac on sale for $999 including free shipping plus NY sales tax only. Their price is $100 off MSRP. Best Buy has the 21″ 1.4GHz iMac on sale for $999.99 on their... Read more
16GB iPad mini 3 on sale for $339, save $60
B&H Photo has the 16GB iPad mini 3 WiFi on sale for $339 including free shipping plus NY tax only. Their price is $60 off MSRP. Read more
Save up to $40 on iPad Air 2, NY tax only, fr...
B&H Photo has iPad Air 2s on sale for up to $40 off MSRP including free shipping plus NY sales tax only: - 16GB iPad Air 2 WiFi: $489 $10 off - 64GB iPad Air 2 WiFi: $559 $40 off - 128GB iPad Air... Read more

Jobs Board

*Apple* Solutions Consultant - Retail Sales...
**Job Summary** As an Apple Solutions Consultant (ASC) you are the link between our customers and our products. Your role is to drive the Apple business in a retail Read more
Program Manger, WW *Apple* Direct Fulfillme...
**Job Summary** We are seeking a business analyst to work within our Worldwide Apple Direct Fulfillment Operations team. This role will work closely with related program Read more
Project Manager, *Apple* Retail New Store O...
**Job Summary** An Apple Retail New Store Openings & Remodels Project Manager is responsible for successfully managing the openings, remodels, and small works of Read more
Technical Project Manager - *Apple* Pay - A...
**Job Summary** Apple Pay is seeking an experienced technical PM to…manage the on boarding of new merchants for the Apple Pay platform in the US Within this role you Read more
*Apple* Pay- Automation Test Engineer - Appl...
**Job Summary** At Apple , great ideas have a way of becoming great products, services, and customer experiences very quickly. Bring passion and dedication to your job Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.