Поиск всех возможных решений в игре «Водопровод»

в 14:47, , рубрики: php
Предыстория

Всем доброго времени суток. По профессии я web-программист. Честно говоря, web-программирование для меня скорее хобби, которое приносит мне доход. Другим моим хобби являются городские экстремальные игры Encounter.
Если вкратце, то суть в том, что необходимо зайти на сайт игры, получить задание, в котором зашифровано место в городе, приехать на это место и решить загадку оставленную там авторами игры. После решения необходимо ввести ответ на сайте и получить следующее задание. Я как играю в игры, так и организовываю их.
Однажды, блуждая по Интернету, я наткнулся на флеш-игру «Водопровод».
image
Немного поиграв в неё, я решил сделать эту игру заданием на одной из предстоящих игр.

Суть идеи

Не буду рассказывать здесь о тонкостях работы движка Encounter, ибо это, как говорится, совсем другая история. Скажу только, что провести игру можно, не обладая знаниями в области программирования. Но при умении программировать на JavaScript можно реализовать самые необычные задумки.
Изначально перед игроками была пустая сетка:
image
По мере нахождения кодов (они были прописаны маркером на локации) и их вводе на сайте, сетка заполнялась сегментами труб:
image
Чтобы перейти на следующий уровень необходимо было открыть как можно больше сегментов, собрать из них водопровод и ввести в движок последовательность букв, расположенных во всех сегментах от начало до конца водопровода.
image
Код для перехода на следующий уровень: AKEZFDMIMQOYGBRZOGJTCSJAUODVYW.
Изначально всё казалось довольно таки простым в плане реализации. Проблемы начались, когда я случайно нашел ещё одно решение:
image
Код для перехода на следующий уровень: AKEZTASWYENBPKRRJAUODVYW.
Получается, сколько всего решений неизвестно, но надо найти их все и «сообщить» игровому движку все коды, чтобы при вводе любого из них, он перевел игроков на следующий уровень.

Выход из ситуации

В качестве инструментов сгодились PHP и MySQL. В базе MySQL хранится информация о каждом сегменте сетки, а скрипт на PHP проходит по всем возможным путям следования «воды» по трубе.

База данных

В таблице базы данных информация о сегментах хранится в следующем виде:
image

  • y — номер строки
  • x — номер столбца
  • type — форма сегмента. Если значение поля 1, то сегмент представляет из себя «колено», если 0, то — «прямую».
  • lit — буква в сегменте. Это поле было добавлено в самом конце, чтобы не составлять коды перехода на следующий уровень вручную, а доверить это скрипту.

Алгоритм

Для поиска всех возможных решений была написана рекурсивная функция tube.

<?   
    function tube($x1, $y1, $x2, $y2, $str) {
        ...
    }
    tube(1, 0 , 1, 1, '|0-1|');
?>

  • $x1 и $y1 — координаты предыдущего сегмента
  • $x2 и $y2 — координаты нового сегмента
  • $str — строка, состоящая из координат всех сегментов водопровода, разделенных символом "|"

При первом вызове функции в нее передаются координаты «крана», координаты верхней левой клетки и строка, в которой изначально только координаты «крана» — '|0-1|'.
Функция должна выполнять следующие задачи:

  1. Проверять, не присутствует ли новый сегмент в водопроводе уже 
    if (strpos($str, '|'.$y2.'-'.$x2.'|')) return;
else $str=$str.$y2.'-'.$x2.'|';
  2. Проверять, не уперся ли трубопровод в границу сетки 
    if ($x2==10 || $x2==0 || $y2==0) return;
if ($y2==9 && $x2<9) $err = return;
  3. Проверять, не дошел ли водопровод до искомой клетки (в нашем случае координаты этой сетки 9-9) и, если решение найдено, выводить его 
    if ($y2==9 && $x2==9) $str.'<br>';
  4. Если водопровод не уперся в границу сетки и решение не найдено, функция должна определить какие сегменты могут быть следующими в водопроводе и вызывать саму себя для каждого из «возможных» сегментов.
    На это пункте остановимся подробнее. Прежде всего необходимо узнать, какой тип у нового сегмента («колено» или «прямая»). Для этого обратимся к нашей базе данных: 
    $result=$dbh->query('SELECT type FROM tube WHERE (x='.$x2.') AND (y='.$y2.')');
$row = $result->fetch(PDO::FETCH_ASSOC);

    Если тип нового сегмента «колено», то в зависимости от того, откуда «пришел» водопровод, возможны следующие варианты развития событий:

    • Вода пришла сверху или снизу, уйти может только влево или вправо.
    • Вода пришла слева или справа, уйти может только вверх или вниз.

    В коде это выглядит следующим образом:

    if ($row['type']==1) {
	if ($y1!=$y2) {
		tube($x2, $y2, $x2-1, $y2, $str);
		tube($x2, $y2, $x2+1, $y2, $str);               
	}
	if ($x1!=$x2) {
		tube($x2, $y2, $x2, $y2-1, $str);
		tube($x2, $y2, $x2, $y2+1, $str);
	}
}

    Если тип нового сегмента не «колено» (то есть «прямая»), то опять же в зависимости от того, откуда «пришел» водопровод, возможны следующие варианты развития событий:

    • Вода пришла сверху, уйти может только вниз.
    • Вода пришла снизу, уйти может только вверх.
    • Вода пришла слева, уйти может только вправо.
    • Вода пришла справа, уйти может только влево.

    Код:

    else {
	if ($y1<$y2) tube($x2, $y2, $x2, $y2+1, $str);
	if ($y1>$y2) tube($x2, $y2, $x2, $y2-1, $str);               
	if ($x1<$x2) tube($x2, $y2, $x2+1, $y2, $str);
	if ($x1>$x2) tube($x2, $y2, $x2-1, $y2, $str);
}

