MihailOlenin Oct 19 2009 at 14:34

Как придумать алгоритм?

1 min

1.4K

Lumber room

+13

Comments 26

NYMEZIDE Oct 19 2009 at 14:41

Как вариант полный перебор. Долго, не спорю. Но ограничений по времени нет.

Napolsky Oct 19 2009 at 14:47

брут — это как минимум не интересно и не по джентельменски ;)

habralan Oct 19 2009 at 14:57

сделаем оценку сверху для полного перебора. всего шариков 12*11 = 132. каждым кликом убиваем не меньше двух шариков. допустим худший (нереальный) случай, что убиваем ровно два шарика на любом ходу. получаем 66 кликов, или 66! ~ 5.4*10^92… многовато

если брать жадный перебор с отсечениями (ну например, убивать всегда не меньше шести шариков, останавливаться, если из оставшегося количества шариков точно не получится рекорда и т.д.), то ну скажем для 20 ходов, на каждом из которых надо сделать выбор, ну, скажем, из четырёх вариантов… получим 4^20 ~ 10^12 — разумнее, но всё равно долго (для миллиона проверок в секунду уйдёт что-то порядка 35тыс лет)

так что надо искать что-то более разумное

smind Oct 19 2009 at 16:57

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

Olexiy Oct 19 2009 at 15:11

Неявное ограничение, на самом деле, есть — надо посчитать при нашей жизни.

b00taNik Oct 19 2009 at 14:53

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

Когда никакой другой цветовой комбинации не остается — убираем набираемую, повторяем алгоритм. Обычно 2-3 итерации позволяют набрать 2-3 тысячи очков. Мало это или нет, я не знаю.

UFO just landed and posted this here

MihailOlenin Oct 19 2009 at 15:05

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

-1

ayurganov Oct 19 2009 at 15:38

а что тут непонятного? каких шариков больше, тот и выбирать

MihailOlenin Oct 19 2009 at 16:00

Если у нас в итоге будет несколько одного цвета групп не связных друг с другом — это будет неоптимально

RomanL Oct 19 2009 at 16:11

Тогда выбирать цвет с экстремумом по двум параметрам: количество шариков и число групп по принципу «чем больше шариков и меньше число групп — тем лучше».

olexandr17 Oct 19 2009 at 19:08

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

ayurganov Oct 19 2009 at 22:29

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

sylvio Oct 19 2009 at 15:01

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

Olexiy Oct 19 2009 at 15:11

А количество возможных состояний для ДП вы посчитали?

MihailOlenin Oct 19 2009 at 15:14

Один сдвиг, к сожалению мало дает… Я плохо представляю себе, что хранить для динамического программирования. В обходе лабиринта используется хранение координат тех ячеек, в которые мы попали на прошлой итерации.

sylvio Oct 19 2009 at 15:36

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

MihailOlenin Oct 19 2009 at 16:01

На каждом шаге лабиринт меняется

Baks Oct 19 2009 at 17:16

как-то тут я лабиринта не вижу… вижу только дерево при том дерево полного перебора.
причём тогда тут ДП.?

XaBoK Oct 19 2009 at 17:28

Дело в том, что оптимальный вариант скорее всего проявится очень глубоко. То есть если считать очки, то первые ходы будут слабо продуктивны по очкам.
Если решать через какой-нибудь А*, то простой эвристической должна стать длинна (количество объеденных шариков) основного цвета (того цвета, которого больше в начале). При выборе цвета надо учитывать и позицию шариков, так как чем выше находятся шарики, тем больше манипуляций с ними можно сделать и есть ли между шариками есть пустоты — вертикальные линии в которых этот цвет не присутствует. Если я не ошибаюсь, то шарики могут сдвигаться только вертикально вниз, а значит если есть по середине колонка без основного цвета, то вам уже никогда не объединить две части в одно целое (значит что если синих шаров 12, а красных 10, но между синими есть пустота делящая их, допустим, на 8 и 4, то 10 красных за раз дадут больше очков)

BarsMonster Oct 19 2009 at 16:31

Эх люблю я это дело, писал резидентную игралку в тетрис для Dos Navigator-а на ассмеблере, и проходилку сапера на скорость :-)

Avart Oct 20 2009 at 00:52

Нужно посчитать алгоритм, по которому считается сумма за кол-во шаров.
Выбрать цвет, которого больше всего.
Просчитать возможные варианты.

А вообще спасибо автору за идею. Подумаю над реализацией.

ЗЫ Средний счёт мегасдвига 786 :)

MihailOlenin Oct 20 2009 at 07:39

Вот с просчетом вариантов основная проблема. Нужно что-то конкретное, чем просчет всех вариантов. Опять же цвет, который мы выбрали, мб в 2-х несвязных группах, которые не удастся связать.

Boomburum Oct 20 2009 at 02:49

Я начинаю с верхнего левого угла, оставляя на сладкое цвет, которого больше всего )

Прикол — один мой знакомый пошел устраиваться на работу… в конце собеседования ему предложили сыграть в эту игру — «если наберешь больше 2000, возьмем без испытательного срока». Набрал, взяли )

MihailOlenin Oct 20 2009 at 07:41

Позиция с логистикой была связана?
Я уж подумал, что если наберешь, то не возьмут, как помешанного на играх =)

MihailOlenin Oct 20 2009 at 07:40

На одном из форумов, я нашел стратегию убирать шарики одного цвета по очереди (то есть сначала все зеленые, потом все красные, потом все синии) и так пока не останется один цвет.

Show the best of all time