Спиральная последовательность перестановок

17

Мы можем свернуть натуральные числа в прямоугольную спираль:

 17--16--15--14--13
  |               |
 18   5---4---3  12
  |   |       |   |
 19   6   1---2  11
  |   |           |
 20   7---8---9--10
  |
 21--22--23--24--25

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

 17  16--15--14--13
  |   |           |
 18   5   4---3  12
  |   |   |   |   |
 19   6   1   2  11
  |   |       |   |
 20   7---8---9  10
  |               |
 21--22--23--24--25

Результирующая последовательность явно является перестановкой натуральных чисел:

1, 4, 3, 2, 9, 8, 7, 6, 5, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, 22, 21, 20, 19, 18, 17, ...

Ваша задача - вычислить эту последовательность. ( OEIS A020703 , но предупреждение о спойлере: оно содержит другое интересное определение и несколько формул, которые вы, возможно, захотите выяснить самостоятельно.)

Интересный факт: все 8 возможных заказов на разматывание имеют свои собственные записи OEIS.

Соревнование

Если задано положительное целое число n, вернуть nэлемент вышеупомянутой последовательности.

Вы можете написать программу или функцию, принимая ввод через STDIN (или ближайшую альтернативу), аргумент командной строки или аргумент функции и выводя результат через STDOUT (или ближайшую альтернативу), возвращаемое значение функции или параметр функции (out).

Применяются стандартные правила .

Тестовые случаи

1       1
2       4
3       3
4       2
5       9
6       8
7       7
8       6
9       5
100     82
111     111
633     669
1000    986
5000    4942
9802    10000
10000   9802

Полный список до и включая n = 11131 смотрите b-файл на OEIS .

Мартин Эндер
источник

Ответы:

6

Желе, 11 10 байт

’ƽð²+ḷ‘Ḥ_

Еще один ответ Jelly на мой телефон.

’ƽð²+ḷ‘Ḥ_   A monadic hook:
’ƽ          Helper link. Input: n
’             n-1
 ƽ            Atop integer square root. Call this m.
   ð         Start a new dyadic link. Inputs: m, n
    ²+ḷ‘Ḥ_    Main link:
    ²+ḷ       Square m, add it to itself,
       ‘      and add one.
        Ḥ     Double the result
         _    and subtract n.

Попробуй это здесь .

lirtosiast
источник
Любые советы по началу работы с желе? Я не могу сказать, как разбираются вилки / хуки.
Линн
Сначала изучите APL или J Цепочки на самом деле проще, чем поезда, потому что все функции имеют фиксированную арность.
lirtosiast
Понимаю. Да, у меня есть опыт J Я полагаю, я попытаюсь прочитать jelly.pyи выяснить, какие цепочки поддерживаются.
Линн
2
Как, черт возьми, вы набрали это на своем телефоне !? Это впечатляет больше, чем сам код!
DJMcMayhem
8

Japt, 20 19 16 байт

V=U¬c)²-V *2-U+2

Проверьте это онлайн!

На основании наблюдения, что

F (N) = ceil (N ^ .5) * (ceil (N ^ .5) -1) - N + 2

Или, скорее, что

F (N) = первый квадрат больше или равен N, минус его квадратный корень, минус N, плюс 2.

Я не знаю, есть ли это объяснение на странице OEIS, поскольку я еще не смотрел его.

ETHproductions
источник
5

Юлия, 28 байт

n->2((m=isqrt(n-1))^2+m+1)-n

Это лямбда-функция, которая принимает целое число и возвращает целое число. Чтобы вызвать его, назначьте его переменной.

Мы определяем m как наибольшее целое число такое, что m 2n -1, то есть целочисленный квадратный корень из n -1 ( isqrt). Затем мы можем упростить выражение OEIS 2 ( m + 1) m - n + 2 до простого 2 ( m 2 + m + 1) - n .

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

Алекс А.
источник
4

CJam, 14 байтов

qi_(mQ7Ybb2*\-

Используя подход Алекса: 2*(m^2+m+1)-nгде m = isqrt(n-1).

Линн
источник
2

ES7, 31 28 26 байт

n=>(m=--n**.5|0)*++m*2-~-n

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

Изменить: 3 байта сохранены частично благодаря @ETHproductions. Сохранено еще 2 байта.

Нил
источник
n=>((m=--n**.5|0)+m*m)*2-n+1будет работать, я думаю.
ETHproductions
@ETHproductions Спасибо, мне было интересно, как туда это попасть --n...
Нил
@ETHproductions Хех, мне удалось побрить 2 байта из твоего ответа.
Нил
1

MATL , 16 13 байт

qX^Y[tQ*Q2*G-

На основании ответа Линн CJam .

Попробуйте онлайн! (Y[был заменен вkсоответствии с изменениями в языке)

q       % input n. Subtract 1
X^      % square root
Y[      % floor
tQ      % duplicate and add 1
*       % multiply
Q       % add 1
2*      % multiply by 2
G-      % subtract n

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

6Y3iQG2\+YLt!G=)

Он явно генерирует две спиральные матрицы (на самом деле, их вертикально перевернутые версии, но это не влияет на вывод). Первый

17    16    15    14    13
18     5     4     3    12
19     6     1     2    11
20     7     8     9    10
21    22    23    24    25

а второй отслеживает измененный путь:

25    10    11    12    13
24     9     2     3    14
23     8     1     4    15
22     7     6     5    16
21    20    19    18    17

Чтобы найти n-ое число последовательности, достаточно найти nво второй матрице и выбрать соответствующее число в первой. Матрицы должны быть достаточно большими, чтобы они nпоявлялись, и иметь нечетный размер, чтобы начало (число 1) находилось в одинаковых позициях в обоих.

Попробуйте тоже онлайн ! (6Y3был перемещен в соответствии с изменениями в языке)

6Y3      % 'spiral' string
i        % input n
QG2\+    % round up to an odd number large enough
YL       % generate spiral matrix of that size: first matrix
t!       % duplicate and transpose: second matrix
G=       % logical index that locates n in the second matrix
)        % use that index into first matrix
Луис Мендо
источник
0

Brachylog , 20 байт

-1$r$[I*I+I+1=*2-?=.

Это использует ту же технику, что и почти все остальные ответы.

объяснение

-1                   § Build the expression Input - 1
  $r                 § Square root of Input - 1
    $[I              § Unify I with the floor of this square root
       *I+I+1        § Build the expression I * I + I + 1
             =*2-?   § Evaluate the previous expression (say, M) and build the expression
                     § M * 2 - Input
                  =. § Unify the output with the evaluation of M * 2 - Input

Интересный факт об этом ответе заключается в том, что его проще и короче использовать =, чем скобки.

Fatalize
источник