To learn to think as a programmer, you must learn to think like a non-programmer.
This is like an answer to the lxsmkv article “The Task of Crossing” . The most memorable part of that article is a huge (in comparison with the complexity of the task) table in which the model of the task is expressed.
Let's try to think of something simpler.
We have a wolf, a goat and a cabbage. They must be transported to the other side. Forwards the person (carrier). The difficulty is that the wolf eats the goat, and the goat - cabbage, if there is no person nearby. In addition, you can only ship one at a time (there is only one place for cargo in the boat).
Now we digitize the problem, that is, we represent it in the form of numbers and operations with them. We must describe the distribution of wolf, goat and cabbage along the shores (configuration) and actions with them. So, we have a verbal formulation of the conditions of the problem. I want in the model to combine the visibility of the picture with the abstractness of the number. That is, the model must be visual, to be understandable to man, and abstract, to be understandable to the machine.
')
I want to present it in such a way that it is easily understood by me and that it is easily programmable.
The most easily perceived image (at a glance). The easiest to program actions with numbers. Thus, I want my model to combine in itself the properties of both the image and the number. And the primary number, since in the future programming is assumed. That is, we need not just a certain number, but such, whose visual image will reflect the task (and the course of its solution). We depict the condition of the problem in the form of a picture. The action "eats" is represented by an arrow.
Someone will see in this picture the food chain, someone oriented graph. But all this does not matter. For us it is important that some couples are prohibited. And which pairs are determined by their position in the picture.
And if so, then it becomes completely indifferent who of them is who and who eats whom. It is important how easy it is to notice that neighboring pairs are prohibited. Consequently, the drawing can be made schematic, depicting both the wolf, and the goat, and the cabbage with the same icons.
Now we need to show the distribution of participants along the shores.
It is easy to see that the information contained in the right part of the diagram is duplicated in the left part. Indeed, the participants do not disappear from the task and do not appear again. Each of them is either on the left or on the right bank. Therefore, one right side of the scheme is enough.
Such a scheme contains all the information about any distribution of objects arising in the course of solving the problem. What kind of object is determined by the place (position) occupied by it in the diagram, and on which bank it is determined by whether the place is occupied or empty.
Now take up the numbers. All modern number systems are positional, that is, the function of a digit in a number is determined by its position in that number. That is a discharge. And each digit can have several values.
Now we associate the task object with each digit. And the values of each category we need two. Let the first rank be the cabbage, the second the goat, and the third the wolf. In each category we will need two values: 1 - starting coast, 0 - finishing coast.
It turns out that to describe any configuration we need a three-digit binary number. For example, 111 - start configuration, 000 - finish.
The same can be said about the coding of the course number. It also needs a three-digit binary number, in which the digit is the participant, and the value of the digit encodes the action (1 - to transport, 0 - not).
It remains to describe the transition from one configuration to another. For this you need to find a mathematical operation on. Then this transition can be described as:
What is this operation? Consider one of the configuration bits and the same action bit. If in this digit of action is unity, then in the discharge of configuration, the unit should change to zero and vice versa. If there is zero in the discharge of the action, then the configuration discharge remains unchanged.
You can make this table:
Obviously, this is xor. That is, the digits of configuration K are inverted by mask D.
In the end, we need to invert configuration 111 by mask 111:
Well, actually the subject-forming part of the article is over - the idea has been found. The rest is the effect.
In the previous part, an idea was formulated on which a digital model of the problem can be built. However, there are also move rules in the problem. Having formulated them with the use of the found idea, we will obtain a model of the problem and its solutions.
Rules are bans, that is, they define what cannot be done. In our case, bans can be converted to permissions. Indeed, for coding positions (configurations) and moves, we can use three-digit binary numbers:
1. The original list of configurations (moves): 000, 100, 010, 001, 110, 101, 011, 111.
2. The original list of masks (actions) is the same: 000, 100, 010, 001, 110, 101, 011, 111.
Interdictions mean that a part of these numbers cannot be used. Consequently, it is possible to use only some subsets of numbers from these lists. Find out what.
To do this, you first need to understand the role of the carrier in our model.
While he is on the shore, everything is calm, nobody eats anyone. But as soon as he swims away to the other side, the wolf eats a goat or a goat cabbage. Therefore, the admissibility of the pair is checked at the end of the turn (or after the turn) on the bank from which the turn is made.
Therefore, we need to encode the carrier in the numbers encoding the configurations and moves. To do this, add another bit. Let the unit in this discharge code carrier at the starting bank, and zero at the finish line. Moreover, it is obvious that the number encoding the move always has the highest (fourth) digit 1. That is, there are no moves without the participation of the carrier. Then the original lists of numbers will be:
1. The initial list of configurations: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111, 0000, 0100, 0010, 0001, 0110, 0101, 0011, 0111.
2. The initial list of masks: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111.
Now we use the same principle for coding the resolution / prohibition of a move or configuration (position). Add one more digit, the fifth - 1 move or configuration is allowed, 0 - is prohibited.
We now create lists of allowed moves.
You can invert only one or one category (you can only carry one passenger or sail empty). Therefore, masks can only be 1000, 1100, 1010, 1001 (this is a list of allowed moves).
We now create lists of allowed positions.
The initial configuration 1111 is forbidden (the first move cannot be empty).
Prohibited units or zeros in the adjacent digits (on the shore can not be a pair of wolf – goat and goat – cabbage).
That is, configurations 1111, 1110, 1011, 1001, 1100 are prohibited. Therefore, 1000, 1101 and 1010 are allowed.
After an odd move, the configuration of the units is checked, and after an even move, the zeros are checked (the units are objects on this bank, the zeros are on that; the odd move is moving from this bank to the even one - from that to this one).
If we want the game to end quickly, we need to limit the number of moves. Therefore, we prohibit the repetition of positions.
This rule requires that the position from which the next move is made becomes prohibited. That is, the same position can be allowed, and it can be prohibited. Therefore, it is necessary to encode the prohibition of the position. Again, we introduce an additional digit — the fifth: position is allowed — 1, position is prohibited — 0.
Obviously, the move code in this position must always contain 0, because the allowed position is not automatically prohibited, but only if the result of the move is also a valid position.
The source position code first, naturally, contains a unit in the fifth digit — it, since we are in it, is resolved.
The list of admissible positions 11000, 11101, 11010 and the list of admissible moves 01000, 01100, 01010, 01001 are finally obtained.
Now let us try to imagine what the function calculating the move (computational) should do.
The arguments for this function are:
Ref Position - starting position,
list ProhibitedPoz - list of prohibited positions,
scrollTopCode - list of valid moves.
The function must be returned by a Result.
So, the computational function should:
Well, it remains to design the main function, which will call the function Calculate with the necessary arguments and add the results to some convenient data structure, from which you can finally display the result on the screen in a human-readable form. Well, actually write the code.
At this place you can begin to think like a programmer. Those interested can do this as a homework.
Let's try to think of something simpler.
1. Condition
We have a wolf, a goat and a cabbage. They must be transported to the other side. Forwards the person (carrier). The difficulty is that the wolf eats the goat, and the goat - cabbage, if there is no person nearby. In addition, you can only ship one at a time (there is only one place for cargo in the boat).
2. Solution idea
Now we digitize the problem, that is, we represent it in the form of numbers and operations with them. We must describe the distribution of wolf, goat and cabbage along the shores (configuration) and actions with them. So, we have a verbal formulation of the conditions of the problem. I want in the model to combine the visibility of the picture with the abstractness of the number. That is, the model must be visual, to be understandable to man, and abstract, to be understandable to the machine.
')
I want to present it in such a way that it is easily understood by me and that it is easily programmable.
The most easily perceived image (at a glance). The easiest to program actions with numbers. Thus, I want my model to combine in itself the properties of both the image and the number. And the primary number, since in the future programming is assumed. That is, we need not just a certain number, but such, whose visual image will reflect the task (and the course of its solution). We depict the condition of the problem in the form of a picture. The action "eats" is represented by an arrow.
Someone will see in this picture the food chain, someone oriented graph. But all this does not matter. For us it is important that some couples are prohibited. And which pairs are determined by their position in the picture.
And if so, then it becomes completely indifferent who of them is who and who eats whom. It is important how easy it is to notice that neighboring pairs are prohibited. Consequently, the drawing can be made schematic, depicting both the wolf, and the goat, and the cabbage with the same icons.
Now we need to show the distribution of participants along the shores.
It is easy to see that the information contained in the right part of the diagram is duplicated in the left part. Indeed, the participants do not disappear from the task and do not appear again. Each of them is either on the left or on the right bank. Therefore, one right side of the scheme is enough.
Such a scheme contains all the information about any distribution of objects arising in the course of solving the problem. What kind of object is determined by the place (position) occupied by it in the diagram, and on which bank it is determined by whether the place is occupied or empty.
Now take up the numbers. All modern number systems are positional, that is, the function of a digit in a number is determined by its position in that number. That is a discharge. And each digit can have several values.
Now we associate the task object with each digit. And the values of each category we need two. Let the first rank be the cabbage, the second the goat, and the third the wolf. In each category we will need two values: 1 - starting coast, 0 - finishing coast.
It turns out that to describe any configuration we need a three-digit binary number. For example, 111 - start configuration, 000 - finish.
The same can be said about the coding of the course number. It also needs a three-digit binary number, in which the digit is the participant, and the value of the digit encodes the action (1 - to transport, 0 - not).
It remains to describe the transition from one configuration to another. For this you need to find a mathematical operation on. Then this transition can be described as:
1 = 2 What is this operation? Consider one of the configuration bits and the same action bit. If in this digit of action is unity, then in the discharge of configuration, the unit should change to zero and vice versa. If there is zero in the discharge of the action, then the configuration discharge remains unchanged.
You can make this table:
| TO | D | Code |
|---|---|---|
| one | one | 0 |
| one | 0 | one |
| 0 | one | one |
| 0 | 0 | 0 |
Obviously, this is xor. That is, the digits of configuration K are inverted by mask D.
In the end, we need to invert configuration 111 by mask 111:
111 xor 111 = 000 Well, actually the subject-forming part of the article is over - the idea has been found. The rest is the effect.
3. Rules
In the previous part, an idea was formulated on which a digital model of the problem can be built. However, there are also move rules in the problem. Having formulated them with the use of the found idea, we will obtain a model of the problem and its solutions.
Rules are bans, that is, they define what cannot be done. In our case, bans can be converted to permissions. Indeed, for coding positions (configurations) and moves, we can use three-digit binary numbers:
1. The original list of configurations (moves): 000, 100, 010, 001, 110, 101, 011, 111.
2. The original list of masks (actions) is the same: 000, 100, 010, 001, 110, 101, 011, 111.
Interdictions mean that a part of these numbers cannot be used. Consequently, it is possible to use only some subsets of numbers from these lists. Find out what.
To do this, you first need to understand the role of the carrier in our model.
While he is on the shore, everything is calm, nobody eats anyone. But as soon as he swims away to the other side, the wolf eats a goat or a goat cabbage. Therefore, the admissibility of the pair is checked at the end of the turn (or after the turn) on the bank from which the turn is made.
Therefore, we need to encode the carrier in the numbers encoding the configurations and moves. To do this, add another bit. Let the unit in this discharge code carrier at the starting bank, and zero at the finish line. Moreover, it is obvious that the number encoding the move always has the highest (fourth) digit 1. That is, there are no moves without the participation of the carrier. Then the original lists of numbers will be:
1. The initial list of configurations: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111, 0000, 0100, 0010, 0001, 0110, 0101, 0011, 0111.
2. The initial list of masks: 1000, 1100, 1010, 1001, 1110, 1101, 1011, 1111.
Now we use the same principle for coding the resolution / prohibition of a move or configuration (position). Add one more digit, the fifth - 1 move or configuration is allowed, 0 - is prohibited.
We now create lists of allowed moves.
You can invert only one or one category (you can only carry one passenger or sail empty). Therefore, masks can only be 1000, 1100, 1010, 1001 (this is a list of allowed moves).
We now create lists of allowed positions.
The initial configuration 1111 is forbidden (the first move cannot be empty).
Prohibited units or zeros in the adjacent digits (on the shore can not be a pair of wolf – goat and goat – cabbage).
That is, configurations 1111, 1110, 1011, 1001, 1100 are prohibited. Therefore, 1000, 1101 and 1010 are allowed.
After an odd move, the configuration of the units is checked, and after an even move, the zeros are checked (the units are objects on this bank, the zeros are on that; the odd move is moving from this bank to the even one - from that to this one).
If we want the game to end quickly, we need to limit the number of moves. Therefore, we prohibit the repetition of positions.
This rule requires that the position from which the next move is made becomes prohibited. That is, the same position can be allowed, and it can be prohibited. Therefore, it is necessary to encode the prohibition of the position. Again, we introduce an additional digit — the fifth: position is allowed — 1, position is prohibited — 0.
Obviously, the move code in this position must always contain 0, because the allowed position is not automatically prohibited, but only if the result of the move is also a valid position.
The source position code first, naturally, contains a unit in the fifth digit — it, since we are in it, is resolved.
The list of admissible positions 11000, 11101, 11010 and the list of admissible moves 01000, 01100, 01010, 01001 are finally obtained.
4. Calculation of moves.
Now let us try to imagine what the function calculating the move (computational) should do.
The arguments for this function are:
Ref Position - starting position,
list ProhibitedPoz - list of prohibited positions,
scrollTopCode - list of valid moves.
The function must be returned by a Result.
So, the computational function should:
= xor and ≠ 0 xor 10000 5. End
Well, it remains to design the main function, which will call the function Calculate with the necessary arguments and add the results to some convenient data structure, from which you can finally display the result on the screen in a human-readable form. Well, actually write the code.
At this place you can begin to think like a programmer. Those interested can do this as a homework.
Source: https://habr.com/ru/post/343124/
All Articles