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.


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Kodi 15.0.beta1 - Powerful media center...
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
DiskCatalogMaker 6.4.12 - Catalog your d...
DiskCatalogMaker is a simple disk management tool which catalogs disks. Simple, light-weight, and fast. Finder-like intuitive look and feel. Super-fast search algorithm. Can compress catalog data... Read more
Macs Fan Control 1.3.0.0 - Monitor and c...
Macs Fan Control allows you to monitor and control almost any aspect of your computer's fans, with support for controlling fan speed, temperature sensors pane, menu-bar icon, and autostart with... Read more
Lyn 1.5.11 - Lightweight image browser a...
Lyn is a lightweight and fast image browser and viewer designed for photographers, graphic artists and Web designers. Featuring an extremely versatile and aesthetically pleasing interface, it... Read more
NeoOffice 2014.11 - Mac-tailored, OpenOf...
NeoOffice is a complete office suite for OS X. With NeoOffice, users can view, edit, and save OpenOffice documents, PDF files, and most Microsoft Word, Excel, and PowerPoint documents. NeoOffice 3.x... Read more
LaunchBar 6.4 - Powerful file/URL/email...
LaunchBar is an award-winning productivity utility that offers an amazingly intuitive and efficient way to search and access any kind of information stored on your computer or on the Web. It provides... Read more
Remotix 3.1.4 - 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
DesktopLyrics 2.6.6 - Displays current i...
DesktopLyrics is an application that displays the lyrics of the song currently playing in "iTunes" right on your desktop. The lyrics for the song have to be set in iTunes; DesktopLyrics does nothing... Read more
VOX 2.5.1 - Music player that supports m...
VOX is a beautiful music player that supports many filetypes. The beauty is in its simplicity, yet behind the minimal exterior lies a powerful music player with a ton of features and support for all... Read more
Microsoft Remote Desktop 8.0.18 - Connec...
With Microsoft Remote Desktop, you can connect to a remote PC and your work resources from almost anywhere. Experience the power of Windows with RemoteFX in a Remote Desktop client designed to help... Read more

Biz Builder Delux (Games)
Biz Builder Delux 1.0.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0.0 (iTunes) Description: Ah, there's nothing like the rhythmic bustle of a burgeoning business burg... especially when you're the one building it... | Read more »
Auroch Digital is Bringing Back Games Wo...
| Read more »
Carbo - Handwriting in the Digital Age...
Carbo - Handwriting in the Digital Age 1.0 Device: iOS Universal Category: Productivity Price: $3.99, Version: 1.0 (iTunes) Description: | Read more »
Draggy Dead (Games)
Draggy Dead 1.1 Device: iOS Universal Category: Games Price: $.99, Version: 1.1 (iTunes) Description: Ditch your dead end job and take up a rewarding career in Grave Robbing today!Guide the recently deceased to a fun filled life of... | Read more »
Bad Dinos (Games)
Bad Dinos 1.0.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0.0 (iTunes) Description: | Read more »
The Apple Watch isn't Great as a Fi...
| Read more »
Show the World What You See With Stre.am...
Live broadcasting is getting popular on mobile devices, which is why you can now get Stre.am, by Infinite Takes. [Read more] | Read more »
PhotoTime's 2.1 Update Adds Apple W...
The latest PhotoTime update is adding even more functionality to the handy photo organizing app. Yep, including Apple Watch support. [Read more] | Read more »
Oh My Glob! Adventure Time Puzzle Quest...
Finn and Jake are taking over D3 Go!'s popular puzzle game series in the upcoming Adventure Time Puzzle Quest. [Read more] | Read more »
Earthcore: Shattered Elements - Tips, Tr...
At first glance, Earthcore: Shattered Elements seems like a rather simple card-battling game. Once you’re introduced to skills that will change quite a bit. Even more so once you start to acquire hero cards. But it’s not so complicated that we... | Read more »

Price Scanner via MacPrices.net

Memorial Day Weekend Sale: New 27-inch 3.3GHz...
Best Buy has the new 27″ 3.3GHz 5K iMac on sale for $1899.99 this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary... Read more
OtterBox Maximizes Portability, Productivity...
From the kitchen recipe book to the boarsroom presentation, the OtterBox Agility Tablet System turns tablets into one of the most versatile pieces of handheld technology available. Available now, the... Read more
Launch of New Car App Gallery and Open Develo...
Automatic, a company on a mission to bring the power of the Internet into every car, has announced the launch of the Automatic App Gallery, an app store for nearly every car or truck on the road... Read more
Memorial Day Weekend Sale: 13-inch 1.6GHz Mac...
Best Buy has the new 13″ 1.6GHz/128GB MacBook Air on sale for $849 on their online store this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders... Read more
Memorial Day Weekend Sale: 27-inch 3.5GHz 5K...
Best Buy has the 27″ 3.5GHz 5K iMac on sale for $2099.99 this weekend. Choose free shipping or free local store pickup (if available). Sale price for online orders only, in-store prices may vary.... Read more
Sale! 16GB iPad mini 3 for $349, save $50
B&H Photo has the 16GB iPad mini 3 WiFi on sale for $349 including free shipping plus NY sales tax only. Their price is $50 off MSRP, and it’s the lowest price available for this model. Read more
Price drop on 2014 15-inch Retina MacBook Pro...
B&H Photo has dropped prices on 2014 15″ Retina MacBook Pros by $200. Shipping is free, and B&H charges NY sales tax only: - 15″ 2.2GHz Retina MacBook Pro: $1799.99 save $200 - 15″ 2.5GHz... Read more
With a Mission to Make Mobile Free, Scratch W...
Scratch Wireless, claiming to be the world’s first truly free mobile service, has announced the availability of a new Scratch-enabled Android smartphone, the Coolpad Arise. The smartphone is equipped... Read more
First-Ever Titanium Alloy Curved iPhone 6 Scr...
One of the most common problems with mobile phones is damage to the screens. The slightest drop can cause a dreaded spider web of gashes and cracks in the glass panel surface that can cost $hundreds... Read more
Preorder new 12-inch MacBook, $10 off, save o...
Adorama has new 12″ Retina MacBooks available for preorder for $10 off MSRP including free shipping plus NY & NJ sales tax only. For a limited time, Adorama will include a free Apple USB-C to USB... 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
*Apple* TV Live Streaming Frameworks Test En...
**Job Summary** Work and contribute towards the engineering of Apple 's state-of-the-art products involving video, audio, and graphics in Interactive Media Group (IMG) at 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
Partner Marketing Manager, Merchant- *Apple*...
**Job Summary** The Apple Pay partner marketing team is looking for a marketing manager to develop and drive US marketing programs with our merchant partners. The right 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
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.