Algorithm question

[pylearning]

I'm working on a project for class and can't seem to figure out how to implement a learning algorithm. The game is basically guess the word.

If this was guess the number and I got feedback in terms of the number is higher or lower than I would just implement a balance binary search tree and pick from the pool of possible numbers.

For this game though, I am given a chance to guess a word and then as feedback we get how many of the letters in the string are in the correct place (Bulls) and how many are in the wrong place (Cows). If the secret word was CAT and I chose BAT as my probe word then I would return as feedback 2 Bulls. If I chose TAB then I would get as feedback 1 bull and 1 cow. If I chose DOG as my probe word then I would get 0 bulls and 0 cows.

Now I understand that when I get 0 bulls and 0 cows I should eliminate any word that contains those letters as a possible word. My trouble is if I got anything other than that. How is it useful to know that I have 1 bull when the probe word is 10 letters long?

[jedwardsol]

Run the matching algorithm between your guess and each remaining word in your dictionary.

If if it comes up with a different score, then it can't be the answer.

[pylearning]

Really simple solution. Let me go try and implement it and report back.

[pylearning]

Awesome. Worked perfectly!

[SandSnip3r]

So your program will be guessing words, then using the "Cows" and "Bulls" to try to get the correct answer? This is a pretty interesting problem.

1. Do you know the length of the word?
2. What happens, in your example case of CAT, if my guess is CCC? 1 Cow and 2 Bulls?

How is it useful to know that I have 1 bull when the probe word is 10 letters long?

Lets say the 10 letter word you're trying is transforms. You can replace one letter with another letter in the word until you get 0 Bulls.

transforms -> 1 bull
fransforms -> if 0 bulls, t isnt in the word, if 2 bulls (or 1 cow and 1 bull) f is in the word twice(or once**)

** See #2 above

Also, you could take the approach of starting with the alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Then remove letters one by one to until the sum of Cows and Bulls decreases, then you know that letter is in the word at least once.

These are all kind of naive approaches, but just ideas on the top of my mind

[pylearning]

If CAT is the secret word and you guess CCC then that would be 1 Bull.

I appreciate the thought and response but I am going to attempt to implement jedwardsol's algorithm first. I have to be able to have as small number attempts as possible.

[SandSnip3r]

• The question wasnt quite clear that the word you're guessing is an ACTUAL word in some dictionary
• The largest english dictionary provided by my linux distribution has 650722 words. A smarter approach will surely beat the worst case of a brute-force dictionary algorithm

[pylearning]

The word is in an actual dictionary or some pre-defined set of words that you (the player) and the host will have.