задачка (математическое)

[avva]

Очень милая задачка от Джона Конвея (изобретателя игры "Жизнь").

Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.

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

Ваша задача - придумать алгоритм, как перекладывать карты, чтобы в конце концов придти к выигрышному положению, когда слева лежат туз, король, дама (туз верхний, дама нижняя), а остальные позиции пустые. Но есть одно осложнение. У вас нет краткосрочной памяти. Каждый раз, когда вы делаете ход, вы забываете, что было раньше, и видите только карты, как они лежат сейчас.

(да, из этого следует, что вы не можете сами обнаружить, когда выиграли. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).

Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.

Comments

[ilya-dogolazky.livejournal.com]

глубина стопки видна? а, наверное не видна, иначе слишком просто

[avva.livejournal.com]

не видна.

[mudasobwa.livejournal.com]

    » из этого следует, что вы не можете сами обнаружить, когда выиграли
Это почему это? Существует момент, когда я вижу карты и они лежат правильно. Или мне нужно вообще запретить смотреть на стол, что сводит задачу к медиумной.

[self_perfection_lj]

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

[carfagen.livejournal.com]

Например, может быть так, что слева лежит король на даме
Are we sure we are talking about card? ;-)

[avva.livejournal.com]

:)

[vsh.livejournal.com]

Решил! Получилось, правда, неизящно, целых четыре правила.

[avva.livejournal.com]

Только четыре? Совсем неплохо, у меня, например, их больше (сколько в точности - смотря как считать) :)

Если вы не уверены на сто процентов и хотите проверить свое решение, то вот программа, которую я написал, чтобы проверить свое:

http://pastebin.com/BkQAKNKQ

Нужно в определении переменной decider в конце описать поведение своего алгоритма в ответ на любую конфигурацию карт, где _ означает пустую позицию. Сейчас я там вбил везде "12" вместо своего решения, что означает всегда передвинуть с первой позиции на вторую, и не работает, ясно. Нужно это поменять на "12", "13", "21", "23", "31" и "32" в соответствии со своим алгоритмом, потом запустить программу.

[dark-barker.livejournal.com]

есть относительно немного вариантов расположения карт. даже при случайных перекладываниях очень быстро будет решение)))

вообще, очевидно, решение тут сводится к построению конечного автомата на состояниях картины которую мы видим

[freedom_of_sea.livejournal.com]

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

позиция при которой стопка слева, сверху туз достигается одноходовкамии

[avva.livejournal.com]

Не очень понял, что значит "кладем туза налево" если и так уже все слева. В общем, это не выглядит правильным решением.

[melkiythegreat.livejournal.com]

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

[avva.livejournal.com]

Да, именно так.

[vnarod.livejournal.com]

Решил на бумаге пока на работу ехал. Честно говоря, не показалось очень сложным.

[vnarod.livejournal.com]

добрался до работы :)
мой вариант. Всего три основных правила.
1. Если видны три карты, то ДКТ->К_Т, КТД->_КД, КДТ->К_Д, ТДК->Т_Д
2. Если видны 1 или 2 карты, то
- К_Т или КТ_ ->Т__ решено
- если нет, то карты слева от дырки двигаем на дырку. Если дырка слева, двигаем на нее правую карту

[ksega.livejournal.com]

Я бы делал так.
1)Очевидно, какая стратегия перекладывания если бы мы видели не только верхнюю, но и карты лежащие ниже (например, сначала отложить даму посередине, а все остальные карты справа, потом начинать укладывать в порядке их слева). Таким образом Для каждого состояния расположения карт у нас есть следующее действие диктуемое стратегией.
2) Теперь для случая, когда мы видим только верхнюю карту. В таком случае наблюдаемое состояния может соответствовать от 1 до 2 полных состояний (например если мы видим туза справа и все, то это может быть туз дама король или туз король дама). И действие алгоритма такое, если состояние полностью определено(например, лежат слева направо туз король дама), то действуем в соответствии с пунктом первым, если состояние не полностью определено, то с вероятностью 0.5 выбираем действие для соответствующее первому состоянию, с вероятностью 0.5 соответствующее второму состоянию.
Очевидно, что для каждого начального состояния, есть конечная вероятность достичь результата. Мат ожидание будет конечно. Но каждая конкретная игра может занять долгое время.

[iisus.livejournal.com]

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

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

при этом, количество ходов, затрачиваемых на решение может быть в некоторых случаях быть меньше для случайного поиска, чем для детерминистического, но статистически время работы случайного метода будет, наверное, раза в полтора-два дольше

[huzhepidarasa.livejournal.com]

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

[captain-tylor.livejournal.com]

1. КТ_, К_Т - туз на короля.
2. Прочие случаи с двумя или одной видимыми картами - кладем карту, справа от которой пусто, на это пустое место (правым от L считается M, от M - R, от R - L).
3. Если видны все три карты. Если дама на L - короля на даму. Если дама на M - даму на R. Если дама на R - L на M.

[avva.livejournal.com]

Да, логично и вроде бы работает.

[sinyuk alexey (from livejournal.com)]

10 правил. Левая позиция ключевая, а середина/справа - нет, поэтому середина и право могут меняться в условии.

Условие : Действие

A K/Q Q/K : A на K
K Q/A A/Q : K на A
Q K/A A/K : K на Q

