Задача по расположению фигур в игре «Тетрис»

[ninacarrot]

В оригинальном тетрисе можно ещё двигать фигурки влево-вправо в процессе падения, что иногда действительно необходимо (по крайней мере, со стандартным тетрисовым набором фигурок).
Вдобавок вы не разрешаете повороты. Когда тетрис был единственной игрой, в которую я играл, то самые эффективные ходы, которые мне удавалось совершать в трудных ситуациях, производились при помощи комбинаций перемещений и поворотов. Особенно это было круто в «кривых» реализациях тетриса (на некоторых телефонах, например); там иногда удавалось «повернуть» фигурку и одновременно установить её внутрь уже стоящего блока.

[plutov]

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

[ninacarrot]

И вы меня простите, пожалуй, я слишком грубо выразился. Думаю, найдутся желающие размять мозги и написать бота для тетриса.

[bay73]

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

[plutov]

Мне прислали уже первый алгоритм, к сожалению, у человека read-only аккаунт, поэтому я опубликую за него:
http://jsfiddle.net/H3kra/

[itspoma]

Еще «speed» не хватает :)
jsfiddle.net/TZ7HJ/

[plutov]

Спасибо, добавлю в base-версию

[plutov]

Еще одно решение от read-only по имени YemSalat:
http://jsfiddle.net/YemSalat/76um8/

[Shultc]

Если бы, хотя бы, заполненные ряды бы исчезали бы, это ещё как-то напоминало бы тетрис. А так от него одно название.
Наверное по этому и интересуются постом в основном те, кто в Read-Only =)

[plutov]

Вы правы, нужно так сделать, тогда нужно разнообразить фигуры, потому что с двумя это будет бесконечная игра.

[vp_arth]

тетрис это полный набор тетрамино, семь фигур, если не ошибаюсь… но это будет задача абсолютно другого уровня

[Shultc]

Зависит от алгоритма. Как я видел, то предложенные на данный момент алгоритмы оставляют дыры, а значит и не будет игра бесконечной, хотя будет достаточно долгой.

[vp_arth]

довольно часто заполняет последний слой:
jsfiddle.net/vp_arth/g8S55/

[plutov]

Интересное у вас решение, у меня всегда слева — 1x4, по центру квадраты, справа колонки:
gyazo.com/990fd14e1f1bf6cc83d5b11fb063d42e

[vp_arth]

да, у фигур есть «свои» места… когда они их заполняют, начинают бороться за чужие :)

[vp_arth]

up: jsfiddle.net/vp_arth/g8S55/1/

[vp_arth]

Кстати, было пару раз «Squares left: 0»

[Ogoun]

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

[plutov]

Мне понравилось ваше решение. Вот только если такой промежуток не найден, то должна тоже быть какая-то логика, куда поставить фигуру. Хотя бы так, чтобы осталось меньше закрытых пробелов.

[Ogoun]

По логике этого алгоритма, такой промежуток найдется всегда (т.е. последняя строка 'return order[0];' никогда не будет вызвана), другое дело что помещение в него не всегда будет оптимально.

[tigerforce]

Моё решение: jsfiddle.net/alex_shnayder/9UsVF/
И простенький тест для сравнения всех решений: jsfiddle.net/alex_shnayder/TbYtF/

[tigerforce]

Упс, вот верная ссылка на решение: jsfiddle.net/alex_shnayder/9UsVF/2/

[vp_arth]

я когда решение выдумывал, больше не про минимизацию окон думал, а про
alert('WOW!. Your algorithm is awesome!');

[tigerforce]

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

Но у вас все равно получилось лучше, чем у других :) И ещё, судя по результатам, у меня такой же алгоритм.

[vp_arth]

Классное решение) Почти человеческое.
И за тестилку спасибо!

[tigerforce]

Добавил в тест решение Ogoun: jsfiddle.net/alex_shnayder/TbYtF/1/

[plutov]

Добавьте еще одного товарища в таблицу: jsfiddle.net/Night_Death/K4x3M/3/

[jojo97]

Вот мое решение: jsfiddle Не самое эффективное, но очень простое.

[vp_arth]

