Уроки Ruby. Как с помощью рубина получить волшебные кубики?

На одной из олимпиад по программированию была следующая простая задача на перебор (см. ниже). И был приведен авторский код на языке C++ (см. ниже). Я посмотрел на все это и понял, что нужно немедленно переписать все на Ruby (см. ещё ниже).

Задача "Волшебные игральные кубики"

Стандартный игральный кубик имеет 6 граней, на которых написаны числа {1,2,3,4,5,6}. Давайте рассмотрим нестандартные кубики, на гранях которых могут быть поставлены различные числа с возможными повторениями. Представьте себе, что у меня есть 3 таких кубика. Я предлагаю своему партнеру выбрать любой из этих кубиков, который ему больше понравился, а сам беру себе другой кубик из двух оставшихся. Далее мы начинаем играть: каждый бросает свой кубик, и выигрывает тот, на чьём кубике выпадет большее число. Оказывается, что при большом числе бросаний в среднем я буду в выигрыше, то есть я буду чаще выигрывать у партнера. Даже если партнер поменяет кубик, например, возьмет кубик, которым играл я, то он все равно будет проигрывать, если я воспользуюсь правом выбрать себе кубик из двух оставшихся. Может ли такое быть? Оказывается, может. Весь секрет в числах, которые расставлены на гранях кубиков. Пусть на гранях трех кубиков числа расставлены так:

• первый кубик: 1, 1, 4, 4, 7, 7,
• второй кубик: 2, 2, 5, 5, 5, 5,
• третий кубик: 3, 3, 3, 3, 6, 6.

Сформулируем сказанное в других терминах. Кубики можно сравнивать друг с другом: кубик A "сильнее" кубика B, если в среднем на кубике A выпадает число большее, чем число, которое выпадает на кубике B. На практике сравнить кубики несложно — нужно просто много раз кинуть два кубика одновременно и считать сколько раз A выиграл B, B выиграл A, и сколько раз была ничья. Но умелый программист может написать функцию is_stronge(A, B), которая абсолютно точно выдаст, какой из кубиков "сильнее". Удивительный факт заключается в том, что бывают тройки кубиков A, B, C в которых A сильнее B, B сильнее C, и C сильнее A, то есть, говоря математическим языком, отношение "сильнее" не транзитивно, и в ориентированном графе, представляющем это отношение, есть циклы длины 3.

Ваша задача заключается в том, чтобы, используя наименьшее количество различных чисел, найти их расстановку (с возможными повторениями) на гранях трёх кубиков такую, чтобы кубики обладали описанным выше "волшебным" свойством.

Решение на C++ (автор неизвестен)

#include <iostream>
using namespace std;
const int  Q = 6,  // число граней игрального кубика
          Mmax = 1000; 
int N;     // число найденных решений
int  P,    // число возможных цифр
     M;    // число игральных кубиков — число
           //  наборов размера Q из P элементов
           //  с возможными повторениями.  
int  C[Mmax][Q],       // коллекция кубиков.
     E[Q] ;

int test(int i, int j) {   // сравнение двух кубиков C[i] и C[j]
   int k, l, t = 0;
   for (k = 0; k < Q; k++)  
       for (l = 0; l < Q; l++)
           if (C[i][k] > C[j][l]) 
               t++;
           else 
               if (C[i][k] < C[j][l]) t--;
   if (t > 0) return 1; 
   else if (t < 0) return -1;
   else return 0;
}

int main(){
   int j, k, q, t;

   M = 0;
   N = 0;
   cout << "Введите число цифр P=";
   cin  >> P; // P = 4;
   // Построение множества всех кубиков
   for (q = 0; q < Q; q++) 
       C[0][q] = E[q] = 1;
   for (M = 1; M < Mmax; M++) {
       for (q = Q - 1; q >= 0; q--) {
           if (E[q] < P) {
               int s;
               E[q]++;
               for (s = q + 1; s < Q; s++)
                   E[s] = E[q];
               break;
           }
       }
       if (q < 0) break;
       for (q = 0; q < Q; q++) 
           C[M][q] = E[q];
    }

    if (M > Mmax)
       cout << "Только " << Mmax << " кубиков будут рассматриваться.\n";

    for (E[0] = 0; E[0] < M - 2; E[0]++) { // Перебор решений
       for (E[1] = E[0] + 1; E[1] < M - 1; E[1]++) {
           t = test(E[0], E[1]);
           if (t != 0) {
               for (E[2] = E[1] + 1; E[2] < M; E[2]++) {
                   if (t == test(E[1], E[2]) && t == test(E[2],E[0]) ) {
                       for (j = 0; j < 3; j++) {
                           // Вывод решения
                           cout << "(";
                           for (q = 0; q < Q; q++) { 
                               if (q) cout << ",";
                               cout << C[E[j]][q];
                           }
                           cout << ")";
                           if (t == 1)  cout << ">";
                           if (t == -1) cout << "<";
                           cout << endl;
                       }
                       cout << endl;
                       N++;
                   }
               }
           }
       }
   }
   cout << "M N: " << M << ' ' << N << endl;
   return 0;
}

