"Bulls and cows" in Python : A tiny game (also a puzzle) with curses TUI

[Dilawar]

Recently, a friend taught me a simple game of bulls and cows. She had some higher purpose behind this game for she is into optimization. 

The game goes like this. There are two players, A and B. A thinks of a 4-letter word and asks B to guess it. Assume that A thought of “link” and B guesses “lean”. The bulls are the number of letters common to both words and at the same location in both words, for example “l” is a bull in “link” and “lean”. The cows  are number of letters which are common to both words but not bull. Letter “l” and “n” are common to both but “l” is the bull, so “n” is the only cow. This guess of “lean” has one bull and one cow. Player A tells B the number of bulls and cows. This helps B in making the next guess; the process goes on till B finds the word. Its not as easy as it looks especially if a compute guesses the word. It also has a numerical version of it where player guesses a four digit number rather than word.

I wrote a python program to play this game on computer. It is a very small program but it has a primitive TUI which might also serve as a small tutorial or reference code to those who wish to add some Text User Interface (TUI) with ncurses library. I am not sure if it will work on windows. Code is kept in this repository implementation of the game. You need to download the python file and text file containing all 4 letters words. If you make an enhancement to this game, or make it windows compatible, do send a pull request.

Those who are studying combinatorics (or VLSI-Cad course) would be interested in this game. What do you think about algorithm which is best suited if a computer were to play this game against another computer. How many steps (on average and upper limit) would that algorithm take to guess the correct word? Dynamic programming? Some Greedy algorithm? Branch-and-bound? Markov chains? Simulated annealing? Binary decision diagrams?

--
Dilawar
NCBS Bangalore
EE IITB

[Sudarshan Wadkar]

sounds like a variety of hangman

cheers,

-S

PS: disabling email notifications, hope to come back in a year!

--
--
The website for the club is http://stab-iitb.org/wncc
To post to this group, send email to wncc...@googlegroups.com
 
---
You received this message because you are subscribed to the Google Groups "Web and Coding Club IIT Bombay" group.
To unsubscribe from this group and stop receiving emails from it, send an email to wncc_iitb+...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Ashwin Paranjape]

A more popular version is called mastermind.

The wiki article links to various papers proving it is NP-complete in general. So its essentially an exponential  search space, each guess an element in the search space and for purposes of imagination the number of "bulls" and "cows" is a two dimensional radius (and the imagination starts breaking down). Selecting the next turn to reduce the possibilities is also known studied as active learning. The goal while selecting the next move should be to eliminate as many possibilities as possible rather than verifying a particular hypotheses.

--

Ashwin P. Paranajape

4th year CSE Btech.
IIT Bombay

[Dilawar Singh]

This one may not be NP. Even by brute force, I can get an answer by exhausting all possibilities (that is no of total four letter words). So a simple inequality is < 99171 (no of four letter words) in /usr/share/dict/words.

@Sudhakar
Yes, it looks like a variation of hangman. But we don't tell the location of the letter after each successful guess. So possibilities of guessing is rather limited here.

Haskell implementation of Hangman (a cleaned up version) is available here.
   
    ghc --make hangman.hs
    ./hangman 

Or
    ghci hangman.hs

 

Dilawar
NCBS Bangalore