6 игр за 6 недель — игра третья

В пятницу должны быть котики. Их есть у меня.



Игра третья — B4.
Это — настоящий пасьянс. Сложный, как запрос в Perl.
Потому успехом будет пользоваться только у математиков с Хабра и командировочных в поезде Москва-Екатеринбург.

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

К комментариях zikher предложил контр-пример, вроде бы опровергающий лемму. Но пример решили.

Правила

Правила такие же, как в игре Четыре комнаты. В комнате лежит цветной мусор. Мусор можно гонять по комнате движениями пальца по экрану — либо по горизонтали, либо — по вертикали.
Красный мусор можно выбросить через красную стенку. Желтый мусор — через желтую. Синий- через синюю. Голубой — голубую. Больше правил нет.

Поонятненько? Перейдем к примерам.

Посмотрите на рисунок 1. Необходимо очистить комнату от цветного мусора.


Рисунок 1. Простейший расклад

Решение для расклада на рисунке 1 состоит из двух ходов.

1. сдвинуть фишки вправо (исчезнет красный мусор через красную стенку)
2. сдвинуть фишки вверх (исчезнет синий мусор)

Пасьянс решен.

На рисунке 2 пример сложнее.


Рисунок 2. Если первый ход сделать вверх — пасьянс не сойдется.

Решение для расклада на рисунке 2 состоит из пяти ходов.

1. сдвинуть фишки вправо
2. сдвинуть фишки вниз
3. сдвинуть фишки влево(исчезнет желтый мусор)
4. сдвинуть фишки вверх(исчезнет синий мусор)
5. сдвинуть фишки вправо

Пасьянс решен.

Пример номер 66

Генерация раскладов

В пасьянсах очень важна генерация раскладов. С одной стороны они должны быть случайными, с другой стороны всегда должна быть возможность повторить случайный расклад — либо подкинуть его приятелю на слабо!, либо сыграть заново самому.

Проблема в том, что моя игра универсальная — есть игра под iPhone, а есть интернет вариант. Как добиться одного и того же расклада на Objective C и JavaScipt?

Как ни странно — решение лежит в Visual Studio от Microsoft.

Я залез в math библиотеки VS и вытащил код функции псевдо-случайной генерации чисел.

- (int)microsoft_rnd {
    holdrand = holdrand * 214013  + 2531011;
    return ((holdrand >> 16)  & 0x7FFF);
}

Задавая начальное значение в глобальной переменной holdrand — я могу повторить случайную последовательность столько раз, сколько захочу. Для удобства я завел 1 000 000 начальных раскладов и расширил функционал своего класса.

- (int) microsoft_rand:(int) number{
    return [self microsoft_rnd] % number;
}

// Пример использования функции - получение случайного числа в диапазоне 1 - 4
...
  int k = 1 + [self microsoft_rand:4];
...

На JavaScript данная функция выглядит чуть иначе

function microsoft_rnd()
{
	var r;
	var big = 4294967295+1;
	microsoft_rnd.seed = (microsoft_rnd.seed * 214013 + 2531011)%big;
	r = microsoft_rnd.seed;
	r = Math.floor(r/65536);
	r = r%32768;
	return r;
}

function microsoft_rand(number)
{
	return (microsoft_rnd())%number;
};

Экспериментально проверено, что результат работы функции во всех системах идентичен.

Таким образом задавая holdrand равным, например 2015, я получаю один и тот же расклад как на iPhone, так и в браузере.

Как я проверял игру

Первый раз запустив игру я расстроился. Выбранный мной расклад не сошелся. Я завелся. То есть завел большую картинку с симпатичной теткой, закрыл ее кнопками от 256 первых раскладов и начал играть с умом. При правильном решении очередного расклада — кнопка исчезала и тетка оголялась.
В результате на третий день я решил 255 из 256 раскладов. Не смог решить лишь один — в котором изначально не было движения по горизонтали.

Отсюда родилась лемма, которую не смог доказать — при наличии двух степеней свободы собирается любой полный пасьянс на доске 5 на 5 и выше.

Всем удачных выходных

Спасибо за внимание, анимация котиков танцы нанайских мальчиков — исключительно мудрецам, сложившим пасьянс.