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
} 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
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:

Network Radar is an advanced network scanning and managing tool. Featuring an easy-to-use and streamlined design, the all-new Network Radar 2 has been engineered from the ground up as a modern Mac... Read more
Printopia 3.0.8 - Share Mac printers wit...
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
ForkLift 3.2.1 - Powerful file manager:...
ForkLift is a powerful file manager and ferociously fast FTP client clothed in a clean and versatile UI that offers the combination of absolute simplicity and raw power expected from a well-executed... Read more
BetterTouchTool 2.417 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Little Snitch gives you control over your private outgoing data. Track background activity As soon as your computer connects to the Internet, applications often have permission to send any... Read more
Google Chrome 65.0.3325.181 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
TeamViewer 13.1.2991 - Establish remote...
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 non... Read more
Printopia 3.0.8 - Share Mac printers wit...
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
BetterTouchTool 2.417 - Customize multi-...
BetterTouchTool adds many new, fully customizable gestures to the Magic Mouse, Multi-Touch MacBook trackpad, and Magic Trackpad. These gestures are customizable: Magic Mouse: Pinch in / out (zoom... Read more
Mellel 4.1.0 - The word processor for sc...
Mellel is the leading word processor for OS X and has been widely considered the industry standard for long form documents since its inception. Mellel focuses on writers and scholars for technical... Read more

Latest Forum Discussions

Destiny meets its mobile match - Everyth...
Shadowgun Legends is the latest game in the Shadowgun series, and it's taking the franchise in some interesting new directions. Which is good news. The even better news is that it's coming out tomorrow, so if you didn't make it into the beta you... | Read more »
How PUBG, Fortnite, and the battle royal...
The history of the battle royale genre isn't a long one. While the nascent parts of the experience have existed ever since players first started killing one another online, it's really only in the past six years that the genre has coalesced into... | Read more »
Around the Empire: What have you missed...
Oh hi nice reader, and thanks for popping in to check out our weekly round-up of all the stuff that you might have missed across the Steel Media network. Yeah, that's right, it's a big ol' network. Obviously 148Apps is the best, but there are some... | Read more »
All the best games on sale for iPhone an...
It might not have been the greatest week for new releases on the App Store, but don't let that get you down, because there are some truly incredible games on sale for iPhone and iPad right now. Seriously, you could buy anything on this list and I... | Read more »
Everything You Need to Know About The Fo...
In just over a week, Epic Games has made a flurry of announcements. First, they revealed that Fortnite—their ultra-popular PUBG competitor—is coming to mobile. This was followed by brief sign-up period for interested beta testers before sending out... | Read more »
The best games that came out for iPhone...
It's not been the best week for games on the App Store. There are a few decent ones here and there, but nothing that's really going to make you throw down what you're doing and run to the nearest WiFi hotspot in order to download it. That's not to... | Read more »
Death Coming (Games)
Death Coming 1.1.1.536 Device: iOS Universal Category: Games Price: \$1.99, Version: 1.1.1.536 (iTunes) Description: --- Background Story ---You Died. Pure and simple, but death was not the end. You have become an agent of Death: a... | Read more »
Hints, tips, and tricks for Empires and...
Empires and Puzzles is a slick match-stuff RPG that mixes in a bunch of city-building aspects to keep things fresh. And it's currently the Game of the Day over on the App Store. So, if you're picking it up for the first time today, we thought it'd... | Read more »
What You Need to Know About Sam Barlow’s...
Sam Barlow’s follow up to Her Story is #WarGames, an interactive video series that reimagines the 1983 film WarGames in a more present day context. It’s not exactly a game, but it’s definitely still interesting. Here are the top things you should... | Read more »
Pixel Plex Guide - How to Build Better T...
Pixel Plex is the latest city builder that has come to the App Store, and it takes a pretty different tact than the ones that came before it. Instead of being in charge of your own city by yourself, you have to work together with other players to... | Read more »

Price Scanner via MacPrices.net

Back in stock! Apple’s full line of Certified...
Save \$300-\$300 on the purchase of a 2017 13″ MacBook Pro today with Certified Refurbished models at Apple. Apple’s refurbished prices are the lowest available for each model from any reseller. A... Read more
Back in stock: 13-inch 2.5GHz MacBook Pro (Ce...
Apple has Certified Refurbished 13″ 2.5GHz MacBook Pros (MD101LL/A) available for \$829, or \$270 off original MSRP. Apple’s one-year warranty is standard, and shipping is free: – 13″ 2.5GHz MacBook... Read more
Apple restocks Certified Refurbished 2017 13″...
Apple has Certified Refurbished 2017 13″ MacBook Airs available starting at \$849. An Apple one-year warranty is included with each MacBook, and shipping is free: – 13″ 1.8GHz/8GB/128GB MacBook Air (... Read more
8-Core iMac Pro on sale for \$4699, save \$300
Amazon has the 8-core iMac Pro on sale for \$4699 including free shipping. Their price is \$300 off MSRP, and it’s the currently lowest price available for an iMac Pro. For the latest up-to-date prices... Read more
10″ 512GB WiFi iPad Pros on sale for \$849, sa...
B&H Photo has Space Gray and Rose Gold 10.5″ 512GB WiFi iPad Pros on sale for \$849. Their price is \$150 off MSRP, and it’s the lowest price available for these models, new, from any Apple... Read more
MacBook Pro sale! B&H drops prices on new...
B&H Photo has dropped prices on new 2017 13″ MacBook Pros, with models now on sale for up to \$200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only. Their... Read more
13″ MacBook Airs on sale for \$100-\$150 off MS...
B&H Photo has 13″ MacBook Airs on sale for \$100-\$150 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 13″ 1.8GHz/128GB MacBook Air (MQD32LL/A): \$899, \$... Read more
Huge iMac sale! Apple reseller now offering 2...
B&H Photo has new 2017 21″ & 27″ iMacs on sale today for up to \$300 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.8GHz iMac (MNED2LL/A): \$... Read more
Sale! 1.4GHz Mac mini for \$399, \$100 off MSRP
B&H Photo has the 1.4GHz Mac mini on sale for \$399 for a limited time. Their price is \$100 off MSRP, and it’s the lowest price available for a mini from any Apple reseller: – 1.4GHz Mac mini (... Read more
Sale of the year continues as Apple resellers...
Adorama has new 2017 15″ MacBook Pros on sale for \$250-\$300 off MSRP. Shipping is free, and Adorama charges sales tax in NJ and NY only: – 15″ 2.8GHz Touch Bar MacBook Pro Space Gray (MPTR2LL/A): \$... Read more

Jobs Board

*Apple* Genius - Technical Customer Service...
Job Description:Job SummaryAs a Genius at the Apple Store, you maintain customers' trust in Apple as the skilled technical customer service expert, Read more