Цікава задачка «Нещасливий квиток» (Elixir edition)

Я не зміг пройти повз поста про нещасливе квитку. Це одна з моїх улюблених завдань. До того ж, комбінації в рішенні були запрограмовані вручну, а було б цікаво перебрати всі варіанти алгоритмічно. Мені стало цікаво, а як би я вирішив цю задачу, використовуючи Elixir.

Якщо вам цікаво, як такі завдання вирішуються в Elixir, або навіть встановити і повторити, то я прошу вас під кат.




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

user@host:~/$ iex
Erlang/OTP 19 [ea-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 RC module (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 ;)
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.