1. Technology

Programming Challenge 68 - Word Crush

Starts March 1st

By

Word Crush Image

Here's a nice and simple programming challenge. You are given a 9 x 9 square with the center square blocked out so leaving 80 blank cells. Here's what it looks like with a . for an empty cell and a * for the blocked out one.

.........
.........
.........
.........
....*....
.........
.........
.........
.........

You are given a list of 4-6 letter words that you can download below. You job is to fit as many of them in the word square so each letter occupies an empty cell. Words can run horizontally, vertically or diagonally in both directions back to front or forward, i.e. in 8 different directions.

Sharing Letters.

Letters can be shared between words in the following ways:

  • Words can overlap so long as the same set of letters occurs in both words at the start or end. So ABRI and RIGHT would occupy 7 letters like this ABRIGHT or THGIRBA.

  • Words can cross and share one or more letters.

Here's an example of several words crushed together.

.SINGER..
..EOA....
...ST....
..TEEN...

That has the words SINGER, GATE,TEEN,ESES, NOSE and EAST. You could add AR,ARE, ARK or AG on the end of the ST (3rd line) to form extra words.

Word List

Download the words.zip file of a list of words. There are nearly 28,000 words all 4-6 letters long, so plenty to choose from.

Winning Criteria

The total of the least number of empty cells plus the number of words used will win. In case of a tie, the fastest wins, so please include the timing code listed in the tips page below. If a word is found twice or more, count each instance.

A Tip

Although you can maybe fit 15 words in, it's worth scanning to see if you've accidentally made other words. So long at the words are in the word list, they count.

Restrictions

If your entry takes over 60 seconds to run it is disqualified.

The output consists of a text file output.txt in the same location as your exe with the following four sections. Please output a blank line between sections.

  1. Output of the 9 x 9 grid with words, blank cells and the blank center cell.
  2. Output of the words in the grid, one per line with comma separated x,y coordinate of the first letter and the direction (See below) of the text 0-7. Eg GATE,5,1,0
  3. Output the comma separated count of the words plus the count plus the number of empty cells. e.g. 15,7.
  4. Total time in seconds to 2 decimal places. This is from the program starting until before writing the output file. It does include reading the word list. E.g. 2.54

Directions

These are with the first letter in the * position below.

701
6*2
543

So the word EAST in direction 7 would be:

T...
.S..
..A.
...E

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!

These tips contain code for C,C++ and C# (Not Go, yet) that can do very high precision timing.

Final Results

Thanks to Mark Mammel and new entrant Ron Spain. Mark's code managed to get more points in half the time, so he wins.

Mar's code was written for GCC but out of interest I also compiled and ran it with VS2010 and got the same results in the same time as the GCC version.

  1. Mark Mammel(C++) Result=146.1, Time = 23.67 (USA)
  2. Ron Spain(C) Result=136, Time = 56.8 (USA,34)

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

It must compile with Open Watcom, Microsoft Visual C++ 2010/2012 Express Edition/Microsoft Visual Studio 2010/2012, CC386 or Borland Turbo C++ Explorer, Microsoft Visual C# 2008/2010 Express Edition, GCC/G++ and any Google Go compiler. 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 March 31, 2013.

The top ten entries in each challenge will be listed, judged on highest score and in the case of a draw, the fastest 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.

  1. About.com
  2. Technology
  3. C / C++ / C#
  4. Programming Challenge List
  5. Programming Challenge 68 - Word Crush

©2014 About.com. All rights reserved.