PolyminoLab — это сильно!
P>Вот так оно перебрало все лабиринты площадью 4. Площади 5 и 6 я ручками проверил, тоже вроде всё верно. Дальше надеюсь тоже не врёт. Считает довольно шустро.
А вот у меня на Атлоне 800 для N=12 считала час.
P>Ниже код, вполне готовый к компиляции. Основная идея не сильно изменилась — волновое распространение. Начинаем с верхней-левой клетки. В неё можно поставить трёх разных "ёжиков" — только_направо, только_вниз, направо_и_вниз. Пробуем поставить каждого и пораспространяться с этого обрывка. И так далее. Каждый раз, ставя ёжика, смотрим, куда он ОБЯЗАН торчать, а куда ПО ЖЕЛАНИЮ. Все желания реализуем по очереди. Основная проблема — перебрать быстро и уникально — для этого, как обычно, организуем fifo.
Можно четвертого — лысого. Но это для лабиринта из одной клетки.
P>Кодирующая последовательность мне здесь совсем не нужна — перебираю сразу раскодированные лабиринты. Но для понимания того, что происходит, могу описать. Каждый лабиринт кодируется линейкой полубайт — по одному на каждую занятую клетку. В каждом полубайте лежат 4 бита — наличие выходов из этой клетки во все 4 стороны. Они зависимы — каждая стенка по сути помечается дважды, поэтому кодировка явно не плотнейшая, но нам по фигу. Последовательность полубайт в линейке определяется распространением от верхней левой клетки — куда раньше пришли, та клетка раньше и описывает в линейке свои выходы.
У меня трех битов хватает — раз прошли в клетку, значит позади нас стенки нету.
P>Всё, на вопросы по коду готов ответить. P>RS, как твой робот вылезет из площади 4, напиши, интересно.
Самому интересно, я еще не смотрел. В среду че-нить принесу.
А пока для 2x3 27, для 2x3&3x2 33, для 3x3 140.
Здравствуйте, RS, Вы писали:
RS>P.S. Вот кой-какие результаты:
RS>1: 1 RS>2: 2 RS>3: 6 RS>4: 23 RS>5: 95 RS>6: 420 RS>7: 1920 RS>8: 9047 RS>9: 43462 RS>10: 212203 RS>11: 1049053 RS>12: 5239622
RS>P.P.S. Я то знаю, у Пушкина прога с минуты на минуту для N=50 лабиринты выдаст.
У меня за минуту Celeron 1200 посчитал N=13.
Но хуже другое — начиная с N=8 у нас с тобой результаты расходятся!!! У меня 9049.
Как проверить, кто прав, не знаю. Ау, MichaelP, где твои любимые сайты?
Возможно N=8 выделно тем, что это первая площадь, где возможна честная петля.
Здравствуйте, RS, Вы писали:
RS>Можно четвертого — лысого. Но это для лабиринта из одной клетки.
Лысых не учитываем
RS>У меня трех битов хватает — раз прошли в клетку, значит позади нас стенки нету.
Думаю, если поставить такую задачу, то можно и ещё зажать. КАЖДАЯ ВНУТРЕННЯЯ стенка может быть учтена лишь один раз.
RS>А пока для 2x3 27, для 2x3&3x2 33, для 3x3 140.
Мне кстати не очевидно, как ты генеришь стенки для скажем 3х3.
Надо же, чтоб односвязным получилось.
Неужели просто генеришь все варианты стенок и проверяешь, зальётся ли?
Может есть какой особый алгоритм быстрого перебора для прямоугольных лабиринтов?
Кстати задача:
Сколько стенок можно поставить в кваднате NxN так, чтобы он остался односвязным?
Здравствуйте, Pushkin, Вы писали:
P>Но хуже другое — начиная с N=8 у нас с тобой результаты расходятся!!! У меня 9049. P>Как проверить, кто прав, не знаю. Ау, MichaelP, где твои любимые сайты? P>Возможно N=8 выделно тем, что это первая площадь, где возможна честная петля.
Ну тут три варианта:
1. У тебя есть одинаковые — проверь (само изображение).
2. У меня чего-то не хватает (а вот тут хрен проверишь — 9 килолабиринтов — сдохнуть можно).
3. Сочетание (1) и (2).
Здравствуйте, Pushkin, Вы писали:
P>Лысых не учитываем
Вообще лысых — конечно. Но если не четыре бита, а три — то вполне будут лысые (то, через что пришли — не иголка, а что-то еще).
P>Думаю, если поставить такую задачу, то можно и ещё зажать. КАЖДАЯ ВНУТРЕННЯЯ стенка может быть учтена лишь один раз.
Более того — у меня не стабильно три бита, а от 0 до трех. Смотри код. То есть, если решили, что тут стенка есть, а тут ее нет, то в обоих случаях, оказавшись в соседних клетках, эти стенки уже не рассматриваем, и биты на них не отводим.
P>Мне кстати не очевидно, как ты генеришь стенки для скажем 3х3. P>Надо же, чтоб односвязным получилось. P>Неужели просто генеришь все варианты стенок и проверяешь, зальётся ли?
Мне очень стыдно, но до позавчера я именно так и делал
P>Может есть какой особый алгоритм быстрого перебора для прямоугольных лабиринтов?
Может и есть.
P>Кстати задача: P>
P>Сколько стенок можно поставить в кваднате NxN так, чтобы он остался односвязным?
Здравствуйте, Pushkin, Вы писали:
P>Хорошо, проверю. Не изображение, конечно P>Множество поюзаю эстээльное...
Ну конечно не изображение, но и не его представление в виде кодирующей последовательности.
RS>>2. У меня чего-то не хватает
P>Очень надеюсь
Если у меня не хватает, я бы попросил тебя прислать мне на мыло все твои 9 килолабиринтов в некотором общем для нас формате, и я тогда буду сравнивать.
Готов начать обсуждение формата. Но ты сперва у себя дупликаты поищи, это все-таки проще (для меня, во всяком случае).
P.S. Что-то мне подсказывает (лень, скорее всего), что у меня все правильно.
Здравствуйте, RS, Вы писали:
RS>Ну конечно не изображение, но и не его представление в виде кодирующей последовательности. RS>Если у меня не хватает, я бы попросил тебя прислать мне на мыло все твои 9 килолабиринтов в некотором общем для нас формате, и я тогда буду сравнивать. RS>Готов начать обсуждение формата. Но ты сперва у себя дупликаты поищи, это все-таки проще (для меня, во всяком случае).
Здравствуйте, Pushkin, Вы писали:
P>OK, но не факт что сегодня...
Ну я и сам попробую, сорец-то твой есть.
Но что-то мне не нравится идея, что у тебя у стенок нет неопределенного состояния. Эдак, не поставив стенку один раз, мы можем поставить ее, подойдя к ней с другой стороны. И тогда две разные кодирующие последовательности опишут один, по сути, лабиринт.
Поправь (сегодня), если я чего не понял.
Здравствуйте, RS, Вы писали:
RS>Здравствуйте, Pushkin, Вы писали:
P>>OK, но не факт что сегодня...
RS>Ну я и сам попробую, сорец-то твой есть. RS>Но что-то мне не нравится идея, что у тебя у стенок нет неопределенного состояния. Эдак, не поставив стенку один раз, мы можем поставить ее, подойдя к ней с другой стороны. И тогда две разные кодирующие последовательности опишут один, по сути, лабиринт. RS>Поправь (сегодня), если я чего не понял.
Поместив ёжика куда-то, мы поместили его всего, такого, какой он есть, со всеми его иголками и мягкими боками. Всякий другой ёжик перед тем как сесть в другую клетку исследует соседей. Если от соседа торчит иголка, то и он пускает. А если там мягко, то не пускает. В те же стороны, где нет соседей, ёжик пускает иголки по желанию, т.е. и так и так.
Иными словами у моих кодирующих последовательностей есть жёсткое свойство — всякая внутренняя стенка или отсутствие внутренней стенки описано ровно дважды , причём одинаково.
А неопределённые состояния у меня есть только для клеток.
Здравствуйте, Pushkin, Вы писали:
P>Поместив ёжика куда-то, мы поместили его всего, такого, какой он есть, со всеми его иголками и мягкими боками. Всякий другой ёжик перед тем как сесть в другую клетку исследует соседей. Если от соседа торчит иголка, то и он пускает. А если там мягко, то не пускает. В те же стороны, где нет соседей, ёжик пускает иголки по желанию, т.е. и так и так.
P>Иными словами у моих кодирующих последовательностей есть жёсткое свойство — всякая внутренняя стенка или отсутствие внутренней стенки описано ровно дважды , причём одинаково.
P>А неопределённые состояния у меня есть только для клеток.
Да, все вроде правильно. И не придраться.
А вот как у меня (может найдешь ошибку?).
У стенок есть три состояния — стенка, проход, неопределено. Когда ставим ежика, его иголки и мягкие бока направляем только в стороны неопределенных стенок. Новый ежик добавляется в фифо, скажем, в начало. Развитие (гду будет следующий ежик) определяется последним ежиком из фифо, чей проход открыт в свободную клетку.
Похоже, все тоже самое, но у тебя попроще (и явно быстрее).
Здравствуйте, RS, Вы писали:
RS>А вот как у меня (может найдешь ошибку?). RS>У стенок есть три состояния — стенка, проход, неопределено.
Я сначала тоже на эту тему колдовал, но потом почему-то бросил, не выходило... Попробую поглядеть твой код на досуге, сейчас надо хоть что-то по работе сделать
Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...
Здравствуйте, Pushkin, Вы писали:
P>Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...
Исключено. Тогда бы у меня больше насчиталось. А до использования рекурсии я пока не дошел.
Здравствуйте, Pushkin, Вы писали:
P>Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...
А эта неестественная "примочка" тебя не раздражает? Я пока до ее смысла не дошел, ибо не читал код. Может из-за нее у тебя насчитываются лишние?
Здравствуйте, RS, Вы писали:
P>>Возможно ошибка в том (у меня была, я долго не мог въехать), что одна и та же клетка закидывается в фифу дважды с разных сторон — ещё прошлый инстанс не обработали, он ждёт своей очереди, а уже следующий зачем-то поставили. У меня для борьбы с этим примочка с "-2" служит. Но оно правда раньше проявлялось, для меньших N...
RS>А эта неестественная "примочка" тебя не раздражает? Я пока до ее смысла не дошел, ибо не читал код. Может из-за нее у тебя насчитываются лишние?
Всё может быть, вскрытие покажет
На самом деле она не такая уж неестественная, я к ней спокойно отношусь. Просто в процессе подсчёта объективно есть 4 типа клеток:
0 - ежа нету и быть не может (вверху)
-1 - фиг его знает, есть ли там ёжик
-2 - ёжик точно есть (т.к. другие ёжики пальцем показали), но неясно какой, надо ещё проверить
1-15 - стоит вполне определённый ёжик
Но!
Ошибка у меня была не в Decode, а в Enum, и вот какая она была:
Enum у меня работает так же, как в первой версии проги Пушкина, которая полимино считала.
Смотрим:
13665040 — Decode говорит, что она плохая,
13665100 — и эта тоже плохая.
И дальше Enum проверяет 13666000 (так уж Enum устроен), и пропускает 13665213. Точно так же была пропущена и еще одна, опять таки по вине Enum.
Итого из 8 клеток 9049 лабиринтов.
Теперь про робота.
По лабиринтам из трех клеток одна последовательность из 9-ти команд (и 7 ее поворотов и отражений):
DRDURLUDL
А вот для четырех клеток я пока не порверил. Просто из-за лени я начал полным последовательным перебором — и пока не добрался. Но в последовательности больше 15-ти команд, это уже точно известно.
Здравствуйте, RS, Вы писали:
RS>Прав был Пушкин, а я не прав.
Прости
RS>И дальше Enum проверяет 13666000 (так уж Enum устроен), и пропускает 13665213. Точно так же была пропущена и еще одна, опять таки по вине Enum.
Мне вообще всегда чудом казалось, что сложные алгоритмы работают
RS>А вот для четырех клеток я пока не порверил. Просто из-за лени я начал полным последовательным перебором — и пока не добрался. Но в последовательности больше 15-ти команд, это уже точно известно.
Ну, это и я да 18 дошёл.
Имхо полный перебор ценнее.
Если его удаётся провести быстро.
Но поиски вширь и вглубь тоже очень интересны.
Как говорится, "не можешь как надо — сделай как можешь"
