1. Computing

Programming Challenge 31 - Flipping Coins

Deadline January 31 2010

By

Flipping Coins

This challenge presents you with a 5 x 5 grid of coins all showing either heads or tails. If you select a coin, it flips from head to tails or tails to heads. Also the coins next to it (horizontally and vertically) also flip as well. So flipping one coin actually flips five if the coin is in rows and columns 2-4 (where 1 is the first row, 5 is the last), four if either column or row is 1 or 5 and 3 if the coin flipped is a corner coin.

The coins initial positions are contained in a text file input.txt that you should download. It has 5 lines of 5 characters each either H or T.

Example

THTTH
HHTHT
TTTTT
HHTHH
THTHT
The answer to that example puzzle is
5,1
4,2
2,4
4,4
2,2

If you start with all Ts and apply the answer in reverse order you will get the example shown.

The Output

Your program must generate an output file called output.txt that contains a number of pairs of coordinates to click that after clicking and flipping the coins will restore the grid to all Ts. Each pair of coordinates should be in the order column, row (both in the range 1-5), one per line i.e. as I showed it above. After the pairs there should be one line that has a count of the number of pairs, followed by the time it took to solve it using the timing code below. So the above would look like this:

5,1
4,2
2,4
4,4
2,2
5 Pairs
Average Time = 0.3 seconds

Average time should be calculated by running the code to solve this in a loop so it takes no more than 5 seconds. If your code can solve it 100 times then divide the total time for the answer (after loading the input.txt file and before saving the output file).

Shortest number of steps wins followed by fastest time for any matches. Note. I will use a different input.txt to run this!

Timing Code

Results

Congrats to Adrian Grigo from Australia with an astonishing 57.8 Nanosecond time. (5.78 x 10-8 seconds). Certainly the fastest entry yet in any challenge! Commiserations to Gabriel Dubois of France whose 3.67 ms was no slouch. Thanks to both entrants.
  1. Adrian Grigo (Australia) - C++ Time(secs) = 0.0000000578
  2. Gabriel Dubois (France, 32) - C++8844 Time(secs) = 0.00367258

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

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 January 31 2010.

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

©2014 About.com. All rights reserved.