Programming the Tree of Times
Introduction
After reading the article TimeCoder - “Time travel and programming” [ 1, 2 ], I remembered my modest practical research in programming related to the implementation of branching worlds. One day a workmate threw an interesting problem to me, but I still could not solve it. The task of how to load the machines in production. It was clear even to a non-programmer that simple brute force was needed, but I could not think of a suitable data structure to provide a computational algorithm. The task is from the real world, so I decided to try to implement in the program the real world in the part that is required to calculate the task. Each time, in further calculations, there was a choice between two actions - there was a “creation of two new worlds” with a different solution in each. Then each world developed its own way.
Under the cut, I'll tell you how the idea developed, and how the erlang helped me. Practice is the criterion of truth!
Content
Terminology - The Tree of Times
First problems
Recall what has already been done
Convergence of worlds
Methodology
Step 1. Put the description of any state of the world in a tuple
Step 2. Describe the function that determines whether the world has reached the goal.
Step 3. Describe the function that determines whether further development of the world is necessary.
Step 4. Describe the branch function of the world.
Step 5. Describe the function of calculating the world HASH
Remaining functions
Version # 1 framework
Application of the framework №1 for solving problems
Calculation of options for issuing 120 rubles different pieces of paper
Calculation of happy tickets
Calculation of lucky tickets, attempt number 2
Task “Wolf, goat and cabbage”
Moment of humor
findings
List of used sources
')
Terminology - The Tree of Times
Golovachev calls such a presentation of the development of the history of the world - the Tree of Times or the fractal [3]. Further, the method of finding a result using this approach, I will call the "method of the Tree of Times."
The world is a list of the properties of the world and their values that determine its state.
Solution of the problem - solving the problem by the Tree of Times we know in advance the result, or the values of certain properties of the world that we want to receive. That is, the result is known to us, but the way to obtain it is unknown. Problem solving is finding a path.
The initial world is the starting point, the world from which we begin our journey in solving the problem.
The target world is the world (or, to be more precise, its state) to which we aspire in solving the problem.
The development of the world - developing the original world, we strive to achieve a target world.
The dead-end world is not a dead-end branch, but a dead-end world. This is a world whose further development will not lead to a target world.
First problems
To test the methodology, I chose a task such as picking up bills for a given amount or searching for lucky tickets. In each case, wrote a recursive result search function. Made a class that stores a copy of the world and its entire state. Possibilities to create a copy of the world, I have not yet become. The tasks are simple and the input parameter fully describes the modest world. But even on such simple tasks all the disadvantages of this approach became clear. The branches of development are expanding very quickly.
In the dream, I received an analogy with the atomic reactor and the fission of particles in it. There is a division and a chain reaction, as a result of an explosion. To prevent the explosion was not the process of division is controlled. It became clear that the process of creating new branches of worlds must be controlled, and very toughly: if the world does not lead to the desired result - we destroy it, if the world has achieved its development goal - we derive the result. The output of the result showed that the way to achieve the result also needs to be controlled and destroyed the worlds with too expensive a path (issuing 1000 rubles with 10 ruble bills. Another problem was the discovery of several identical results. Different ways of the worlds development can eventually lead to the same result.
Thus, when calculating the method of the Tree of Times, the following problems should be solved:
- Limit thoughtless paralleling of realities, because resources are limited
- Analyze the path to the result if we have reached the world in a “hard” way or a way that we don’t need - do not go any further
- We must do something with duplicate results. In fact, different worlds in different ways can come to the same state - what to do about it?
The old story with the calculation of the results by the “Tree of Times” method was for the time being “in the table”. Because not all computation problems have been solved. And it is clear that it is time to use parallel computing, new, different from the programming languages I used to. But there were no easy solutions.
As time goes by, technologies in the field of programming are evolving. It became clear that it was impossible to increase megahertz infinitely. It is necessary to parallelize the calculations. And such opportunities began to appear, support for parallelism in languages began to be simplified.
But what about the clones of the worlds? Things are getting off the ground for TimeCoder articles. One must be able not only to separate the branches of the development of worlds, but also to interconnect.
Armed with new ideas and tools, I decided to return to the study of the Trees of Time.
Recall what has already been done
Task - happy tickets. Ticket will be considered happy if he has the sum of the first three digits equal to the sum of the rest.
C QT [4]:
void bilet(int x1, int x2, int x3, int x4, int x5, int x6) { // if ((x1+x2+x3)==(x4+x5+x6)) { qDebug() << x1<< x2<< x3<< x4<< x5<< x6; } // if((x1+1)<3) bilet(x1 + 1, x2, x3, x4, x5, x6); if((x2+1)<10) bilet(x1, x2 + 1, x3, x4, x5, x6); if((x3+1)<10) bilet(x1, x2, x3 + 1, x4, x5, x6); if((x4+1)<10) bilet(x1, x2, x3, x4 + 1, x5, x6); if((x5+1)<10) bilet(x1, x2, x3, x4, x5 + 1, x6); if((x6+1)<3) bilet(x1, x2, x3, x4, x5, x6 + 1); } // bilet(0, 0, 0, 0, 0, 0); I did not wait for the result. Long. Therefore, part of the code removed:
void bilet(int x1, int x2, int x3, int x4, int x5, int x6) { // if ((x1+x2+x3)==(x4+x5+x6)) { qDebug() << x1<< x2<< x3<< x4<< x5<< x6; } // if((x1+1)<3) bilet(x1 + 1, x2, x3, x4, x5, x6); if((x6+1)<3) bilet(x1, x2, x3, x4, x5, x6 + 1); } The result was as follows:
000000 200002 100001 200002 200002 100001 200002 200002 200002 The algorithm has not been subjected to any optimization. Especially not thought out. And the result is appropriate - doubles.
The task is to exchange money. Let there be bills of 1000, 500, 100, 50, 10 rubles. It is necessary to calculate the options for issuing.
Erlang Solution [5,6]: File <i> we01.erl </ i>:
-module(we01). -export([sum_money/6, sum_money/1]). sum_money(Itog) -> sum_money(Itog, 0, 0, 0, 0, 0). sum_money(Itog, X1000, X500, X100, X50, X10) -> if ((X1000 + X500 + X100 + X50 + X10) > 100) -> ok; (Itog == ((1000*X1000)+(500*X500)+(100*X100)+(50*X50)+(10*X10))) -> io:format("Itog(~w)(~w) = 1000*~w + 500*~w + 100*~w + 50*~w + 10*~w ~n", [Itog,(X1000 + X500 + X100 + X50 + X10), X1000, X500, X100, X50, X10]); (Itog > ((1000*X1000)+(500*X500)+(100*X100)+(50*X50)+(10*X10))) -> sum_money(Itog, 1+X1000, X500, X100, X50, X10), sum_money(Itog, X1000, 1+X500, X100, X50, X10), sum_money(Itog, X1000, X500, 1+X100, X50, X10), sum_money(Itog, X1000, X500, X100, 1+X50, X10), sum_money(Itog, X1000, X500, X100, X50, 1+X10); (true) -> ok end. How to run this file on Erlang?
- Run the Erlang:
erl - Compile the module:
c(we01). - We start the calculation of issue for 120 rubles:
we01:sum_money(120). - Result:
Itog(120)(3) = 1000*0 + 500*0 + 100*1 + 50*0 + 10*2 Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2 Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2 Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(3) = 1000*0 + 500*0 + 100*1 + 50*0 + 10*2 Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2 Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(3) = 1000*0 + 500*0 + 100*1 + 50*0 + 10*2 Itog(120)(4) = 1000*0 + 500*0 + 100*0 + 50*2 + 10*2 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(8) = 1000*0 + 500*0 + 100*0 + 50*1 + 10*7 Itog(120)(12) = 1000*0 + 500*0 + 100*0 + 50*0 + 10*12 ok ^ | +----
Obviously, it is necessary to somehow ignore duplicates (identical worlds). The brain, trained on correct programming, immediately starts thinking about how to optimize the algorithm so that this does not happen, optimization, optimization ... In fact, this is a very simple example, but even here it becomes difficult to come up with optimization. And what will happen in more complex worlds? In general, if there is such a possibility, then obviously unnecessary worlds do not have to be produced, in all other cases it is necessary to invent methods for the convergence of worlds.
Convergence of worlds
Let us try to check if there is such a person in the world. If there is, then nothing else to do (do not create child worlds).
So, QT, the task is again the same - tickets:
QHash hash; // void bilet(int x1, int x2, int x3, int x4, int x5, int x6) { int result = x1*100000+x2*10000+x3*1000+x4*100+x5*10+x6; if(hash.contains(result)) { // . //qDebug() << x1<< x2<< x3<< x4<< x5<< x6 << "skip"; return; } else { //. hash.insert(result, ((x1+x2+x3)==(x4+x5+x6))); } // if ((x1+x2+x3)==(x4+x5+x6)) { //, //qDebug() << x1<< x2<< x3<< x4<< x5<< x6 << "*"; } else { //, //qDebug() << x1<< x2<< x3<< x4<< x5<< x6; } // if((x1+1)<10) bilet(x1 + 1, x2, x3, x4, x5, x6); if((x2+1)<10) bilet(x1, x2 + 1, x3, x4, x5, x6); if((x3+1)<10) bilet(x1, x2, x3 + 1, x4, x5, x6); if((x4+1)<10) bilet(x1, x2, x3, x4 + 1, x5, x6); if((x5+1)<10) bilet(x1, x2, x3, x4, x5 + 1, x6); if((x6+1)<10) bilet(x1, x2, x3, x4, x5, x6 + 1); } To analyze what worlds we fall into, we will review the conclusion, if we have found it and if we have not. In all conditions, replace <10 by <2 to limit the amount of computation. We start. Result:
Result
start "00:19:04.394" 0 0 0 0 0 0 * 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 * 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 * 1 1 0 1 1 1 1 1 0 1 0 1 * 1 1 0 0 1 0 1 1 0 0 1 1 * 1 1 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 * 1 0 1 1 1 1 1 0 1 1 0 1 * 1 0 1 0 1 0 1 0 1 0 1 1 * 1 0 1 0 0 1 1 0 0 1 0 0 * 1 0 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 0 * 1 0 0 0 1 1 1 0 0 0 0 1 * 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 * 0 1 1 1 1 1 0 1 1 1 0 1 * 0 1 1 0 1 0 0 1 1 0 1 1 * 0 1 1 0 0 1 0 1 0 1 0 0 * 0 1 0 1 1 0 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0 * 0 1 0 0 1 1 0 1 0 0 0 1 * 0 0 1 0 0 0 0 0 1 1 0 0 * 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 0 * 0 0 1 0 1 1 0 0 1 0 0 1 * 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 1 end "00:19:04.407" In general, lines 64, that is 2 ^ 6, that is, true. In full, the algorithm works quickly, approximately 155ms. Parallelizing using QtConcurect offhand failed.
And what about Erlang?
The task is the same - busting tickets. But there are no global variables in Erlang.
We will have a process as storage.
% ( , ) world_server(World_list) -> receive finished -> io:format("World server is down~n", []); list -> io:format("World list ~w ~n", [World_list]), world_server(World_list); {new_world, PID, New_world, Par} -> % case lists:keymember(New_world, 1, World_list) of true -> PID ! world_exist, world_server(World_list); % false -> PID ! world_new, world_server([{New_world, Par}|World_list]) % end end. world_server_start() -> register(ws, spawn(?MODULE, world_server, [[]])). world_server_stop() -> ws ! finished. How does it work
To start the server, the
Getting into a function, we essentially get into the world. And the first thing we do is check its existence - send a request to the server-storage of worlds. If you received the answer
world_server_start() function is world_server_start() . It runs the world_server function in a new thread and associates it with the name ws . The function calls itself recursively, and passes a list of worlds as a parameter. Initially, it is passed to [] , that is, an empty array. During operation, the function waits all the time for messages from other processes:- If a message is received - the atom is
finished, then the function displays a message about stopping and does not call itself recursively, thereby the server stops. - If a message is received - the atom
list, then a list of worlds is displayed and work continues (used for debugging) - If the tuple
{new_world, PID, New_world, Par}then this means that the server is asked if there is such a world in the list? If there is a world, then the process returns the messageworld_existorworld_new, and the function is performed further with the addition of a new world to the list (if there isn’t already).
Getting into a function, we essentially get into the world. And the first thing we do is check its existence - send a request to the server-storage of worlds. If you received the answer
world_exist , then do not work further (return ok ). Otherwise, we display information about the world (with an asterisk, if it is a target, the ticket is happy). new_ww(X1, X2, X3, X4, X5, X6) -> ws ! {new_world, self(), X1*10+X2*100+X3*1000+X4*10000+X5*100000+X6*1000000, (X1+X2+X3 == X4+X5+X6) }, receive world_exist -> ok; world_new -> if (X1+X2+X3 == X4+X5+X6) -> io:format("~w ~w ~w ~w ~w ~w *~n", [X1, X2, X3, X4, X5, X6]); true-> io:format("~w ~w ~w ~w ~w ~w ~n", [X1, X2, X3, X4, X5, X6]) end, if ((X1+1) < 10) -> new_ww(X1+1, X2, X3, X4, X5, X6); true -> ok end, if ((X2+1) < 10) -> new_ww(X1, X2+1, X3, X4, X5, X6); true -> ok end, if ((X3+1) < 10) -> new_ww(X1, X2, X3+1, X4, X5, X6); true -> ok end, if ((X4+1) < 10) -> new_ww(X1, X2, X3, X4+1, X5, X6); true -> ok end, if ((X5+1) < 10) -> new_ww(X1, X2, X3, X4, X5+1, X6); true -> ok end, if ((X6+1) < 10) -> new_ww(X1, X2, X3, X4, X5, X6+1); true -> ok end end. What do we get from the new technologies in the form of Erlang? Nothing yet:
- counts longer than C ++ QT
- There are no parallelization and multi-machine calculations.
- There is no elegant and compact code inherent in the OP, instead the sheets of the same type of code
- In general, the recursive function solved a simple enumeration of values, which is solved in cycles more easily and clearly in procedural languages. not everyone understands and loves recursion
What to do? Need a methodology! Simple, step by step, understandable even to the student.
Methodology
After the experiments, I came to the conclusion that certain parts of the code are the same for any calculations, only the conditions change. Therefore, when setting the task and programming it, you can completely withdraw from recursion, parallelization, and other technical tricks and focus on setting the conditions for the calculation. That is, create a framework for calculation. In erlang methodologies, this is called behavior. The bottom line is that to implement, for example, a server, you need to implement its behavior: what to do when starting, stopping, etc.
What does this give? Each behavior is one simple and clear function. Pure function, the result of which depends only on the input data. It can be checked independently of others.
Thus, the version 1 framework has appeared. In order to solve the problem, you need to go through the steps
Step 1. Put the description of any state of the world in a tuple
An important point in programming Time Trees computing is agreement on how to store the description of the world. What is called "the matrix of the world" in science fiction. The description of the world contains information about the state of the world at the moment, but only what is required.
In my earlier studies on the Time Trees, I tried to use classes and fields, but programming for each individual task forced me to do a lot of code that quickly ceased to be comprehensible and universal. Therefore, it is necessary to describe the world as simply as possible.
Agreement describing the world: the world should be described by one tuple.
A tuple is a set of values of limited length. The tuple is limited to curly braces, and the elements of the tuple are separated from each other by commas. Tuples can be nested in each other.
Example 1. A tuple describing the state of the world at the initial moment of time when calculating variants of lucky tickets.
{0,0,0,0,0,0} Each digit is a separate digit in the ticket number.
It would be more correct to write not “at the initial moment of time”, but “at the initial state of the world”, because time does not matter for this world. Only the state of the world matters. If time in the form in which we are accustomed to understand it, will have a value for calculations, it will be added as another value in the tuple.
Example 2. A tuple describing the state of the world in which we found a way to issue 120 rubles in the form of 1x100p and 2x10p . We have five types of banknotes: 1000, 500, 100, 50, 10. Therefore, the world will have five parameters. It was decided that they will follow from the biggest to the smallest, that is, the first number is the number of 1,000 rubles, etc.
{0,0,1,0,2} Step 2. Describe the function that determines whether the world has reached the goal.
Functions as a parameter is passed to the world. Its task is to determine whether it is targeted. If yes, then print the result and return
true . Otherwise false . Step 3. Describe the function that determines whether further development of the world is necessary.
Functions as a parameter is passed to the world. Its task is to determine whether it is necessary to further develop it. If the further development of the world cannot lead to a goal, then it does not make sense to develop it further. Dead-end branch. If development is needed, return
true . Otherwise false . At the same time, if the further development of the world is a dead end, this does not mean that the world cannot be targeted.Step 4. Describe the branch function of the world.
The development of the world can go in different directions. Functions as a parameter is passed to the world. In response, a list of worlds in which you can evolve from a given world.
Step 5. Describe the function of calculating the world HASH
By default, the world HES calculation function is as follows:
%% w2hash(Wrld) -> erlang:phash2(Wrld). The standard
erlang:phash2 function erlang:phash2 a hash number for the passed tuple. But the exact correspondence of one world to another is not always required. About it is written in the articles [1, 2], the point is that regardless of which intermediate decisions were made, you can come to the same result and the branches of development will converge. Worlds will not converge “up to the atom,” but will converge in the context of solving the problem. If the task is to get to work by car, then you can come along different roads, but at 12 o'clock we will be at the meeting. The difference, of course, will be in the mileage of the car, but this moment does not matter for us.The convergence of worlds in the framework №1 is implemented through the repository of already created worlds. Rather, the hash numbers of these worlds. And if the world into which we fell during the development of a branch already exists in the repository, then the further development of the world does not occur. In essence, the worlds are converging, because the two paths of development of the worlds came to the same result, and further they went the same way. Therefore, if some of the parameters of the world do not affect the result, then you need to correct the function of calculating the world’s hash so that this parameter does not participate in the tuple-> hash number conversion.
Remaining functions
Functions such as brute force, worlds, convergence of worlds, for any task will be the same. They will be included in the framework and it is not necessary for the user to change / understand them. And if you strictly adhere to the methodology, then the framework can be improved in terms of parallel computing, without changing the functions that set the rules of the world.
Version # 1 framework
wf1.erl
-module(wf1). -export([start/0, stop/0, br/1, is_target/1, is_dead/1, ent/1, lib/0]). %% w2hash(Wrld) -> erlang:phash2(Wrld). %% lib() -> lib([]). lib(List) -> receive stop -> ok; {Wrld, Pid} -> WHash = w2hash(Wrld), NewList = case lists:member(WHash, List) of false -> Pid ! ok, [WHash]++List; true -> Pid ! exist, List end, lib(NewList); _ -> ok end. ent([]) -> ok; %% , Wrld %% Tail ent([Wrld|Tail]) -> try spawn(?MODULE, ent, [Wrld]) of _Pid -> ent(Tail) catch _:_ -> io:format("spawn overload~n", []), ent(Wrld), ent(Tail) end; %% ent(Wrld) -> lib_srv ! {Wrld, self()}, %% receive ok -> is_target(Wrld), %% Is_dead = is_dead(Wrld), %% if (Is_dead==false) -> %% - NewBranches = br(Wrld), ent(NewBranches); true -> ok end; exist -> ok end. stop() -> lib_srv ! stop. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% , %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% ? is_target(Wrld) -> true. %% - is_dead(Wrld) -> false. %% br(Wrld) -> []. %% start() -> register(lib_srv, spawn(?MODULE, lib, [])), io:format("start~n", []), %% [] spawn(?MODULE, ent, [[]]). Application of the framework №1 for solving problems
Calculation of options for issuing 120 rubles different pieces of paper
Step 1 - Lay the world in a tuple
The world is described in five digits.
{0,0,0,0,0} Step 2. Describe the function that determines whether the world has reached the goal.
%% ? is_target(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, if ((X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)==120) -> io:format("120 (~w) = 1000p*~w 500p*~w 100p*~w 50p*~w 10p*~w~n", [X1000+X500+X100+X50+X10,X1000,X500,X100,X50,X10]); true -> ok end, (X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)==120. A quick note on the Erlang syntax. The very first operation is not assignment, but matching. The
Wrld variable Wrld tuple with five elements. During the operation, the values of the elements in the tuple are assigned to the variables X1000, X500, X100, X50, X10 . For more information about matching in Erlang, please read on your own. Or just accept this syntax as a way to pull values from a tuple.Step 3. Describe the function that determines whether further development of the world is necessary.
%% - is_dead(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, (X1000*1000 + X500*500 + X100*100 + X50*50 + X10*10)>120. Step 4. Describe the branch function of the world.
%% br(Wrld) -> {X1000,X500,X100,X50,X10} = Wrld, [ {X1000+1,X500,X100,X50,X10}, {X1000,X500+1,X100,X50,X10}, {X1000,X500,X100+1,X50,X10}, {X1000,X500,X100,X50+1,X10}, {X1000,X500,X100,X50,X10+1} ]. Run the calculation
%% start() -> register(lib_srv, spawn(?MODULE, lib, [])), io:format("start~n", []), %% [] spawn(?MODULE, ent, [{0,0,0,0,0}]). As a result, received:
1> c(wf1). {ok,wf1} 2> wf1:start(). start <0.455.0> 120 (3) = 1000x0 500x0 100x1 50x0 10x2 120 (4) = 1000x0 500x0 100x0 50x2 10x2 120 (8) = 1000x0 500x0 100x0 50x1 10x7 120 (12) = 1000x0 500x0 100x0 50x0 10x12 Calculation of happy tickets
Step 1 - Lay the world in a tuple
The world is described in six digits.
{0,0,0,0,0,0} Step 2. Describe the function that determines whether the world has reached the goal.
%% ? is_target(Wrld) -> {X1,X2,X3,X4,X5,X6} = Wrld, if ((X1+X2+X3)==(X4+X5+X6)) -> cnt_srv ! inc, cnt_srv ! {cnt, self()}, receive X -> ok end, io:format("~w ~w ~w ~w ~w ~w (~w)~n", [X1,X2,X3,X4,X5,X6, X]); true -> ok end, ((X1+X2+X3)==(X4+X5+X6)). Step 3. Describe the function that determines whether further development of the world is necessary.
%% - is_dead(Wrld) -> {X1,X2,X3,X4,X5,X6} = Wrld, if (X1>9)-> true; (X2>9)-> true; (X3>9)-> true; (X4>9)-> true; (X5>9)-> true; (X6>9)-> true; true -> false end. Step 4. Describe the branch function of the world.
%% br(Wrld) -> {X1,X2,X3,X4,X5,X6} = Wrld, [ {X1+1,X2,X3,X4,X5,X6}, {X1,X2+1,X3,X4,X5,X6}, {X1,X2,X3+1,X4,X5,X6}, {X1,X2,X3,X4+1,X5,X6}, {X1,X2,X3,X4,X5+1,X6}, {X1,X2,X3,X4,X5,X6+1} ]. To count the number of lucky tickets, we will create another server that will store, increase, and return the number of found worlds with a positive result:
%%- cnt() -> cnt(0). cnt(N) -> receive inc -> cnt(N+1); {cnt,Pid} -> Pid ! N, cnt(N) end. When starting the calculation, we start it too:
%% start() -> register(lib_srv, spawn(?MODULE, lib, [])), register(cnt_srv, spawn(?MODULE, cnt, [])), io:format("start~n", []), %% [] spawn(?MODULE, ent, [{0,0,0,0,0,0}]). But if you set the rules in this way, you will have to wait a long time for the result. There are so many processes created that the Erlang node stops cope with so many and stops creating new processes. And this is good, because I had to find a solution to this problem (through try).
It is obvious that the branching of the worlds is not set in the best way and it turns out that the same worlds are created many times, constantly there are checks and it turns out that there have already been worlds. This suggests that the brain will have to be used in such resource-intensive tasks.
Calculation of lucky tickets, attempt number 2
Solving the problem of happy tickets turned out to be a very useful activity. In the process of solving, a number of very important nuances were clarified in each step, demanding an adjustment of the main worlds processing cycle. And even revealed the need for step number 5 (which was not originally).
The last attempt to solve the problem with tickets showed us that we did not effectively branch out the worlds, which resulted in a large number of duplicates. But there is no problem to calculate all the options for the development of the world right from the initial state. But we have the same Erlang, so we will do it recursively, by dividing the segment in half. We will have a segment from 0 to 999999, we will divide it until the boundaries of the ranges coincide. Therefore, the properties of the world will be two more: add the left and right border. At the same time, these boundaries are needed only for the recursive function of computing the list of worlds and are not affected by the result. Moreover, dividing the segment in half, we have an integer and somewhere in the algorithm I made a mistake, which gives us the same worlds in different segments. Therefore, an adjustment of the world hash calculation is required.
Step 1 - Lay the world in a tuple
The first two parameters are the range. The rest - as before - the numbers.
{0,999999,0,0,0,0,0,0} Step 2. Describe the function that determines whether the world has reached the goal.
%% ? is_target(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, if ((X1+X2+X3)==(X4+X5+X6)) -> cnt_srv ! inc, cnt_srv ! {cnt, self()}, receive X -> ok end, io:format("~w ~w ~w ~w ~w ~w (~w)~n", [X1,X2,X3,X4,X5,X6, X]); true -> ok end, ((X1+X2+X3)==(X4+X5+X6)). Step 3. Describe the function that determines whether further development of the world is necessary.
The development of worlds in this version of the calculation is not assumed, because we immediately know all the options for development. That is, development has only one step - the very first step, when the range 0 - 999999 is indicated. When we have a range decomposed into the list, the development of the world should no longer be. The world is always a dead end, except for the first step.
%% - is_dead(Wrld) -> {St_d,En_d,_X1,_X2,_X3,_X4,_X5,_X6} = Wrld, (St_d == En_d). Step 4. Describe the branch function of the world.
%% br(Wrld) -> {St_d,En_d,X1,X2,X3,X4,X5,X6} = Wrld, THalf = round((St_d + En_d) / 2), if (St_d == En_d) -> []; ((En_d - St_d) == 1) -> XX6 = En_d rem 10, XX5 = trunc((En_d rem 100)/10), XX4 = trunc((En_d rem 1000)/100), XX3 = trunc((En_d rem 10000)/1000), XX2 = trunc((En_d rem 100000)/10000), XX1 = trunc((En_d rem 1000000)/100000), [{St_d,St_d,XX1,XX2,XX3,XX4,XX5,XX6}] ++ [{En_d,En_d,XX1,XX2,XX3,XX4,XX5,XX6}]; true -> br({St_d,THalf,X1,X2,X3,X4,X5,X6}) ++ br({THalf,En_d,X1,X2,X3,X4,X5,X6}) end. Step 5. Describe the function of the world HASH
%% w2hash(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, X1*100000 + X2*10000 + X3*1000 + X4*100 + X5*10 + X6. Or you can build a tuple, but without a range
%% w2hash(Wrld) -> {_St_d,_En_d,X1,X2,X3,X4,X5,X6} = Wrld, erlang:phash2({X1,X2,X3,X4,X5,X6}). Launch
%% start() -> register(lib_srv, spawn(?MODULE, lib, [])), register(cnt_srv, spawn(?MODULE, cnt, [])), io:format("start~n", []), %% [] spawn(?MODULE, ent, [{0,999999,0,0,0,0,0,0}]). Total
In the process of execution, the program issued a list of lucky tickets, which turned out to be 55252. It turned out , hurray !!!
Single line shredding
length([ [A,B,C,D,E,F] || A <- [0,1,2,3,4,5,6,7,8,9], B<-[0,1,2,3,4,5,6,7,8,9], C<-[0,1,2,3,4,5,6,7,8,9], D <- [0,1,2,3,4,5,6,7,8,9], E <- [0,1,2,3,4,5,6,7,8,9], F <- [0,1,2,3,4,5,6,7,8,9], (A+B+C==D+E+F)]). : 16:49 , 17:23. 30 . ? . , . . . 5 . , . , , , , , , Erlang. . Erlang, . «» , , .
“, ”
“ , . , , , , . , , , . ?”
, [7].
1.
(
r — , l — ) — , , , , ([] — ). ? , . {{ded,r},{koza,r},{volk,r},{kapusta,r},[]} 2. ,
%% ? is_target(Wrld) -> {{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld, if ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)) -> cnt_srv ! inc, cnt_srv ! {cnt, self()}, receive X -> ok end, io:format("~w) movs=~w ~w ~n", [X, length(History),History]); true -> ok end, ((DedBereg==r) and (KozaBereg==r) and (VolkBereg==r) and (KapustaBereg==r)). , — .
3. ,
%% - is_dead(Wrld) -> {{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld, if (length(History) > 8) -> true; ((KozaBereg==VolkBereg)and(DedBereg/=KozaBereg)) -> true; %% , ((KozaBereg==KapustaBereg)and(DedBereg/=KozaBereg)) -> true; %% , true -> false end. -, .
, ( ), .
, ( ), .
.
4.
, . . — .
, ( ):
na_drugoi_bereg(l) -> r; na_drugoi_bereg(r) -> l. Build a list of development options for the transferred world. But before that we add the transferred world to the list - history. We need to know the way in which we came to the result.
%% br(Wrld) -> {{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},History} = Wrld, NewHistory = History ++ [{{ded,DedBereg},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg}}], %% , %% , %% , %% - , if (DedBereg==KozaBereg) -> Variant1 = {{ded,na_drugoi_bereg(DedBereg)},{koza,na_drugoi_bereg(KozaBereg)},{volk,VolkBereg},{kapusta,KapustaBereg},NewHistory}; true -> Variant1 = [] end, %% - , if (DedBereg==VolkBereg) -> Variant2 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,na_drugoi_bereg(VolkBereg)},{kapusta,KapustaBereg},NewHistory}; true -> Variant2 = [] end, %% - , if (DedBereg==KapustaBereg) -> Variant3 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,VolkBereg},{kapusta,na_drugoi_bereg(KapustaBereg)},NewHistory}; true -> Variant3 = [] end, %% - - Variant4 = {{ded,na_drugoi_bereg(DedBereg)},{koza,KozaBereg},{volk,VolkBereg},{kapusta,KapustaBereg},NewHistory}, %% [Variant1]++[Variant2]++[Variant3]++[Variant4]. Step 5. Describe the function of calculating the HES of the
world. The standard HASH in the world is quite suitable for us.
%% w2hash(Wrld) -> erlang:phash2(Wrld). And if we calculate only the hash of the final world? Yes, we don’t need it. The result we already know - all on the right bank. The path is important to us - the value of the array of history. Therefore, before calculating the hash of the world, there is no point in removing something from it.
Launch
%% start() -> register(lib_srv, spawn(?MODULE, lib, [])), register(cnt_srv, spawn(?MODULE, cnt, [])), io:format("start~n", []), %% [] spawn(?MODULE, ent, [{{ded,l},{koza,l},{volk,l},{kapusta,l},[]}]). Analysis of the result
There were several options for solving the problem, in a given number of movements of the grandfather across the river. Among them, the shortest solutions are in 7 movements. There are two such solutions, as they are written in the article [ 7 ].
1) movs=7 [ {{ded,l},{koza,l},{volk,l},{kapusta,l}}, - {{ded,r},{koza,r},{volk,l},{kapusta,l}}, - {{ded,l},{koza,r},{volk,l},{kapusta,l}}, - {{ded,r},{koza,r},{volk,r},{kapusta,l}}, - {{ded,l},{koza,l},{volk,r},{kapusta,l}}, - {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - {{ded,l},{koza,l},{volk,r},{kapusta,r}}] - , 5) movs=7 [ {{ded,l},{koza,l},{volk,l},{kapusta,l}}, - {{ded,r},{koza,r},{volk,l},{kapusta,l}}, - {{ded,l},{koza,r},{volk,l},{kapusta,l}}, - {{ded,r},{koza,r},{volk,l},{kapusta,r}}, - {{ded,l},{koza,l},{volk,l},{kapusta,r}}, - {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - {{ded,l},{koza,l},{volk,r},{kapusta,r}}] - , Other options require more movement, but it is obvious that these
2) movs=9 [ {{ded,l},{koza,l},{volk,l},{kapusta,l}}, - {{ded,r},{koza,r},{volk,l},{kapusta,l}}, - {{ded,l},{koza,r},{volk,l},{kapusta,l}}, - {{ded,r},{koza,r},{volk,r},{kapusta,l}}, - {{ded,l},{koza,l},{volk,r},{kapusta,l}}, - {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - {{ded,l},{koza,l},{volk,r},{kapusta,l}}, - {{ded,r},{koza,l},{volk,r},{kapusta,r}}, - {{ded,l},{koza,l},{volk,r},{kapusta,r}}] - Moment of humor
Picture - an illustration of the Tree of Times method The
American version of the problem about a wolf, a goat and a cabbage
findings
, , , erlang, , . .
.
. , , .. ( « »), , . , brute force .
. erlang pool.
№2 , , . , AI . . , AI , , .
1. — habrahabr.ru/post/150300
2. 2: — habrahabr.ru/post/178959
3. —
4. qt-project.org
5. Erlang — rsdn.ru/article/erlang/GettingStartedWithErlang.xml
6. www.erlang.org
7. “, ” — suhin.narod.ru/mat4.htm
8. Constraint programming — en.wikipedia.org/wiki/Constraint_programming
9. — ru.wikipedia.org/wiki/__
10. — .
11. — ru.wikipedia.org/wiki/___
Ps. !
—
—
—
Source: https://habr.com/ru/post/217031/
All Articles