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

Apple Pro Video Formats 2.0.2 - Updates...
Apple Pro Video Formats brings updates to Apple's professional-level codes for Final Cut Pro X, Motion 5, and Compressor 4. Version 2.0.2: Includes support for the following professional video codecs... Read more
Apple Final Cut Pro X 10.2.2 - Professio...
Apple Final Cut Pro X is a professional video editing solution.Completely redesigned from the ground up, Final Cut Pro adds extraordinary speed, quality, and flexibility to every part of the post-... Read more
Apple Compressor 4.2.1 - Adds power and...
Compressor adds power and flexibility to Final Cut Pro X export. Customize output settings, work faster with distributed encoding, and tap into a comprehensive set of delivery features. Powerful... Read more
Apple Motion 5.2.2 - Create and customiz...
Apple Motion is designed for video editors, Motion 5 lets you customize Final Cut Pro titles, transitions, and effects. Or create your own dazzling animations in 2D or 3D space, with real-time... Read more
A Better Finder Rename 10.00b1 - File, p...
A Better Finder Rename is the most complete renaming solution available on the market today. That's why, since 1996, tens of thousands of hobbyists, professionals and businesses depend on A Better... Read more
CrossOver 14.1.6 - Run Windows apps on y...
CrossOver can get your Windows productivity applications and PC games up and running on your Mac quickly and easily. CrossOver runs the Windows software that you need on Mac at home, in the office,... Read more
Printopia 2.1.14 - Share Mac printers wi...
Run Printopia on your Mac to share its printers to any capable iPhone, iPad or iPod Touch. Printopia will also add virtual printers, allowing you to save print-outs to your Mac and send to apps.... Read more
Google Drive 1.24 - File backup and shar...
Google Drive is a place where you can create, share, collaborate, and keep all of your stuff. Whether you're working with a friend on a joint research project, planning a wedding with your fiancé, or... Read more
Chromium 45.0.2454.85 - Fast and stable...
Chromium is an open-source browser project that aims to build a safer, faster, and more stable way for all Internet users to experience the web. Version 45.0.2454.85: Note: Does not contain the "... Read more
OmniFocus 2.2.5 - GTD task manager with...
OmniFocus helps you manage your tasks the way that you want, freeing you to focus your attention on the things that matter to you most. Capturing tasks and ideas is always a keyboard shortcut away in... Read more

