Sieve method in the game "Bulls and Cows"
Hello.
Back in the fall of the 2nd year as a laboratory work on the Theory of Automata, the teacher thought up tasks for us on the move, orienting ourselves to our wishes in the assessment. These were mostly games. Someone got hockey, someone got tennis, but I did not get the well-known logic game "Bulls and Cows . "
It was necessary to implement at least some reasonable behavior of the computer in a game with a person. But I went further and already after a month the computer in most cases easily beat my classmates. And on the subject was received automatic. Get the program after the description of the algorithms.
The player and computer guess four-digit numbers using numbers from 0 to 9 . Players try to figure out the opponent’s numbers by sending him possible numbers, in return, receiving two numbers - the number of "bulls" and the number of "cows . " What are these numbers like?
For understanding, I will give an example:
Using data about the "cattle" of the enemy, you need to guess the number faster than him.
')
The first trivial algorithm that suggests itself is to iterate over the sets “1111”, “2222”, “3333” ... until the complete set is obtained, and then to generate displacements of this set.
Obviously, the algorithm is not very good, but it is understandable and not confused. The maximum number of guesses for guessing is 10 (“7890”) + 24 permutations. 34 is the worst case. Of course, it is possible to optimize brute force and permutations, for example, iterate alternately from two ends - “1111”, “0000”, “2222”, “9999” ... also optimize the generation of permutations in the presence of identical numbers (as in our example - several times ask the same thing).
But we will not do it. Let this strategy be with us an easy level of computer complexity.
I sat a lot on pairs and played with myself, trying to come up with some kind of a cool algorithm. But only individual ideas came from which I could not make a single strategy. He began to study literature. I came across articles, sort of "guessing in 7 moves." They did not attract me, because there is a lot of branching. But after reading the book of our Kirov professor (but not from our university) S.M. Okulova "Programming in algorithms," I found a description of a fairly simple and fairly effective algorithm. It uses the so-called “sieve method” (an example is the well-known “Erastophen sieve” - the classical problem of finding primes). We consider a finite set of all possible numbers and every move excludes all elements of the set that are of no interest.
Let's start with the data structures. Pascal code:
Initialization:
The function that implements the analysis of the element set for the values ​​of variables (bk, kr - bulls and cows)
so after each of our moves we launch a sieve
In conclusion, we can say that the algorithm is memory-intensive and, compared to standard algorithms, it will think “longer”, but how much simpler and fully optimized it is.
Well, that's all, not at all difficult. My first article to judge strictly.
As promised, a link to my toy from the second year to feel the “sieve” method on myself:
Bulls and cows
Back in the fall of the 2nd year as a laboratory work on the Theory of Automata, the teacher thought up tasks for us on the move, orienting ourselves to our wishes in the assessment. These were mostly games. Someone got hockey, someone got tennis, but I did not get the well-known logic game "Bulls and Cows . "
It was necessary to implement at least some reasonable behavior of the computer in a game with a person. But I went further and already after a month the computer in most cases easily beat my classmates. And on the subject was received automatic. Get the program after the description of the algorithms.
The essence of the game
The player and computer guess four-digit numbers using numbers from 0 to 9 . Players try to figure out the opponent’s numbers by sending him possible numbers, in return, receiving two numbers - the number of "bulls" and the number of "cows . " What are these numbers like?
- "Bulls" - the right numbers in the right places. Four "bull" - a pledge of victory, the dream of every farmer.
- “Cows” are the right numbers in the wrong places.
For understanding, I will give an example:
The number 1622 is made . If we assume 6112 , then the answer will come: 1 bull (fourth digit “2” in its place), 2 cows (six and one not in their places).
Using data about the "cattle" of the enemy, you need to guess the number faster than him.
')
The first trivial algorithm that suggests itself is to iterate over the sets “1111”, “2222”, “3333” ... until the complete set is obtained, and then to generate displacements of this set.
For example, the same number is made up in 1622 , we assume “1111” , we get “bull” in response, then “2222” - we get in response already 2 “bulls” , “3333” is empty, “4444” is empty, “5555” - it is empty, "6666" - 1 bull .
We will not continue further, since there are already 4 bulls in total. It remains to find the right combination. We will generate permutations until we get Ta-daaam: “1226”, “1262”, “1226”, “1262”, “1622” . Everything.
Obviously, the algorithm is not very good, but it is understandable and not confused. The maximum number of guesses for guessing is 10 (“7890”) + 24 permutations. 34 is the worst case. Of course, it is possible to optimize brute force and permutations, for example, iterate alternately from two ends - “1111”, “0000”, “2222”, “9999” ... also optimize the generation of permutations in the presence of identical numbers (as in our example - several times ask the same thing).
But we will not do it. Let this strategy be with us an easy level of computer complexity.
I sat a lot on pairs and played with myself, trying to come up with some kind of a cool algorithm. But only individual ideas came from which I could not make a single strategy. He began to study literature. I came across articles, sort of "guessing in 7 moves." They did not attract me, because there is a lot of branching. But after reading the book of our Kirov professor (but not from our university) S.M. Okulova "Programming in algorithms," I found a description of a fairly simple and fairly effective algorithm. It uses the so-called “sieve method” (an example is the well-known “Erastophen sieve” - the classical problem of finding primes). We consider a finite set of all possible numbers and every move excludes all elements of the set that are of no interest.
For example, for the hidden number 1234 we assumed 5678 , and got 0 bulls and 0 cows , what to think - we exclude all numbers containing 5, 6, 7, 8 . You can immediately estimate how much will be taken from 10,000. Do not be afraid of the multitude of 10,000 elements. For 5-6 moves, only a few numbers will remain.
Let's start with the data structures. Pascal code:
Const Pmax=10000; Type Post=string[4]; Var A:array[1..Pmax] of Post; // B:array[1..Pmax] of boolean; // , 1 - , 0 - Initialization:
t:=1; for i:=0 to 9 do for j:=0 to 9 do for k:=0 to 9 do for l:=0 to 9 do begin a[t]:=inttostr(i)+inttostr(j)+inttostr(k)+inttostr(l); // inc(t); end; for i:=1 to pmax do b[i]:=true; // The function that implements the analysis of the element set for the values ​​of variables (bk, kr - bulls and cows)
function pr(a,b:post;bk,kr:integer):boolean; //b - , a- "" var i,x:integer; begin x:=0; for i:=1 to 4 do // if a[i]=b[i] then inc(x); if x<>bk then begin pr:=false; exit; end; x:=0; for i:=1 to 4 do // if (a[i]<>b[i]) and (pos(b[i],a)<>0) then inc(x); if x<kr then begin pr:=false; exit; end; pr:=true; end; so after each of our moves we launch a sieve
for i:=1 to Pmax do if b[i] and not pr(a[i],hod,bk,kr) then b[i]:=false; In conclusion, we can say that the algorithm is memory-intensive and, compared to standard algorithms, it will think “longer”, but how much simpler and fully optimized it is.
Well, that's all, not at all difficult. My first article to judge strictly.
As promised, a link to my toy from the second year to feel the “sieve” method on myself:
Bulls and cows
Source: https://habr.com/ru/post/148846/
All Articles