Entertaining task “Unlucky Ticket” (Elixir edition)

I could not get past the post about an unlucky ticket . This is one of my favorite tasks. In addition, the combinations in the solution were programmed manually, and it would be interesting to iterate over all the options algorithmically . I wanted to solve this problem using Elixir .

If you're wondering what came of it or even install and repeat, then I ask you under the cat.

After installing Elixir, go to the runtime:

user@host:~/$ iex Erlang/OTP 19 [erts-8.0.2] [source-753b9b9] [64-bit] [smp:2:2] [async-threads:10] [hipe] [kernel-poll:false] Interactive Elixir (1.3.2) - press Ctrl+C to exit (type h() ENTER for help) iex(1)> 

Set the source data, say, as a string, into a variable
')

 iex(1)> data_in = "123456" "123456" 

Now, you need to somehow break this line apart. First, convert the string "123456" into an array of strings, but one character at a time - ["1", "2", "3", "4", "5", "6"] , and after that, each element we transform an array into an integer: [1, 2, 3, 4, 5, 6] . We do this using pipes ( pipe operator ):

 iex(2)> [a,b,c,d,e,f] = data_in \ ...(2)> |> String.split("", trim: true) \ ...(2)> |> Enum.map(fn(x)-> String.to_integer(x) end) [1, 2, 3, 4, 5, 6] 

The channels are easy to understand. At each stage of processing, a function is put, but input data is supplied to the first parameter of the function. So, in the applicable case, the called function String.split has 3 parameters, but the first one will be substituted with data_in . The result of this conversion will be passed to the next function Enum.map . The first parameter is again not visible, and will be automatically substituted. The second parameter is ok. It specifies the function that will be called to convert each element of the array. Only the function, we immediately identified and passed as a parameter. This is called higher order functions . We see that now in the variables a, b, c, d, e, d are numbers:

 iex(4)> a 1 iex(5)> b 2 

Without hesitation, we come to the conclusion that for a complete enumeration of all variants of signs and brackets, you need to use the Polish notation . From this it follows that in order to solve we need to go through all the permutations of 3 of 3 numbers. And go through all the options of two operators out of four that we decide to use ( "+", "-", "*", "/" ).

Now we need to find a function that will give us all the permutation options. A short search results in rosettacode . Create a (touch perm.ex) file and enter the module text into it:

 defmodule RC do def permute([]), do: [[]] def permute(list) do for x <- list, y <- permute(list -- [x]), do: [x|y] end end 

Compile:

 iex(7)> c("perm.ex") warning: redefining module RC (current version loaded from Elixir.RC.beam) perm.ex:1 [RC] 

We try:

 iex(9)> RC.permute([1, 2, 3]) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 

This is exactly what we need. Now we are looking for an algorithm for calculating combinations. Somewhere in the vast stack overflow, we find this solution. I also add it to perm.ex:

 def comb(0,_), do: [[]] def comb(_,[]), do: [] def comb(n, [x|xs]) do (for y <- comb(n - 1, xs), do: [x|y]) ++ comb(n, xs) end 

Add it to the same perm.ex file, compile it. Checking:

 iex(12)> RC.comb(2, [1,2,3,4]) [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]] 

Great, go ahead. Now we need to multiply these two arrays. So that each element of the first, put in line with the second. As it turned out, this is called the Cartesian product of sets . At Elixir, such an operation is done through comprehensions :

 iex> for i <- [:a, :b, :c], j <- [1, 2], do: {i, j} [a: 1, a: 2, b: 1, b: 2, c: 1, c: 2] 

