Current issue

Vol.26 No.4

Vol.26 No.4

Volumes

© 1984-2017
British APL Association
All rights reserved.

Archive articles posted online on request: ask the archivist.

archive/11/2

Volume 11, No.2

Cows and Bulls - A Solution

by Anne Wilson

Herewith my solution to Cows and Bulls, when the computer guesses. The problem is one of reducing the number of possibilities using the ‘hits’. I used this as the design of the function:

  • evaluate all possibilities [4] – [8]
  • drop those with wrong bull score [16]
  • drop those with wrong cow score [18] – [19]
[0]   FROM BULLCOW PICK;ABC;BC;FREQ;GUESS;POSS;TRIES;X
[1]   ABC←FROM↑'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
[2]   TRIES←0
[3]  ⍝ This ran out of space   POSS←ABC[⍉1+(PICK⍴FROM)⊤¯1+⍳FROM*PICK]
[4]   X←((PICK,19)⍴'((FROM*PICK)⍴(FROM⍴')
[5]   X←X,[2]((PICK,5)⍴ 5 0 ⍕FROM*⌽¯1+⍳PICK)
[6]   X←X,[2](PICK,10)⍴')/ABC),[2]'
[7]   X←'((FROM*PICK),PICK)⍴ ',(,X),'((FROM*PICK),0)⍴'' '''
[8]   POSS←⍎X
[9]  loop:→(0 1 =1↑⍴POSS)/lerr2,lok
[10] ⍝ A random choice for the next guess
[11]  'Is it ',(GUESS←,POSS[?1↑⍴POSS;]),' Enter BULLS (hits) and COWS (near)'
[12]  →(2≠⍴BC←⎕)/lerr1
[13]  →(PICK<+/BC)/lerr1
[14]  TRIES←TRIES+1
[15] ⍝ Keep only if the number of BULLS is correct
[16]  POSS←(BC[1]=POSS+.=GUESS)⌿POSS
[17] ⍝ Next look at COWS + BULLS
[18]  FREQ←+/ABC∘.=GUESS
[19]  POSS←((+/BC)=+/((+/[2]POSS∘.=ABC)⌊((1↑⍴POSS),⍴FREQ)⍴FREQ))⌿POSS
[20]  →loop
[21] lerr1: 'Try again - you have made a mistake'
[22]  →loop
[23] lerr2: 'You have made a mistake - I''VE WON'
[24]  →lend
[25] lok: 'After ',(⍕TRIES),' tries I reckon it is ',,POSS
[26] lend: 

Sample run, where solution is ABCD:

       4 BULLCOW 4 
Is it DBBA Enter BULLS (hits) and COWS (near)
 ⎕:       1 2 
Is it AABD Enter BULLS (hits) and COWS (near)
 ⎕:       2 1 
Is it ABCD Enter BULLS (hits) and COWS (near)
 ⎕:       4 0 
After 3 tries I reckon it is ABCD

Editorial comment: This is an excellent solution to the general m×n problem. It works provided FROM*¯1+PICK is less than 100000 (though this could be extended by minor modification of lines [4] to [8]). For the larger problems, of course, you need lots of megabytes of RAM!


(webpage generated: 14 October 2007, 19:04)

script began 23:42:34
caching off
debug mode off
cache time 3600 sec
indmtime not found in cache
cached index is fresh
recompiling index.xml
index compiled in 0.3 secs
read index
read issues/index.xml
identified 26 volumes, 101 issues
array (
  'id' => '10010940',
)
regenerated static HTML
article source is 'HTML'
source file encoding is 'ASCII'
read as 'Windows-1252'
URL: mailto:-*- => mailto:-*-
URL: mailto:-*- => mailto:-*-
completed in 0.3274 secs