Календарь-головоломка
Feb. 1st, 2022 11:01 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frНа новый год ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
sasmok подарил мне календарь-головоломку. Нужно уложить вот эти 8 деталей вот в эту форму, чтобы в оставшихся клеточках была видна текущая дата. Справа — решение для сегодняшней даты.
Какое-то время я пытался решить для 1 января — нужно же всё делать по порядку! Потом для текущей даты — нужно же сделать хотя бы что-то! Затем просто складывал детали в надежде, что когда-нибудь они улягутся, и записывал получавшиеся даты впрок. Ну а потом вспомнил про MatLab.
1. Первая версия, тупой брутфорс
Написал класс Piece с матрицей, описывающей каждую деталь. Пара пространственных методов — flip и rotate, преобразующих матрицу. Служебный класс-структура Placement с номером детали, координатами на поле и информацией о том, как именно повёрнута деталь. Класс Plateau с матрицей игрового поля. Метод поиска всех возможных положений детали на поле (Placement). Методы put и remove, которые отражают на матрице поля тот факт, что мы положили или убрали деталь.
И рекурсивный метод решения задачи:
* Метод принимает список деталей, которые нужно уложить
* Если список пустой — значит мы уже уложили всё необходимое => сохраняем в файле найденное решение
* Иначе берём первую деталь из списка и ищем все возможные положения её на поле
* Пробегаем по полученному списку положений
** Кладём деталь на поле
** Вызываем этот же метод со списком без первой детали — её мы только что уложили
** (мы вернёмся сюда, когда обработаем все возможные последствия уложенной детали) Убираем деталь с поля
** Переходим к следующему возможному положению
Отличная программа. Гарантированно решает всё. Запустил, проверил первое найденное решение, проверил второе найденное решение. Поставил считать. Прикинул, сколько времени понадобится для полного прохода — порядка 10 лет. Надо что-то делать.
2. Косметические улучшения
Прекращаю вызывать flip и remove в этих бесконечных циклах. Для каждой детали можно с самого начала просчитать все её возможные положения. Более того, не у всех деталей все 8 положений отличаются друг от друга — есть и симметричные детали. Сразу же выкидываю повторяющиеся картинки. На глазок прикидываю ускорение — задача должна решиться примерно за пол года.
Одновременно написал скрипт, который пробегает по уже найденным решениям и идентифицирует их. Скрипт смотрит, какие именно клеточки остались свободными, и если они складываются в дату — помечает эту дату как «решённую».
3. Нужно решать чётко поставленную задачу
Только что написанный скрипт чётко показывает, что не все найденные варианты меня интересуют. Некоторые не соответствуют никакой дате (например, остались видимыми клеточки 1, 8 и 19). А некоторые дают альтернативное решение для уже найденной даты. Это наводит меня на мысль: а чем, собственно, я тут занимаюсь? Я решаю задачу «найти все возможные варианты укладки 8 деталей в указанный шаблон». А какая задача передо мной стояла? Совсем другая — «для каждой даты найти хотя бы одну укладку». Это же существенно более простая задача!
Пишу цикл по всем дням года (для простоты полагаю, что у нас во всех месяцах есть 31 день). Сразу помечаю эти клеточки как занятые — количество доступных положений резко падает!
4. Прозрачные матрицы
Одновременно в голову приходит идея для упрощения поиска всех доступных положений детали на поле. Моё первое «интуитивное» решение — перебирать все варианты для верхней левой точки каждой детали (точнее, верхней левой точки описывающей её матрицы), накладывать матрицу поля на матрицу детали и смотреть, есть ли пересечения — стандартная операция «и». Если есть — деталь положить нельзя. Если нет — запомнили, переходим к следующий координатам / варианту поворота детали. Долго, нудно, качественно.
Но есть вариант и без перебора, который сразу даёт все возможные положения. Представим для начала, что у нас есть некоторое положение деталей на поле. Сделаем «прозрачку» — на прозрачной плёнке нарисуем поле и эти детали. Оставшиеся прозрачными клеточки показывают нам, куда можно положить деталь 1×1. Пока что ничего сверхъестественного.
Возьмём теперь две одинаковые прозрачки (на картинке я их сделал разыми цветами). Наложим их друг на друга со сдвигом на 1 клеточку по горизонтали. Что теперь символизируют оставшиеся прозрачными клеточки? Те места, куда можно положить деталь, состоящую из двух расположенных горизонтально клеточек!
На всякий случай ещё одна картинка для детали из 3 клеточек «уголком». Легко проверить, что на изначальном поле этот уголок можно уложить именно указанными 16 способами.
Обобщение для более сложных деталей тривиальное: делаем столько копий поля, сколько клеточек у детали, располагаем их со сдвигами, соответствующими клеточкам детали, записываем все просветы — всё та же операция «и». Только она даёт нам не проверку одного положения, а сразу список всех возможных положений.
Всё, с этим улучшением задача поиска укладки для одного дня решается за ~1 минуту. Наверняка можно и ещё улучшить — а можно запустить на ночь, и утром у меня будут все решения :-)
Сделал и завис. Сказать Анюте, что вместо того, чтобы получать тактильное удовольствие (деревянный пазл, детали из бамбука!) каждый день — я взял всё удовольствие за один раз, но в виртуальном мире? Это может оказаться обидным. Ещё пару дней отсылал ей решения (на самом деле, она подсмотрела идею подарка на работе, и у них там образовался чатик, где все хвастались, кто решил сегодняшнюю задачу), а потом она мне возмущённо говорит: представляешь? Jean-Hervé вместо того, чтобы самому решать — написал какую-то приблуду на Excel! — Ты не поверишь, говорю...
Вчера Жан-Эрве приходил в гости, сравнивали наши методы. Ну, помимо того, что не надо на Excel ничего серьёзного считать, у меня метод, наверное, эффективнее. Но и у него интересно. Он сделал сначала для каждой детали список всех возможных положений на доске. Потом скрестил их: проверил, какие положения первой детали совместимы (не пересекаются) с какими положениями второй детали — и так далее, для всех возможных пар. Потом сделал виртуальную деталь «1+2» — у её положения определяются совместимыми положениями из предыдущего этапа. А следующий этап — построение детали «1+2+3» — существенно проще. Потому что совместимость определённого положения «1+2» с положением «3» определяется через совместимость «1» и «3» умноженную на совместимость «2» и «3». То есть всё делается практически без кода, одними формулами Excel. Даже поворот на 90° он делал через комплексные числа, умножением на мнимую единицу. Проблема лишь в объёме данных — он вынужден хранить всё, и в какой-то момент файл вырастал до 2GB и падал. Ну и во времени расчётов — по его прикидкам машина сама решает одну задачу примерно за один день. Поэтому он работал в режиме «киборга», проверяя какие-то варианты ручками.
sasmok подарил мне календарь-головоломку. Нужно уложить вот эти 8 деталей вот в эту форму, чтобы в оставшихся клеточках была видна текущая дата. Справа — решение для сегодняшней даты. Какое-то время я пытался решить для 1 января — нужно же всё делать по порядку! Потом для текущей даты — нужно же сделать хотя бы что-то! Затем просто складывал детали в надежде, что когда-нибудь они улягутся, и записывал получавшиеся даты впрок. Ну а потом вспомнил про MatLab.
1. Первая версия, тупой брутфорс
Написал класс Piece с матрицей, описывающей каждую деталь. Пара пространственных методов — flip и rotate, преобразующих матрицу. Служебный класс-структура Placement с номером детали, координатами на поле и информацией о том, как именно повёрнута деталь. Класс Plateau с матрицей игрового поля. Метод поиска всех возможных положений детали на поле (Placement). Методы put и remove, которые отражают на матрице поля тот факт, что мы положили или убрали деталь.
И рекурсивный метод решения задачи:
* Метод принимает список деталей, которые нужно уложить
* Если список пустой — значит мы уже уложили всё необходимое => сохраняем в файле найденное решение
* Иначе берём первую деталь из списка и ищем все возможные положения её на поле
* Пробегаем по полученному списку положений
** Кладём деталь на поле
** Вызываем этот же метод со списком без первой детали — её мы только что уложили
** (мы вернёмся сюда, когда обработаем все возможные последствия уложенной детали) Убираем деталь с поля
** Переходим к следующему возможному положению
Отличная программа. Гарантированно решает всё. Запустил, проверил первое найденное решение, проверил второе найденное решение. Поставил считать. Прикинул, сколько времени понадобится для полного прохода — порядка 10 лет. Надо что-то делать.
2. Косметические улучшения
Прекращаю вызывать flip и remove в этих бесконечных циклах. Для каждой детали можно с самого начала просчитать все её возможные положения. Более того, не у всех деталей все 8 положений отличаются друг от друга — есть и симметричные детали. Сразу же выкидываю повторяющиеся картинки. На глазок прикидываю ускорение — задача должна решиться примерно за пол года.
Одновременно написал скрипт, который пробегает по уже найденным решениям и идентифицирует их. Скрипт смотрит, какие именно клеточки остались свободными, и если они складываются в дату — помечает эту дату как «решённую».
3. Нужно решать чётко поставленную задачу
Только что написанный скрипт чётко показывает, что не все найденные варианты меня интересуют. Некоторые не соответствуют никакой дате (например, остались видимыми клеточки 1, 8 и 19). А некоторые дают альтернативное решение для уже найденной даты. Это наводит меня на мысль: а чем, собственно, я тут занимаюсь? Я решаю задачу «найти все возможные варианты укладки 8 деталей в указанный шаблон». А какая задача передо мной стояла? Совсем другая — «для каждой даты найти хотя бы одну укладку». Это же существенно более простая задача!
Пишу цикл по всем дням года (для простоты полагаю, что у нас во всех месяцах есть 31 день). Сразу помечаю эти клеточки как занятые — количество доступных положений резко падает!
4. Прозрачные матрицы
Одновременно в голову приходит идея для упрощения поиска всех доступных положений детали на поле. Моё первое «интуитивное» решение — перебирать все варианты для верхней левой точки каждой детали (точнее, верхней левой точки описывающей её матрицы), накладывать матрицу поля на матрицу детали и смотреть, есть ли пересечения — стандартная операция «и». Если есть — деталь положить нельзя. Если нет — запомнили, переходим к следующий координатам / варианту поворота детали. Долго, нудно, качественно.
Но есть вариант и без перебора, который сразу даёт все возможные положения. Представим для начала, что у нас есть некоторое положение деталей на поле. Сделаем «прозрачку» — на прозрачной плёнке нарисуем поле и эти детали. Оставшиеся прозрачными клеточки показывают нам, куда можно положить деталь 1×1. Пока что ничего сверхъестественного.
Возьмём теперь две одинаковые прозрачки (на картинке я их сделал разыми цветами). Наложим их друг на друга со сдвигом на 1 клеточку по горизонтали. Что теперь символизируют оставшиеся прозрачными клеточки? Те места, куда можно положить деталь, состоящую из двух расположенных горизонтально клеточек!
На всякий случай ещё одна картинка для детали из 3 клеточек «уголком». Легко проверить, что на изначальном поле этот уголок можно уложить именно указанными 16 способами.
Обобщение для более сложных деталей тривиальное: делаем столько копий поля, сколько клеточек у детали, располагаем их со сдвигами, соответствующими клеточкам детали, записываем все просветы — всё та же операция «и». Только она даёт нам не проверку одного положения, а сразу список всех возможных положений.
Всё, с этим улучшением задача поиска укладки для одного дня решается за ~1 минуту. Наверняка можно и ещё улучшить — а можно запустить на ночь, и утром у меня будут все решения :-)
Сделал и завис. Сказать Анюте, что вместо того, чтобы получать тактильное удовольствие (деревянный пазл, детали из бамбука!) каждый день — я взял всё удовольствие за один раз, но в виртуальном мире? Это может оказаться обидным. Ещё пару дней отсылал ей решения (на самом деле, она подсмотрела идею подарка на работе, и у них там образовался чатик, где все хвастались, кто решил сегодняшнюю задачу), а потом она мне возмущённо говорит: представляешь? Jean-Hervé вместо того, чтобы самому решать — написал какую-то приблуду на Excel! — Ты не поверишь, говорю...
Вчера Жан-Эрве приходил в гости, сравнивали наши методы. Ну, помимо того, что не надо на Excel ничего серьёзного считать, у меня метод, наверное, эффективнее. Но и у него интересно. Он сделал сначала для каждой детали список всех возможных положений на доске. Потом скрестил их: проверил, какие положения первой детали совместимы (не пересекаются) с какими положениями второй детали — и так далее, для всех возможных пар. Потом сделал виртуальную деталь «1+2» — у её положения определяются совместимыми положениями из предыдущего этапа. А следующий этап — построение детали «1+2+3» — существенно проще. Потому что совместимость определённого положения «1+2» с положением «3» определяется через совместимость «1» и «3» умноженную на совместимость «2» и «3». То есть всё делается практически без кода, одними формулами Excel. Даже поворот на 90° он делал через комплексные числа, умножением на мнимую единицу. Проблема лишь в объёме данных — он вынужден хранить всё, и в какой-то момент файл вырастал до 2GB и падал. Ну и во времени расчётов — по его прикидкам машина сама решает одну задачу примерно за один день. Поэтому он работал в режиме «киборга», проверяя какие-то варианты ручками.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2022-02-01 11:45 am (UTC)Французу респект (наверное), мне бы в голову не пришло использовать Эксель для такой задачи. Могу только сказать, что в Office 64-bit нет ограничений на размер памяти для экселевского файла, так что 2Гб — не предел. Возможно, он сидит на 32-битном, тогда пусть попробует на другой машине.
no subject
Date: 2022-02-01 12:29 pm (UTC)А Excel падал не столько из-за размера 32 или 64 бит (хотя, я сам на 32 бита, и про 64 бита на работе страшные ужасы рассказывали), сколько из-за миллионов друг на друга завязанных формул. То есть ну вот совершенно не по назначению им пользовался товарищ!
no subject
Date: 2022-02-01 01:26 pm (UTC)no subject
Date: 2022-02-01 01:41 pm (UTC)no subject
Date: 2022-02-01 01:42 pm (UTC)no subject
Date: 2022-02-01 02:09 pm (UTC)И что характерно, из этой компании он как раз-то уже ушёл. Но гугл помнит всё.
no subject
Date: 2022-02-01 02:20 pm (UTC)Поэтому сразу полез проверять твою рыбу.
no subject
Date: 2022-02-01 05:38 pm (UTC)В инторнетах нашла вот такие календари, но они сильно попроще выглядят:
https://www.dragonfjord.com/product/a-puzzle-a-day
https://www.amazon.com/gp/aw/d/B09PFPYYVM/
И кажется это очень подойдёт для мобильной игры типа, Wordle — по загадке на каждый день
no subject
Date: 2022-02-01 06:01 pm (UTC)Мы ещё потом разговаривали о других возможных вопросах. Например — есть ли даты, для которых есть только одно решение? Или наоборот, для каких дат разных решений больше всего?
А "по загадке каждый день" — так так оно изначально и задумывалось. А дальше — кто как предпочитает относиться к задачкам. Кто-то каждый день решает независимо от других. А кто-то вот пытается найти общее решение, пусть и на компьютере :-)
no subject
Date: 2022-02-01 07:08 pm (UTC)no subject
Date: 2022-02-02 07:44 am (UTC)no subject
Date: 2022-02-01 08:15 pm (UTC)no subject
Date: 2022-02-02 07:47 am (UTC)Потому что там же главное не в увеличении всемеро количества задач, а в том, что для каждой задачи остаётся на 6 клеточек больше (неиспользованные дни недели). Разве только если взамен у тебя месяца не двумя, а одной клеточкой — тогда наоборот, твоя версия проще.
no subject
Date: 2022-02-07 02:26 pm (UTC)Про 7 раз дольше я имел ввиду, что в в твоем варианте есть 366 (ну или 12*31=372) разных целевых картинок. А в моём для каждой даты ещё есть 7 разных дней недели и всего надо решить не 366 задач а в семь раз больше.
Понятно, что для каждого конкретного дня (сегодня понедельник 7 февраля, например) сложность примерно та же (завист, конечно, от числа деталей).
no subject
Date: 2022-02-07 04:25 pm (UTC)no subject
Date: 2022-02-07 08:27 pm (UTC)В предельном случае если рассмотреть задачу с двумя большими деталями, то там вариантов для перебора всего десяток.
no subject
Date: 2022-02-07 09:13 pm (UTC)no subject
Date: 2022-02-09 10:21 am (UTC)no subject
Date: 2022-02-09 10:35 am (UTC)no subject
Date: 2022-02-01 08:45 pm (UTC)no subject
Date: 2022-02-02 07:48 am (UTC)off: ты долго ещё томить будешь? прошёл экзамен-то? :-)
no subject
Date: 2022-02-02 08:35 am (UTC)https://kruzzik.livejournal.com/474753.html
А по поводу экзаменов — там еще не все круги ада закончились. Следите за рекламой.
no subject
Date: 2022-02-02 09:25 am (UTC)no subject
Date: 2022-02-02 10:02 am (UTC)И чсх, ни один из двух не работает программистом, а выделывают такое, что вовсю развивается комплекс профнепригодности.
no subject
Date: 2022-02-02 12:59 pm (UTC)