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

Drama 2.0.7 - Prototyping, animation...
Drama's handy 3-in-1 functionality uniquely integrates design, animation and prototyping into a single familiar tool. No more frustrating switching between apps or learning new stuff. And by... Read more
Navicat Premium Essentials 15.0.11 - Pro...
Navicat Premium Essentials is a compact version of Navicat which provides basic and necessary features you will need to perform simple administration on a database. It supports the latest features... Read more
Delicious Library 3.9 - Import, browse a...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
ffWorks 2.0.1 - Convert multimedia files...
ffWorks, focused on simplicity, brings a fresh approach to the use of FFmpeg, allowing you to create ultra-high-quality movies without the need to write a single line of code on the command-line.... Read more
TeamViewer 15.3.2682 - 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
Affinity Designer 1.8.1 - Vector graphic...
Affinity Designer is an incredibly accurate vector illustrator that feels fast and at home in the hands of creative professionals. It intuitively combines rock solid and crisp vector art with... Read more
Wireshark 3.2.2 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
Affinity Photo 1.8.1 - Digital editing f...
Affinity Photo - redefines the boundaries for professional photo editing software for the Mac. With a meticulous focus on workflow it offers sophisticated tools for enhancing, editing and retouching... Read more
iShowU Instant 1.3.2 - Full-featured scr...
iShowU Instant gives you real-time screen recording like you've never seen before! It is the fastest, most feature-filled real-time screen capture tool from shinywhitebox yet. All of the features you... Read more
NeoFinder 7.5.1 - Catalog your external...
NeoFinder (formerly CDFinder) rapidly organizes your data, either on external or internal disks, or any other volumes. It catalogs and manages all your data, so you stay in control of your data... Read more

Latest Forum Discussions

See All

Amon Amarth Berserker is a side-scrollin...
Amon Amarth Berserker is the latest game from Ride & Crash and serves as a follow up to the previous title that was simply called Amon Amarth. It's available now as a premium title for both iOS and Android. [Read more] | Read more »
Team up with your guildmates to take on...
MU Origin 2's latest update is now live and brings with it two new Abyss-related events to challenge Guilds. There are also a few new features that will allow players to enhance their costumes, an increased level cap and more. [Read more] | Read more »
Build Your Own Apple Arcade, For $400
Apple Arcade has been out for a little over a month, and I’m not entirely thrilled with it. It’s definitely an interesting idea, but it leaves a lot to be desired, especially in fulfilling its commitment to letting folks “play anywhere.” Still, at... | Read more »
Creepy Little Monsters is a cute, monste...
Creepy Little Monsters is a retro throwback that sees you traversing tricky puzzle-platformer levels as a one-eyed monster. It aims to offer a fresh take on 80s and 90s classics of the genre, and it's out right now for iOS and Android. [Read more... | Read more »
Tyrant's Arena delivers intense her...
Tyrant's Arena is an intense midcore multiplayer actioner where you'll compete in tricky 3v3 matches to crush your opponents and earn neat rewards. It comes to us from developer Kroy Games, and it's now available for pre-registration on iOS and... | Read more »
Mobile Games Starter Kit
Over here at 148Apps, we regularly dive deep into the latest and greatest mobile games hitting the App Store, but that’s not always what people are looking for when searching for a new mobile game. Some folks just want to dip their toes into... | Read more »
Unresolved is a hard-hitting narrative a...
Ghofran Akil's Unresolved in an upcoming text-based adventure game that sees you playing as a mother attempting to find her disappeared husband during the Lebanese Civil War. [Read more] | Read more »
Marvel Strike Force introduces new brawl...
FoxNext's squad-based RPG Marvel Strike Force is set to receive some fresh characters from the X-Men and Iron Man series. They'll arrive as part of the game's latest update, which follows a sizable spending boycott on the title due to complaints... | Read more »
Speed Dating for Ghosts is a narrative a...
Speed Dating for Ghosts originally released on Steam back 2018, since then it has received honourable mentions for narrative during the Independent Games Festival. Now it's made its way over to iOS devices where it's available as a premium title... | Read more »
Fast-paced multiplayer title Tennis Star...
Tennis Stars: Ultimate Clash is the latest free-to-play tennis title to hit iOS and Android. It's said to be a fairly casual experience, offering easy-to-learn controls and fast-paced, mobile-friendly matches. [Read more] | Read more »

