Entertaining task “Unlucky ticket” (Elixir edition)

I could not get past the post about the 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 sort through all the options algorithmically . I wanted to solve this problem using Elixir .

If you are interested in what came of this or even install and repeat, then I ask you under cat.

After installing Elixir, we go into the runtime environment:

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, for example, as a string, into a variable

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

Now, you need to somehow parse this string into pieces. First we transform the row "123456"into an array of rows of but one character - ["1", "2", "3", "4", "5", "6"], and after, each element of the array has an integer transform: [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]

Channels are easy to understand. At each stage of processing, a function is put, but the input data is supplied to the first parameter of the function. So, in the applicable case, the called function String.splithas 3 parameters, but the first will be substituted 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 substituted automatically. The second parameter is nothing to worry about. It indicates the function that will be called to convert each element of the array. Only a 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, dare numbers:

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

Without hesitation, we come to the conclusion that to completely enumerate all the options for signs and brackets, you need to use the Polish notation . It follows from this that for the solution we need to sort out all permutations of 3 out of 3 numbers. And iterate over all variants of two of the four operators, which we decide to use for now ( "+", "-", "*", "/").

Now we need to find a function that will give us all the permutations. A short search returns the result on rosettacode . We create (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

We 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 just what we need. Now we are looking for an algorithm for calculating combinations. Somewhere in the open spaces 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. We check:

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

Great, move on. Now we need to multiply these two arrays. So that to each element of the first, the second is assigned. As it turned out, this is called the Cartesian product of sets . On 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 sort through all the combinations, then ... we begin to sort through them! The 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 the 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 by all variants of the sequences of operations, and we 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:

iex(24)> length(vari1)
36

Now we would like to learn how to count expressions in the Polish notation. To do this, add a little more code to the same perm.ex file. First, we learn how to perform an operation on two numbers
Initially, I will call the function with a single parameter, and this parameter is a tuple of two elements {операции, числа}. By the number of parameters, using the function matching mechanism, a single function will be selected. In it, the values ​​from the tuple will be “rolled up” into two variables opsand a stackfunction with two parameters will be called. In Elixir, as in Erlang, instead of ifandelse if, Matching is used in the function, according to the value of the incoming parameters. Moreover, the function that is described earlier will work. In our case, until the first parameter has an 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 with 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, calс is called with three parameters (a function and two numbers). When doing the division by zero, we get an error. Therefore, before the function for performing the division, instead of the conditions, we add a function that, by means of matching, “catches” zero at the input of the divider and gives the atom: err as the result. Accordingly, before all operations, we add a match for the fact that the first or second option can be: err, in which 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, using the construction already familiar to us, we multiply combinations of the left side of the number and the right.

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

We get a very long output, shortened by a virtual machine. We filter so that only equalities of the left and right sides are deduced

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 side (4 + 6) / 5 = 2. That's right, only the Polish notation is not convenient for humans. Convert by adding a little 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 transformation to 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 can be improved here (remove duplicate 666), not to 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 from the first three digits will not coincide with 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 applying Elixir. A complete solution of the task will require calculations of the entire range of ticket numbers, and here it would be possible to show the full power of Erlang \ Elixir parallel computing, but this is a topic, perhaps, for a separate article, and the clock is already 02:53;)