Comments 8
Вместо «ячейка памяти хранит 0 или 1» можно взять более богатую сущность:
положение объекта,
ориентацию,
фазу,
допустимые симметрии,
правила локального преобразования.
В моей модели такой сущностью стал локальный кластер тетраэдров.
Бит — это лампочка: либо включена, либо выключена.
Тетраэдрический мотив — это уже маленькая механическая конструкция, у которой есть:
как она стоит,
куда повернута,
в каком состоянии находится,
как она может перестроиться дальше.
То есть одна «единица состояния» становится намного богаче обычного бита.
Было бы здорово проиллюстрировать сказанное картинками, чтобы было всё хорошо понято. Идея понятна, но важно понять и реализацию. (Крайне интересно поэкспериментировоать, попредставлять разное. Может быть, в будущем, кто-то найдёт способ воплотить это всё в "железе".)))
визуализация - https://disk.yandex.ru/d/xyVsRCyzAP2-KA
в архиве 6 svg файлов
Вы представили себе комбинаторный объект, опеределили операции на нем а дальше реализовали чуть-чуть не самый наивный метод вычисления чего-то этих операций. Зачем?
Задача сама по себе с точки зрения комбинаторики или computer science очень типовая. Метод оптимизации через предподсчет - тоже.
Вообще, дарю вам идею, обощение вашего предподсчета: двочиная таблица предподсчета. Вы считайте не только F64, а считайте A_n = F{2^n} = A_{n-1}(A_{n-1}).
В table[state][0] подсчитайте результат применения операции один раз а потом тупо двумя вложенными циклами: table[state][n] = table[table[state][n-1]][n-1].
Еще в 10 раз ускорите, потратив в несколько раз больше памяти правда, но памяти-то надо всего 15к ячеек - фигня.
Edit: Ах, извиняюсь, вы до этого уже додумались, это у вас называется binary jump hierarchy.
Основной посыл моего комментария остался в силе. Смысла всего этого не вижу. Простое упражнение в базовых комбинаторных задачках.
Ничего не понятно... даже прям вот с нотации где \text{motif} и даже что такое "мотив". Тут явно нужны какие-то введения в предметную область.
Если совсем просто,то motif (мотив) — это одна локальная конфигурация из 4 позиций,где 3 заняты тетраэдрами,а 1 пустая,причём у каждого тетраэдра есть дискретная ориентация и фаза.
То есть motif — это просто “типовой маленький геометрический паттерн”,с которым дальше работает алгоритм.
Формула motif -> F(motif) означает буквально:
“берём одну такую локальную конфигурацию и применяем к ней правило преобразования F”
Да что в этом простого?! Начать с того, почему оно вообще называется "мотив", а дальше совершенно не раскрыты понятия ориентации и фазы. Я же говорю, тут явно подразумеваетсся некий такой нехилый бэкграунд в какой-то области математики, остальным же ничего не понятно.То есть вот вообще, от слова совсем.
Да нет, нету тут никакого бэкраунда заумного у автора. Автор просто выдумал эти термины. Возможно, так солиднее выглядит у автора в голове. По идее, это простенькая комбинаторная задачка, так что тут можно было бы натянуть ее на комбинаторный бэкраунд и использовать всем известные оттуда термины. Но автор их не знает.
Вот есть тетраедр. Его можно по разному крутить. Это 12 положений: 4 варианта, на какой грани он стоит, и для каждого из них по 3 варианта, как он повернут вкруг вертикальной оси ( какая из трех вершин смотрит условно на север). Фазой автор тут называет номер или цвет тетраедра. Вот решил он, что у него будет 3 тетраэдра на 4 слота и они все 3 уникальные, т.е. мы различаем где какой будет. Их можно по разному расставить в эти 4 слота. Но вместо того, что бы следить за перестановкой 4-х обхеъктов (3 тетраэдра и 1 пустота) и отдельно ориентацией каждого из трех тетраэдров, автор засунул эту информацию в каждый из 4-х слотов. Т.е. у него там хранится какой это тетраэдр + как он там ориентирован. Но при этом положение пустоты храниться где-то рядом. Странное решение.
Вот это все возможные состояния. Потом автор решает, что а давайте эти 4 слота тоже расположим в виде тетраедра и будем считать все состояния, переводимые в друг друга поворотами этого тетраэдра, идентичными. И называет это сжатием и каким-то его достижением. Но это просто он так с потолка взял, что у него важными состояниями считаются вот такие-то. А мог бы запросто считать их различными, или расположить эти 4 слота не в тетраэдре а просто по кругу и считать повороты не важными.
Автор, а еще у вас какой-то косяк в программе. Числа не сходятся.
Во-первых, в ваших 36^3*4 вариантах встречаются варианты с повторениями тетраэдров, т.е. с одинаковыми "фазами". У вас же 3 фазы разные должны быть? Тогда должно быть чуть больше 3000 канонизированных состояний:
Вот у тетраэдра 12 ориентаций. Вот у вас 3 тетраэдра, раз у них фазы разные, т.е. они уникальные, то запихать их три в 4 слота есть 4!=24 варианта. Это же перестановка из 4 элементов {0,1,2,∅}
Значит всего "неканонизированных" состояний должно быть 24*12^3=41472. Потом, судя по вашей визуализации, вы считаете повороты этих 4 слотов неразличимыми. И они у вас как тетраэдр вращаются. У тетраэдра 12 различных поворотов, значит канонизированных состояний должно быть в 12 раз меньше: 41472/12=3456.
Как вы там насчитали 15576 состояний?
Если же вы рассматриваете варианты с повторяющемися фазами, то там будет 12^3*(24/12+6*12/12+3*4/4) = 1728*(2+6+3)=19008 состояний. Опять не как у вас.
Тут простые вычисления: 12^3 - это каждый из тетраэдров как-то ориентирован.
24/12 - это сколько способов расположить 3 различных элемента + пустоту в вершинах тетраэдра. 4! перестановки, но каждая имеет 12 уникальных поворотов.
3*12/12 - это сколько способов расположить 3 элемента, из которых 2 неразличимы. Это если у вас одна фаза повторяется 2 раза. Множитель 6, потому что 3 варианта, какая фаза повторяется, потом 2 варианта, какая из оставшихся фаз присутствует. Потом есть 12 перестановок из элементов {a,b,b,c} (2 фазы + пустота). Потом все остается 12 уникальных поворотов: какое из 6 ребер будет покрыто повторяшками и 2 варианта, как будут оставшиеся вершины.
3*4/4 - это вариант когда у вас одна фаза повторяется 3 раза. Там всего 4 перестановки и 4 поворота тетраэдра.
Не биты, а тетраэдры: как я построил геометрический движок состояний и ускорил точную задачу в 555 раз