1. Computing

Programming Challenge 25a - Fit tetris shapes in a Box

By

Tetris Shapes
This challenge is about taking a file of Tetris shapes and fitting them into a box. Ie it's just like playing the game Tetris. You are provided with a text file of shapes in one of 4 rotations. You must write a program that reads the input file and places each piece in the box at the bottom.

The game

You can read more about Tetris in this Wikipedia article. The 7 pieces (shown) are referred to by their letter I, J, L, O, S, T and Z. In the input file there is one piece per line starting with an identification letter, then the piece and it is followed by optional digit 1,2 or 3. This indicates it is rotated clockwise by 90 degrees, once, twice or three times. I can only be rotated once, O never at all, S and Z by 1 or 2, and J, L and Z by 1-3.

The identifying letters are a-Z,A-Z and the digits 1-4. There are 56 pieces, 8 of each letter. The order of the pieces is random.

Examples

 aI unrotated I piece ****
 bL3 Rotated 3 **
 ...............*
 ...............*
 

The box This is 15 x 15 box with the top row being numbered 0-14, the 2nd row 15-29 etc and the last row 210-224. In theory as each piece occupies 4 squares and there are 56 pieces (X 4 = 224) so all should fit in the 225 square grid.

Your Entry

Download the input file.
Your program must fit all the pieces into the 15 x 15 grid or fill as many rows as it can. Unlike the Tetris game where pieces are dropped in, you are free to place pieces anywhere, and can rotate them. You get 1 point for each solid line.

If however you can fill the grid by dropping them in you get 2 points per line.

The Output

Output a text file showing the 15 x 15 grid with the pieces identifying characters. This is the top corner of one possible grid
 Z y y 1 1 1 1.
 Z X y y H P...
 Z X X H H P...
 Z X S S H P...
 K K S U U U...
 K K S L L L...
 ...
 
If you have placed the pieces there then you should also output a list of placed pieces. This should be one line saying Placed followed by 56 lines in the following format:

Identifying letter Location Number(0-224) (Optional) Orientation(1-3)

 Z 0 - Piece Z at location 0 with no orientation
 K 60 - Piece K at location 60 with no orientation.
 B 1
 H 18 3 Piece H at location 18 (See below) orientation 3.
 

Note. The location is the top left square of a piece even if that piece in an orientation has no part there. Consider a T piece in orientation 0. There is no * in the top left corner.

 .*
 ***
 

Dropped Pieces

As with placed pieces, output the grid. The text file should also have one line saying Dropped followed by 56 lines the same as the Placed version except the location is just 0-14. Also the order of dropped pieces must be the order your program dropped them. so when I run a check program it will put the pieces in the right place and fill the grid.

Tie Breaker

to avoid the situation that two or more entrees have the same top score, generate the solution in a loop a few hundred or thousand times so that it takes roughly under 5 sec total time and write out the average time for solving it once. Something like
 Time to solve (once): 0.0476 seconds.
 
This is the code that you can use for timing.

The results

Thank you to all who entered this which was on reflection quite a complicated programming challenge.

Congrats to Zufolek with a very fast half second result. Francis Rammeloo submitted both a console and a a colorful graphical version that actually showed it solving the solution so gets a mention for a great entry. There was a 3rd entry but I never managed to build it.

  1. Zufolek (USA) - C Time = 0.517974
  2. Francis Rammeloo - C++ Time = Unknown

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 Challenge 25a email address with the subject line Programming Challenge 25a.

It must compile with Open Watcom, Microsoft Visual C++ 2005/2008 Express Edition/Microsoft Visual Studio 2003/2005/2008 or Borland Turbo C++ Explorer, Microsoft Visual C# 2005/2008 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 July 31 2009.

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.

Have fun!

More Programming Challenges

  1. About.com
  2. Computing
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 25a - Fit Tetris Shapes in a box - Deadline July 31 2009

©2014 About.com. All rights reserved.