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

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

    Похожие публикации

    Комментарии 16

      0
      Скажите, а Elixir — это математический язык программирования, которым удобно решать задачи по комбинаторике?
      Есть одна задача по перестановке. Хотелось бы найти элегантное решение. Но перебор «в лоб» получается чрезвычайно неэффективным. Можете посоветовать новичку где почитать?
        +1
        Нет, для тяжёлых математических вычислений Elixir не самый подходящий ЯП. Посмотрите в сторону Julia, или в сторону математических пакетов Mathematica, Maxima, Maple, etc.
          0
          Для алгебраических вычислений была хорошая вещь — GAP, правда она чисто консольная почти. Для нее был хороший гуй ggap, но он свежии версии не поддерживает (
          +1
          Нет. Elixir — это функциональный язык программирования. Построен поверх Erlang. Используя функциональный подход и синтаксический сахар, который дает Elixir, некоторые задачи решаются меньшим количеством кода.
          0
          Писать функцию с двумя параметрами вместо одного кортежа это религиозное или есть какой-то практический смысл?
            0
            Это чтобы они отличались, хотя бы количеством параметров, ведь у них одинаковое имя. Где как удобнее.
            +2

            Насчет синтаксического сахара,


            |> Enum.map(fn(x)-> String.to_integer(x) end)

            можно сократить до


            |> Enum.map(&String.to_integer/1)
              0
              Мне как-то тоже стало интересно какие номера «счастливые» и захотелось попробовать сделать это на С++: https://github.com/Baldrs/Happy-tickets

              Т.к. основной язык на котором я пишу, это PHP, подозреваю что код на С++ у меня вышел не очень «православный» :-)
                +2
                Глаза же вытекают, натурально.

                https://github.com/tallakt/comb ⇐ комбинаторика.

                Ну и дальше вместо велосипедов с непонятными сигнатурами, давайте писать на Elixir’е, раз уж мы тут уже. AST же бесплатно все за вас сделает. По шагам:

                Поглядим, как оно выглядит в AST:

                iex> quote do 1 + 2 * 3
                {:+, [context: Elixir, import: Kernel], [1, {:*, [context: Elixir, import: Kernel], [2, 3]}]}
                


                осталось всего ничего: объявить макрос

                iex> defmacro operation([var1, var2, var3], [op1, op2]) do
                ...>   {op1, [context: Elixir, import: Kernel], [var1, {:op2, [context: Elixir, import: Kernel], [var2, var3]}]}
                ...> end
                


                и пройтись по всем пермутациям

                iex> m = ~w|+ - * /|a
                [:+, :-, :*, :/]
                iex> Comb.cartesian_product(m, m) |> Enum.map(&operation([var1, var2, var3], &1))
                


                Ну и сравнить еще надо будет, да. Мне лень дописывать пример до работающего, но вот есть прекрасный use-case, где торчащий наружу из языка AST — прямо в тысячу раз все упрощает, а вы настойчиво его обходите по кривым топким дорожкам.

                  0
                  iex> defmacro
                  У меня и к Вам и к автору статьи вопрос: зачем вы путаете новичков? Они ведь не знают, что def и defmacro работают только внутри defmodule. Аналогичный косяк и с `quote do 1 + 2 * 3` без end.
                    0
                    В каком месте я путаю? Там, где у меня def, я каждый раз пишу, что мы это добавляем в файл perm.ex. Все остальное в консоли.
                      +1
                      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
                        0
                        Верно! Это я недоглядел. Спасибо за подсказку, сейчас исправлю.
                      +1
                      В `quote do: 1 + 2 * 3` я двоеточие куда-то подевал, а не `end` :)

                      Это же не SO, чтобы код проверять, как набралось, так и тиснул. В принципе, я только хотел сказать, что у Elixir’а есть одна просто killer-feature, и это макросы в чистом AST, так что вся эта статья — идеальный пример того, как ни в коем случае не нужно писать код на этом языке. Такой ярчайший антипаттерн, пример того, что на PHP можно программировать даже с использованием синтаксиса эликсира.

                        0
                        Чтож, буду улучшать свое Elixir кунг-фу.
                      0
                      https://github.com/tallakt/comb ⇐ комбинаторика.
                      Вот за это, отдельная благодарность! Все мои проблемы решены в одном месте.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое