pengantar
Terinspirasi oleh video terbaru The Trapped Knight - Numberphile , saya mendapat tantangan.
The Urutan ksatria terjebak adalah urutan bilangan bulat terbatas panjang 2016, mulai dari 1, dan memiliki aturan konstruksi berikut:
- Tulis angka spiral dengan cara berikut:
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 ...
- Tempatkan seorang ksatria pada 1.
- Pindahkan ksatria ke grid dengan jumlah terkecil yang bisa pergi yang belum pernah dikunjungi sebelumnya, sesuai dengan aturan catur (yaitu 2 unit secara vertikal dan 1 unit secara horizontal, atau sebaliknya).
- Ulangi sampai ksatria macet.
Inilah tiga langkah pertama:
Langkah 1
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
Kemungkinan gerakan adalah 10, 12, 14, 16, 18, 20, 22, 24, di antaranya yang terkecil adalah 10, sehingga suku kedua adalah 10.
Langkah 2
4 [ 3] 12 [29] 54
( 1) 2 11 28 [53]
8 9 <10> 27 52
[23] 24 25 26 [51]
46 [47] 48 [49] 50
Kemungkinan gerakan adalah 1 , 3, 23, 29, 47, 49, 51, 53, di antaranya yang terkecil adalah 3, sehingga suku ketiga adalah 3.
Langkah 3
35 [34] 33 [32] 31
[16] 15 14 13 [30]
5 4 < 3> 12 29
[ 6] ( 1) 2 11 [28]
7 [ 8] 9 (10) 27
Kemungkinan bergerak adalah 6, 8, 10 , 16, 28, 30, 32, 34, di antaranya yang terkecil adalah 6, jadi istilah keempat adalah 6.
Urutan dibintangi dengan:
1 10 3 6 9 4 7 2 5 8 11 14 ...
dan diakhiri dengan
... 2099 2284 2477 2096 2281 2474 2675 2884 3101 2880 2467 2084
Tantangan
Menulis program atau fungsi terpendek, menerima bilangan bulat dalam kisaran [1, 2016]
(atau [0, 2015]
jika 0-diindeks digunakan) sebagai input, output angka pada indeks itu dalam urutan knight yang terperangkap. Anda dapat memilih untuk mengindeks urutan dengan 0-diindeks atau 1-diindeks, tetapi Anda harus menentukan skema pengindeksan yang Anda gunakan.
Kasus uji (1-diindeks)
n | s(n)
-----+-----
1 | 1
2 | 10
3 | 3
6 | 4
11 | 11
21 | 23
51 | 95
101 | 65
201 | 235
501 | 761
1001 | 1069
2001 | 1925
2016 | 2084
Untuk semua kemungkinan keluaran, silakan merujuk ke halaman ini .
Kriteria Menang
Kode terpendek dari setiap bahasa menang. Batasan pada celah standar berlaku.
12851850258
Jawaban:
JavaScript (ES7),
182181 byteCobalah online!
Bagaimana?
Versi yang sedikit dimodifikasi dari jawaban saya untuk The Path Of The Wildebeest jelas lebih pendek (dan lebih cepat) dari itu. Tetapi saya ingin mencoba pendekatan yang berbeda. Kebetulan, saya pikir mungkin lebih mudah untuk menerapkan metode ini di beberapa esolang.
Algoritma:
Kami memulai kembali pada langkah 2 atau mengembalikan indeks terakhir yang ditemukan jika kami selesai.
Node.js , 155 byte
Cobalah online!
sumber
05AB1E , 53 byte
3
2
θ
Cobalah secara online atau verifikasi beberapa kasus uji lagi (waktu habis untuk kasus uji terbesar).
Penjelasan:
Lihat penjelasan di saya terkait The Path of the Wildebeest jawaban . Satu-satunya bagian yang dimodifikasi adalah:
dan sebuah trailing:
EDIT: Port pendekatan @Arnauld dalam jawabannya JavaScript (ES7) adalah (saat ini):
05AB1E ,
5756 byteCobalah secara online atau verifikasi beberapa kasus uji lagi (waktu habis untuk kasus uji terbesar).
Penjelasan:
Σ·nàDtyÆ+yO·<.±*->}
sumber
MATL ,
4137 byteInput berbasis 0.
Cobalah online!
sumber