Zen Brush 2 (Entertainment)
Zen Brush 2 1.0 Device: iOS Universal Category: Entertainment Price: $2.99, Version: 1.0 (iTunes) Description: Zen Brush 2 is a drawing app focused on the strong yet beautiful feel of the East Asian ink brush. | Read more »
NetNewsWire (News)
NetNewsWire 4.0.0 Device: iOS iPhone Category: News Price: $3.99, Version: 4.0.0 (iTunes) Description: Follow the Web NetNewsWire 4, completely written from the ground up for iPhone. NetNewsWire is the best way to keep up with the... | Read more »
Huzzah! Farming Simulator 16 Supports Cl...
As though it weren't difficult enough to resist the siren call of Farming Simulator 16, now it's been updated with cloud saves - so you can jump between devices without missing any of that precious crop-harvesting time. [Read more] | Read more »
Don't Starve: Pocket Edition Finall...
I've made no effort to hide my enjoyment of Don't Starve: Pocket Edition, but I will admit I was a tiny bit disappointed that it was only available for the iPad. Well nuts to that, because Klei Entertainment has made it universal! [Read more] | Read more »
Goat Simulator Wasn't Enough? Then...
If you just didn't get enough goat in Goat Simulator - or if you've been wanting to play a simulated MMO as a microwave - then you're in luck! Goat Simulator MMO Simulator is out now, and it's a game about simulated goats in simulated MMOs. Plus... | Read more »
You Can Play Madfinger Games' Unkil...
Madfinger Games - probably best known for the Dead Trigger series - has officially launched their newest zombie shooter (that isn't called Dead Trigger), named Unkilled. [Read more] | Read more »
KORG iELECTRIBE for iPhone (Music)
KORG iELECTRIBE for iPhone 1.0.1 Device: iOS iPhone Category: Music Price: $9.99, Version: 1.0.1 (iTunes) Description: ** 50% OFF Special Launch Sale - For a Limited Time **The ELECTRIBE reborn in an even smaller form A full-fledged... | Read more »
Toca Life: City Just Got a Bunch of New...
Toca Life: City is Toca Boca's most popular app (number 1 in 47 different countries, apparently), and it's just had an update that adds a bunch of new content. [Read more] | Read more »
My Country 3D is More About Cities than...
My Country 3D is an upcoming city builder from Game Insight that looks pretty decent - although the name seems a tad out of whack for a city builder. Ah well, it is what it is. [Read more] | Read more »
I am Bread (Games)
I am Bread 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: ‘I am Bread’ is the latest quirky adventure from the creators of 'Surgeon Simulator', Bossa Studios. This isn't the best thing... | Read more »

Price Scanner via MacPrices.net

Near-Office Input Functionality Virtually Any...
Today Logitech introduced the Logitech K380 Multi-Device Bluetooth Keyboard and the Logitech M535 Bluetooth Mouse, giving users the freedom to work on any device, most anywhere. According to... Read more
College Student Deals: Additional $100 off Ma...
Take an additional $100 off all MacBooks and iMacs at Best Buy Online with their College Students Deals Savings, valid through September 4, 2015. Anyone with a valid .EDU email address can take... Read more
2.8GHz Mac mini available for $988, includes...
Adorama has the 2.8GHz Mac mini available for $988, $11 off MSRP, including a free copy of Apple’s 3-Year AppleCare Protection Plan. Shipping is free, and Adorama charges sales tax in NY & NJ... Read more
Will You Buy An iPad Pro? – The ‘Book Mystiqu...
It looks like we may not have to wait much longer to see what finally materializes as a new, larger-panel iPad (Pro/Plus?) Usually reliable Apple product prognosticator KGI Securities analyst Ming-... Read more
eFileCabinet Announces SMB Document Managemen...
Electronic document management (EDM) eFileCabinet, Inc., a hosted solutions provider for small to medium businesses, has announced that its SecureDrawer and eFileCabinet Online services will be... Read more
WaterField Designs Unveils American-Made, All...
San Francisco’s WaterField Designs today unveiled their all-leather Cozmo 2.0 — an elegant attach laptop bag with carefully-designed features to suit any business environment. The Cozmo 2.0 is... Read more
Apple’s 2015 Back to School promotion: Free B...
Purchase a new Mac or iPad at The Apple Store for Education and take up to $300 off MSRP. All teachers, students, and staff of any educational institution qualify for the discount. Shipping is free,... Read more
128GB MacBook Airs on sale for $100 off MSRP,...
B&H Photo has 11″ & 13″ MacBook Airs with 128GB SSDs on sale for $100 off MSRP. Shipping is free, and B&H charges NY sales tax only: - 11″ 1.6GHz/128GB MacBook Air: $799.99, $100 off MSRP... Read more
13-inch 2.5GHz MacBook Pro (refurbished) avai...
The Apple Store has Apple Certified Refurbished 13″ 2.5GHz MacBook Pros available for $829, or $270 off the cost of new models. Apple’s one-year warranty is standard, and shipping is free: - 13″ 2.... Read more
27-inch 3.2GHz iMac on sale for $1679, save $...
B&H Photo has the 27″ 3.2GHz iMac on sale for $1679.99 including free shipping plus NY sales tax only. Their price is $120 off MSRP. Read more

Jobs Board

*Apple* Retail - Multiple Positions (US) - A...
Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, you're also the Read more
Content Partner Engineer - *Apple* TV - App...
**Job Summary** The Apple TV team is looking for an experienced engineer with a passion for delivering first in class home entertainment solutions. The candidate will Read more
*Apple* Desktop Analyst - KDS Staffing (Unit...
…field and consistent professional recruiting achievement. Job Description: Title: Apple Desktop AnalystPosition Type: Full-time PermanentLocation: White Plains, NYHot Read more
*Apple* Retail - Multiple Customer Support P...
Job Description: Customer Support Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the Read more
*Apple* Desktop Analyst - KDS Staffing (Unit...
…field and consistent professional recruiting achievement. Job Description: Title: Apple Desktop AnalystPosition Type: Full-time PermanentLocation: White Plains, NYHot Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.