Now that we are ready to go through all the combinations, then ... we begin to go through them! Left three digits of a number and their combinations:

 iex(14)> digs1 = RC.permute([a,b,c]) [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 

The right three digits of a number and their combinations:

 iex(14)>digs2 = RC.permute([d,e,f]) [[4, 5, 6], [4, 6, 5], [5, 4, 6], [5, 6, 4], [6, 4, 5], [6, 5, 4]] 

Now we multiply each into all variants of the sequence of operations, and we will get everything that can be done with these three numbers (left three):

 iex(19)> vari1 = for i <- ops, j <- digs1, do: {i, j} [{["+", "-"], [1, 2, 3]}, {["+", "-"], [1, 3, 2]}, {["+", "-"], [2, 1, 3]}, {["+", "-"], [2, 3, 1]}, {["+", "-"], [3, 1, 2]}, {["+", "-"], [3, 2, 1]}, {["+", "*"], [1, 2, 3]}, {["+", "*"], [1, 3, 2]}, {["+", "*"], [2, 1, 3]}, {["+", "*"], [2, 3, 1]}, {["+", "*"], [3, 1, 2]}, {["+", "*"], [3, 2, 1]}, {["+", "/"], [1, 2, 3]}, {["+", "/"], [1, 3, 2]}, {["+", "/"], [2, 1, 3]}, {["+", "/"], [2, 3, 1]}, {["+", "/"], [3, 1, 2]}, {["+", "/"], [3, 2, 1]}, {["-", "*"], [1, 2, 3]}, {["-", "*"], [1, 3, 2]}, {["-", "*"], [2, 1, 3]}, {["-", "*"], [2, 3, 1]}, {["-", "*"], [3, 1, 2]}, {["-", "*"], [3, 2, 1]}, {["-", "/"], [1, 2, 3]}, {["-", "/"], [1, 3, 2]}, {["-", "/"], [2, 1, 3]}, {["-", "/"], [2, 3, 1]}, {["-", "/"], [3, 1, 2]}, {["-", "/"], [3, 2, 1]}, {["*", "/"], [1, 2, 3]}, {["*", "/"], [1, 3, 2]}, {["*", "/"], [2, 1, 3]}, {["*", "/"], [2, 3, 1]}, {["*", "/"], [3, 1, 2]}, {["*", "/"], [3, 2, 1]}] 

And the right three:

 iex(22)> vari2 = for k <- ops, l <- digs2, do: {k, l} [{["+", "-"], [4, 5, 6]}, {["+", "-"], [4, 6, 5]}, {["+", "-"], [5, 4, 6]}, {["+", "-"], [5, 6, 4]}, {["+", "-"], [6, 4, 5]}, {["+", "-"], [6, 5, 4]}, {["+", "*"], [4, 5, 6]}, {["+", "*"], [4, 6, 5]}, {["+", "*"], [5, 4, 6]}, {["+", "*"], [5, 6, 4]}, {["+", "*"], [6, 4, 5]}, {["+", "*"], [6, 5, 4]}, {["+", "/"], [4, 5, 6]}, {["+", "/"], [4, 6, 5]}, {["+", "/"], [5, 4, 6]}, {["+", "/"], [5, 6, 4]}, {["+", "/"], [6, 4, 5]}, {["+", "/"], [6, 5, 4]}, {["-", "*"], [4, 5, 6]}, {["-", "*"], [4, 6, 5]}, {["-", "*"], [5, 4, 6]}, {["-", "*"], [5, 6, 4]}, {["-", "*"], [6, 4, 5]}, {["-", "*"], [6, 5, 4]}, {["-", "/"], [4, 5, 6]}, {["-", "/"], [4, 6, 5]}, {["-", "/"], [5, 4, 6]}, {["-", "/"], [5, 6, 4]}, {["-", "/"], [6, 4, 5]}, {["-", "/"], [6, 5, 4]}, {["*", "/"], [4, 5, 6]}, {["*", "/"], [4, 6, 5]}, {["*", "/"], [5, 4, 6]}, {["*", "/"], [5, 6, 4]}, {["*", "/"], [6, 4, 5]}, {["*", "/"], [6, 5, 4]}] 

I wonder how many options there are:

 iex(24)> length(vari1) 36 

Now we would like to learn how to count the expressions in the Polish notation. To do this, add some more code to the same perm.ex file. First, learn to perform an operation on two numbers.
Initially, I will call a function with one parameter, and as this parameter there will be a tuple of two elements: {, } . According to the number of parameters, using the mechanism of function matching, a single function will be selected. In it, the values ​​from the tuple will be “matched” into two variables, ops and stack and a function with two parameters will already be called. In Elixir, as in Erlang, instead of if and else if , matching is used in the function, according to the value of the input parameters. And, that function which is described earlier will work. In our case, while in the first parameter there is no empty array ([]), the third function will be executed. But as soon as the array is empty, the second function will work, which will give us the result. This example is a typical implementation of tail recursion. All calculations take place in the third function, where the first operation and the “tail” are taken from the array of operations. From the array of numbers, which plays the role of a stack, two numbers and a tail are selected. Then the function is called recursively until the data runs out. Implementing cycles through recursion is also a typical approach. And directly for calculations, calc is called with three parameters (a function and two numbers). When performing division by zero, we get an error. Therefore, before the function of performing the division, instead of the conditions, we add a function that, with the help of the match, “catches” the zero at the input of the divider, and yields the atom: err as a result. Accordingly, before all operations, we add a match for the fact that the first or second option may be: err, in this case the result will be the same.

  def calc({ops,stack}), do: calc(ops,stack) def calc([], stack), do: hd(stack) def calc(ops, stack) do [op|ops_tail] = ops [a,b|stack_tail] = stack calc(ops_tail, [calc(op, a, b)|stack_tail]) end def calc(_, :err,_), do: :err def calc(_, _,:err), do: :err def calc("*", a, b), do: a * b def calc("/", _, 0), do: :err def calc("/", a, b), do: a / b def calc("+", a, b), do: a + b def calc("-", a, b), do: a - b 

So, with the help of the already familiar construction, we multiply the combinations of the left side of the number and the right one.

 iex(27)> vari_all = for m <- vari1, n <- vari2, do: {m, n} 

We get a very long output, shortened by the virtual machine. We filter in such a way that only equalities of the left and right parts are output.

 iex(30)> vari_all \ ...(30)> |> Enum.filter(fn({left, right})-> RC.calc(left) == RC.calc(right) end) [{{["+", "-"], [1, 3, 2]}, {["+", "/"], [4, 6, 5]}}, {{["+", "-"], [1, 3, 2]}, {["+", "/"], [6, 4, 5]}}, {{["+", "-"], [2, 3, 1]}, {["-", "*"], [6, 5, 4]}}, {{["+", "-"], [3, 1, 2]}, {["+", "/"], [4, 6, 5]}}, {{["+", "-"], [3, 1, 2]}, {["+", "/"], [6, 4, 5]}}, {{["+", "-"], [3, 2, 1]}, {["-", "*"], [6, 5, 4]}}, {{["+", "*"], [2, 3, 1]}, {["+", "-"], [4, 6, 5]}}, {{["+", "*"], [2, 3, 1]}, {["+", "-"], [6, 4, 5]}}, {{["+", "*"], [3, 2, 1]}, {["+", "-"], [4, 6, 5]}}, {{["+", "*"], [3, 2, 1]}, {["+", "-"], [6, 4, 5]}}, ... 

From the first line we can understand that (1 + 3) -2 = 2 and the right part (4 + 6) / 5 = 2. That's right, only Polish notation is not convenient for humans. Let's transform by adding some more to perm.ex:

  def expr_to_str({ops, stack}), do: expr_to_str(ops, stack) def expr_to_str(ops, stack) do [d1, d2, d3] = Enum.map(stack, fn(x)-> Integer.to_string(x) end) [op1, op2] = ops to_string(["(", d1, op1, d2, ")", op2, d3]) end 

Add a pipe to the pipe:

 iex(37)> vari_all \ ...(37)> |> Enum.filter(fn({left, right})-> RC.calc(left) == RC.calc(right) end) \ ...(37)> |> Enum.map(fn({left, right})-> \ ...(37)> RC.expr_to_str(left) <> " = " <> \ ...(37)> RC.expr_to_str(right) \ ...(37)> end) ["(1+3)-2 = (4+6)/5", "(1+3)-2 = (6+4)/5", "(2+3)-1 = (6-5)*4", "(3+1)-2 = (4+6)/5", "(3+1)-2 = (6+4)/5", "(3+2)-1 = (6-5)*4", "(2+3)*1 = (4+6)-5", "(2+3)*1 = (6+4)-5", "(3+2)*1 = (4+6)-5", "(3+2)*1 = (6+4)-5", "(1+3)/2 = (4+6)/5", "(1+3)/2 = (6+4)/5", "(2+3)/1 = (4+6)-5", "(2+3)/1 = (6+4)-5", "(3+1)/2 = (4+6)/5", "(3+1)/2 = (6+4)/5", "(3+2)/1 = (4+6)-5", "(3+2)/1 = (6+4)-5", "(1-3)*2 = (5-6)*4", "(2-1)*3 = (4+5)-6", "(2-1)*3 = (5+4)-6", "(3-1)*2 = (6-5)*4", "(1*3)/2 = (4+5)/6", "(1*3)/2 = (5+4)/6", "(2*3)/1 = (5-4)*6", "(3*1)/2 = (4+5)/6", "(3*1)/2 = (5+4)/6", "(3*2)/1 = (5-4)*6"] 

Now we repeat the same thing for the ticket in the picture:

 iex(39)> data_in = "666013" "666013" iex(40)> [a,b,c,d,e,f] = data_in \ ...(40)> |> String.split("", trim: true) \ ...(40)> |> Enum.map(fn(x)-> String.to_integer(x) end) [6, 6, 6, 0, 1, 3] iex(41)> ops = RC.comb(2, ["+","-","*","/"]) [["+", "-"], ["+", "*"], ["+", "/"], ["-", "*"], ["-", "/"], ["*", "/"]] iex(42)> digs1 = RC.permute([a,b,c]) [[6, 6, 6], [6, 6, 6], [6, 6, 6], [6, 6, 6], [6, 6, 6], [6, 6, 6]] iex(43)> digs2 = RC.permute([d,e,f]) [[0, 1, 3], [0, 3, 1], [1, 0, 3], [1, 3, 0], [3, 0, 1], [3, 1, 0]] iex(44)> vari1 = for i <- ops, j <- digs1, do: {i, j} ... iex(45)> vari2 = for k <- ops, l <- digs2, do: {k, l} iex(46)> vari_all = for m <- vari1, n <- vari2, do: {m, n} iex(47)> vari_all \ ...(47)> |> Enum.filter(fn({left, right})-> RC.calc(left) == RC.calc(right) end) \ ...(47)> |> Enum.map(fn({left, right})-> \ ...(47)> RC.expr_to_str(left) <> " = " <> \ ...(47)> RC.expr_to_str(right) \ ...(47)> end) ["(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6+6)/6 = (0+3)-1", "(6+6)/6 = (3+0)-1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", "(6-6)*6 = (1*0)/3", "(6-6)*6 = (3*0)/1", "(6-6)*6 = (1+3)*0", "(6-6)*6 = (3+1)*0", "(6-6)*6 = (1-3)*0", "(6-6)*6 = (3-1)*0", "(6-6)*6 = (0*1)/3", "(6-6)*6 = (0*3)/1", ...] 

As you can see, the ticket is quite happy! )

Of course, something that can be improved (remove duplicate 666), do not compare the results with: err, and indeed, we did not solve the problem posed by the author initially: “Find all values ​​from 6 digits, for which none of the values ​​of the set obtained of the first three digits, does not match any value of the set of the last three digits " . But I did not set such a goal. It was more interesting to show the difference in approaches to solving problems when using Elixir. A complete solution of the task will require calculations of the entire range of ticket numbers, and here you could show the full power of parallel computing Erlang \ Elixir, but this is a topic, perhaps, for a separate article, and the clock is already 02:53;)