В этой статье, я попытаюсь объяснить, как мне удалось своими силами создать алгоритм свертки одного из самых загадочных пасьянсов — Пасьянса Медичи. Предупреждаю сразу, в отличии от множества эзотерически настроенных людей, я не склонен думать, что этот пасьянс как-то влияет на события или описывает алгоритм их схождения к некому результату. Я скромный экспериментатор, которому интересна любая нетривиальная задача, которой в этот раз оказался злополучный пасьянс…
Пасьянс Медичи очень известная и при этом простая вещь, связанная с обыкновенными игральными картами. Соответственно, используется всем знакомая и довольно стандартная колода, состоящая из 36 карт и не содержащая карт достоинством (или номиналом) меньше шестерки. Также, колода не содержит джокеров.
Правила пасьянса Медичи (далее — ПМ) предельно просты: перемешанная колода карт выкладывается «рубашками вверх» и к уже выложенным картам применяется правило сложения. Правило сложения тривиальное, но оно еще и управляет процессом выкладки карт из колоды и вот почему: сначала выкладываются «рубашками вверх» три карты и идет их анализ — если первая и третья карта имеют одинаковую масть или одинаковое достоинство (одинаковый номинал), то происходит сложение, т.е вторая карта накрывает первую и к уже проанализированным картам выкладывается новая. После выкладки новой карты, повторяется анализ на предмет карт для сложения и в случае наличия возможного сложения (так называемой свертки), выполняется сложение и если необходимо, выкладывается очередная карта из колоды; в противном случае — выполняется просто выкладка новой карты и повтор анализа до обнаружения или новой свертки, или до тех пор (в случае отсутствия сверток вообще) до окончания колоды карт.
При этом, налицо две ситуации: первая — остается большая стопка карт и одна карта, и вторая — остается несколько стопок карт и отдельные карты с самым различным расположением и порядком. В первом случае считается, что пасьянс сложился, а вот втором — нет. Самый забавный факт в том, что складывается этот пасьянс довольно редко (по нашим чисто экспериментальным данным, в среднем 1 раз из 1000). Более подробно и с примерами можно посмотреть тут (только не вчитывайтесь в эзотерическую муть и не обращайте на нее внимание).
Казалось бы, реализовать такой алгоритм проще простого, но как оказалось, что просто тут все только на первый взгляд…
Для начала опишем масти (Suit) и достоинства карт (Rank), сделав это с помощью строковых enum:
enum Suit : string
{
DIAMONDS = "♢",
HEARTS = "♡",
SPADES = "♤",
CLUBS ="♧"
}
enum Rank : string
{
ACE = "A",
KING = "K",
QUEEN = "Q",
JACK = "J",
TEN = "10",
NINE = "9",
EIGHT = "8",
SEVEN = "7",
SIX = "6"
}
Игральная карта состоит из обоих этих элементов, и потому, имея описания мастей и достоинств, можно построить описание карты так:
class Card
{
mixin(addProperty!(Rank, "rank", "Rank"));
mixin(addProperty!(Suit, "suit", "Suit"));
this(Rank rank, Suit suit)
{
this.rank = rank;
this.suit = suit;
}
override bool opEquals(Object o)
{
auto rhs = cast(Card) o;
return (
(rank == rhs.getRank) &&
(suit == rhs.getSuit)
);
}
override string toString()
{
return cast(string) rank ~ cast(string) suit;
}
}
Здесь, используется наш знаменитый шаблон addProperty, который позволяет добавить сеттеры и геттеры для задания/получения значений достоинства/масти (порядок следования в конструкторе такой из-за того, что при упоминании карт в разговорной речи, мы называем сначала номинал, а потом саму масть). Также, не вызывает вопросов и перегруженный метод toString, управляющий формированием строкового представления карт (просто совмещаем достоинство и символ Unicode, соответствующий заданной масти).
Самое интересное в этом коде — это перегрузка метода opEquals, которая позволяет изменить стратегию сравнения объекта с любым другим. Для классов opEquals согласно правилам D возможно перегрузить только при такой сигнатуре, если, конечно, мы хотим, чтобы автоматически подхватились операторы == и !=, но проблема в том, что нам нужно сравнить между собой объекты типа Card. Для того, чтобы разрешить проблему, обходим ее с помощью стандартного трюка: приводим объект o типа Object к типу Card, и уже с ним и производим необходимые действия. В нашем случае действия заключаются в том, чтобы сравнить достоинства и масти у двух карт, и карты будут одинаковыми только в том случае, если их достоинства и масти одинаковы (причем, одновременно).
У нас есть реализация игральных карт, но в пасьянсе мы оперируем не только картами, но и свертками, т.е наборами карт. Для этих наборов справедлив тот факт, что только верхняя карта из свертки участвует в анализе и (возможно) в сложении, при этом в случае сложения карты со сверткой, изменится верхняя карта свертки; а в случае сложения свертки с картой, то вся свертка заменит собой карту. Кроме того, удобно думать, что свертка может состоять не только из нескольких карт, но и из одной, что упрощает некоторые дальнейшие процедуры в нашем алгоритме.
Реализация свертки выглядит так:
class Fold
{
mixin(addProperty!(Card[], "folds", "Folds"));
this()
{
}
void adjoin(Card card)
{
folds ~= card;
}
void adjoin(Fold fold)
{
folds ~= fold.getFolds;
}
Card last()
{
return folds[$-1];
}
override string toString()
{
import std.algorithm : map;
import std.conv;
import std.functional;
import std.string;
return folds
.map!(a => to!string(a))
.join(" ")
.reverseArgs!format("< %s >");
}
}
Конструктор сделан пустым из того соображения, что в начале работы алгоритма нет ни одной свертки, а в процессе его работы в свертки, как в контейнеры, попадают карты или целые свертки. Поскольку в свертку попадают объекты разных видов, а именно Card и Fold, то реализованы различные варианты метода adjoin, осуществляющего добавление новых элементов в свертку. Метод last напротив имеет лишь одну вариацию, поскольку с точки зрения пасьянса, нас интересует верхняя карта на свертке, а что находится под этой картой не имеет значения, и при этом last исправно возвращает верхнюю карту (карту оказавшуюся последней в свертке). Определение метода last предполагает, что пустых сверток не бывает (и в нашем случае это действительно так !).
Кроме того, в целях удобства отображения была осуществлена перегрузка метода toString, который позволяет сделать удобное отображение экземпляра класса Fold в строку. Как известно, это отображение используется в функциях типа writeln, а в нашем случае, это и нужно. Перегрузка реализована очень просто: с помощью map и to внутренний массив карт folds превращается в набор строк (поскольку у класса Card метод toString уже перегружен нужным образом), затем с помощью алгоритма join разрозненный набор данных собирается в одну строку и каждый элемент данных отделен от другого двумя пробелами. А вот дальше используется reverseArgs из std.functional, для того, чтобы поменять местами аргументы в функции format (изначально, format принимает строку формата, а уж потом аргумент, но благодаря reverseArgs принимается сначала аргумент, а затем строка формата). Также, функция format заключает в угловые скобки набор карт, принадлежащий данной свертке, что и приводит к комфортному отображению данных.
С помощью реализованной структуры свертки можно определить процедуру, проверяющую есть ли в текущей колоде карт хотя бы одна свертка, т.е есть ли хотя бы одно сложение. Но для этого, необходимо выполнить неявный переход от набора карт к набору сверток, для чего следует предположить, что в качестве входного набора данных используется массив сверток. Таким образом, нужно определить функцию превращения единичной карты в свертку из одной карты:
// преобразовать в свертку карт
auto toFold(Card card)
{
Fold fold = new Fold;
fold.adjoin(card);
return fold;
}
Данная функция поможет нам в дальнейшем, когда будут производится действия над целой колодой.
Тогда, процедура, которая проверяет наличие свертки в колоде, а также производит само сложение (в том случае, если оно возможно), выглядит так:
// возможно ли сложение хотя бы одного набора внутри колоды ?
auto isFoldableUp(ref Fold[] allFolds)
{
import std.range : array, slide;
bool result;
bool isFoldable(Fold lhs, Fold rhs)
{
auto L = lhs.last;
auto R = rhs.last;
return (
(L.getRank == R.getRank) ||
(L.getSuit == R.getSuit)
);
}
foreach (e; allFolds.slide(3))
{
auto f = e.array;
auto L = f[0];
auto M = f[1];
auto R = f[2];
if (isFoldable(L, R))
{
L.adjoin(M);
allFolds = allFolds.removeElement(M);
result = true;
break;
}
}
return result;
}
Данная функция работает следующим образом: массив из сверток подвергается разделению на независимые перекрывающиеся куски, своеобразные «окна», реализованные с помощью алгоритма slide из std.range; после чего происходит преобразование каждого отдельного «окна» в обычный динамический массив, из которого по индексу выделяются три элемента с именами L (левая свертка карт), M (средняя свертка) и R (самая правая свертка). Этими элементами и манипулирует процедура: в случае, если верхние карты сверток L и R одинаковы по масти и номиналу ( это проверяется с помощью isFoldable), то в левую свертку добавляем свертку M с помощью метода adjoin, а затем удаляем свертку M из списка всех сверток с помощью removeElement. Процедуры removeElement нет в стандартной библиотеки и ее описание взято из Idiomatic D, перевод которого (для данной идиомы) доступен здесь.
В случае, если нашлась возможность для сложения, то происходит запись true в переменную result и далее следует остановка цикла перебора по всем «окнам» из трех карт (в противном случае, переменная result останется в состоянии по умолчанию и равной изначальному значению при инициализации, а именно false).В случае, если нашлась возможность для сложения, то происходит запись true в переменную result и далее следует остановка цикла перебора по всем «окнам» из трех карт (в противном случае, переменная result останется в состоянии по умолчанию и равной изначальному значению при инициализации, а именно false).
Дополнение. Функция isFoldable описанная на свертках работает следующим образом: есть две свертки (неявно предполагается, что это левая и правая свертки, т.е переменные L и R, как в цикле описанном выше) из которых берутся верхние карты. Эти карты сравниваются между собой по достоинству и по масти, и если хотя бы один из этих признаков у двух карт является одинаковым, то функция возвращает true (т.е сложение возможно); и false в противном случае.
Таким образом, весь смысл данной функции сводится к поиску и выполнению сложения карт пасьянса, но срабатывает эта процедура лишь один раз. Такое срабатывание совместно с указанием ref (доступность по ссылке и возможность прямого доступа и изменения) для аргумента и формирует дальнейшую структуру алгоритма складывания пасьянса, над которым я мучался всю неделю…
Складывание пасьянса Медичи выглядит следующим образом:
// сложить пасьянс Медичи
auto mediciFold(Fold[] deck)
{
import std.range : empty;
auto allFolds = deck[0..3];
auto allCards = deck[3..$];
while (!allCards.empty)
{
bool isFoldable = isFoldableUp(allFolds);
if ((allFolds.length < 3) || (!isFoldable))
{
allFolds ~= allCards[0];
allCards = allCards[1..$];
}
}
while ((isFoldableUp(allFolds)) && (allFolds.length >= 3)) {
// nothing to do
}
return allFolds;
}
Самое интересное происходит именно в этой процедуре…
Для начала определимся, что все свертки будут размещаться в переменной allFolds, которая не только будет представлять собой временное хранилище сверток для процесса складывания, но и также будет содержать итоговый результат. Складывание пасьянса начинается с трех карт, поэтому в allFolds размещаем первые три элемента колоды сверток (тип Fold[]), а остаток помещаем в переменную allCards (потребуется далее, для дополнения «окна» allFolds).
Предполагаем, что складывание ПМ будет идти до тех пор пока не закончатся карты колоды и пока не будет достигнут предел по наличию возможностей для сложения: т.е если не осталось во всем массиве сверток ни одной возможности под сложение, то складывание пасьянса завершено вне зависимости от его результата (т.е вне зависимости от того сошелся ли он до стопки карт и еще одной, или нет). Поэтому в цикле while, пока есть в колоде карты (роль колоды играет остаток от входного массива по имени allCards) проверяем есть ли возможность сложить карты в текущей колоде (и выполняем, по необходимости, сложение) и если размерность allFolds меньше 3 (т.е произошло первое сложение, а значит, количество сверток уменьшилось до 2) и/или ни одного сложения в allFolds не произошло, то необходимо дополнить allFolds одной сверткой из колоды allCards, после чего удалить эту свертку из allCards.
Цикл обеспечивает повторение этой процедуры ровно до тех пор, пока не иссякнут все свертки (т.е все карты, поскольку в массиве allCards находятся свертки из одной карты), но это не гарантирует того, что все сложения уже выполнены и не осталось ни одного варианта под сложения, а потому (и это самое сложное для восприятия в алгоритме) необходимо выполнять поиск сложений процедурой isFoldableUp до тех пор, пока сама эта процедура подтверждает наличие сложений. Кроме того, в одном случае невозможно будет выполнить даже поиск сложения, и этим случаем является получение в ходе работы алгоритма массива allFolds длиной 2 (напоминаю, это значит что ПМ сложился или сошелся) — и именно поэтому нужно добавить проверку длины, как одно из ограничительных условий для цикличной работы isFoldableUp. Поскольку, само условие окончания перебора всех сверток выполняет процедуру приближающую цикл к окончанию, то внутри цикла while не требуется размещение каких-либо иных действий.
Функция mediciFold принимая в качестве входного аргумента колоду из сверток из карт возвратит также колоду из сверток, но таких, которые уже подвергнуты алгоритму сложения пасьянса. Но для дальнейших испытаний необходима любая колода карт (желательно, с известным результатом сложения) и при этом необходимо еще и преобразовать колоду карт в колоду сверток.
Поэтому создадим простой генератор начальной колоды:
// колода по умолчанию
auto createDeck()
{
import std.traits;
auto ranks = EnumMembers!Rank;
auto suits = EnumMembers!Suit;
Card[] cards;
foreach (rank; ranks)
{
foreach (suit; suits)
{
cards ~= new Card(rank, suit);
}
}
return cards;
}
Здесь используется трайт (trait) EnumMembers из std.traits, который позволяет во время компиляции сгенерировать полный набор всех членов некоторого перечисления, что необходимо для получения всей колоды: вложенный цикл, включающий в себя элементы обоих перечислений, позволяет получить карты всех мастей и всех номиналов с помощью простого перебора значений перечисления. После генерации очередной карты она просто записывается в массив всех карт, который потом и выдается в качестве результата.
Теперь, начнем испытания с колодой «по умолчанию» (кстати, она сходится, проверено вручную):
void main()
{
import std.algorithm : each, map;
import std.range : array, slide, empty;
auto f = createDeck
.map!toFold
.array
.mediciFold;
f.writeln;
}
Результат:
Сначала мы преобразуем набор карт в набор сверток с помощью алгоритма map и процедуры toFold, после чего превращаем набор из итогового диапазона в массив с помощью алгоритма array и подаем его в алгоритм складывания пасьянса mediciFold. Последняя процедура не определяет сходится пасьянс или нет, она лишь выполняет сложение по всей колоде карт; сходимость ПМ можно проверить очень просто — достаточно посчитать длину выходного массива, полученного из mediciFold: если длина массива равна двум, то пасьянс сложился (сошелся); если же длина отлична от двух, то схождение не произошло.
Полный код эксперимента:
import std.stdio;
auto removeElement(R, N)(R haystack, N needle)
{
import std.algorithm : countUntil, remove;
auto index = haystack.countUntil(needle);
return (index != -1) ? haystack.remove(index) : haystack;
}
enum Suit : string
{
DIAMONDS = "♢",
HEARTS = "♡",
SPADES = "♤",
CLUBS ="♧"
}
enum Rank : string
{
ACE = "A",
KING = "K",
QUEEN = "Q",
JACK = "J",
TEN = "10",
NINE = "9",
EIGHT = "8",
SEVEN = "7",
SIX = "6"
}
template addProperty(T, string propertyVariableName, string propertyName)
{
import std.string : format;
const char[] addProperty = format(
`
private %2$s %1$s;
void set%3$s(%2$s %1$s)
{
this.%1$s = %1$s;
}
%2$s get%3$s()
{
return %1$s;
}
`,
propertyVariableName,
T.stringof,
propertyName
);
}
class Card
{
mixin(addProperty!(Rank, "rank", "Rank"));
mixin(addProperty!(Suit, "suit", "Suit"));
this(Rank rank, Suit suit)
{
this.rank = rank;
this.suit = suit;
}
override bool opEquals(Object o)
{
auto rhs = cast(Card) o;
return (
(rank == rhs.getRank) &&
(suit == rhs.getSuit)
);
}
override string toString()
{
return cast(string) rank ~ cast(string) suit;
}
}
class Fold
{
mixin(addProperty!(Card[], "folds", "Folds"));
this()
{
}
void adjoin(Card card)
{
folds ~= card;
}
void adjoin(Fold fold)
{
folds ~= fold.getFolds;
}
Card last()
{
return folds[$-1];
}
override string toString()
{
import std.algorithm : map;
import std.conv;
import std.functional;
import std.string;
return folds
.map!(a => to!string(a))
.join(" ")
.reverseArgs!format("< %s >");
}
}
// колода по умолчанию
auto createDeck()
{
import std.traits;
auto ranks = EnumMembers!Rank;
auto suits = EnumMembers!Suit;
Card[] cards;
foreach (rank; ranks)
{
foreach (suit; suits)
{
cards ~= new Card(rank, suit);
}
}
return cards;
}
// преобразовать в свертку карт
auto toFold(Card card)
{
Fold fold = new Fold;
fold.adjoin(card);
return fold;
}
// возможно ли сложение хотя бы одного набора внутри колоды ?
auto isFoldableUp(ref Fold[] allFolds)
{
import std.range : array, slide;
bool result;
bool isFoldable(Fold lhs, Fold rhs)
{
auto L = lhs.last;
auto R = rhs.last;
return (
(L.getRank == R.getRank) ||
(L.getSuit == R.getSuit)
);
}
foreach (e; allFolds.slide(3))
{
auto f = e.array;
auto L = f[0];
auto M = f[1];
auto R = f[2];
if (isFoldable(L, R))
{
L.adjoin(M);
allFolds = allFolds.removeElement(M);
result = true;
break;
}
}
return result;
}
// сложить пасьянс Медичи
auto mediciFold(Fold[] deck)
{
import std.range : empty;
auto allFolds = deck[0..3];
auto allCards = deck[3..$];
while (!allCards.empty)
{
bool isFoldable = isFoldableUp(allFolds);
if ((allFolds.length < 3) || (!isFoldable))
{
allFolds ~= allCards[0];
allCards = allCards[1..$];
}
}
while ((isFoldableUp(allFolds)) && (allFolds.length >= 3)) {
// nothing to do
}
return allFolds;
}
void main()
{
import std.algorithm : each, map;
import std.range : array, slide, empty;
auto f = createDeck
.map!toFold
.array
.mediciFold;
f.writeln;
}
