There are three friends who want to decide which of three drinks they should try first. They use the ladders method to decide. They draw three parallel vertical lines A, B and C. Then each friend draws a few horizontal lines, from A to B, A to C or B to C.
Each friend then picks a line A, B or C and follows it down. When they get to the end of a horizontal line they follow it across to the other end's target vertical line and then start following that line down. If you start with A the first horizontal line takes you to B then to C then across to A and so on. Eventually you end up at the bottom of one of the three vertical lines and that's the drink they have A, B or C. Note if you are following B and there's a line from A to C (or C to A) you ignore it. You only follow from one end to the other
In the image you can see that A ends up in the 2nd column, B in the third and C in the first. No matter how many columns or lines, each column ends up in its own one.
It's a variation on the tangled cords puzzles you sometimes see in magazines. Where three or four cords are all intertwined and you have to follow them to see what's at the end of each.
The Challenge
You are provided with a text file with one such puzzle, except there are 10 vertical lines A-J and 1,000 rows. Each line in the input file has ten characters that are either a period . or the letters A-J. There can be 0, 1 or more horizontal lines in each row but no two horizontal lines will touch.
- Download the input file input.txt
A line might look like this, with the top line showing the top of all ten columns.
ABCDEFGHIJ
...C.....I
..A.F...H.
This means there is a horizontal line from vertical line D to vertical line C and one from J to I. On the second line C goes to A, E goes to F and I goes to H
Write a program to read the text file and process it and discover where each of the ten columns ends. Note that no two horizontal lines will ever touch, so there should be ten individual routes through this!
Output
Please output the 10 columns in the order you've found. If the 10 columns end up as GEADHICBFJ then output that on one line, followed by the time it took to solve.
Timing Code
Please time from after reading the input.txt to doing the output. As this is likely to be very fast, please add code to loop multiple times processing the columns so that the total elapsed time is 1-5 seconds. If for instance it took 0.001 seconds to process the columns once once then a loop of 1000 times should take just about a second to run.
This code below will do high speed timing for Windows (first three) and the fourth one for Linux.
Winning Criteria
This is a pure speed contest. Whoever's code can follow the ten lines to the bottom the fastest wins.
Final Results
Thank you to all eight who entered the challenge with entries from the Brazil, Canada, Japan, Romania and USA. There were three who didn't get the correct answer, sorry chaps, and congratulations to Chris Saam whose C++ was lightning quick at 0.0000173 of a second, though closely followed by the next three entrants.
- Chris Saam EAICDFGHBJ - C++ 0.0000172866
- Tavis Bohne EAICDFGHBJ - C++ 0.0000356504
- Doru Constantin EAICDFGHBJ - C 0.000036988
- Jeremiah Hornick EAICDFGHBJ - C# 0.0000602966
- Pham Viet Tung EAICDFGHBJ - C# 0.0233325
- James Borden GGGGGGGGGG - C# 0.0000973348
- Alex Onofrei ABCDEFGHIJ - C++0.000045
- Jan Hadrava Disqualified - C++
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 52 email address with the subject line Programming Contest 52.
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 November 30 2011.
The top ten entries will be listed, judged purely on speed. 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
