bulls and cows algorithm
hello people...
i've been asked to make a program of the game "bulls and cows".
before you shout at me, i know there is a lot of stuff in the net
but i got confused. i searched a lot in the net
and i found some algorithms, but the problem is that they aren't
efficient as i need to do.
the game, shortly, for who doesn't know:
i need to receive a secret number- 4 numbers between 0 to 6, with repeats
(for example, 0112 is legal).
i need to guess the secret with 5 guesses max.
with any guess i receive a feedback that says how much guesses were right
but at the wrong place(=cows), and how much were right and in the right place(=bulls).
for example: the secret is 5657. my guess is 3456.
i have one bull-the number 5 at the third place.
and one cow- the number 6.
the most efficient algo' that i found do it with 7 guesses and it's not good
enough for me.
i need it to be fast too. for example, i saw an algo' with trees
but it takes too much time. i need it to run as fast as possible.
i see to much information in the net so i need someone to focus me.
can you bring me an algorithm that do it with 5 guesses max, and generally efficient (if you can also add an example how it works, it will be great)?
you can write it on english (psaodo code). i will convert it to c.
thanks a lot people. maybe it's a small question for u guys, but for inexperienced like me it's an hard one.
i've been asked to make a program of the game "bulls and cows".
before you shout at me, i know there is a lot of stuff in the net
but i got confused. i searched a lot in the net
and i found some algorithms, but the problem is that they aren't
efficient as i need to do.
the game, shortly, for who doesn't know:
i need to receive a secret number- 4 numbers between 0 to 6, with repeats
(for example, 0112 is legal).
i need to guess the secret with 5 guesses max.
with any guess i receive a feedback that says how much guesses were right
but at the wrong place(=cows), and how much were right and in the right place(=bulls).
for example: the secret is 5657. my guess is 3456.
i have one bull-the number 5 at the third place.
and one cow- the number 6.
the most efficient algo' that i found do it with 7 guesses and it's not good
enough for me.
i need it to be fast too. for example, i saw an algo' with trees
but it takes too much time. i need it to run as fast as possible.
i see to much information in the net so i need someone to focus me.
can you bring me an algorithm that do it with 5 guesses max, and generally efficient (if you can also add an example how it works, it will be great)?
you can write it on english (psaodo code). i will convert it to c.
thanks a lot people. maybe it's a small question for u guys, but for inexperienced like me it's an hard one.
Last edited on
Unfortunately for you, as this is a homework question, you must figure it out yourself.
A few hints though: you have ten digits to guess with, and four places. Your first guess should always be something like 0123. This uses four of your ten digits in a single blow, and you get an impressive amount of feedback.
As you work your way through the numbers, you will get a list of cows that you must simply permute through the non-bull spots. The std::next_permutation() function will help you with that.
Also, you really only need remember your last guess to formulate the next one.
If you are unsure of how to do it, write a version of the game for yourself so that you can play, making guesses. You will find that you usually need only three or four guesses to get it right.
Good luck!
A few hints though: you have ten digits to guess with, and four places. Your first guess should always be something like 0123. This uses four of your ten digits in a single blow, and you get an impressive amount of feedback.
As you work your way through the numbers, you will get a list of cows that you must simply permute through the non-bull spots. The std::next_permutation() function will help you with that.
Also, you really only need remember your last guess to formulate the next one.
If you are unsure of how to do it, write a version of the game for yourself so that you can play, making guesses. You will find that you usually need only three or four guesses to get it right.
Good luck!
i can't use any library except stdio.h so i can't use std::next_permutation().
or maybe i can?
and i didn't ask u to solve my homework. just need a bit of intuition.
please give me an example to your idea.
thanks a lot again...
or maybe i can?
and i didn't ask u to solve my homework. just need a bit of intuition.
please give me an example to your idea.
thanks a lot again...
The algorithms you saw online were probably for using numerals 0-9, which is why they were worst case 7 steps. You are only using numerals 0-6, so the same algorithms will probably work for you in 5 steps (worst case).
Topic archived. No new replies allowed.