An entropy-based approach to Bulls and Cows To better understand Bulls and Cows I reduced the problem to 4-digit numbers that contain only digits 1 thru 5. There are 120 such numbers (5*4*3*2). We pick a number at random as our first guess (5421) and another number at random as our "secret number" (3541). We score the guess and then reduce the set of numbers to those that have this score. In our example this brings the set down to 36 numbers. For each number in this set we score it against all 36 elements in the set. We count the number of scores of 0, 1, 2, ..., 8. We compute the entropy of these guesses via entropy = sum over |ts| not = 0 of |ts|*log(|ts|) where |ts| is the number of elements that have a score of s. We select the guess with the minimum entropy. We again reduce the set of numbers to those that have a score of this guess. This brings the set down to 12 in our example. We repeat the entropy evaluation process. This brings our set down to 4 elements. The entropies are all equal in our example. We pick a random element. In our example we got lucky and hit the bullseye! tc>.entropy entropy.tc - tct - 11/19/15 Ref: http://primepuzzle.com/tc/bullcow.html Think of a 4-digit number. Use digits 1 thru 5. No repeating digits. 1234 1235 1243 1245 1253 1254 1324 1325 1342 1345 1352 1354 1423 1425 1432 1435 1452 1453 1523 1524 1532 1534 1542 1543 2134 2135 2143 2145 2153 2154 2314 2315 2341 2345 2351 2354 2413 2415 2431 2435 2451 2453 2513 2514 2531 2534 2541 2543 3124 3125 3142 3145 3152 3154 3214 3215 3241 3245 3251 3254 3412 3415 3421 3425 3451 3452 3512 3514 3521 3524 3541 3542 4123 4125 4132 4135 4152 4153 4213 4215 4231 4235 4251 4253 4312 4315 4321 4325 4351 4352 4512 4513 4521 4523 4531 4532 5123 5124 5132 5134 5142 5143 5213 5214 5231 5234 5241 5243 5312 5314 5321 5324 5341 5342 5412 5413 5421 5423 5431 5432 My guess for your 4-digit number is 5421. override y/n? n Compare your number to my guess. Count the Bulls (right digit, right position) and the Cows (right digit, wrong position). Enter a number from 0 to 8 using the table below, e.g. if there are 2 Bulls 2 Cows, enter 4. 4B0C 0 3B0C 1 3B1C 2 2B1C 3 2B2C 4 1B2C 5 1B3C 6 0B3C 7 0B4C 8 ? 5 0 - 1324 - 1 1 0 4 1 10 3 12 4 1 - 1325 - 1 2 0 1 2 12 2 12 4 2 - 1432 - 1 1 0 4 1 10 3 12 4 3 - 1435 - 1 2 0 1 2 12 2 12 4 4 - 1453 - 1 1 0 4 1 10 3 12 4 5 - 1523 - 1 1 0 4 1 10 3 12 4 6 - 2341 - 1 1 0 4 1 10 3 12 4 7 - 2351 - 1 2 0 1 2 12 2 12 4 8 - 2413 - 1 1 0 4 1 10 3 12 4 9 - 2435 - 1 1 0 4 1 10 3 12 4 10 - 2453 - 1 2 0 1 2 12 2 12 4 11 - 2531 - 1 1 0 4 1 10 3 12 4 12 - 3124 - 1 2 0 1 2 12 2 12 4 13 - 3125 - 1 1 0 4 1 10 3 12 4 14 - 3241 - 1 2 0 1 2 12 2 12 4 15 - 3251 - 1 1 0 4 1 10 3 12 4 16 - 3412 - 1 2 0 1 2 12 2 12 4 17 - 3415 - 1 1 0 4 1 10 3 12 4 18 - 3452 - 1 1 0 4 1 10 3 12 4 19 - 3524 - 1 1 0 4 1 10 3 12 4 20 - 3541 - 1 1 0 4 1 10 3 12 4 21 - 4123 - 1 1 0 4 1 10 3 12 4 22 - 4231 - 1 1 0 4 1 10 3 12 4 23 - 4325 - 1 1 0 4 1 10 3 12 4 24 - 4351 - 1 1 0 4 1 10 3 12 4 25 - 4523 - 1 2 0 1 2 12 2 12 4 26 - 4531 - 1 2 0 1 2 12 2 12 4 27 - 5132 - 1 1 0 4 1 10 3 12 4 28 - 5134 - 1 2 0 1 2 12 2 12 4 29 - 5143 - 1 1 0 4 1 10 3 12 4 30 - 5213 - 1 1 0 4 1 10 3 12 4 31 - 5234 - 1 1 0 4 1 10 3 12 4 32 - 5243 - 1 2 0 1 2 12 2 12 4 33 - 5312 - 1 2 0 1 2 12 2 12 4 34 - 5314 - 1 1 0 4 1 10 3 12 4 35 - 5342 - 1 1 0 4 1 10 3 12 4 My guess for your 4-digit number is 2531. override y/n? y enter overide : 1324 Compare your number to my guess. Count the Bulls (right digit, right position) and the Cows (right digit, wrong position). Enter a number from 0 to 8 using the table below, e.g. if there are 2 Bulls 2 Cows, enter 4. 4B0C 0 3B0C 1 3B1C 2 2B1C 3 2B2C 4 1B2C 5 1B3C 6 0B3C 7 0B4C 8 ? 7 0 - 2435 - 1 0 0 2 1 2 1 4 1 1 - 2453 - 1 0 0 0 2 5 1 3 0 2 - 2531 - 1 1 0 2 0 1 2 4 1 3 - 3251 - 1 0 0 2 0 4 2 2 1 4 - 3415 - 1 0 0 2 0 3 1 3 2 5 - 3452 - 1 0 0 2 1 2 1 4 1 6 - 3541 - 1 0 0 2 1 2 2 4 0 7 - 4531 - 1 1 0 0 1 3 0 4 2 8 - 5132 - 1 0 0 1 0 4 2 3 1 9 - 5143 - 1 1 0 2 0 1 1 4 2 10 - 5213 - 1 1 0 1 0 2 2 4 1 11 - 5243 - 1 2 0 0 0 3 1 3 2 My guess for your 4-digit number is 5213. override y/n? y enter override : 2435 Compare your number to my guess. Count the Bulls (right digit, right position) and the Cows (right digit, wrong position). Enter a number from 0 to 8 using the table below, e.g. if there are 2 Bulls 2 Cows, enter 4. 4B0C 0 3B0C 1 3B1C 2 2B1C 3 2B2C 4 1B2C 5 1B3C 6 0B3C 7 0B4C 8 ? 7 0 - 3251 - 1 0 0 1 0 0 1 1 0 1 - 3541 - 1 0 0 1 0 0 1 1 0 2 - 5143 - 1 0 0 1 0 0 1 1 0 3 - 5213 - 1 0 0 1 0 0 1 1 0 My guess for your 4-digit number is 3541. override y/n? n Compare your number to my guess. Count the Bulls (right digit, right position) and the Cows (right digit, wrong position). Enter a number from 0 to 8 using the table below, e.g. if there are 2 Bulls 2 Cows, enter 4. 4B0C 0 3B0C 1 3B1C 2 2B1C 3 2B2C 4 1B2C 5 1B3C 6 0B3C 7 0B4C 8 ? 0 It took me 4 tries! I am pretty much awesome. I used a tiny-c program and an external javascript evaluator to determine whether to override the random number picked from the available numbers. http://primepuzzle.com/tc/x.html http://primepuzzle.com/tc/y.html The goal is to eventually change this approach to one that is written in C (which supports the log function and reals) and to bring it back to 4-digit numbers that use digits 1 thru 9. This approach emerged after struggling and only partially understanding Vitaly's python program and reading many articles on entropy-based solution strategies. I finally think I have figured out the (it turns out not really too hard to grasp) basic idea of using entropy to select the best number to use for each new guess. The tiny-c program may be seen at http://primepuzzle.com/tc/entropy.tc |