Решение на Ruby.

Это задача решается методом перебора. По сути, нам нужно перебрать различные сочетания элементов из промежутка (1..P) с возможными повторениями, и для получившегося множества сочетаний перебрать всевозможные тройки (уже без повторения). Естественно для этого написать методы для экземпляров класса Array - массивов.

class Array
   # перебрать все наборы с возможными повторениями
   def tuples(size, &block)
       tuples0(size,[],0,&block)
   end
       
   private
   # перебрать все наборы элементов с возможными 
   # повторениями, при условии, что уже набран
   # частично набор ary, и в него нужно добрать 
   # элементы из хвоста массива self[i..].
   def tuples0(size,ary,i,&block)
       if ary.size == size
           # получен очередной набор
           # отдадим его ассоциированному блоку
           block[ary] 
       elsif i < self.size
           # возьмем self[i]
           ary.push self[i]
           tuples0(size,ary,i,&block)
           ary.pop

           # или пропустим self[i]
           tuples0(size,ary,i+1,&block) 
       end
   end
end

# сгенерируем сочетания 3-х элементов из 5 
# с возможными повторениями 
(1..5).to_a.tuples(3) do |tuple|
   puts tuple.inspect
end

Вывод программы:

[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 1, 4]
[1, 1, 5]
[1, 2, 2]
[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 3]
[1, 3, 4]
[1, 3, 5]
[1, 4, 4]
[1, 4, 5]
[1, 5, 5]
[2, 2, 2]
[2, 2, 3]
[2, 2, 4]
[2, 2, 5]
[2, 3, 3]
[2, 3, 4]
[2, 3, 5]
[2, 4, 4]
[2, 4, 5]
[2, 5, 5]
[3, 3, 3]
[3, 3, 4]
[3, 3, 5]
[3, 4, 4]
[3, 4, 5]
[3, 5, 5]
[4, 4, 4]
[4, 4, 5]
[4, 5, 5]
[5, 5, 5]

Предъявленный метод tuples у экземпляров класса Array генерирует различные сочетания с возможными повторениями из элементов массива. Этот метод вызывается как метод конкретного массива, который внутри определений имеет имя self (сам объект). Алгоритм генерации основан на методе рекурсии. Введем в задачу дополнительные параметры - ary и i:

Эту подзадачу решает функция tuples0(size,ary,i,block), при этом эта подзадача легко сводится сама к себе, и её можно решить, используя рекурсию.

Решите эту задачу, не поленитесь. Проверить работу можно с помощью строки

(1..5).to_a.subsets(3) { |subset|  puts subset.inspect }

Эта строка должна вывести 10 различных сочетаний 3 элементов из 5 первых натуральных чисел. без повторений

Для решения задачи о волшебных тройках осталось сделать совсем немного - определить метод сравнения двух наборов. Для этого давайте переопределим оператор <=> так, чтобы он возвращал -1, 0 или 1, в зависимости от того, какой из двух наборов чисел выигрывает:

• 1 - первый выигрывает;
• 0 - ничья;
• -1 - второй выигрывает.

class Array
   def <=>(ary)
       res = 0
       self.each do |x|
           ary.each do |y|
               res += (x<=>y)
           end
       end
   end
end

Заметьте, что в Ruby можно свободно "дописывать" существующие классы, добавляя в них новые методы и переопределяя существующие.

