Bulls and Cows

Bulls and Cows

Lee Bradley

Friday, December 18, 2015

This document describes a computer program that finds a number you are thinking of based on scores you give to the guesses it makes.

A Bulls / Cows solver which uses an entropy-based guessing scheme may be found at

http://primepuzzle.com/tc/entropy.c

A developmental document which led up to this may be found at

http://primepuzzle.com/tc/entropy.html

The C solution grew out of the tiny-c solution which is discussed below.

You think of a 4-digit number. You may use any digit between 1 and 9 but you are not allowed to repeat digits. The computer prints out its first guess. You tell it the score of its guess. It gets one "bull" for every correctly placed digit and one "cow" for every digit that is in your number but not in the correct place. You are told what score to use for each of the 14 possibilities. For example, 2 bulls and 2 cows gets a score of 4.

 4B0C  0
 3B0C  1
 2B0C  2  2B1C  3  2B2C  4
 1B0C  5  1B1C  6  1B2C  7  1B3C  8
 0B0C  9  0B1C 10  0B2C 11  0B3C 12  0B4C 13

If the score isn't 0 (all bulls), the computer prints out its next guess and you score it. This goes on till the computer gets a perfect score (namely 0).

The program was written in tiny-c, a C-like interpreter.

Details: All 3024 possible numbers are loaded into an array. You supply a random number (to seed a random number generator). A random element from this array is given as the first guess. This guess is scored by you. If this is not your number, all elements in the array that satisfy this score are determined, the array is reloaded with just these elements, and a random one of them is used by the computer for its next guess. This goes on till what you were thinking of is the only survivor.

http://primepuzzle.com/tc/bc.tc

An "automated" version of the program (http://primepuzzle.com/tc/bca.tc) was written to investigate the average number of guesses. The first 300 "secret numbers" give the statistics below. The guess sequence is shown for only the last four of them. The number of times it took 1 guess (try), 2 guesses (tries) etc. is shown.

 296 1925 6598 1654 2964 2681 1936 1925 6 tries!
 297 1926 4239 6892 8426 1926 4 tries!
 298 1927 7536 1859 6812 2389 4258 1927 6 tries!
 299 1928 1597 7893 3529 1289 1928 5 tries!

 1 0
 2 2
 3 12
 4 54
 5 135
 6 82
 7 14
 8 1
 9 0

Average number of tries was 5.09666

A tiny-c interpreter and the source files discussed above may be found at http://primepuzzle.com/tc/bullcow.zip

Extract all the files to some folder on your hard disc and run the program as follows:

C:\>tinyc

tc>.r bc.tc

tc>.bullcow

To exit, type

tc>.x

Here's a link to a movie of bc.tc running under Linux.

http://primepuzzle.com/tc/bctoday.mp4

Note: The above does not work under Firefox but does under Chrome. Right click the link and choose Save Link As... and then play it with VLC media player.