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

MacCleanse 6.0.5 - $29.95
MacCleanse is the product of thousands of hours of intense research and development. It meticulously scans all of the nooks and crannies of a computer for unnecessary junk that can take up huge... Read more
Smultron 10.0.2 - 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
Capto 1.2.5 - $29.99
Capto (was Voila) is an easy-to-use app that takes capturing, recording, video and image editing to the next level. With an intelligent file manager and quick sharing options, Capto is perfect for... Read more
Cocktail 11.0.1 - General maintenance an...
Cocktail is a general purpose utility for macOS that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Sketch 47.1 - Design app for UX/UI for i...
Sketch is an innovative and fresh look at vector drawing. Its intentionally minimalist design is based upon a drawing space of unlimited size and layers, free of palettes, panels, menus, windows, and... Read more
Slack 2.8.2 - Collaborative communicatio...
Slack is a collaborative communication app that simplifies real-time messaging, archiving, and search for modern working teams. Version 2.8.2: A small release containing nothing but another Electron... Read more
Path Finder 7.6.1 - Powerful, award-winn...
Path Finder makes you a master of file management. Take full control over your file system. Save your time: compare and synchronize folders, view hidden files, use Dual Pane and full keyboard... Read more
Sketch 47.1 - Design app for UX/UI for i...
Sketch is an innovative and fresh look at vector drawing. Its intentionally minimalist design is based upon a drawing space of unlimited size and layers, free of palettes, panels, menus, windows, and... Read more
Cocktail 11.0.1 - General maintenance an...
Cocktail is a general purpose utility for macOS that lets you clean, repair and optimize your Mac. It is a powerful digital toolset that helps hundreds of thousands of Mac users around the world get... Read more
Path Finder 7.6.1 - Powerful, award-winn...
Path Finder makes you a master of file management. Take full control over your file system. Save your time: compare and synchronize folders, view hidden files, use Dual Pane and full keyboard... Read more

