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

Я решил подкинуть Хабрасообществу небольшую задачу по поиску и реализации лучшего алгоритма. Все знают игру «Тетрис». Представьте, что вместо вас в эту игру играет компьютер. Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест. Я сделал на JSFiddle простой UI для тестирования алгоритма. Всё, что вам нужно — это реализовать одну функцию. Но стойте, для начала я объясню правила.



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

• Всего 2 фигурки: 1x4 и 2x2


• Размер поля: 10x20


• 2 положения — вертикальное и горизонтальное


• Нельзя поворачивать фигурки


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

В коде есть одна пустая функция (точнее, сейчас она возвращает какое-то случайное число) — getColumnNumberForLeftFigureSquare(w, h). Вам нужно будет ее реализовать. w — это ширина новой фигурки, h — это высота. Всего вы можете пользоваться 3-мя переменными: w, h и cols. cols — это массив, состоящий из 10 элементов. Каждый элемент — это колонка, значение — занятая высота колонки. Функция должна возвращать целое число от 1 до 10 включительно. Это будет номер колонки, в которую упадет самая левая клеточка фигуры.

Всего в данном тетрисе 200 клеточек, т.е. вы сможете тестировать свой алгоритм по количеству оставшихся для заполнения (выводится в UI)

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

Еще раз ссылка на JSFiddle

P.S. Если увидите ошибки в самом UI — сообщите мне.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.