Urutan Permutasi Spiral

17

Kita bisa menggulung bilangan asli dalam spiral persegi panjang:

 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

Tetapi sekarang setelah kita memilikinya di kotak persegi panjang kita bisa melepas spiral dalam urutan yang berbeda, misalnya pergi searah jarum jam, mulai dari utara:

 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

Urutan yang dihasilkan jelas merupakan permutasi dari bilangan asli:

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, ...

Tugas Anda adalah untuk menghitung urutan ini. ( OEIS A020703 , tetapi peringatan spoiler: itu berisi definisi menarik lainnya dan beberapa rumus yang mungkin ingin Anda ketahui sendiri.)

Fakta menyenangkan: ke-8 pesanan yang mungkin dibatalkan memiliki entri OEIS mereka sendiri.

Tantangan

Dengan bilangan bulat positif n, kembalikan nelemen ke-5 dari urutan di atas.

Anda dapat menulis suatu program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter fungsi (keluar).

Aturan standar berlaku.

Uji Kasus

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

Untuk daftar lengkap hingga dan termasuk n = 11131 melihat file-b pada OEIS .

Martin Ender
sumber

Jawaban:

6

Jelly, 11 10 byte

’ƽð²+ḷ‘Ḥ_

Jawaban jelly lain di ponsel saya.

’ƽð²+ḷ‘Ḥ_   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.

Coba di sini .

lirtosiast
sumber
Adakah tips untuk memulai dengan Jelly? Saya tidak tahu bagaimana garpu / kait diurai sama sekali.
Lynn
Pelajari APL atau J terlebih dahulu. Chains sebenarnya lebih mudah daripada kereta karena semua fungsi memiliki arity tetap.
lirtosiast
Saya melihat. Ya, saya punya pengalaman J. Saya kira saya akan mencoba membaca jelly.pydan mencari tahu rantai mana yang didukung.
Lynn
2
Bagaimana Anda mengetik itu di ponsel Anda !? Itu lebih mengesankan daripada kode itu sendiri!
DJMcMayhem
8

Japt, 20 19 16 byte

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

Uji secara online!

Berdasarkan pengamatan itu

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

Atau, lebih tepatnya, itu

F (N) = kuadrat pertama lebih besar dari atau sama dengan N, minus akar kuadratnya, minus N, ditambah 2.

Saya tidak tahu apakah penjelasan ini ada di halaman OEIS, karena saya belum melihatnya.

Produksi ETH
sumber
5

Julia, 28 byte

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

Ini adalah fungsi lambda yang menerima integer dan mengembalikan integer. Untuk menyebutnya, tetapkan ke variabel.

Kami mendefinisikan m menjadi bilangan bulat terbesar sehingga m 2n -1, yaitu akar kuadrat bilangan bulat dari n -1 ( isqrt). Kita kemudian dapat menyederhanakan ekspresi OEIS 2 ( m + 1) m - n + 2 ke bawah menjadi 2 ( m 2 + m + 1) - n .

Cobalah online

Alex A.
sumber
4

CJam, 14 byte

qi_(mQ7Ybb2*\-

Menggunakan pendekatan Alex: di 2*(m^2+m+1)-nmana m = isqrt(n-1).

Lynn
sumber
2

ES7, 31 28 26 byte

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

Saya telah menemukan formula Alex secara mandiri tetapi saya tidak dapat membuktikannya karena saya tidak berada di dekat komputer pada saat itu.

Sunting: Disimpan 3 byte sebagian berkat @ETHproductions. Menyimpan 2 byte lebih lanjut.

Neil
sumber
n=>((m=--n**.5|0)+m*m)*2-n+1akan bekerja, saya pikir.
ETHproduksi
@ ETHproductions Terima kasih, saya bertanya-tanya pada diri sendiri bagaimana mendapatkannya --ndi sana ...
Neil
@ ETHproductions Heh, saya berhasil mencukur 2 byte dari jawaban Anda.
Neil
1

Pyth, 21 byte

K2-h+^.E@QKK^t.E@QKKQ

Cobalah online!

Tidak ada yang mewah terjadi. Metode yang sama seperti pada jawaban JAPT.

Denker
sumber
1

MATL , 16 13 byte

qX^Y[tQ*Q2*G-

Berdasarkan jawaban Lynn CJam .

Cobalah online! (Y[telah diganti olehksesuai dengan perubahan bahasa)

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

Ini menggunakan pendekatan yang berbeda dari jawaban lain ( 16 byte ):

6Y3iQG2\+YLt!G=)

Ini secara eksplisit menghasilkan dua matriks spiral (sebenarnya, versi terbalik secara vertikal, tetapi itu tidak mempengaruhi output). Yang pertama adalah

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

dan yang kedua melacak jalur yang dimodifikasi:

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

Untuk menemukan nnomor-urutan yang cukup untuk menemukan ndalam matriks kedua dan memilih nomor yang sesuai dalam yang pertama. Matriks harus cukup besar sehingga nmuncul, dan harus memiliki ukuran ganjil sehingga titik asal (angka 1) berada pada posisi yang sama di keduanya.

Coba juga online ! (6Y3telah dipindahkan sesuai dengan perubahan bahasa)

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
Luis Mendo
sumber
0

Brachylog , 20 byte

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

Ini menggunakan teknik yang sama seperti hampir semua jawaban lainnya.

Penjelasan

-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

Fakta yang =agak menarik tentang jawaban ini adalah bahwa lebih mudah dan lebih pendek untuk menggunakan daripada tanda kurung.

Fatalisasi
sumber