1. Technology

Programming Challenge 58 - Place Words

Deadline May 31 (or first Sunday afterwards)

By

There's a certain very popular board game where you have to make words from letters and try and achieve a high score. It's trademarked by a very big corporation so this puzzle isn't about that game and any similarities are er coincidental!

No seriously, it's a sort of Scrabble® programming challenge. You are given a board and 49 letters. There's also a text file of allowed words. Only words from that list are allowed.

The 49 letters are: TDOUBJS LFAEUKO LMEECYA NIMXOWE QYUDTAF RSREIOV GOJAPNO

The word list is a zip file with one word on each line, in alphabetic order from 2-9 letters long. There are just over 100,000 words in the wordlist.zip

The idea is to pick words from the list that can be made using the first seven letters from the list. The used letters are removed, the word placed on the board and it continues until all 49 letters are used up or no more words can be made.

UpdateYour program can look ahead through all the tiles (not just the current 7) to see other words that may be playable. I know it's not strictly like in Scrabble, but hey it's my Challenge!

The letters are scored using the standard Scrabble® scoring which is:

  • 0 Points - Blank tile. (there are none in the 49)
  • 1 Point - A, E, I, L, N, O, R, S, T and U.
  • 2 Points - D and G.
  • 3 Points - B, C, M and P.
  • 4 Points - F, H, V, W and Y.
  • 5 Points - K.
  • 8 Points - J and X.
  • 10 Points - Q and Z.

The board

You can download the board as a text file. I've used the period . for normal tiles, 2 and 3 to represent double and triple letters scores and = for double word and # for triple word scores.

These two files will be in the same location as your exe.

Placing Tiles.

The first word must be placed (horizonatlly or vertically) so one tile in that word falls in the center and scores double. Letter tiles must be placed according to the rules so at least one letter in the 2nd, 3rd and subsequent words placed must be on the board already. If two words run parallel, all 2 letter words formed must exist or it's invalid.

E.G. if JACK was on the board and you had CON you could play it like this

..JACK.
.CON..

AS JO and AN are apparently valid words. No I don't know what JO is!

The Challenge

Read the word list into memory then use the first 7 letters (TDOUBJS) and start placing words.

  1. Read tiles from the tile list (in order) until it's empty or there are seven tiles.
  2. Find a word that can be placed or throw away letters.
  3. Place the word and work out the score.
  4. Remove those tiles from your hand.

The board has special multipliers: double and triple letter and word points. Combinations are allowed so a triple word with a double letter score can score high points. Once a multiplier has been used, it should be removed so another word using a letter on a double or triple letter multiplier just gets the normal score.

The Output

Output the words placed into the file output.txt in the same location as your exe.

Letters are TDOUBJS
x,y,WORD,score

Where x and y are 0-14 each. So for instance the first word placed might be:

Letters are TDOUBJS
7,7,DO,5

D is on the center so scores double = 4 plus 1. And after the last word output the letters left over (or None if there are none)( and the total of all scores.

Throwing Away Letters

Your program can drop 1 or more letters for 0 points. Output two lines like this if it drops a letter:

Letters are TDOUBJS
Dropped Letter: U
Letters are TDOBJSL
...

If all seven tiles can be played in one go, 50 bonus points are gained.

WInning

Get the highest score. If two entries have the same score, the fastest wins. The link to tips on entering (below) page linked below has code for timing.

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@aboutguide.com?subject=Programming Contest 587 email address with the subject line Programming Contest 58.

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 May 31, 2012 (or first Sunday afterwards).

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 58 - Place Words

©2014 About.com. All rights reserved.