Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #14955

Slightly off-topic: Determining the strength of "Hangman" word.

Show all headers | View raw

I've been playing a bit of Zynga's "Hanging with friends". I was 
thinking about how to go about creating an "aid" for this. I don't 
cheat, but I like solving these kinds of problems, just to prove I can.

There are two phases in Hanging with Friends. One phase is to guess the 
word that your opponent has constructed, and the other phase is to 
construct a word yourself.

In the construction phase, you are given a "bag" of 12 letters. I'm not 
sure if its a completely random distribution. I suspect its weighted in 
some way. Anyway, that's not relevant for this question.

So, It is relatively easy to write a program that uses a word list (such 
the "official scrabble dictionary" word lists in the Moby collection), 
to find all words in that list that can be constructed from the bag.

The problem is determining the strength of the word, how hard it is to 
guess.

There is probably a psychological component to this, since the "average" 
player isn't likely to use logic and will more likely just "guess" 
letters that seem likely.  A program (or expert) has the advantage 
(somewhat) in that it can figure out statistically which letters are 
most likely based on the remaining possible words, and it would then 
"guess" that letter. Although I'm not certain that is actually the most 
effective strategy either.

The algorithm for the "guess-ability" of a word is made more complicated 
by the fact that the word itself effects how many failed guesses 
opponent can have before losing the round.  I'm not sure what the 
algorithm is for that, though I suspect it has to do with the number of 
distinct letters and word-length.

Any thoughts on algorithms or data structures you might use to solve 
this kind of problem?

I've solved parts of this already. I've created "LetterBag", "Word", 
"LetterSet", and "WordIndex" classes.

The WordIndex makes it easy to find "All words that match a pattern, but 
don't contain letters in a specific LetterSet" and "All words that can 
be made from a specific LetterBag".

Oh, and to tie this into a previous thread, the whole thing fits in 
memory with room to spare ;-)

Thanks,
Daniel.

Back to comp.lang.java.programmer | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Slightly off-topic: Determining the strength of "Hangman" word. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-31 09:26 -0700
  Re: Slightly off-topic: Determining the strength of "Hangman" word. Lew <lewbloch@gmail.com> - 2012-05-31 09:44 -0700
  Re: Slightly off-topic: Determining the strength of "Hangman" word. Roedy Green <see_website@mindprod.com.invalid> - 2012-05-31 10:43 -0700
    Re: Slightly off-topic: Determining the strength of "Hangman" word. Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-05-31 11:34 -0700
      Re: Slightly off-topic: Determining the strength of "Hangman" word. Roedy Green <see_website@mindprod.com.invalid> - 2012-06-01 02:55 -0700
        Re: Slightly off-topic: Determining the strength of "Hangman" word. Gene Wirchenko <genew@ocis.net> - 2012-06-01 09:34 -0700
          Re: Slightly off-topic: Determining the strength of "Hangman" word. Roedy Green <see_website@mindprod.com.invalid> - 2012-06-01 11:58 -0700
            Re: Slightly off-topic: Determining the strength of "Hangman" word. Lew <lewbloch@gmail.com> - 2012-06-01 12:46 -0700
          Re: Slightly off-topic: Determining the strength of "Hangman" word. Lew <lewbloch@gmail.com> - 2012-06-01 12:45 -0700
            Re: Slightly off-topic: Determining the strength of "Hangman" word. Gene Wirchenko <genew@ocis.net> - 2012-06-01 13:46 -0700

csiph-web