The gameYou 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.
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 EntryDownload 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 OutputOutput a text file showing the 15 x 15 grid with the pieces identifying characters. This is the top corner of one possible grid
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:
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... ...
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 PiecesAs 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 Breakerto 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
This is the code that you can use for timing.
Time to solve (once): 0.0476 seconds.
The resultsThank 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.
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 email@example.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.
More Programming Challenges
- Link to Rock, Scissors and Paper Bot Ongoing Programming Challenge - Runs weekly.
- Link to Programming Challenge 2 - Count the Islands. (Finished)
- Link to Programming Challenge 3 - Manage Elevators. (Finished)
- Link to Programming Challenge 4 - Guess the Mastermind Code - (Finished)
- Link to Programming Challenge 5 - Squeeze words into a crossword grid - (Finished)
- Link to Programming Challenge 6 - Guess the Mastermind Code - (Finished)
- Link to Programming Challenge 7 - Validate Chess Positions - (Finished)
- Link to Programming Challenge 8 - Score Poker Hands - (Finished)
- Link to Programming Challenge 9 - Manage a Data structure - (Finished)
- Link to Programming Challenge 10 - Hide Text (Finished)
- Link to Programming Challenge 11 - Match Sets of Cards (Finished)
- Link to Programming Challenge 12 - Calculate Shortest Path - Completed)
- Link to Programming Challenge 13 - Play Battleships (Finished)
- Link to Programming Challenge 14 - Multiply Large Numbers(Completed)
- Link to Programming Challenge 15 - Generate a Dungeon (Completed)
- Link to Programming Challenge 16 - Solve 1,000 Sliding Puzzles ( Completed)
- Link to Programming Challenge 17 - Implement Life (Completed)
- Link to Programming Challenge 19 - Complete a Puzzle (Completed)