Функции subsets и tuples слишком сильно повторяют друг друга. Это не соответствует основной концепции Ruby - не повторяйся (принцип DRY - don't' repeat yourself). Этих повторений можно избежать, введя дополнительный аргумент у функции tuples0. Кроме того, хотелось бы, чтобы функции tuples и subsets, если их вызывать без ассоциированного блока, просто возвращали массив наборов. Это сделано в приведённом ниже полном коде программы.

Решение задачи выглядит следующим образом:

class Array
   def <=>(ary)
       res = 0
       self.each do |x|
           ary.each do |y|
               res += (x<=>y)
           end
       end
       res <=> 0
   end
   
   # пояснение этой функции нам придётся отложить
   # до лучших времён
   def set_optional_block(block)
       if block.nil?
           [result=[], lambda {|x| result << x }]
       else
           [nil, block]
       end
   end
       
   # перебрать все наборы с возможными повторениями
   def tuples(size, &block)
       result,block = set_optional_block(block)
       tuples0(size,[],0,0,block)
       result
   end
   
   # перебрать все наборы без повторений
   def subsets(size, &block)
       result,block = set_optional_block(block)
       tuples0(size,[],0,1,block)
       result
   end
       
   private
   # перебрать все наборы элементов при условии, что уже 
   # набрана часть набора ary и нужно добрать элементов 
   # из хвоста массива self[i..].
   # Повторения возможны, если norepeat = 0.
   def tuples0(size,ary,i,norepeat,block)
       if ary.size == size
           block[ary.dup] 
       elsif i < self.size
           # возьмем self[i]
           ary.push self[i]
           tuples0(size,ary,i+norepeat,norepeat,block)
           ary.pop

           # или пропустим self[i]
           tuples0(size,ary,i+1,norepeat,block)
       end
   end

end

puts "Волшебные тройки:"
puts (1..4).to_a.tuples(6).subsets(3).select { |t|
   ((t[0]<=>t[1]) + (t[1]<=>t[2]) + (t[2]<=>t[0])).abs == 3
}.inspect

Данный код не намного короче кода на языке С++. Но заметьте, что приведённое здесь решения содержит определение функции tuples и subsets, которые могут быть использованы при решении многих других алгоритмических задач. Причём эти функции можно использовать с ассоциированным блоком или без, в зависимости от того, хоти те вы проитерировать наборы ("пробежаться" по ним), или хотите получить массив наборов. Задача была разбита на отдельные методы, так что само решение по сути, состоит из 4-х последних строчек кода.

Данный код можно существенно ускорить, если сделать кэширование значений сравнения:

    def <=>(ary)
       @cache = Hash.new if @cache.nil?
       return @cache[ary] if @cache.has_key?(ary)
       res = 0
       self.each do |x|
           ary.each do |y|
               res += (x<=>y)
           end
       end
       @cache[ary]=(res <=> 0)
   end

Это кэширование позволяет уменьшить время поиска с 11,3 сек. до 2,7 сек. (на ноутбуке Pentium M, 1.7MHz). Для получения информации об использовании памяти и процессорного времени удобно использовать модуль benchmark:

require 'benchmark'
puts Benchmark.measure {
   puts [1,2,3,4].to_a.tuples(6).subsets(3).select { |t|
       ((t[0]<=>t[1]) + (t[1]<=>t[2]) + (t[2]<=>t[0])).abs == 3
   }.size
}

Данный код напечатает число найденных волшебных троек (43, досадно, что не 42) и время, потраченное на вычисления: процессорное время, потраченное на пользовательский код, процессорное время, потраченное на выполнение системных вызовов и реальное время, которое прошло, пока вычислялся заданный блок.

Документацию по различным классам и их методам можно получить, используя графическое приложение fxri, включенное в дистрибутив Ruby под Windows.

Автор статьи: Артем Ворожцов

См. также

• http://ru.wikibooks.org/wiki/Ruby - книжка про Ruby на русском языке.
• http://acm.mipt.ru/bin/view/Ruby - учебные материалы на сайте МФТИ.
• Programming Ruby, Dave Thomas with Chad Fowler and Andy Hunt (Программирование на Ruby, Дейв Томас, совместно с Чадом Фоулером и Энди Хантом)
• Agile Web Development with Rails - Pragmatic Programmers Guide, Dave Thomas (Гибкое программирование под Web на Rails, Дейв Томас)