Price Scanner via MacPrices.net

Back in stock! Apple’s 4-core and 6-core 2018...
Apple has Certified Refurbished 2018 Mac minis available on their online store for $120-$170 off the cost of new models. Each mini comes with a new outer case plus a standard Apple one-year warranty... Read more
10″ 128GB iPads on sale today at Amazon for $...
Amazon has new 10.2″ 128GB WiFI iPads for $100 off Apple’s MSRP. These are the same iPads sold by Apple in their retail and online stores. Note that some sale prices may be restricted to certain... Read more
Orcam MyEye 2 Is Inspiration Apple Needs To M...
EDITORIAL: 02.28.20- It’s no secret that Apple is planning to further expand into the wearables segment, working quietly behind the scenes to create its own smart glasses — as rumors have suggested... Read more
Boost Mobile 1-day Flash Sale: $100 off all A...
Boost Mobile is offering Apple’s 2019 iPhone 11 and 11 Pro models for $100 off MSRP. Boost is also offering the same $100 discount on new previous-generation iPhone XS, XR, X, 8, and 7 models. For... Read more
13″ 1.4GHz Silver MacBook Pros on sale for $1...
B&H Photo has new 2019 13″ 1.4GHz Silver MacBook Pros on sale for $150 off Apple’s MSRP today with prices starting at $1149. Overnight shipping is free to many addresses in the US. These are the... Read more
Apple resellers offer $150-$170 discounts on...
Amazon has new 2019 13″ MacBook Airs on sale for $150-$170 off Apple’s MSRP, with prices starting at $949, each including free shipping. These are the same MacBook Airs Apple sells in their retail... Read more
B&H is again offering $100 discounts on M...
B&H Photo has 4-Core and 6-Core Mac minis on sale for $100 off Apple’s standard MSRP, with prices starting at only $699. Overnight shipping is free to many US addresses: – 3.6GHz Quad-Core mini... Read more
B&H Photo drops iMac prices, offers model...
B&H Photo has new 2019 21″ and 27″ 5K iMacs in stock today and on sale for up to $250 off Apple’s MSRP, with prices starting at only $999. These are the same iMacs sold by Apple in their retail... Read more
Flash sale! 11″ 64GB WiFi iPad Pro for $674,...
Walmart has the 11″ 64GB WiFi iPad Pro on sale on their online store today for $674. That’s $125 off Apple’s MSRP for this model and the cheapest price available from any Apple reseller. Choose free... Read more
Sale! Get the 256GB 13″ Silver MacBook Air fo...
Amazon has new 2019 13″ 1.6GHz/256GB MacBook Airs, in Silver, on sale today for only $999 shipped. Their price is $300 off Apple’s MSRP for this model, and it’s the cheapest price for a 256GB MacBook... Read more

Jobs Board

Windows/ *Apple* Technical Support Engineer...
Windows/ Apple Technical Support Engineer Key Role: Serve as a part of a dynamic corporate technical support group. Provide Tier III technical support and monthly Read more
Medical Assistant - *Apple* Valley Clinic -...
…professional, quality care to patients in the ambulatory setting at the M Health Fairview Apple Valley Clinic, located in Apple Valley, MN. Join the **M Health Read more
Medical Assistant - *Apple* Valley Clinic -...
…professional, quality care to patients in the ambulatory setting at the M Health Fairview Apple Valley Clinic, located in Apple Valley, MN. Join the **M Health Read more
Geek Squad Advanced Repair *Apple* Professi...
**764652BR** **Job Title:** Geek Squad Advanced Repair Apple Professional **Job Category:** Store Associates **Store NUmber or Department:** 000245- Apple Read more
Medical Assistant - *Apple* Valley Clinic -...
…professional, quality care to patients in the ambulatory setting at the M Health Fairview Apple Valley Clinic, located in Apple Valley, MN. Join the **M Health Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.