You are given a set of rectangles or squares, 2 x 3, 4 x 4 etc. All your program has to do is pack them into a box so that there is minimum wasted space. Rectangles can be horizontal or vertically aligned. To make it a bit more interesting, each puzle must take no more than 5 seconds to solve or it will be disaqualified. It's not a speed puzzle though as the least number of wasted squares wins with speed being a tie-breaker.
There are no more than 9 blocks per box, numbered 1..9. So if the blocks are like these:
- 2,2
- 3,4
- 5,5
One solution, probably not optimal. might be this:
3333311xx
3333311xx
333332222
333332222
333332222
There are ten puzzles and for each one your program needs to output the packing arrangement (as above) and the number of wasted spaces, 4 in the above case marked by x's.
Input File
- Download Input.txt
Each of the ten puzzles starts with a line like this
Puzzle nand is followed by 1-9 lines each with two digits. The digits are each 1-9 and are not separate so if the first puzzle was the example above, it would look like this. The first piece is piece 1 etc.
Puzzle 122
34
55
Puzzle 2
...
Output File
Output for each puzzle the title followed by the output like the example above (use x for wasted squares) and a count of the wasted squares. At the end output two more lines: Wasted Total = and Total Time = n.xxxx seconds.
Puzzle 1
3333311xx
3333311xx
333332222
333332222
333332222
Wasted Count = 4
Puzzle 2
...
...
Wasted Total = 76
Total Time = 2.345 Seconds
Winning Criteria
The lowest total wasted squares win. In the case of a tie, the fastest wins (Use the timing code below). Good Luck!
Final Results
Thanks to Paul Goldenberg, James Borden and Ivan Dimov for their entries. Note the download links don't work yet due to technical difficulties. I hope to have them fixed later today (Monday 7th March).
- Ivan Dimov 43 - C++ 0.000635
- James Borden 78 - C# 0.028714
- Paul Goldenberg 83 - C# 0.1182567
There was a late entry (My fault) who got an even higher score (but the slowest) but it's not fair to change the ordering so I present Chad Joppeck's entry.
- Chad Joppeck 35 - C++ 0.825527
Timing Code
Please time from the start of the run, after reading in the input files until just before the output file is opened for writing. This code below will do high speed timing for Windows and the fourth one for Linux.
Rules
This is for glory only. About.com does not permit prizes to be given.Please submit your source code and the output file to the cplus.guide@about.com?subject=Programming Contest 44 email address with the subject line Programming Contest 44.
It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition or GCC/G++. If it doesn't compile, it can't be run so is automatically disqualified.
Please include your name, age (optional), blog/website url (optional) and country. Your email address will not be kept, used or displayed except to acknowledge your challenge entry. You can submit as many entries as you like before the deadline which is February 28 2011.
The top ten entries will be listed, judged purely on points. A condition of entry is that you allow your source code to be published on this website, with full credits to you as the author.
- An index of Every Past Programming Contest on this site