Returner 77 (Games)
Returner 77 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Returner 77 is a cinematic space mystery puzzle game. You are in a giant alien spaceship hovering above Earth, after everything... | Read more »
Dune! guide - how to toe the line and ge...
Publisher Voodoo is at it again with an all new high score chaser -- Dune! In this fast-paced arcade game, you have to propel yourself along sand dunes, gaining enough momentum to jump above the line to score points, while making sure you have... | Read more »
The best deals on the App Store this wee...
Happy Tuesday, dear readers. Your favorite part of the week as officially arrived. It's time to take a look at the best deals in games. Things are admittedly a bit sparse, but there are a few diamonds in the rough to see you through if you're... | Read more »
Be the last person standing in Legacy of...
Yoozoo Games’ popular action MMO Legacy of Discord is getting a huge new update to celebrate its first anniversary. Perhaps the biggest change is the addition of an exciting survival mode titled Last Guardian. This new survival mode will pit you... | Read more »
Home Street guide - how to make friends...
From the creators of Food Street comes Home Street, a new simulation game that tasks you with building a social network and designing a beautiful home. It's a bit like The Sims, but you won't have to worry about the daily chores involved (feeding,... | Read more »
Color Ballz guide - how to bounce to the...
Color Ballz is an addictive new arcade title from Ketchapp Studios. It takes old school mechanics from games like Brickles and puts a fun twist on it. Your job? To catch balls with a paddle and send them back into a chute to be carried back to... | Read more »
Q&A: A-33 Studio explains why Combat...
When it comes to mobile FPS, it’s often tricky to get the fundamentals right on a platform lacking a physical controller, large display and hefty RAM. With Combat Squad: Project Wednesday, A-33 Studio bravely took on the challenge of making a... | Read more »
Taichi Panda 3: Dragon Hunter guide - ti...
Taichi Panda 3: Dragon Hunter launched this week to players all over the world. It's a beautiful mobile MMORPG that blends elements of Eastern and Western fantasy. It reminds us of a mix between World of Warcraft and Jade Empire. MMO's can have a... | Read more »
The best new games we played this week -...
Phew. It has been a week, but now it's time to relax, put your feet up, and enjoy some brand new mobile games. It was a bit of slow week, but there's still plenty of new titles to add to your collection. Here are four of our favorites. [Read... | Read more »
Yoink - Improved Drag and Drop (Product...
Yoink - Improved Drag and Drop 1.0 Device: iOS Universal Category: Productivity Price: $2.99, Version: 1.0 (iTunes) Description: Yoink for iPad and iPhone lets you easily and quickly store items you drag, copy or share, for later use... | Read more »

Price Scanner via MacPrices.net

13″ MacBook Pros on sale for up to $120 off M...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for up to $120 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more
15″ MacBook Pros on sale for up to $200 off M...
B&H Photo has 15″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2249, $150... Read more
Roundup of Apple Certified Refurbished iMacs,...
Apple has a full line of Certified Refurbished 2017 21″ and 27″ iMacs available starting at $1019 and ranging up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free... Read more
Sale! 27″ 3.8GHz 5K iMac for $2098, save $201...
Amazon has the 27″ 3.8GHz 5K iMac (MNED2LL/A) on sale today for $2098 including free shipping. Their price is $201 off MSRP, and it’s the lowest price available for this model (Apple’s $1949... Read more
Sale! 10″ Apple WiFi iPad Pros for up to $100...
B&H Photo has 10.5″ WiFi iPad Pros in stock today and on sale for $50-$100 off MSRP. Each iPad includes free shipping, and B&H charges sales tax in NY & NJ only: – 10.5″ 64GB iPad Pro: $... Read more
Apple iMacs on sale for up to $130 off MSRP w...
B&H Photo has 21-inch and 27-inch iMacs in stock and on sale for up to $130 off MSRP including free shipping. B&H charges sales tax in NY & NJ only: – 27″ 3.8GHz iMac (MNED2LL/A): $2179 $... Read more
2017 3.5GHz 6-Core Mac Pro on sale for $2799,...
B&H Photo has the 2017 3.5GHz 6-Core Mac Pro (MD878LL/A) on sale today for $2799 including free shipping plus NY & NJ sales tax only . Their price is $200 off MSRP. Read more
12″ 1.2GHz Space Gray MacBook on sale for $11...
Amazon has the 2017 12″ 1.2GHz Space Gray Retina MacBook on sale for $100 off MSRP. Shipping is free: 12″ 1.2GHz Space Gray MacBook: $1199.99 $100 off MSRP Read more
Bare Bones Software Releases macOS High Sierr...
Bare Bones Software has announced the release and immediate availability of BBEdit 12.0, a significant upgrade to its professional strength text and code editor. BBEdit 12 introduces a new foundation... Read more
Yale Announces Availability of Apple HomeKit-...
Yale Locks & Hardware has announced that Apple HomeKit support for its Assure Lock family is available this month. The new Yale iM1 Network Module, which provides support for the Apple Home app... Read more

Jobs Board

*Apple* News Product Marketing Mgr., Publish...
Job Summary The Apple News Product Marketing Manager will work closely with a cross-functional group to assist in defining and marketing new features and services. Read more
Fraud Analyst, *Apple* Advertising Platform...
Job Summary Apple Ad Platforms has an opportunity to redefine advertising on mobile devices. Apple reaches hundreds of millions of iPhone, iPod touch, and iPad Read more
*Apple* Information Security - Security Data...
Job Summary This role is responsible for helping to strengthen Apple 's information security posture through the identification and curation of security event data. Read more
Lead *Apple* Solution Consultant - Apple In...
…develop a team of diverse partner employees focusing on excellence to deliver the Apple story. Even when you're not present, you will maintain a consistent influence Read more
watchOS Frameworks Engineering Manager, *App...
Job Summary Join the team that is shaping the future of software development for Apple Watch! Apple is looking for an exceptional software engineering leader to Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.