- See all Programming Challenges.
Imagine a 30 wide by 20 deep grid with 600 locations. You are given a list of integer percentages that add up to 100. Your challenge is to completely fill the grid with rectangles where each rectangle matches one of the numbers as fast as possible.
Challenge DefinitionEach number is an integer in the range 1-20. There can be any numbers (well a maximum of 100) but they all add up to 100. So each percentage point is represented by 6 locations. Your task is to place a shape down on the grid for each number where the size of that shape = 6 x number in locations occupied, and try to completely fill the grid as quick as possible
There are however some constraints:
- A maximum of five rectangles that are one width or height.
- Shapes have to be rectangular.
Without that first constraint it would be possible to just solve it with all pieces having a width or height of one.
There will be roughly the same count of odd numbers as there are even.
This consists of four puzzles. Each puzzle is a singe line comma separated list: these three below. The 15 0s in the 4th puzzle are a place holder for the 4th one which I will add to your code, so please write your code to solve 4 puzzles (put your own in if you like during testing).
Please output the grids into a text file output.txt in the same location as your exe using the characters below (given with their ASCII codes). Note, if you have trouble with ASCII code, it's permissible to write their equivalent UTF-8 codes.
For single rows just use the characters 196 horizontally and 179 vertically. See the examples below
Please write the two digit code of the zero based index in the list inside the box or in the single row or column. Example: For puzzle one, the 2 is at index 3. As it's 2, the rectangle must occupy 12 squares. This is how the 4 x 3 box would look.
The first 1 (index 0) as a single row would look like this horizontally:
and like this vertically
Just be the fastest to solve the four. Please use the timing code from the General tips link below. Note, each %age that you fail to fit it incurs a 5 second penalty.
You can enter these characters in Windows in a text editor by holding down the ALT key and hitting the keys on the keyboard. ALT + 218 gives the top left corner character ┌.
General Tips on Entering
This is a single page article with tips on things to do and not do when entering challenges. Please read it!
These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.
RulesThis is for glory only. About.com does not permit prizes to be given.
Please submit your source code and the output file to the firstname.lastname@example.org?subject=Programming Contest 72 email address with the subject line Programming Contest 72.
It must compile with Open Watcom, Microsoft Visual C++ 2010/2012 Express Edition/Microsoft Visual Studio 2010/2012, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition, GCC/G++ and any Google Go compiler. If it doesn't compile, it can't be run so is automatically disqualified.
- Fancy learning C#? Read all About C#
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 the first Sunday on or after the last day in the challenge month.
The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest time. 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