Dec 96 Challenge
 Volume Number: 12 Issue Number: 12 Column Tag: Programmer’s Challenge

# Programmer’s Challenge

by Bob Boonstra

## Tangrams

The Challenge this month is to write code that will solve a tangram puzzle - that is, reassemble a two-dimensional shape that has been cut into a number of smaller shapes. The classic tangram consists of five right triangles of three different sizes, a square, and a rhomboid that are to be reassembled into a larger square. Your code will have to deal with a more general set of polygons. The prototype for the code you should write is:

```#define kMaxVertices 10

typedef struct MyVertex {
float  h;/* horizontal coordinate of vertex */
float  v;/* vertical coordinate of vertex */
} MyVertex;

typedef struct MyPolygon {
long     numVertices;/* number of vertices in polygon */
MyVertex vertex[kMaxVertices];        /* vertex coordinates */
} MyPolygon;

typedef struct MyTransform {
float     rotateClockwise;      /* then rotate polygon clockwise by this many
float     rotateCenterH;   /* around the point with this horiz coordinate */
float     rotateCenterV;   /* and with this vertical coordinate */
float     translateH;    /* then translate horizontally by this amount */
float  translateV;/* then translate vertically by this amount */
Boolean doFilp;                /* only perform flip if this is TRUE */
} MyTransform;

void SolveTangram(
MyPolygon     *theShape,          /* shape to be reassembled */
long     numHoles,            /* shape has this many holes (>=0) */
MyPolygon     *theHoles[],  /* pointers to polygons that form the holes */
long     numPieces,   /* number of pieces to reassemble */
MyPolygon     *thePieces[],      /* shape and position of pieces to reassemble */
MyTransform *theXForms[]      /* reassembly transforms corresponding to  thePieces */
);

```

The shape to be reassembled is a polygon pointed to by theShape, except that the reassembled shape may have some holes in it. The number of holes, which might be zero, is provided by numHoles, and the shape of the i-th hole is a polygon pointed to by theHoles[i]. You are to reassemble theShape using numPieces polygons pointed to by thePieces[]. For each piece, you should transform it to its correct position by optionally flipping it about a vertical axis, rotating it, and translating it, in that order. For the j-th piece, you should store the required transformation in the structure pointed to by theXForms[j]. Set doFilp to FALSE if no flip is needed, otherwise set doFilp to TRUE to flip the horizontal coordinates about the vertical axis with horizontal coordinate flipH. Set rotateClockwise to the number of radians that the piece should be rotated about the point (rotateCenterH, rotateCenterV). Finally, set translateH and translateV to the amount that the piece should be moved in the horizontal and vertical directions, respectively.

Calculations should be accurate to .00001, meaning that when I apply your transformations using the sin() and cos() library functions, the resulting positions should agree with theShape to within that accuracy.

All of the polygons will be legal polygons - no edge formed by a pair of adjacent vertices will intersect any other edge in the same polygon except at a vertex. The last vertex in each polygon connects to the first vertex (i.e., a square will have four vertices, not a fifth that is the same as the first). All of theHoles in the shape to be reassembled will be strictly inside theShape, not intersecting the edges. No hole will intersect any other hole. You may allocate up to 10MB of memory for your own use, provided you deallocate any allocated memory prior to returning.

This will be a native PowerPC Challenge, using the latest CodeWarrior environment. Solutions may be coded in C, C++, or Pascal. The winner will be the solution that solves my set of test tangrams in the shortest amount of time. And thanks go out to Ernst Munter for suggesting this Challenge - he wins two contest points for the suggestion.

## Two Months Ago Winner

Congratulations to... Well, that is what you would normally read in this part of the column. Alas, the realities of publication deadlines have forced us to make a change in when we publish the winning solution. Perhaps an example of the publishing schedule for this, the December issue which ships in mid-November, would help me explain. Most of the articles for this issue were due to the editorial staff on September 23. Now, if that seems like a lot of lead time to you, it does to me also. However, people who know a lot more about publishing than I do assure me that This Is The Way It Is (e.g., most monthlies have 4-6 month lead times). I believe them - what does a software guy know about publishing deadlines anyway?

Well, I know enough simple arithmetic to realize that it is difficult to include a solution submitted on October 1 in an article due on September 23. The publishers, being just as good at arithmetic, also figured this out, so they have always given me a little extra time to write the Challenge column. That presented the magazine with a Challenge of its own, in that the Challenge column is very unpredictable in length, making magazine layout difficult.

