Уроки 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.
Решение на 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
:
Подзадача. Пусть у нас уже взято несколько элементов, и они собраны в массиве
Эту подзадачу решает функция ary
. Необходимо доложить в этот набор элементы так, чтобы он имел размер size
, используя при этом только элементы хвоста массива: self[i]
, self[i+1]
, …
tuples0(size,ary,i,block)
, при этом эта подзадача легко сводится сама к себе, и её можно решить, используя рекурсию.
Задача. Загрузите и установите Ruby (http://www.ruby-lang.org/en/downloads). Используя редактор SciTe?, который поставляется вместе с дистрибутивом, наберите данный текст программы и запустите её, нажав на F5. Создайте новые функции
Решите эту задачу, не поленитесь. Проверить работу можно с помощью строки
subsets
и subsets0
, которые генерирую наборы без повторений элементов. Для этого нужно взять за основу функции tuples
и tuples0
, а именно, сначала нужно точно повторить их (скопировать), заменить везде tuples
на subsets
, а также заменить строку
tuples0(size,ary,i,block)
на строку
subsets0(size,ary,i+1,block)
(1..5).to_a.subsets(3) { |subset| puts subset.inspect }
- 1 - первый выигрывает;
- 0 - ничья;
- -1 - второй выигрывает.
class Array def <=>(ary) res = 0 self.each do |x| ary.each do |y| res += (x<=>y) end end end end
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
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 }
См. также
- 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, Дейв Томас)