Здравствуйте, Кодт, Вы писали:
К>http://i.imgur.com/dAtcCfH.gif[/img]
К>Ну и этюд для программистов: придумать алгоритм управления змейкой.
Не, это тривиально -- уменьшать заметаемую площадь. А вот задача покруче -- найти минимальную длину змейки, ее конфигурацию (не считаем, что управление было оптимальным) и положение яйца, которая на заданном поле уже не сможет съесть его.
Здравствуйте, denisko, Вы писали:
К>>Ну и этюд для программистов: придумать алгоритм управления змейкой. D>Не, это тривиально -- уменьшать заметаемую площадь. А вот задача покруче -- найти минимальную длину змейки, ее конфигурацию (не считаем, что управление было оптимальным) и положение яйца, которая на заданном поле уже не сможет съесть его.
На самом деле, не совсем тривиально.
Одно из возможных решений — построить гамильтонов цикл и всегда бегать по нему.
Проблема здесь лишь в том, что время достижения яйца не условно-линейное (по кратчайшему пути), а условно-квадратичное (через все свободные ячейки).
В реальных змейках у яиц был таймаут, после которого они исчезали и перебазировались в новом месте.
А задача про минимальный геймовер — ну, например, такой ответ
Змейка, чья голова 1, хвост 8
345
216
87
яйцо — в любой другой точке. Управление было жесточайше неоптимальным.
Предшествующий скриншот выглядит так
234
1@5
76
поворачиваем за яйцом, съедаем его и геймовер.
Почти очевидно, что змейка или попадает в заранее подготовленный (предыдущим неоптимальным управлением) тупик и вскоре погибает, или (начав оптимально управляться с данного момента) способна добраться до любой точки игрового поля.
Минимальный тупик я показал.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, denisko, Вы писали:
К>>>Ну и этюд для программистов: придумать алгоритм управления змейкой. D>>Не, это тривиально -- уменьшать заметаемую площадь. А вот задача покруче -- найти минимальную длину змейки, ее конфигурацию (не считаем, что управление было оптимальным) и положение яйца, которая на заданном поле уже не сможет съесть его.
К>На самом деле, не совсем тривиально.
К>Одно из возможных решений — построить гамильтонов цикл и всегда бегать по нему.
Ну или по-просту максимально длинный путь без самопересечений. К>Проблема здесь лишь в том, что время достижения яйца не условно-линейное (по кратчайшему пути), а условно-квадратичное (через все свободные ячейки). К>В реальных змейках у яиц был таймаут, после которого они исчезали и перебазировались в новом месте.
Все равно, если бегаешь так, то умрешь последним (но, может быть, голодным). А вообще отсюда много довольно интересных задач вытекает, даже не связанных непосредственно с управлением. Типа существования хоть какой-то стратегии, когда время появления и исчезновения яиц сравнимо или много меньше длины питончика (скорость всегда 1).
Здравствуйте, fin_81, Вы писали:
_>На сколько я помню для квадратной решетки нечетного размера нельзя построить гамильтонов путь.
Ну и нестрашно. Для такой решётки без одной клетки можно построить путь.
Прокладываем два пути, отличающихся в одной клетке — например, без 1,1 и без 2,2. Дальше, по-моему, очевидно.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, fin_81, Вы писали:
_>>На сколько я помню для квадратной решетки нечетного размера нельзя построить гамильтонов путь.
К>Ну и нестрашно. Для такой решётки без одной клетки можно построить путь. К>Прокладываем два пути, отличающихся в одной клетке — например, без 1,1 и без 2,2. Дальше, по-моему, очевидно.
А можно ли переключится на другой путь когда змейка полная?
Здравствуйте, fin_81, Вы писали:
_>А можно ли переключится на другой путь когда змейка полная?
Дык, разумеется.
Вот у нас ситуация: n-1 точка содержит змейку, последняя n'ная точка — яйцо.
Добегаем до точки ветвления (1,2) и съедаем яйцо. При этом гамильтонов цикл размыкается, а змейке больше некуда расти. Мультик!
Вот, к примеру, поле 3*3.
цикл цикл змейка добежала и съела!
через через до яйца
1,1 2,2
+-+-+ + +-+ @ #-# @ #-# H #-#
| | | | | | | | | | |
+ + + +-+ + #-# H H t # # t #
| | | | | | | | |
+-+-+ +-+-+ #-#-t #-#-# #-#-#
Здравствуйте, Кодт, Вы писали:
_>>А можно ли переключится на другой путь когда змейка полная?
К>Дык, разумеется. К>... К>Вот, к примеру, поле 3*3. К>...
Это еще не доказательство для всех размеров полей и почти полных змеек длиной n-k (k>=1).
Решение не знаю.
Здравствуйте, denisko, Вы писали:
К>>Одно из возможных решений — построить гамильтонов цикл и всегда бегать по нему. D>Ну или по-просту максимально длинный путь без самопересечений.
Путь (должен) быть замкнутым. Иначе мы рискуем пробежать до конца этого пути и упереться.
Либо это должен быть максимально длинный путь в пространстве-времени (с учётом того, что освобождается место от хвоста), — но это "по определению" и неконструктивно.
Можно поискать середину между достаточным условием (цикл) и необходимым, но неконструктивным. Какой-то класс путей...
К>>В реальных змейках у яиц был таймаут, после которого они исчезали и перебазировались в новом месте. D>Все равно, если бегаешь так, то умрешь последним (но, может быть, голодным). А вообще отсюда много довольно интересных задач вытекает, даже не связанных непосредственно с управлением. Типа существования хоть какой-то стратегии, когда время появления и исчезновения яиц сравнимо или много меньше длины питончика (скорость всегда 1).
Если таймаут яйца больше, чем количество свободных клеток (делённое на скорость змейки), то, как бы яйцо ни перебазировалось, рано или поздно гамильтонова змейка до него добежит. Либо сдохнет с голоду, конечно...
Здравствуйте, fin_81, Вы писали:
_>Это еще не доказательство для всех размеров полей и почти полных змеек длиной n-k (k>=1). _>Решение не знаю.
Для поля 2n*2n есть цикл.
Для поля 2n*(2n-1) есть цикл.
Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен.
Завтра придумаю, как он выглядит.
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, fin_81, Вы писали:
_>>Это еще не доказательство для всех размеров полей и почти полных змеек длиной n-k (k>=1). _>>Решение не знаю.
К>Для поля 2n*2n есть цикл. К>Для поля 2n*(2n-1) есть цикл. К>Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен. К>Завтра придумаю, как он выглядит.
Здравствуйте, AlexRK, Вы писали:
ARK>Здравствуйте, Кодт, Вы писали:
К>>Ну и этюд для программистов: придумать алгоритм управления змейкой.
ARK>Круто! ARK>Я даже до половины никогда не доходил.
так здесь компьютерное управление, не ручное, с клавиатуры.
Здравствуйте, dimgel, Вы писали:
D>Здравствуйте, clickfraudprotection, Вы писали:
C>>так здесь компьютерное управление, не ручное, с клавиатуры.
D>Слишком витиеватая траектория местами для компьютерного управления.
поскольку скорость большая то вручную с клавиатуры маловероятно. а вот заранее расчитать траекторию возможно.
Здравствуйте, clickfraudprotection, Вы писали:
К>>Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен. К>>Завтра придумаю, как он выглядит.
C>http://en.wikipedia.org/wiki/De_Bruijn_sequence C>так. "змея" максимум семимерная.
Моя круче умеет (на A* 2). :р Правда, все равно тупая. :) Иногда такие триллеры получаются — никаких мультиков не надо (Replay -> вставить -> Load -> Start).
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, clickfraudprotection, Вы писали:
К>>>Для поля (2n-1)*(2n-1) с выколотой точкой (2,2) есть цикл? Если да, то и с выколотой точкой (1,1) есть, и именно такой, какой нам нужен. К>>>Завтра придумаю, как он выглядит.
C>>http://en.wikipedia.org/wiki/De_Bruijn_sequence C>>так. "змея" максимум семимерная.
К>При чём здесь последовательность де Брёйна?
гамильтонов путь самый длинный возможен только в них.
От выколотого угла
— в одну сторону — идём по краю поля
— в другую сторону — обходим квадрат (2n-1)×(2n-1) "волнами": {вниз, влево, вправо, вверх}
Затем
— в одну сторону — идём дальше по краю поля
— в другую — обходим оставшийся прямоугольник чётной ширины: {вверх, вниз}
И встречаемся в углу, противоположном выколотому.
Как построить многомерную змейку в гиперпрямоугольнике с нечётными сторонами — это отдельная интересная тема...
Здравствуйте, clickfraudprotection, Вы писали:
К>>При чём здесь последовательность де Брёйна? C>гамильтонов путь самый длинный возможен только в них.
Всё равно не уловил, как это.
Вот у нас есть, к примеру, 8-мерный куб с чётной длиной ребра. И что, хочешь сказать, в нём невозможно построить гамильтонов цикл?
Контрпример элементарный. Рассмотрим 8-куб с ребром 2. Каждой клетке соответствует, очевидно, 8-разрядный двоичный вектор.
Строим код Грея, и готово!
Ну почему же? Примерно так же это выглядело хрен-знает-сколько-лет назад у меня на Nokia 3310, только там всё было ещё хуже: во-первых, еда исчезала, если не сожрать, через некоторое время, плюс типов еды было два или даже больше (больший кусок давал больше прироста хвосту). Классная игра, вообще-то.
К>Ну и этюд для программистов: придумать алгоритм управления змейкой.
встречал похожий этюд. найти минимальную и максимальную длину и ширину поля при котором не существует выигрышной стратегии у змейки (яйцом играет компьютер). игра пошаговая (как в уфо), т.е. не на реакцию. яйцо не может дважды выпадать на том же месте. змейка увеличивается на одну клетку каждый второй шаг. яйцо ждет N шагов, где N это сумма длины и ширины игрового поля, после чего перебазируется.
я нашел решение если яйцо ждет C ходов, где C не зависит от размеров поля и достаточно велико. а когда все взаимосвязано, то тут я туплю. жопой чувствую, что решение есть, а найти не могу. минимальную конфигурацию можно найти методом перебора. там и перебирать нечего. а максимальную? размер змейки растет квадратично (с увеличением поля), а "ожидание" змейки -- линейно.
и странное доп. условие, что на одну и ту же клетку яйцо не попадает дважды. из чего следует, что змейке можно выиграть тупо вращаясь в цикле пока яйцо не обойдет все клетки. но что-то я все проигрываю да проигрываю. яйцо в самую последнюю минуту падает там где был хвост, а я никак не могу до него дотянуться. а если не дотянулся -- то все. змейка проиграла. а надо чтобы она съела и следующему яйцу некуда было упасть (змейка заняла все клетки или яйцо на них уже успело побывать).
americans fought a war for a freedom. another one to end slavery. so, what do some of them choose to do with their freedom? become slaves.
Перекуём баги на фичи!
