Sign in to follow this  
AnujSuper9

Scrabble in C

Recommended Posts

Hello everyone! So, I've been given an assignment to create something of a simplified Scrabble game in C. I'll start of by mentioning that I'm aware of the vastness in similarities between C and C++, but I am more versed in C++ and so I'd consider my C to be slow but functional, so please bear with me if I'm making trivial syntax errors. Now, the assignment is to take an existing 'board' with some letters already placed on it, and a 'tray' of letters for the player, and then output a new 'board_res' with the new words/letters on it, a new 'tray_res' with the letters removed that were added to the board, and the total word score for the letters added (no triple or double word/letter scoring either). The idea is to create a function that finds the maximal score possible, and uses those letters to form those words. Scoring is based on a template similar to traditional Scrabble letter scoring. Now, I haven't even began writing too much code for this yet as I am still in the design phase of this. I'm not really sure what the best approach of attack is. My initial thought is to check each 'word' present on the board, or even each grouping of letters, and see if it matches in similarity to any other words possible with letters in my tray, but that seems roundabout and not necessarily capable of achieving the optimal score. My second thought is to take the letters one by one and place them near the words and see if they match something in the dictionary, check the score of it, and store the highest scoring variation of this. Now of course, the problems with this are immediately easy to recognize, as this is also somewhat of a roundabout way of doing it, and may not allow taking advantage of things like multiple word scores or etc. Btw, when I refer to the dictionary, I refer to the a random
char *dictionary[]
array that I've been provided to check against, which we assume has words in it similar to what would be found in a dictionary. So my other thought was to maybe start taking letters from my tray, and letters from the board, and checking in the dictionary the possibilities allowed by those letters. Maybe even establish some sort of order for the letters already on the board and then gauge the potential word scores there. But this seems a bit overly complex for this kind of thing. Anyway, I assume that the creation of this design is one of the biggest purposes of this problem. I will continue to think about this obviously, but input/ideas/suggestions from you all would be most welcome.

Share this post


Link to post
Share on other sites
Pre-sort the dictionary (or make a sorted copy) from highest-scoring word to lowest. Then when asked to move, try to make each word in order until one of them is possible. To figure out if a word is possible, you could check every board position for a word of that length; if it overlaps at least one existing letter, and every overlapped letter matches the corresponding letter in the word, then it can be laid down in that position - so check if the tray contains the remaining letters.

Share this post


Link to post
Share on other sites
Hmmmmmm.... that's not bad at all.

That's actually the simplest suggest I've heard so far. But at the same time, is that an efficient way to do it?

Also, how do you think I should go about checking the possible words from the tray and the board? Just take all letters from the tray and the board and come up with the potential words? Seems like that wouldn't work when there are more letters on the board...

Regardless actually, I'm still having trouble coming up with the algorithm for this...

So I figure maybe I'll do this:

1. Find the spots on the board where there are "attachment points," i.e. next to tiles there there are already letters.
2. Cycle through all of the possible letters that could go there and see if it contributes towards forming a word.
3. If so, continue forming said word till complete.
4. Once said word is complete, calculate and store its score.
5. Continue process for any remaining letters.
6. Repeat process and store only the highest score.

...Hmm, how would I make certain that it wasn't trying the same letters/words in step 2?

Ugh, this entire process sounds relatively simple on paper, but I still can't figure out how exactly to write it, because I keep thinking of test cases where it wouldn't work. Not to mention the overall complexity of the individual steps outline above as well.

Share this post


Link to post
Share on other sites
Quote:
Original post by AnujSuper9
Hmmmmmm.... that's not bad at all.

That's actually the simplest suggest I've heard so far. But at the same time, is that an efficient way to do it?


It seems reasonable to me. But why don't you try it?

Quote:
Also, how do you think I should go about checking the possible words from the tray and the board?


Don't. Like I said:

Quote:
Then when asked to move, try to make each word in order until one of them is possible.


That is to say, "Can I make the first word in my sorted dictionary? Well, let's see... where on the board could it possibly fit? Ok, for each of those locations, what tiles are missing? Ok, do I have those tiles? No? Not for any of those locations? Ok, let's try the next word...".

To figure out where on the board a word could possibly fit, you can do something like:


For each tile already on the board:
For each position in the candidate word where the tile could be:
Consider placing the word horizontally such that the tile supplies the
letter in the given position. Would this overlap any other tiles on the
board that don't match the corresponding letter in the word? If there are
no conflicts, then we could place the word here.

Make a similar consideration for a vertical placement.


When you find a potential place for a word, you then have to figure out which parts of the word are not supplied by tiles on the board, and see if the tray can supply the missing letters.

Quote:
Just take all letters from the tray and the board and come up with the potential words? Seems like that wouldn't work when there are more letters on the board...


Although actually, that's not a bad filter to have. If there's no 'z' on either the tray or the board, you can immediately skip words in the dictionary with a 'z' in them. :)

Share this post


Link to post
Share on other sites
This sounds exactly like a programming test given to me for a position I applied for. The initial email I got before the test said that most of their tests they issued should only take 2-4 hours. After getting this particular test I was like "...yeah". Eventually I completed the test after doing lots of research on the game Scrabble itself(never really played it much before). Anyways...

Basically in order to account for new words being formed from playing other words(such as playing a horizontal word and it in turn also creates one or more verticle words in the process) I went down each word in the dictionary and looked at each anchor point, testing if the letters that were on all sides plus what was in my tray could complete the word. Then I scored the entire board for new any new words formed(including the one played). If the word created a higher score than the previous word then it became the new high word until the entire dictionary was finished.

Sadly the position I applied for was erased when the entire company decided to merge all their offices into one location(axing several jobs in the process :( ).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this