1. Technology

Programming Challenge 72 - Divide and Fill

Starts July 1st, 2013

By

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 Definition

Each 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:

  1. A maximum of five rectangles that are one width or height.
  2. 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.

The input

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).

1,1,1,2,2,6,7,14,11,4,13,5,5,12,3,2,4,4,3
18,7,2,12,2,6,7,6,11,3,1,5,5,12,3
2,1,3,4,1,2,3,5,8,4,1,6,5,4,12,17,4,5,7,6
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

The Output

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.

218 ┌
217 ┘
191 ┐
192 └
196 ─
179 │

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.

┌──┐
│03│
└──┘

The first 1 (index 0) as a single row would look like this horizontally:

──00──

and like this vertically



0
0


Winning Criteria

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.

Specific Tip

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.

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@aboutguide.com?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.

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.

  1. About.com
  2. Technology
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 72 - Divide and Fill

©2014 About.com. All rights reserved.