Комментарии 61
В оригинальном тетрисе можно ещё двигать фигурки влево-вправо в процессе падения, что иногда действительно необходимо (по крайней мере, со стандартным тетрисовым набором фигурок).
Вдобавок вы не разрешаете повороты. Когда тетрис был единственной игрой, в которую я играл, то самые эффективные ходы, которые мне удавалось совершать в трудных ситуациях, производились при помощи комбинаций перемещений и поворотов. Особенно это было круто в «кривых» реализациях тетриса (на некоторых телефонах, например); там иногда удавалось «повернуть» фигурку и одновременно установить её внутрь уже стоящего блока.
Вдобавок вы не разрешаете повороты. Когда тетрис был единственной игрой, в которую я играл, то самые эффективные ходы, которые мне удавалось совершать в трудных ситуациях, производились при помощи комбинаций перемещений и поворотов. Особенно это было круто в «кривых» реализациях тетриса (на некоторых телефонах, например); там иногда удавалось «повернуть» фигурку и одновременно установить её внутрь уже стоящего блока.
Вы действительно фанат тетриса! Извините, я не хотел обидеть игру. Всё, что я хотел — это дать возможность читателям решить задачку, подумать немного, возможно, посоревноваться в лучшем алгоритме. Для этого я и упростил входные данные. Думаю, потом можно будет тетрис сделать действительно тетрисом, чтобы функция возвращала не только номер колонки, но еще и состояние поворота.
И вы меня простите, пожалуй, я слишком грубо выразился. Думаю, найдутся желающие размять мозги и написать бота для тетриса.
В данном случае целевая функция слишком отличается от того, что нужно в настоящем тетрисе. И дело не в форме фигур и возможности поворачивать, а в том, что в тетрисе полностью заполненный ряд — исчезает, поэтому появление внутренних пустот проблемой не является. А в данном случае задача выглядит, как минимизация числа пустот.
Мне прислали уже первый алгоритм, к сожалению, у человека read-only аккаунт, поэтому я опубликую за него:
http://jsfiddle.net/H3kra/
http://jsfiddle.net/H3kra/
Еще «speed» не хватает :)
jsfiddle.net/TZ7HJ/
jsfiddle.net/TZ7HJ/
Еще одно решение от read-only по имени YemSalat:
http://jsfiddle.net/YemSalat/76um8/
http://jsfiddle.net/YemSalat/76um8/
Если бы, хотя бы, заполненные ряды бы исчезали бы, это ещё как-то напоминало бы тетрис. А так от него одно название.
Наверное по этому и интересуются постом в основном те, кто в Read-Only =)
Наверное по этому и интересуются постом в основном те, кто в Read-Only =)
довольно часто заполняет последний слой:
jsfiddle.net/vp_arth/g8S55/
jsfiddle.net/vp_arth/g8S55/
Интересное у вас решение, у меня всегда слева — 1x4, по центру квадраты, справа колонки:
gyazo.com/990fd14e1f1bf6cc83d5b11fb063d42e
gyazo.com/990fd14e1f1bf6cc83d5b11fb063d42e
Еще одно решение
Простой поиск промежутка подходящего по ширине для текущей фигуры, начиная с минимально заполненного столбца. Высота не учитывается.
Простой поиск промежутка подходящего по ширине для текущей фигуры, начиная с минимально заполненного столбца. Высота не учитывается.
Моё решение: jsfiddle.net/alex_shnayder/9UsVF/
И простенький тест для сравнения всех решений: jsfiddle.net/alex_shnayder/TbYtF/
И простенький тест для сравнения всех решений: jsfiddle.net/alex_shnayder/TbYtF/
Упс, вот верная ссылка на решение: jsfiddle.net/alex_shnayder/9UsVF/2/
я когда решение выдумывал, больше не про минимизацию окон думал, а про
alert('WOW!. Your algorithm is awesome!');Классное решение) Почти человеческое.
И за тестилку спасибо!
И за тестилку спасибо!
Добавил в тест решение Ogoun: jsfiddle.net/alex_shnayder/TbYtF/1/
Добавьте еще одного товарища в таблицу: jsfiddle.net/Night_Death/K4x3M/3/
Вот мое решение: jsfiddle Не самое эффективное, но очень простое.
добавил в тестилку, плюс запилил минимакс — jsfiddle.net/vp_arth/TbYtF/4/
Ловите очень тупое, очень быстрое решение, которое за призы может и побороться :)
jsfiddle.net/by8c6/1/
jsfiddle.net/by8c6/1/
Хм, добавил свое решение в тестилку: jsfiddle.net/TbYtF/6/
Стабильно показывает лучший результат и по очкам и по времени. Не думал, что столь тупой алгоритм может быть настолько эффективен.
Стабильно показывает лучший результат и по очкам и по времени. Не думал, что столь тупой алгоритм может быть настолько эффективен.
С первого же раза все заполнил :)
jsfiddle.net/QPC7v/
jsfiddle.net/QPC7v/
Забыл обновить… jsfiddle.net/QPC7v/4/
Никого здесь не смущает, что задача о заполнении рюкзака (частными случаем которой является и предложенный вариант тетриса) является NP-полной? И что оптимальное решение NP-полной задачи может быть получено только методом полного перебора?
Нет не смущает. В задаче с рюкзаком, нам известен набор вещей заранее, а тут другая задача.
И что? NP-полной задачей является не только задача в канонической форме, но и любая задача, сводимая за полиномиальное время к любой из канонических.
Доказано, что классический тетрис является именно NP-полной задачей.
Доказано, что классический тетрис является именно NP-полной задачей.
Доказано, что классический тетрис является именно NP-полной задачей.А ссылочкой не поделитесь?
Ну или хотя бы формулировкой «классической задачи тетриса», так чтобы ее можно было к NP-задачам отнести?
Наоборот, NP-полная задача — та, к которой сводится другая NP-полная задача (плюс наша задача еще сама должна лежать в NP).
Дык частный случай же. Да и NP-полные задачи необязательно решаются «полным перебором».
НЛО прилетело и опубликовало эту надпись здесь
А можно еще один мой алгоритм разместить? Он тоже довольно простой, но намного эффективнее: jsfiddle
Действительно хороший алгоритм, но финишную часть надо бы доработать, чтобы при сильном заполнении стакана оставлял место для вертикальной «палки»
Спасибо. Попробую, но он и так очень медленный, боюсь, что тогда придется 5 секунд ждать на выполенние:)
Добавил оставление места для палки, но так он наоборот теряет в эффективности, где-то 2-5(в зависимости от порога сильного заполнения) очек на 100 запусков. Ну по крайней мере в моей реализации.
Алгоритм ваш мне понравился, компактно написан.
jsfiddle.net/TbYtF/7/
оставил лучший из трёх
оставил лучший из трёх
Да, спасибо!
Что-то меня так никто и не добавил :) jsfiddle.net/QPC7v/7/
Спасибо вам огромное за ваш тест! С ним намного удобней. Давайте тогда добавим всех участников. На моём блоге оставили такое решение:
jsfiddle.net/H3kra/
jsfiddle.net/H3kra/
Вот товарищ один еще усовершенствовал своё решение, тоже может принять участие. jsfiddle.net/Night_Death/K4x3M/5/
во первых, невалидный код — не закрыт блок switch.
во вторых, некорректный алгоритм:
— возвращает значения от 0 до 9, вместо «от 1 до 10»
— не проверяет влезет ли фигура в эту колонку
во вторых, некорректный алгоритм:
— возвращает значения от 0 до 9, вместо «от 1 до 10»
— не проверяет влезет ли фигура в эту колонку
Извините, я не сохранил последнюю версию в jsFiddle, поэтому и глупейшие ошибки присутствуют. Вот: jsfiddle.net/kaY62/2/
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Задача по расположению фигур в игре «Тетрис»