0 A/K Q : Q на 0
K A 0 : A на K
A Q 0 : A на 0
Q K/A 0 : Q на 0

A 0 0 : A на 0
K 0 0 : K на 0
Q 0 0 : Q на 0

Три правила

[mudasobwa.livejournal.com]

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

Вроде работает.

Re: Три правила

[mudasobwa.livejournal.com]

А, черт. Так мы получим ДКТ.

[angerona.livejournal.com]

Написано по очереди проверки (если условие выполнено, исполняем действие и опять начинаем проверку сверху)

1. Если видны только К и Т и К слева, то кладем Т на К
2. Если Д слева и видимы К и Т, то кладем К на Д
3. Если Д слева и видим только К и К посредине, то кладем К на Д.
4. Если Д видна и самое левое место свободно, то кладем Д туда
5. Если Д видна, но левое место не свободно, то берем карту оттуда и кладем НЕ на Д.
6. Если Д слева, но не видим К, а Т посредине, то двигаем Т на правое место.
7. Если Д слева, но не видим К, а Т справа, то двигаем Д на среднее место.
8. Если виден только К слева, то кладем его на самое правое место
9. Если Д слева, посредине пусто, а справа К, то двигаем К на средину.
10. Двигаем самую верхнуюю левую карту направо.

Только, кажется, я под конец запуталась.

[gul-kiev.livejournal.com]

Начальная позиция: дама слева, король-туз справа (туз сверху).
По правилу 7 двигаем даму в центр.
Потом по правилу 4 двигаем даму влево, чем возвращаемся к исходной позиции.

Другой вариант. Слева туз-дама-король, король сверху.
По правилу 8 кладём короля вправо.
Потом по правилу 9 кладём короля в центр.
Потом по правилу 3 кладём короля на даму, приходим к исходной позиции.

[taganay.livejournal.com]

Самый простой работающий алгоритм - снять верхнюю карту из случайной позиции и положить ее в случайную позицию. Когда-нибудь к верному решению придем, вариантов не бесконечное количество.
Нормальный алгоритм тоже вроде придумал, надо записать теперь, пока не забыл.

[burrru.livejournal.com]

Напоминает задачу про вращающийся стол и четыре выключателя.

[avva.livejournal.com]

Да, мне ее как раз сегодня напомнили и я решил заново. Но она проще.

[zero-sharp.livejournal.com]

Забавно, что и для ханойских башен существует алгоритм с почти такими же характеристиками.

Он формулируется как «переносим поочерёдно либо меньший диск по часовой стрелке, либо второй по размеру диск». Как видно, во входных данных есть ещё и чётность номера хода. Интересно, можно ли от этой чётности избавиться. (Например, как-то «захешировав» все состояния)

[p_govorun.livejournal.com]

(не читая комментов)

Вот такое решение.

0. Если все карты на одной позиции -- положить верхнюю куда попало.
1. Если две позиции заняты, а третья свободна -- переместить на свободную позицию карту, лежащую слева от неё. (На крайнюю левую позицию -- с крайней правой). В результате через один или два хода карты будут лежать по одной.
2. Если дама не слева -- переложить карту так, чтобы пункт 1 алгоритма привёл даму налево. (Дама на M -- переложить её на R; дама на R -- переложить карту с L на M.)
3. Если дама слева -- положить на неё короля.
4. (Исключение из правила 1.) Если король слева, а дамы не видно -- положить туза на короля. При этом мы либо выигрываем, либо дама оказывается под тузом и начинает действовать правило 1.
Бонус: если все карты на одной позиции, и мне смутно помнится, что я что-то с ними делал -- я выиграл. И даже наблюдателя не надо.

[a-konst.livejournal.com]

Довольно очевидно, что если алгоритм есть, то его можно переделать в не менее эффективный "без памяти". Разве нет?

[a-konst.livejournal.com]

А нет, ошибся.

[onedrey.livejournal.com]

Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас

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

[comichelle.livejournal.com]

А если в какой-то момент я вижу слева туза, а остальные места пустые, я понимаю, что это значит, что там туз-дама-король? То есть, если игра заканчивается, я об этом мгновенно узнаю?

[comichelle.livejournal.com]

Всё, уже поняла, что узнаю:)

[ansr.livejournal.com]

На всякий случай уточню для себя - это некий длинный стол или на столе есть три фиксированных слота под карты?

[avva.livejournal.com]

три фиксированных слота.

[pffnzrpb.livejournal.com]

Вчера заходил в родной институт, прошел в комнату отдых выпить кофе. Там вся доска исписана рисуночками вида: Т_Д, К__, КТ_, и тд, соединенных стрелочками.

[avva.livejournal.com]

:)

[tigran martirosyan (from livejournal.com)]

1. Карта всегда передвигается на соседний слот.
2. Передвижение влево от левого (L) слота переходит в правый (R), передвижение вправо от правого (R) - в левый (L)
3. Туз и дама всегда передвигаются влево, король - вправо.
4. Передвижение разрешено, если слот назначения пустой или в нем находится младшая карта (старшинство в порядке возрастания: дама, король, туз). Так, дама может передвигаться только в пустой слот.
5. За ход передвигается младшая карта из тех, у которых есть разрешенное передвижение.

:)

[kotakahr.livejournal.com]

Как обычно, тот кто писал недурно написал!