If you have heard of the game Boggle then you'll be way ahead here. I've provided two files, one games.txt has 100 lines each with 25 characters (uppercase). Each line is one game. The other words5.txt has 14,084 valid words of 5 or less letters long. Both files will be located in the same location as your exe.
- Download games.txt.
- Download words5.txt.
These games were generated just as in the Boggle game using 25 dice (no not manually!) so the first line of games.txt is NKGERUHMYJZOERSHSWAJFTEAE and should be actually laid out as a 5 x 5 character square like this :
NKGER
UHMYJ
ZOERS
HSWAJ
FTEAE
Your program should examine each square in all 100 games and look for words that appear horizontally, vertically and diagonally in both directions. It should for example find TEA, WE and WO in that square above. For every word you find (for each occurrence- there are two of WE in that square) you get 1 point per letter. TEA (3) + WE (2 x 2) + WO (2) give you 9 points. I'm sure there's more!
For each game, output the following in a file results.txt in the same location as the exe.
This is made up of sections, one section per game. Each section starts off with the game number
Game 1
Then for every word found output a line like this:
word, line number in words5.txt, score, x,y,dir
Where x and y are 0..4 starting at the top left where x is horizontal position and y vertical. The N is at 0,0, the R on the first line is at 4,0, the bottom left is at 0,4. Direction is a number 1..8 (clockwise, North=1, East = 3 etc) so the first WE is at X= 2, Y = 3, dir = 1 and the second WE is at the same x,y but dir = 5. E.g. for WE the lines would be:
WE,13384,2,2,3,1
WE,13384,2,2,3,5
and finally output one last line to complete the section for that game:
Total Game Points = 45
Keep a total points for all games and finally output as the last line of your file something like this:
Games Totals Points = 4,765 Total Average Time = 0.678 secsIf you can do all 100 games in less than a second then please redo it in a loop (you don't need to reload both files but you must redo the search, no cached calculations!) several times so that it takes 5-10 seconds. The average time = total time/ number of times your program looped where each loop is one run of all 100 games. Use the code below to calculate timings.
Important Note
The letter Q represents QU and if your program finds QIET then that is a 5 point QUIET. I.E. unless a U exists next to a Q, you can add it in. If the U is already there, say so you find the letters QUITE then that is also valid.
Winning Criteria
Highest points first but in the case of tie-breaker, fastest code wins.
Timing Code
Please time from the start of the run, after reading in the input files until just before the output file is opened for writing. This code below will do high speed timing for Windows and the fourth one for Linux.
Final Results
Congratulations to Loren for a very fast win and to Pedro for a very close second. Thanks to everyone who submitted (and resubmitted) entries.
- Loren Eggert 11889 - C++ 0.000243435
- Pedro Graca 11889 - C 0.00026
- Ivan Dimov 11889 - C 0.001542
- Al Rithm 11899 - C 0.004679
- James Borden 11889 - C # 0.0066589
- Jonathan Lim 11883 - C #0.01051
- Jason Marks 11889 - C++ 0.0435863
- Sameerkumar Namdeo 11889 - C++ 0.0734
- Kenneth Tham 8039 - C++ 4.92732
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 43 email address with the subject line Programming Contest 43.
It must compile with Open Watcom, Microsoft Visual C++ 2008/2010 Express Edition/Microsoft Visual Studio 2008/2010 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 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.
- An index of Every Past Programming Contest on this site
