Карта кота Арнольда

21

Вызов

Учитывая цветное растровое изображение * с той же шириной и высотой, выведите изображение, преобразованное под карту кота Арнольда . (* подробности см. ниже)

Определение

Учитывая размер изображения, Nмы предполагаем, что координаты пикселя даны как числа между 0и N-1.

Карта кота Арнольда определяется следующим образом:

Пиксель с координатами [x,y]перемещен в [(2*x + y) mod N, (x + y) mod N].

Это не что иное, как линейное преобразование на торе: желтая, фиолетовая и зеленая части возвращаются на начальный квадрат благодаря mod N.

визуализация

Эта карта (назовем ее f) имеет следующие свойства:

  • Это биективно , что означает обратимость: это линейное преобразование с матрицей [[2,1],[1,1]]. Поскольку он имеет определитель 1и имеет только целочисленные записи, обратное также имеет только целочисленные записи и определяется как [[1,-1],[-1,2]], это означает, что он также является биективным по целочисленным координатам.

  • Это элемент кручения группы биективных карт N x Nизображений, что означает, что если вы примените его достаточно много раз, вы вернете исходное изображение: f(f(...f(x)...)) = xколичество раз, когда карта, примененная к себе, приводит к идентичности, гарантированно будет меньше или равно 3*N. Далее вы можете увидеть изображение кота после заданного числа повторяющихся приложений карты кота Арнольда и анимацию того, как выглядит повторяющееся приложение:

несколько повторных заявлений

Детали

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

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

Testcases

В матричной форме ( [1,2,3,4]верхний ряд, 1индекс (0,0), 2индекс (1,0), 5индекс (0,1))

 1     2     3     4
 5     6     7     8
 9    10    11    12
13    14    15    16

maps to:

 1    14    11     8
12     5     2    15
 3    16     9     6
10     7     4    13

 --------------------

 1     2     3
 4     5     6
 7     8     9

 map to:

 1     8     6
 9     4     2
 5     3     7

Как изображение (внизу слева (0,0)):

flawr
источник
1
Бедная лена. Я надеюсь, что вы продолжали повторяться достаточно долго
Луис Мендо
2
Можем ли мы взять размер изображения в качестве входного? Это всегда квадрат?
xnor
1
Да, изображение всегда квадратное, и я не уверен насчет размера, есть ли что-то против этого?
flawr

Ответы:

10

Желе , 9 байт

Zṙ"JC$µ2¡

Попробуйте онлайн! Координаты как в ответе.

объяснение

      µ2¡   Twice:
Z             Transpose, then
 ṙ"           Rotate rows left by
   JC$          0, -1, -2, -3, …, 1-n units.

Это обернуть-сдвинуть матрицу в одном направлении, затем в другом.

Линн
источник
Фантастический алгоритм!
Грег Мартин
7

MATL , 23 байта