We always try to guess how long the column is going to be, but that means guessing how long the winning solutions are going to be. Sometimes the solutions do not cooperate by being predictable in length. The Challenge deadlines (mine, not yours) kept creeping toward the 1st-of-the-month solution submission deadline. Sometimes there was only one day to compile the solutions, score them, select the winner, and write the column. Sometimes that one day was a day when that Real Job got in the way. (That’s right kids, you can’t make a living writing the Programmer’s Challenge column.) Soooo, in undeniable recognition of publishing reality and our continued goal of improving the magazine, we have reluctantly decided that we need to publish the winning solution three months after we publish the puzzle, instead of two. That is why you are reading this explanation instead of a description of the winning solution to the DNA Match Challenge.

Seriously though, this change will provide me with a more reasonable amount of time to analyze submitted solutions and hopefully point out more interesting and useful features of competitive solutions. For Challenge contestants, we will be announcing the identity of the winner on the CHALLENGE email list at approximately the time that we would have published under the previous arrangement. We hope that this change, in addition to restoring some sanity to the publishing schedule, will allow us to produce a more informative and interesting column. See you next month.

Community Search:
MacTech Search:

Time Out 2.4 - Break reminder tool with...
Time Out helps remind you to take work breaks throughout the day. It has two kinds of breaks: a "Normal" break, typically for 10 minutes after 50 minutes of work, so you can move about and relax,... Read more
Smultron 10.1.3 - Easy-to-use, powerful...
Smultron 10 is an elegant and powerful text editor that is easy to use. You can use Smultron 10 to create or edit any text document. Everything from a web page, a note or a script to any single piece... Read more
Tor Browser Bundle 7.5.2 - Anonymize Web...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
Yummy FTP Pro 2.0.3 - \$29.99
Yummy FTP Pro is an advanced Mac file transfer app which provides a full-featured professional toolkit combined with blazing speeds and impeccable reliability, so whether you want to transfer a few... Read more
BetterTouchTool 2.412 - 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
Monosnap 3.4.11 - Versatile screenshot u...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
BetterTouchTool 2.412 - 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
Tor Browser Bundle 7.5.2 - Anonymize Web...
The Tor Browser Bundle is an easy-to-use portable package of Tor, Vidalia, Torbutton, and a Firefox fork preconfigured to work together out of the box. It contains a modified copy of Firefox that... Read more
Monosnap 3.4.11 - Versatile screenshot u...
Monosnap lets you capture screenshots, share files, and record video and .gifs! Features Capture Capture full screen, just part of the screen, or a selected window Make your crop area pixel... Read more
Yummy FTP Pro 2.0.3 - \$29.99
Yummy FTP Pro is an advanced Mac file transfer app which provides a full-featured professional toolkit combined with blazing speeds and impeccable reliability, so whether you want to transfer a few... Read more

## Latest Forum Discussions

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 »
Fortnite Will Be Better Than PUBG on Mob...
Before last week, if you asked me which game I prefer between Fortnite Battle Royale and PlayerUnknown’s Battlegrounds (PUBG), I’d choose the latter just about 100% of the time. Now that we know that both games are primed to hit our mobile screens... | Read more »

## Price Scanner via MacPrices.net

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
Walmart has 9.7″ Apple iPads on sale for \$50-\$80 off MSRP for a limited time. Sale prices are for online orders only, in-store prices may vary: – 9″ 32GB iPad: \$249.99 \$80 off – 9″ 128GB iPad: \$379 \$... Read more
Apple resellers offer 27″ 3.4GHz 5K iMac for...
B&H Photo has new 2017 27″ 3.4GHz iMacs on sale for \$200 off MSRP. Shipping is free, and B&H charges sales tax for NY & NJ residents only: – 27″ 3.4GHz iMac (MNE92LL/A): \$1599.99 \$200 off... Read more
Certified Refurbished 21″ & 27″ iMacs ava...
Apple has a full line of Certified Refurbished iMacs available for up to \$350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free. The following models are available: – 27... Read more

## Jobs Board

*Apple* Solutions Consultant - Apple (United...
# Apple Solutions Consultant Job Number: 113587340 Hialeah, Florida, United States Posted: 12-Mar-2018 Weekly Hours: 40.00 **Job Summary** Are you passionate about Read more
*Apple* Watch HW Engineering Program Special...
# Apple Watch HW Engineering Program Specialist Job Number: 113466877 Santa Clara Valley, California, United States Posted: 12-Mar-2018 Weekly Hours: 40.00 **Job Read more
*Apple* Technical Specialist - Apple, Inc. (...
…customers purchase our products, you're the one who helps them get more out of their new Apple technology. Your day in the Apple Store is filled with a range of Read more
*Apple* Information Security Project Manager...
# Apple Information Security Project Manager Job Number: 113440724 Santa Clara Valley, California, United States Posted: 15-Mar-2018 Weekly Hours: 40.00 **Job Read more
Senior Linus Systems Engineer, *Apple* Pay...
# Senior Linus Systems Engineer, Apple Pay Job Number: 113584532 Santa Clara Valley, California, United States Posted: 13-Mar-2018 Weekly Hours: 40.00 **Job Read more