Занимательная задачка «Несчастливый билет» (Elixir edition)18.10.2016 11:19

a63ad2f3e986310539124d3c3ee502b3.jpg Я не смог пройти мимо поста о несчастливом билете. Это одна из моих любимых задач. К тому же, комбинации в решении были запрограммированы вручную, а было бы интересно перебрать все варианты алгоритмически. Мне стало интересно, а как бы я решил эту задачу, используя 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 находим вот такое решение: 
iex(9)>    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;)

Комментарии (3)

  • 18 октября 2016 в 09:54

    0

    ↑

    ↓

    Скажите, а Elixir — это математический язык программирования, которым удобно решать задачи по комбинаторике?
    Есть одна задача по перестановке. Хотелось бы найти элегантное решение. Но перебор «в лоб» получается чрезвычайно неэффективным. Можете посоветовать новичку где почитать?

    • 18 октября 2016 в 10:08

      0

      ↑

      ↓

      Нет, для тяжёлых математических вычислений Elixir не самый подходящий ЯП. Посмотрите в сторону Julia, или в сторону математических пакетов Mathematica, Maxima, Maple, etc.

    • 18 октября 2016 в 10:10

      0

      ↑

      ↓

      Нет. Elixir — это функциональный язык программирования. Построен поверх Erlang. Используя функциональный подход и синтаксический сахар, который дает Elixir, некоторые задачи решаются меньшим количеством кода.

© Habrahabr.ru