tt&n:qt&+&y\tb+&y\b*+Q(

(0,0)Точка вверху слева, как и в примерах , приведенных в тексте вызова.

Попробуйте онлайн!

объяснение

Матрица в MATL может быть проиндексирована с одним индексом вместо двух. Это называется линейным индексированием и использует основной порядок столбцов . Это иллюстрируется следующей матрицей 4 × 4, в которой значение в каждой записи совпадает с ее линейным индексом:

1   5   9  13
2   6  10  14
3   7  11  15
4   8  12  16

Существует два похожих подхода для реализации сопоставления в задаче:

  1. Постройте индексную матрицу, которая представляет обратное отображение Арнольда на линейные индексы, и используйте ее для выбора значений из исходной матрицы. Для случая 4 × 4 индексная матрица будет

     1  8 11 14
    15  2  5 12
     9 16  3  6
     7 10 13  4
    

    сообщая, что, например, оригинал 5при x = 2, y = 1 переходит к x = 3, y = 2. Эта операция называется индексированием ссылок : используйте матрицу индексирования, чтобы указать, какой элемент выбрать из исходной матрицы. Это функция ), которая принимает два входа (в конфигурации по умолчанию).

  2. Постройте индексную матрицу, которая представляет прямое отображение Арнольда на линейные индексы, и используйте ее, чтобы записать значения в исходную матрицу. Для случая 4 × 4 индексная матрица будет

     1 10  3 12
     6 15  8 13
    11  4  9  2
    16  5 14  7
    

    сообщая, что запись x = 2, y = 1 новой матрицы будет перезаписана на запись с линейным индексом 10, то есть x = 3, y = 2. Это называется индексацией присваивания : используйте матрицу индексации, матрицу данных и исходную матрицу и запишите данные в исходную матрицу по указанным индексам. Это функция (, которая принимает три входа (в конфигурации по умолчанию).

Метод 1 более прост, но метод 2 оказался короче.

tt     % Take the input implicitly and push two more copies
&n     % Get its size as two (equal) numbers: N, N
:qt    % Push range [0  1 ... N-1] twice. This represents the original x values
&+     % Matrix of all pairwise additions. This represents x+y
&y     % Push a copy of N onto the top of the stack
\      % Modulo. This is the new y coordinate: y_new
t      % Push another copy
b+     % Bubble up the remaining copy of [0 1 ... N-1] and add. This is 2*x+y
&y     % Push a copy of N onto the top of the stack
\      % Modulo. This is the new x coordinate: x_new
b*+    % Bubble up the remaining copy of N, multiply, add. This computes
       % x_new*N+y_new, which is the linear index for those x_new, y_new 
Q      % Add 1, because MATL uses 1-based indexing
(      % Assigmnent indexing: write the values of the original matrix into
       % (another copy of) the original matrix at the entries given by the
       % indexing matrix. Implicitly display the result
Луис Мендо
источник
5

Mathematica, 44 байта

(n=MapIndexed[RotateLeft[#,1-#2]&,#]&)@*n

Порт фантастического алгоритма Линн . Перед последним есть невидимый 3-байтовый символ U + F3C7 в кодировке UTF-8 ]; Mathematica отображает его как верхний индекс T, и он принимает транспонирование матрицы.

Mathematica, 54 байта

Table[#2[[Mod[2x-y-1,#]+1,Mod[y-x,#]+1]],{x,#},{y,#}]&

Безымянная функция, принимающая два аргумента: положительное целое число #и двумерный массив #2измерений #x #и возвращающая двумерный массив аналогичной формы. Как и в данном тестовом примере, точка с координатами {0,0} находится в верхнем левом углу, а ось x - горизонтальная. Простая реализация, использующая обратное, [[1,-1],[-1,2]]упомянутое в вопросе, с -1первой координатой, чтобы учесть тот факт, что массивы по своей природе индексируются 1 в Mathematica. Если мы не позволили взять размерность матрицы в качестве дополнительного аргумента, то это решение будет девять байт больше (заменить первый #-не на #2a=Length@#и все последующие #с с aе).

Грег Мартин
источник
Черт, побей меня к этому
JungHwan Мин
3

Python 2, 89 82 77 73 байта

def f(a):exec'a=[l[-i:]+l[:-i]for i,l in enumerate(zip(*a))];'*2;return a

Ввод - это список списков
. Строка внутри exec транспонирует список списков и циклически поворачивает каждый список на индекс строки (на основе 0 - 3-я строка поворачивается 2 раза вправо).
Этот процесс делается 2 раза для ввода.

+4 байта, которые сделают преобразование N раз

def f(a,n):exec'a=[l[-i:]+l[:-i]for i,l in enumerate(zip(*a))];'*2*n;return a
прут
источник
2

Haskell, 55 байтов

m#n|r<-[0..n-1]=[[m!!mod(2*y-x)n!!mod(x-y)n|x<-r]|y<-r]

Пример использования: [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]] # 4-> [[1,14,11,8],[12,5,2,15],[3,16,9,6],[10,7,4,13]].

0,0это верхний левый угол. Это использует обратное преобразование.

Ними
источник
1

Python, 69 байт

lambda M:eval("[r[-i:]+r[:-i]for i,r in enumerate(zip(*"*2+"M))]))]")

Усовершенствование метода транспонирования и сдвига в два раза . Применяет операцию M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]дважды, создавая и оценивая строку

[r[-i:]+r[:-i]for i,r in enumerate(zip(*[r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]))]

Это узко выбивает прямое преобразование (70 байт), предполагая, что изображение квадратное и его длина может быть взята в качестве входного:

lambda M,n:[[M[(2*j-i)%n][(i-j)%n]for i in range(n)]for j in range(n)]
XNOR
источник
1

Макрос ImageJ, 29 байт

v=getPixel((x+y)%w,(2*y+x)%h)
  • Открытое изображение Лены
  • В меню Process выберите Math / Macro ...
rahnema1
источник
Разве это не выполняет f ^ (- 1)? Он получает значение пикселя в координатах, в которые предполагается переместить его. Вы, наверное, имеете в виду v=getPixel((2*y-x)%w,(x-y)%h).
Робин Кох
@RobinKoch Спасибо, 2*x+yизменился на2*y+x
rahnema1
Это ни то, что я написал, ни то, что я имел в виду. Вам нужно обратное преобразование для вашего подхода. Для f(x,y) = (2x+y, x+y)этого обратное преобразование описывается f^(-1) = (x-y, 2y-x). (Мой другой комментарий был неверным.) Так что ваш код должен быть v=getPixel((x-y)%w,(2*y-x)%h).
Робин Кох
Я проверил мою формулу, и результат такой же, как изображение Лены в вопросе
rahnema1
@RobinKoch Вы можете загрузить ImageJ и протестировать обе формулы
rahnema1
1

Ява, 160

Golfed:

int[][]f(int[][]m){int x=0,y,l=m.length,r[][]=new int[l][];for(;x<l;++x)r[x]=new int[l];for(x=0;x<l;++x)for(y=0;y<l;++y)r[(x+y)%l][(2*x+y)%l]=m[y][x];return r;}

Ungolfed:

  int[][] f(int[][] m) {
    int x = 0, y, l = m.length, r[][] = new int[l][];
    for (; x < l; ++x) {
      r[x] = new int[l];
    }
    for (x = 0; x < l; ++x) {
      for (y = 0; y < l; ++y) {
        r[(x + y) % l][(2 * x + y) % l] = m[y][x];
      }
    }
    return r;
  }

источник