Вот и всё. Осталось только дополнить функцию кодом, который при нахождении решения задачи будет составлять буквенный код для перехода на следующий уровень:

        if ($y2==9 && $x2==9) {
            $mass = explode('|', $str);
            $answer = '';
            for ($i=0; $i<count($mass)-1; $i++) {
                if ($mass[$i]!='' && $mass[$i]!='0-1' && $mass[$i]!='9-9') {
                    $koor = explode('-', $mass[$i]);                
                    $result=$dbh->query('SELECT lit FROM tube WHERE (y='.$koor[0].') AND (x='.$koor[1].')');
                    $row = $result->fetch(PDO::FETCH_ASSOC);
                    $answer=$answer.$row['lit'];
                }
            }
            echo $str.'<br>'.$answer.'<br>';
            return;
        }

И всё вместе: 

function tube($x1, $y1, $x2, $y2, $str) {
	if (strpos($str, '|'.$y2.'-'.$x2.'|')) return;
	else $str=$str.$y2.'-'.$x2.'|';
	
	if ($x2==10 || $x2==0 || $y2==0) return;
	if ($y2==9 && $x2<9) $err = return;
	if ($y2==9 && $x2==9) {
		$mass = explode('|', $str);
		$answer = '';
		for ($i=0; $i<count($mass)-1; $i++) {
			if ($mass[$i]!='' && $mass[$i]!='0-1' && $mass[$i]!='9-9') {
				$koor = explode('-', $mass[$i]);                
				$result=$dbh->query('SELECT lit FROM tube WHERE (y='.$koor[0].') AND (x='.$koor[1].')');
				$row = $result->fetch(PDO::FETCH_ASSOC);
				$answer=$answer.$row['lit'];
			}
		}
		echo $str.'<br>'.$answer.'<br>';
		return;
	} 

	$result=$dbh->query('SELECT type FROM tube WHERE (x='.$x2.') AND (y='.$y2.')');
	$row = $result->fetch(PDO::FETCH_ASSOC);
	if ($row['type']==1) {
		if ($y1!=$y2) {
			tube($x2, $y2, $x2-1, $y2, $str);
			tube($x2, $y2, $x2+1, $y2, $str);               
		}
		if ($x1!=$x2) {
			tube($x2, $y2, $x2, $y2-1, $str);
			tube($x2, $y2, $x2, $y2+1, $str);
		}
	}
	else {
		if ($y1<$y2) tube($x2, $y2, $x2, $y2+1, $str);
		if ($y1>$y2) tube($x2, $y2, $x2, $y2-1, $str);               
		if ($x1<$x2) tube($x2, $y2, $x2+1, $y2, $str);
		if ($x1>$x2) tube($x2, $y2, $x2-1, $y2, $str);
	}
}
tube(1, 0 , 1, 1, '|0-1|');

Результат работы скрипта (первые 5 из 39 решений задачи):

|0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-2|5-1|6-1|7-1|7-2|7-3|8-3|8-4|8-5|8-6|7-6|6-6|6-7|5-7|5-6|4-6|4-7|4-8|5-8|5-9|6-9|7-9|7-8|8-8|8-9|9-9|
AKEZFDMIMHYENQOUWIXBZIUAJSCZOGJTQYLVYW

|0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-2|5-1|6-1|7-1|7-2|7-3|8-3|8-4|8-5|8-6|7-6|6-6|6-7|7-7|7-8|8-8|8-9|9-9|
AKEZFDMIMHYENQOUWIXBZIUAJSDVYW

|0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-4|4-4|4-5|3-5|3-6|2-6|2-7|1-7|1-8|1-9|2-9|3-9|3-8|3-7|4-7|5-7|5-6|6-6|6-7|7-7|7-8|8-8|8-9|9-9|
AKEZFDMIMHYENBPKSRONHIGULAHGCZJSDVYW

|0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-4|4-4|4-5|3-5|3-6|2-6|2-7|3-7|3-8|3-9|4-9|5-9|5-8|4-8|4-7|4-6|5-6|5-7|6-7|6-6|7-6|8-6|8-7|7-7|7-8|8-8|8-9|9-9|
AKEZFDMIMHYENBPKSRONHALPQTJGOZCSJAUODVYW

|0-1|1-1|1-2|1-3|2-3|2-2|2-1|3-1|4-1|4-2|3-2|3-3|4-3|5-3|5-4|4-4|4-5|3-5|3-6|4-6|4-7|4-8|5-8|5-7|6-7|6-6|7-6|8-6|8-7|7-7|7-8|8-8|8-9|9-9|
AKEZFDMIMHYENBPKSROGJTCSJAUODVYW

Всем спасибо за внимание.

Автор: Budyaga

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js