Я не смог пройти мимо поста о несчастливом билете. Это одна из моих любимых задач. К тому же, комбинации в решении были запрограммированы вручную, а было бы интересно перебрать все варианты алгоритмически. Мне стало интересно, а как бы я решил эту задачу, используя Elixir.

Если вам интересно, как такие задачи решаются в Elixir, или даже установить и повторить, то я прошу вас под кат.

После установки Elixir, заходим в среду выполнения:

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)>

Зададим исходные данные, допустим, в виде строки, в переменную

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

Теперь, нужно как-то разобрать эту строку на части. Сначала преобразуем строку "123456" в массив из из строк, но по одному символу — ["1", "2", "3", "4", "5", "6"], а после этого, уже каждый элемент массива преобразуем в целое число: [1, 2, 3, 4, 5, 6]. Сделаем это, используя каналы (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]

Каналы понять просто. На каждом этапе обработки ставится функция, но в первый параметр функции подаются входные данные. Так, в применяемом случае, вызываемая функция String.split имеет 3 параметра, но в первый будет подставлено data_in. Результат этого преобразования будет передан в следующую функцию Enum.map. Первый параметр — опять же не виден, и будет подставлен автоматически. Второй параметр — ничего страшного. Там указывается функция, которая будет вызываться для преобразования каждого элемента массива. Только функцию, мы сразу же определили и передали в качестве параметра. Это называется — функции высшего порядка. Видим, что теперь в переменных a, b, c, d, e, d находятся числа:

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

Не долго думая, приходим к выводу, что для полного перебора всех вариантов знаков и скобок, нужно использовать Польскую нотацию. Из этого следует, что для решения нам нужно перебрать все перестановки 3 из 3 чисел. И перебрать все варианты двух операторов из четырех, которые мы пока решим использовать ("+", "-", "*", "/").

Теперь нам нужно найти функцию, которая даст нам все варианты перестановок. Недолгий поиск выдает результат на rosettacode. Создаем (touch perm.ex) файл, и заносим в него текст модуля:

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

Компилируем:

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

[RC]

Пробуем:

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]]

Это как раз то, что нам нужно. Теперь ищем алгоритм вычисления комбинаций. Где-то на просторах stack overflow находим вот такое решение. Его тоже добавляю в 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

Добавляем его в тот же файл perm.ex, компилируем. Проверяем:

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

Отлично, идем дальше. Теперь нам нужно перемножить эти два массива. Так, чтобы каждому элементу первого, поставился в соответствие второй. Как выяснилось, это называется Декартово произведение множеств. На Elixir такая операция делается через 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]

Теперь, когда мы готовы перебрать все комбинации, то… начинаем их перебирать! Левые три цифры числа и их комбинации:

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]]

Правые три цифры числа и их комбинации:

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]]

Теперь каждой перемножим на все варианты последовательностей операций, и получим все, что можно сделать с этими тремя числами (левыми тремя):

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]}]

И правыми тремя:

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]}]

Интересно, а сколько же вариантов:

iex(24)> length(vari1)
36

Теперь нам бы хотелось научиться считать выражения в Польской записи. Для этого в тот же файл perm.ex добавляем еще немного кода. Сначала научимся выполнять операцию над двумя числами
Изначально, я буду вызывать функцию с одним параметром, и в качестве этого параметра будет кортеж из двух элементов: {операции, числа}. По количеству параметров, с помощью механизма матчинга функций, будет выбрана единственная функция. В ней, значения из кортежа будут «сматчены» в две переменных ops и stack и уже вызовется функция с двумя параметрами. В Elixir, как и в Erlang, вместо if и else if, используется матчинг в функции, по значению входящих параметров. Причем, сработает та функция, которая описана раньше. В нашем случае, пока в первом параметре не будет пустой массив ([]), будет выполняться третья функция. Но как только массив будет пустым, сработает вторая функция, которая выдаст нам результат. Этот пример — типичный пример реализации хвостовой рекурсии. Все вычисления происходят в третьей функции, где от массива операций берется первая операция и «хвост». Из массива с числами, который исполняет у нас роль стека, выбыраются два числа и хвост. Потом функция вызывается рекурсивно, пока данные не закончатся. Реализация циклов через рекурсию — тоже типичный подход. А непосредственно для рассчетов, вызывается calс с тремя параметрами (функция и два числа). При выполнении деления на ноль, мы получаем ошибку. Поэтому, до функции выполнения деления, вместо условий, добавим функцию, которая с помощью матчинга «поймает» ноль на входе делителя, и выдаст атом :err в качестве результата. Соответственно, перед всеми операциями, добавим матчинг на предмет того, что первый или второй вариант может быть :err, в этом случае итог будет тот же.

    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

Итак, с помощью уже знакомой нам конструкции перемножаем комбинации левой части числа и правой.

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

Получаем очень длинный вывод, сокращенный виртуальной машиной. Фильтруем так, чтобы выводились только равенства левой и правой части

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]}}, ...

Из первой строки можем понять, что (1+3)-2 = 2 и правая часть (4+6)/5 = 2. Все верно, только польская нотация не удобна для человека. Преобразуем, добавив в 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

Добавим в 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"]

Теперь повторим всё то же самое для билетика на картинке:

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", ...]

Как видим, билет вполне счастливый! )

Конечно, кое что тут можно улучшить (убрать дублирующиеся 666), не сравнивать результаты с :err, да и вообще, мы не решили задачу, поставленную автором изначально: «Найти все значения из 6 цифр, для которых ни одно из значений множества, полученного из первых трех цифр, не совпадет ни с одним значением множества из последних трех цифр». Но я такой цели и не ставил. Интереснее было показать разницу в подходах к решению задач, когда применяется Elixir. Полное решение поставленной задачи потребует расчетов всего диапазона чисел билетиков, и тут можно было бы показать всю мощь параллельных вычислений Erlang\Elixir, но это тема, пожалуй, для отдельной статьи, а на часах уже 02:53 ;)