Ruby: наследие Smalltalk

I always knew that one day Smalltalk would replace Java.
I just didn't know it would be called Ruby.
 —Kent Beck

Если совсем вкратце, суть языка Smalltalk состоит в том, что:

1. всё, что ни есть — объект, числа и строки в том числе;
2. объектам можно посылать произвольные сообщения, а уж что эти объекты будут с ними делать — на их усмотрение. Сообщение, как нетрудно догадаться, — тоже объект.

Ruby, появившийся на полтора десятка лет позже, включил в себя обе эти черты. У всех объектов есть метод send:

-5.send :abs => 5
51.send :gcd, 34 => 17
7.send :send, :+, 24 => 33

Сообщение — это объект класса Symbol; в коде он начинается с двоеточия. В качестве аргументов send посылаются сообщение и необходимые аргументы. Заметьте, что в последнем примере отсылается сам :send, и, вообще говоря, цепочка :send-ов перед параметрами может быть любой длины :-)

Однако как эти свойства можно применить на практике?
Предлагаю рассмотреть задачу 93 с projecteuler.net: из любого набора четырёх цифр от 1 до 9 с помощью знаков +, -, *, / и скобок можно составить арифметические выражения навроде (1+3)*(5-2), при этом не разрешается "склеивать" цифры и использовать каждую более одного раза. Так из 4-х цифр можно получить все числа от 1 до N включительно. Вопрос: для какого набора N максимально? (например, из 1,2,3,4 можно состряпать числа от 1 до 28)

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

class Float
    def inverse_div(other)
        other / self
    end
    def inverse_sub(other)
        other - self
    end
end

Теперь все возможные комбинации представимы либо как (a @ b) @ (c @ d), либо как a @ (b @ (c @ d)), где @ — одна из операций +, -, *, /, inverse_div, inverse_sub.

Концепция сообщений позволяет безо всякой лишней возни составить массив из объектов типа Symbol (а заодно и всех перестановок с повторениями из 3-х элементов):

MESSAGES = [ :+, :-, :*, :/, :inverse_div, :inverse_sub]
MSG_PERMUTATIONS = MESSAGES.repeated_permutation(3).to_a

Вызов метода to_a здесь нужен, чтобы перестановки были записаны в массив (единожды и до конца работы программы). Иначе получился бы объект класса Enumerator, выдающий следующую перестановку по требованию, а нам нужно перебирать все перестановки для всех наборов цифр: работа повторилась бы 9!/(5!*4!) = 126 раз вместо одного. Enumerator-ы хороши с точки зрения экономии памяти, но здесь не тот случай.

Теперь для каждого набора из четырёх цифр можно запросто найти N (алгоритм не особо оптимизирован, но и выполняться ему всего один раз):

def chain_length(numbers)
    possible_values = []
    numbers.permutation.each do |a,b,c,d|
        MSG_PERMUTATIONS.each do |m1, m2, m3|
                possible_values << (a.send m1, b).send(m2, (c.send m3, d))
                possible_values << ((a.send m1, b).send(m2, c)).send(m3, d)
            end
    end
    possible_values.uniq
                   .sort
                   .select { |x| x > 0 and x.finite? and x.floor == x }
                   .each_with_index.take_while { |x,i| x == i+1 }
                   .length
end

Заметьте, что нас не заботит деление на 0 (например, 1 / (6/3 - 2)): класс Float содержит объект Infinity, и выяснить, конечен объект этого класса или нет, можно с помощью методов finite? и infinite?

Последние несколько строк проделывают следующие нехитрые манипуляции:
 uniq избавляется от повторений элементов в массиве, sort сортирует полученный массив. (Вообще говоря, в стандартной библиотеке Ruby есть классы Set и SortedSet, но в данном случае они отрицательно сказываются на скорости.)
После этого мы оставляем только целочисленные элементы, большие нуля. Порядок предикатов здесь важен: Infinity не имеет метода floor. После чего, пользуясь методом take_while, выбираем цепочку от 1 до N (индексация с нуля, потому i+1) и определяем её длину.

Остаётся перебрать все наборы цифр:

print (1..9).map(&:to_f)         # преобразуем (1..9) в массив float
            .combination(4)      # перебираем все сочетания из 4-х элементов
            .map { |x| [x, chain_length(x)] } 
            .max { |x,y| x[1] <=> y[1] } # находим элемент с максимальным N