Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

Re: Challenge: Design A Better Hangman Algorithm

by Kache (Initiate)
on Dec 12, 2012 at 14:29 UTC ( #1008507=note: print w/replies, xml ) Need Help??

in reply to Challenge: Design A Better Hangman Algorithm

Stumbled on this (and the previous) old thread. Thought I could provide some input even if the thread is dead.

Strategy in this thread up to this point:

  1. Find all possible candidate words, given correct guesses so far. e.g.: If the word is "PerlMonks" and we've got "Pe___o_ks", candidate words will match the regex "Pe...o.ks" perfectly.
  2. Determine which unguessed letter appears in the most candidate words. Break ties for letters that occur most of all (i.e. density).
  3. Discussion of using probabilistic/heuristic analyses, with undetermined efficacies.

I would suggest one more deterministic strategy before getting to (3): entropy and distribution.

Suppose we have the following five candidate words: aacd, aaef, bbgh, bibj. Using rules listed in (2), letters 'a' and 'b' are still tied.

However, it's clear that guessing 'b' will give us more information than 'a'. While guessing 'b' would reveal the solution, guessing 'a' would not. This is because 'b' is more evenly and chaotically distributed throughout the length of the words, allowing the step (1) in the next guessing round to narrow down candidate words even faster.

  • Comment on Re: Challenge: Design A Better Hangman Algorithm

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1008507]
[Corion]: ... the socket is done by my code. Ideally that module would not be based on callbacks ;)
[Corion]: Basically, something that decouples the HTTP parsing (+ determining whether to redirect, etc) from the IO
[Corion]: All clients I'm aware of don't do that but issue all IO themselves

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (12)
As of 2016-12-07 15:52 GMT
Find Nodes?
    Voting Booth?
    On a regular basis, I'm most likely to spy upon:

    Results (130 votes). Check out past polls.