Programming Challenge 19 - Fill a Grid of Tiles

Reader Kenneth D Weinert pointed me to an interesting game with a board made of 14 x 14 colored squares. By changing the color of the top left hand corner to match those below or to the right, you buildup a bigger and bigger block of contiguous squares of the same color. the twist: is you have to fill the whole board in 25 moves or less. You can try this puzzle out. After you click that link, click the View Max Mode button under the Gadget Preview to pop up a window in which you can play it.

So that's the basis for this programming challenge, except we'll use a 14 x 14 grid of characters 1-6. These are generated randomly and you must transform all 196 characters into the same character in 25 or less moves. To make it interesting, there are 1,000 boards all in one text file, laid out in lines of 196 characters each. The first 14 characters are the first line of the board, the next 14 the second etc. This is what the first line looks like if it is split over 14 lines.

11622521331316
12635256521232
52316256365111
41415455425464
62521536446531
56552165465214
26124621224321
45511115534353
35511112524236
22456232554534
46513311451665
62553412631621
16451512642363
33165263163254

If the first move was 6 then the top two lines would now look like this.

66622521331316
62635256521232

Specifically, you play a digit 1-6 in the top left hand corner. All contiguous cells (i.e. those with the same value adjacent horizontally or vertically but not diagonally) change to the digit chosen. So the 1 to the right and the 1 below the top left hand corner became 6.

If I know played 2, then the top three lines would now look like this:

22222521331316
22235256521232
52316256365111

If you have trouble understanding the puzzle, play the game I linked to. It's exactly the same principle except with digits 1-6 instead of colors.

Download the Input file. (194 Kb)

The Challenge

Read the file tiles.txt into memory and process each board, creating an output file called results.txt in the same folder as your executable and the input file. Each line of output (there should be 1,000) should be up to 25 characters each 1-6.

If your program can't solve a board in 25 or less moves, just output the first 25 moves. Total up the length of each line and output Total Moves = x where x is your total. It should be less than 25,000 as that is the worst score. Lowest score wins!

Results

Congratulations to Aliaksei whose entry ran for over 20,000 seconds and won with the lowest score. This was a tough challenge so thanks to all who entered.

1. Aliaksei Sanko (Belarus,) - C++ Points = 20086
2. Joshua Warner (USA) - C# Points = 20195
3. Clinton Shephard (USA) - C# Points = 20363
4. Tyler Mitchell (Canada,25) - C Points = 21033
5. Antonio Cortes (Mexico) - C# Points = 22243
6. St0le(India) C++ Points = 24097
7. Kenneth D Weinert (USA,53) - C# Points = 24415

Clinton's is still running and I'll update this once it's finished.

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

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 December 31 2008.

The top ten entries will be listed, judged purely by myself. 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

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