добавил в тестилку, плюс запилил минимакс — jsfiddle.net/vp_arth/TbYtF/4/

[jojo97]

Ух ты, у меня 6 место, я попал в десятку лучших:)

[plutov]

jsfiddle.net/Night_Death/K4x3M/3/

[bay73]

Ловите очень тупое, очень быстрое решение, которое за призы может и побороться :)
jsfiddle.net/by8c6/1/

[bay73]

Хм, добавил свое решение в тестилку: jsfiddle.net/TbYtF/6/
Стабильно показывает лучший результат и по очкам и по времени. Не думал, что столь тупой алгоритм может быть настолько эффективен.

[SiDChik]

С первого же раза все заполнил :)
jsfiddle.net/QPC7v/

[SiDChik]

Забыл обновить… jsfiddle.net/QPC7v/4/

[eandr_67]

Никого здесь не смущает, что задача о заполнении рюкзака (частными случаем которой является и предложенный вариант тетриса) является NP-полной? И что оптимальное решение NP-полной задачи может быть получено только методом полного перебора?

[SiDChik]

Нет не смущает. В задаче с рюкзаком, нам известен набор вещей заранее, а тут другая задача.

[eandr_67]

И что? NP-полной задачей является не только задача в канонической форме, но и любая задача, сводимая за полиномиальное время к любой из канонических.

Доказано, что классический тетрис является именно NP-полной задачей.

[bay73]

Доказано, что классический тетрис является именно NP-полной задачей.

А ссылочкой не поделитесь?
Ну или хотя бы формулировкой «классической задачи тетриса», так чтобы ее можно было к NP-задачам отнести?

[eandr_67]

arxiv.org/abs/cs.CC/0210020

[SiDChik]

При условии что имеют известный порядок фигур. В случае рандома, задача не будет полная же.

[bay73]

Ага, я так и думал, что вы детерменированный тетрис подгоните. Не уверен, что такую задачу можно назвать «классическим тетрисом».

[hellman]

Наоборот, NP-полная задача — та, к которой сводится другая NP-полная задача (плюс наша задача еще сама должна лежать в NP).

[hellman]

Дык частный случай же. Да и NP-полные задачи необязательно решаются «полным перебором».

[jojo97]

А можно еще один мой алгоритм разместить? Он тоже довольно простой, но намного эффективнее: jsfiddle

[bay73]

Действительно хороший алгоритм, но финишную часть надо бы доработать, чтобы при сильном заполнении стакана оставлял место для вертикальной «палки»

[jojo97]

Спасибо. Попробую, но он и так очень медленный, боюсь, что тогда придется 5 секунд ждать на выполенние:)

[jojo97]

Добавил оставление места для палки, но так он наоборот теряет в эффективности, где-то 2-5(в зависимости от порога сильного заполнения) очек на 100 запусков. Ну по крайней мере в моей реализации.

[plutov]

Алгоритм ваш мне понравился, компактно написан.

[jojo97]

Пасиб!

[vp_arth]

jsfiddle.net/TbYtF/7/
оставил лучший из трёх

[jojo97]

Да, спасибо!

[SiDChik]

Что-то меня так никто и не добавил :) jsfiddle.net/QPC7v/7/

[vp_arth]

jsfiddle.net/TbYtF/9/

[plutov]

Спасибо вам огромное за ваш тест! С ним намного удобней. Давайте тогда добавим всех участников. На моём блоге оставили такое решение:
jsfiddle.net/H3kra/

[vp_arth]

Это не мой тест, а товарища tigerforce…
Вам ничто не мешает добавлять самому — это же fiddle

[plutov]

Вот товарищ один еще усовершенствовал своё решение, тоже может принять участие. jsfiddle.net/Night_Death/K4x3M/5/

[jinxal]

jsfiddle.net/kaY62/

[vp_arth]

во первых, невалидный код — не закрыт блок switch.
во вторых, некорректный алгоритм:
— возвращает значения от 0 до 9, вместо «от 1 до 10»
— не проверяет влезет ли фигура в эту колонку

[jinxal]

Извините, я не сохранил последнюю версию в jsFiddle, поэтому и глупейшие ошибки присутствуют. Вот: jsfiddle.net/kaY62/2/