TweetFollow Us on Twitter

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     flipH;         /* optionally flip polygon about this horiz coordinate */
    float     rotateClockwise;      /* then rotate polygon clockwise by this many                                        
    radians */
    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.


 
AAPL
$111.16
Apple Inc.
+1.75
MSFT
$47.05
Microsoft Corpora
+1.31
GOOG
$510.51
Google Inc.
+5.62

MacTech Search:
Community Search:

Software Updates via MacUpdate

BBEdit 11.0.2 - Powerful text and HTML e...
BBEdit is the leading professional HTML and text editor for the Mac. Specifically crafted in response to the needs of Web authors and software developers, this award-winning product provides a... Read more
ExpanDrive 4.2.1 - Access cloud storage...
ExpanDrive builds cloud storage in every application, acts just like a USB drive plugged into your Mac. With ExpanDrive, you can securely access any remote file server directly from the Finder or... Read more
Adobe After Effects CC 2014 13.2 - Creat...
After Effects CC 2014 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous After Effects customer). After Effects CS6 is still available... Read more
Command-C 1.1.7 - Clipboard sharing tool...
Command-C is a revolutionary app which makes easy to share your clipboard between iOS and OS X using your local WiFi network, even if the app is not currently opened. Copy anything (text, pictures,... Read more
Tidy Up 4.0.2 - Find duplicate files and...
Tidy Up is a complete duplicate finder and disk-tidiness utility. With Tidy Up you can search for duplicate files and packages by the owner application, content, type, creator, extension, time... Read more
Typinator 6.3 - Speedy and reliable text...
Typinator turbo-charges your typing productivity. Type a little. Typinator does the rest. We've all faced projects that require repetitive typing tasks. With Typinator, you can store commonly used... Read more
GraphicConverter 9.5 - Graphics editor w...
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Toast Titanium 12.0.1 - The ultimate med...
Toast Titanium goes way beyond the very basic burning in the Mac OS and iLife software, and sets the standard for burning CDs, DVDs, and now Blu-ray discs on the Mac. Create superior sounding audio... Read more
QuickBooks 2015 16.0.2.1422 R3 - Financi...
Save 20% on QuickBooks Pro for Mac today through this special discount link QuickBooks Pro 2013 helps you manage your business easily and efficiently. Organize your finances all in one place, track... Read more
Remotix 3.0.6 - Access all your computer...
Remotix is a fast and powerful application to easily access multiple Macs (and PCs) from your own Mac. Features: Complete Apple Screen Sharing support - including Mac OS X login, clipboard... Read more

Latest Forum Discussions

See All

Brothers in Arms 3: Sons of War Review
Brothers in Arms 3: Sons of War Review By Jennifer Allen on December 18th, 2014 Our Rating: :: FUN BUT PUSHYUniversal App - Designed for iPhone and iPad Brothers in Arms 3: Sons of War could be great fun, but its plethora of... | Read more »
The Snow is Falling on the French Countr...
The Snow is Falling on the French Countryside of Carcassonne’s Newest Update Posted by Jessica Fisher on December 18th, 2014 [ permalink ] < | Read more »
Creatures Such As We Review
Creatures Such As We Review By Jennifer Allen on December 18th, 2014 Our Rating: :: INTERESTING DISCUSSIONSUniversal App - Designed for iPhone and iPad Taking a more sedate approach to interactive fiction, Creatures Such As We... | Read more »
Give It Up! (Games)
Give It Up! 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: GIVE IT UP is a rather hard game where you have to assist this cheerful, singing Blob in jumping through 9 different tracks.So far... | Read more »
The Drive : Devil's Run (Games)
The Drive : Devil's Run 1.0 Device: iOS Universal Category: Games Price: $.99, Version: 1.0 (iTunes) Description: ON THE ROAD AGAIN! The Drive - Devil’s Run is classic point to point style racing game that pays homage to the classics... | Read more »
Procreate Pocket (Entertainment)
Procreate Pocket 1.01 Device: iOS iPhone Category: Entertainment Price: $2.99, Version: 1.01 (iTunes) Description: Create - anytime, anywhere. Made by the developers of the award-winning Procreate® for iPad®, Procreate Pocket™ allows... | Read more »
IRON FINGER - Mini Games Championship (...
IRON FINGER - Mini Games Championship 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Quick to play, easy to learn yet hard to master.. TAP, SWIPE & TILT your way through mini games that... | Read more »
Pentaction: Medieval (Games)
Pentaction: Medieval 1.0 Device: iOS Universal Category: Games Price: $1.99, Version: 1.0 (iTunes) Description: Pentaction: Medieval is a turn-based strategy board-game about chance and skill on the battlefield. Take control of your... | Read more »
Hipstify Review
Hipstify Review By Jennifer Allen on December 17th, 2014 Our Rating: :: COOL FILTERSUniversal App - Designed for iPhone and iPad Add filters, quotes, and fancy frames to your images, thanks to Hipstify.   | Read more »
Mighty Smighties Gets Evolve Cards and N...
Mighty Smighties Gets Evolve Cards and New Worlds Posted by Jessica Fisher on December 17th, 2014 [ permalink ] Universal App - Designed for iPhone and iPad | Read more »

Price Scanner via MacPrices.net

KMI MIDI K-Board Great Gift for Amateur &...
The K-Board is a MIDI Nano keyboard for music creation for iPad, Android, And computers; the easiest way to make music with iPads & Android tablets, and Mac, Windows, or Linux computers. Ultra-... Read more
Amazon offers 15-inch 2.2GHz Retina MacBook P...
 Amazon.com has the 15″ 2.2GHz Retina MacBook Pro on sale for $1699 including free shipping. Their price is $300 off MSRP. Stock is limited, so act now if you’re interested. Read more
Holiday sales continue: MacBook Pros for up t...
 B&H Photo has new MacBook Pros on sale for up to $300 off MSRP as part of their Holiday pricing. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1699... Read more
Google Search App For iOS Gets A Major Makeov...
Google has given iOS users an early Christmas present with a substantial update of it’s not-very-often-upgraded Google Search app. Google Search has been my go-to tool for Web searches since it was... Read more
ShopKeep Apple Pay And Chip Card Reader Avail...
ShopKeep, a cloud-based technology provider to more than 10,000 small business owners to manage retail shops and restaurants with iPads, has released its new Apple Pay and chip card reader. This... Read more
Holiday sale! 27-inch 5K iMac for $2299, save...
 B&H Photo has the 27″ 3.5GHz 5K iMac in stock today and on sale for $2299 including free shipping plus NY sales tax only. Their price is $200 off MSRP, and it’s the lowest price available for... Read more
Holiday Sale! 3.7GHz Quad Core Mac Pro availa...
 B&H Photo has the 3.7GHz Quad Core Mac Pro on sale for $2599 including free shipping plus NY sales tax only. Their price is $400 off MSRP, and it’s the lowest price for this model from any... Read more
iPhone 6 Number 3 Canadian Google Search Of 2...
CTVNews.ca reports that Apple’s iPhone 6 was the third highest-trending Google Canada search topic of 2014, exceeded only by Robin Williams largely after his death by suicide in August, and the FIFA... Read more
New iPad mini 3 Counter-Top & Wall Mount...
newMacgadgets has announced new secure all-acrylic displays for the iPad mini 3 (also works fine with the mini 2, last year’s iPad mini With Retina Display, and the original iPad mini). The new iPad... Read more
Holiday sales continue, MacBook Airs for up t...
B&H Photo has 2014 MacBook Airs on sale for up to $120 off MSRP, for a limited time, for the Thanksgiving/Christmas Holiday shopping season. Shipping is free, and B&H charges NY sales tax... 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
*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
*Apple* Retail - Multiple Positions (US) - A...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
*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
Project Manager / Business Analyst, WW *Appl...
…a senior project manager / business analyst to work within our Worldwide Apple Fulfillment Operations and the Business Process Re-engineering team. This role will work Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.