bulls and cows game -- programming algorithm(python)
Posted
by
IcyFlame
on Stack Overflow
See other posts from Stack Overflow
or by IcyFlame
Published on 2013-06-26T09:42:45Z
Indexed on
2013/06/26
10:21 UTC
Read the original article
Hit count: 123
python
This is a simulation of the game Cows and Bulls with three digit numbers
I am trying to get the number of cows and bulls between two numbers. One of which is generated by the computer and the other is guessed by the user. I have parsed the two numbers I have so that now I have two lists with three elements each and each element is one of the digits in the number. So:
237 will give the list [2,3,7]
. And I make sure that the relative indices are maintained.the general pattern is:(hundreds, tens, units)
.
And these two lists are stored in the two lists: machine
and person
.
ALGORITHM 1
So, I wrote the following code, The most intuitive algorithm:
cows
and bulls
are initialized to 0 before the start of this loop.
for x in person:
if x in machine:
if machine.index(x) == person.index(x):
bulls += 1
print x,' in correct place'
else:
print x,' in wrong place'
cows += 1
And I started testing this with different type of numbers guessed by the computer.
Quite randomly, I decided on 277. And I guessed 447. Here, I got the first clue that this algorithm may not work. I got 1 cow and 0 bulls. Whereas I should have got 1 bull and 1 cow.
This is a table of outputs with the first algorithm:
Guess Output Expected Output
447 0 bull, 1 cow 1 bull, 1 cow
477 2 bulls, 0 cows 2 bulls, 0 cows
777 0 bulls, 3 cows 2 bulls, 0 cows
So obviously this algorithm was not working when there are repeated digits in the number randomly selected by the computer.
I tried to understand why these errors are taking place, But I could not. I have tried a lot but I just could not see any mistake in the algorithm(probably because I wrote it!)
ALGORITHM 2
On thinking about this for a few days I tried this:
cows
and bulls
are initialized to 0 before the start of this loop.
for x in range(3):
for y in range(3):
if x == y and machine[x] == person[y]:
bulls += 1
if not (x == y) and machine[x] == person[y]:
cows += 1
I was more hopeful about this one. But when I tested this, this is what I got:
Guess Output Expected Output
447 1 bull, 1 cow 1 bull, 1 cow
477 2 bulls, 2 cows 2 bulls, 0 cows
777 2 bulls, 4 cows 2 bulls, 0 cows
The mistake I am making is quite clear here, I understood that the numbers were being counted again and again.
i.e.: 277 versus 477
When you count for bulls then the 2 bulls come up and thats alright. But when you count for cows:
- the 7 in 277 at units place is matched with the 7 in 477 in tens place and thus a cow is generated.
- the 7 in 277 at tens place is matched with the 7 in 477 in units place and thus a cow is generated.'
Here the matching is exactly right as I have written the code as per that. But this is not what I want. And I have no idea whatsoever on what to do after this.
Furthermore...
I would like to stress that both the algorithms work perfectly, if there are no repeated digits in the number selected by the computer.
Please help me with this issue.
P.S.: I have been thinking about this for over a week, But I could not post a question earlier as my account was blocked(from asking questions) because I asked a foolish question. And did not delete it even though I got 2 downvotes immediately after posting the question.
© Stack Overflow or respective owner