Я решил подкинуть Хабрасообществу небольшую задачу по поиску и реализации лучшего алгоритма. Все знают игру «Тетрис». Представьте, что вместо вас в эту игру играет компьютер. Так вот, задачей будет описать алгоритм, который будет правильно размещать фигурки, таким образом, чтобы не было пустых мест. Я сделал на JSFiddle простой UI для тестирования алгоритма. Всё, что вам нужно — это реализовать одну функцию. Но стойте, для начала я объясню правила.
Я решил пока не делать полный аналог тетриса, так как начинать нужно с малого, тогда, возможно, большее количество людей сможет проверить себя. Итак, упрощения нашего тетриса:
- Всего 2 фигурки: 1x4 и 2x2
- Размер поля: 10x20
- 2 положения — вертикальное и горизонтальное
- Нельзя поворачивать фигурки
- Фигурки появляются случайным образом, случайно повернутые. Вам нужно найти оптимальное для нее место
В коде есть одна пустая функция (точнее, сейчас она возвращает какое-то случайное число) — getColumnNumberForLeftFigureSquare(w, h). Вам нужно будет ее реализовать. w — это ширина новой фигурки, h — это высота. Всего вы можете пользоваться 3-мя переменными: w, h и cols. cols — это массив, состоящий из 10 элементов. Каждый элемент — это колонка, значение — занятая высота колонки. Функция должна возвращать целое число от 1 до 10 включительно. Это будет номер колонки, в которую упадет самая левая клеточка фигуры.
Всего в данном тетрисе 200 клеточек, т.е. вы сможете тестировать свой алгоритм по количеству оставшихся для заполнения (выводится в UI)
Делайте форки фиддла и отправляйте в комментарии. Любая попытка будет оценена. Идеально, решение должно быть максимально эффективным и максимально производительным. Потом мы можем усовершенствовать тетрис до оригинального.
P.S. Если увидите ошибки в самом UI — сообщите мне.
Автор: plutov
