There's a puzzle game online (there's one free version in the Chrome WebStore), done in HTML where you have a 2D 14 x 14 board randomly covered in colored squares. Each turn you select one of the six colors and all squares in the same color as the top left square that are connected aptobliquely (it's a portmanteau word meaning horizontally or vertically but not diagonally from the Latin Aptus - Connected and Oblique - Sideways) become that color.
If you are good and a little lucky you can clear the board in under 25 turns. I've done it about 50% of the time and my best was 18. I thought it would make a good programming challenge and so it's the challenge for March.
Your program must read the input file which contains a text file holding 5 rows of 196 characters each one of P,B,Y,R,C and G. (Short for Pink, Blue, Yellow, Cyan, Red and Green). These are generated randomly.
- Download the boards.txt file.
Your Task
You must write a program that reads all five lines and then solves each board in as few steps as possible. Note the contest will use a different set of five boards to the ones provided here.
Each turn you select a different color to the one in the top left cell. Then all connected cells in the same color as the top left cell must be changed to new color.
Example
This top left 6 x 6 cells of the starting board
PPBYRR
BRGGGY
CGGRRR
YYCRBP
PPPYRB
RGYCGB
If B is picked then all connected cells that are P (in the top left cell) change to B
BBBYRR
BRGGGY
CGGRRR
YYCRBP
PPPYRB
RGYCGB
If G is picked next then it becomes
GGGYRR
GRGGGY
CGGRRR
YYCRBP
PPPYRB
RGYCGB
And so on.
Time Limit
Each board should take no more than 1 second to solve or say 5 seconds for the lot.Scoring Your Entry
Add up the total number of turns for each board, i.e. all 5 values. If there is a draw for lowest scores then the fastest wins. Please time using this code and if your code is very fast please run it in a loop so the average speed can be reliably measured.
The Output
Please create a text file results.txt with every board shown in 14 x 14 chars using the color chars (PBYRCG) for each turn. So worst case it should contsain 5 x 25 boards shown. Something like this will do, note I've only shown the first 6 chars of each row
Board 1 Starting Position
PPBYRR
BRGGGY
CGGRRR
YYCRBP
PPPYRB
RGYCGB
Turn 1 Played B
BBBYRR
BRGGGY
CGGRRR
YYCRBP
PPPYRB
RGYCGB
...
Turn 24 Played B. (Complete)
Board 2 Starting Position
...
...
Total Score for five boards: 120
This code below will do high speed timing for Windows (first three) and the fourth one for Linux.
Winning Criteria
Lowest score wins.
Results
Thanks to all three who entered and congratulations to Igor Dimitrijevic whose C++ program just pipped Pedro Simões by one. Igor's was also fastest but only by 1/3rd of a second. Thanks to everyone who entered.
- Igor Dimitrijevic C++ Score = 94, Time = 0.458974 (France,36)
- Pedro Simões C# Score = 95, Time = 0.76739976 (Portugal)
- Mark MammelC++ Score = 116 Time = 0.717587 (USA,21)
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!
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 Contest 55 email address with the subject line Programming Contest 55.
It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 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 February 29, 2012.
The top ten entries in each challenge will be listed, judged on lowest number of moves and in the case of a draw, the lowest 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
