Golf program atau fungsi yang memberikan $n^{\text{th}}$ lokasi rusa kutub yang dimulai pada persegi pada terbatas papan catur yang bernomor dalam spiral persegi anti-searah jarum jam, dimana rusa kutub selalu kunjungan bernomor terendah persegi dia bisa mencapai bahwa dia belum belum dikunjungi.$1$

Inspirasi: The Trapped Knight dan OEIS A316667 .

Sunting: Urutan ini sekarang di OEIS sebagai A323763 .

Kode dapat menghasilkan lokasi ke-$n^{\text{th}}$ , lokasi ke - pertama , atau menghasilkan urutan tanpa input.$n$

Jangan ragu untuk memberikan lokasinya setelah (atau sampai) melompat, tetapi jika demikian tolong sebutkan ini dengan jelas dalam jawaban Anda dan pastikan bahwa input menghasilkan (atau jika sesuai).$n$$n=0$1[1]

Ini adalah kode-golf , jadi tujuannya adalah untuk menghasilkan kode kerja dalam sesedikit mungkin byte dalam bahasa yang Anda pilih.

Catatan: rusa kutub menjadi terperangkap (seperti ksatria di lokasi , persegi , dan unta melakukannya di , square ) di lokasi di bujur sangkar . Perilaku kode Anda mungkin tidak ditentukan untuk lebih besar dari ini. (Berkat Deadcode untuk kode C ++ yang menemukan ini!)$2016^{\text{th}}$$2084$$3723^{\text{rd}}$$7081$$12899744968^{\text{th}}$$12851850258$$n$

Detail

Papan terlihat seperti di bawah ini, dan berlanjut tanpa batas:

101 100  99  98  97  96  95  94  93  92  91
102  65  64  63  62  61  60  59  58  57  90
103  66  37  36  35  34  33  32  31  56  89
104  67  38  17  16  15  14  13  30  55  88
105  68  39  18   5   4   3  12  29  54  87
106  69  40  19   6   1   2  11  28  53  86
107  70  41  20   7   8   9  10  27  52  85
108  71  42  21  22  23  24  25  26  51  84
109  72  43  44  45  46  47  48  49  50  83
110  73  74  75  76  77  78  79  80  81  82
111 112 113 114 115 116 117 118 119 120 121

Sebuah rusa kutub adalah "gnu" peri catur piece - catur sepotong non-standar yang bisa bergerak baik sebagai ksatria (a $(1,2)$ -leaper) dan sebagai unta (a $(1,3)$ -leaper).
Karena itu ia dapat pindah ke salah satu lokasi ini dari lokasi awalnya yaitu $1$ :

  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .  35   .  33   .   .   .   .
  .   .   .   .  16   .  14   .   .   .   .
  .   .  39  18   .   .   .  12  29   .   .
  .   .   .   .   .  (1)  .   .   .   .   .
  .   .  41  20   .   .   .  10  27   .   .
  .   .   .   .  22   .  24   .   .   .   .
  .   .   .   .  45   .  47   .   .   .   .
  .   .   .   .   .   .   .   .   .   .   .

Yang terendah adalah $10$ dan dia belum mengunjungi alun-alun itu, jadi $10$ adalah istilah kedua dalam urutan.

Selanjutnya dia bisa pindah dari $10$ ke salah satu lokasi ini:

  .   .   .   .   .   .   .   .   .   .   .
  .   .   .   .   .   .  14   .  30   .   .
  .   .   .   .   .   .   3   .  29   .   .
  .   .   .   .   6   1   .   .   .  53  86
  .   .   .   .   .   .   . (10)  .   .   .
  .   .   .   .  22  23   .   .   .  51  84
  .   .   .   .   .   .  47   .  49   .   .
  .   .   .   .   .   .  78   .  80   .   .
  .   .   .   .   .   .   .   .   .   .   .

Namun, dia sudah mengunjungi kotak $1$ sehingga lokasi ketiganya adalah kotak $3$ , terendah yang belum dia kunjungi.

---

$100$ syarat pertama dari jalur rusa kutub adalah:

1, 10, 3, 6, 9, 4, 7, 2, 5, 8, 11, 14, 18, 15, 12, 16, 19, 22, 41, 17, 33, 30, 34, 13, 27, 23, 20, 24, 44, 40, 21, 39, 36, 60, 31, 53, 26, 46, 25, 28, 32, 29, 51, 47, 75, 42, 45, 71, 74, 70, 38, 35, 59, 56, 86, 50, 78, 49, 52, 80, 83, 79, 115, 73, 107, 67, 64, 68, 37, 61, 93, 55, 58, 54, 84, 48, 76, 43, 69, 103, 63, 66, 62, 94, 57, 87, 125, 82, 118, 77, 113, 72, 106, 148, 65, 97, 137, 91, 129, 85

$11$ lompatan pertama adalah gerakan ksatria sehingga $12$ syarat pertama bertepatan dengan A316667 .

JavaScript (Node.js) ,  191 ... 166  164 byte

Disimpan 2 byte berkat @grimy .

Mengembalikan istilah ^ke- $N$ .

n=>(g=(x,y)=>n--?g(Buffer('QPNP1O?O@242Q3C3').map(m=c=>g[i=4*((x+=c%6-2)*x>(y+=c%7-2)*y?x:y)**2,i-=(x>y||-1)*(i**.5+x+y)]|i>m||(H=x,V=y,m=i))&&H,V,g[m]=1):m+1)(1,2)

Cobalah online! atau Lihat versi yang diformat

Bagaimana?

Indeks spiral

Untuk mengkonversi koordinat $(x,y)$ ke dalam indeks spiral $I$ , pertama-tama kita menghitung layer $L$ dengan:

$$L=\max(|x|,|y|)$$

Pemberian yang mana:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&3&3&3&3&3&3&3\\ -2&3&2&2&2&2&2&3\\ -1&3&2&1&1&1&2&3\\ 0&3&2&1&0&1&2&3\\ +1&3&2&1&1&1&2&3\\ +2&3&2&2&2&2&2&3\\ +3&3&3&3&3&3&3&3 \end{array}$$

Kami kemudian menghitung posisi $P$ di layer dengan:

$$P=\begin{cases} 2L+x+y&\text{if }x>y\\ -(2L+x+y)&\text{if }x\le y \end{cases}$$

Pemberian yang mana:

$$\begin{array}{c|ccccccc} &-3&-2&-1&0&+1&+2&+3\\ \hline -3&0&1&2&3&4&5&6\\ -2&-1&0&1&2&3&4&7\\ -1&-2&-1&0&1&2&5&8\\ 0&-3&-2&-1&0&3&6&9\\ +1&-4&-3&-2&-3&-4&7&10\\ +2&-5&-4&-5&-6&-7&-8&11\\ +3&-6&-7&-8&-9&-10&-11&-12 \end{array}$$

Indeks akhir $I$ diberikan oleh:

$$I=4L^2-P$$

NB: Formula di atas menghasilkan spiral berindeks 0.

Dalam kode JS, kami sebenarnya menghitung $4L^2$ segera dengan:

i = 4 * (x * x > y * y ? x : y) ** 2

Dan kemudian kurangi $P$ dengan:

i -= (x > y || -1) * (i ** 0.5 + x + y)

Bergerak dari rusa kutub

Mengingat posisi saat ini $(x,y)$ , 16 kuadrat target yang mungkin dari rusa kutub diuji dalam urutan berikut:

$$\begin{array}{c|cccccccc} &-3&-2&-1&x&+1&+2&+3\\ \hline -3&\cdot&\cdot&9&\cdot&11&\cdot&\cdot\\ -2&\cdot&\cdot&8&\cdot&10&\cdot&\cdot\\ -1&7&6&\cdot&\cdot&\cdot&12&13\\ y&\cdot&\cdot&\cdot&\bullet&\cdot&\cdot&\cdot\\ +1&5&4&\cdot&\cdot&\cdot&14&15\\ +2&\cdot&\cdot&2&\cdot&0&\cdot&\cdot\\ +3&\cdot&\cdot&3&\cdot&1&\cdot&\cdot \end{array}$$

Kami berjalan melalui mereka dengan menerapkan 16 pasang nilai yang ditandatangani $(dx,dy)$ . Setiap pasangan dikodekan sebagai karakter ASCII tunggal.

 ID | char. | ASCII code | c%6-2 | c%7-2 | cumulated
----+-------+------------+-------+-------+-----------
  0 |  'Q'  |     81     |   +1  |   +2  |  (+1,+2)
  1 |  'P'  |     80     |    0  |   +1  |  (+1,+3)
  2 |  'N'  |     78     |   -2  |   -1  |  (-1,+2)
  3 |  'P'  |     80     |    0  |   +1  |  (-1,+3)
  4 |  '1'  |     49     |   -1  |   -2  |  (-2,+1)
  5 |  'O'  |     79     |   -1  |    0  |  (-3,+1)
  6 |  '?'  |     63     |   +1  |   -2  |  (-2,-1)
  7 |  'O'  |     79     |   -1  |    0  |  (-3,-1)
  8 |  '@'  |     64     |   +2  |   -1  |  (-1,-2)
  9 |  '2'  |     50     |    0  |   -1  |  (-1,-3)
 10 |  '4'  |     52     |   +2  |   +1  |  (+1,-2)
 11 |  '2'  |     50     |    0  |   -1  |  (+1,-3)
 12 |  'Q'  |     81     |   +1  |   +2  |  (+2,-1)
 13 |  '3'  |     51     |   +1  |    0  |  (+3,-1)
 14 |  'C'  |     67     |   -1  |   +2  |  (+2,+1)
 15 |  '3'  |     51     |   +1  |    0  |  (+3,+1)

Kami melacak nilai minimum yang dijumpai di $m$ dan koordinat sel yang sesuai di $(H,V)$ .

Setelah kandidat terbaik ditemukan, kami menandainya sebagai dikunjungi dengan menetapkan bendera pada objek $g$ , yang juga merupakan fungsi rekursif utama kami.

$x=1$$y=2$$(0,0)$

Kelapa , 337 276 byte

import math
def g((x,y))=
 A=abs(abs(x)-abs(y))+abs(x)+abs(y)
 int(A**2+math.copysign(A+x-y,.5-x-y)+1)
def f():
 p=x,y=0,0;s={p};z=[2,3,1,1]*2
 while 1:yield g(p);p=x,y=min(((a+x,b+y)for a,b in zip((1,1,2,-2,-1,-1,3,-3)*2,z+[-v for v in z])if(a+x,b+y)not in s),key=g);s.add(p)

Mengembalikan nilai generator. Mungkin bisa bermain golf lebih banyak. (Terutama urutan perbedaan tupel.) Algoritma spiral diambil dari jawaban math.se ini .

Cobalah online!

05AB1E , 77 65 58 57 52 byte

Xˆ0UF3D(Ÿ0KãʒÄ1¢}εX+}Dε·nàDtyÆ+yO·<.±*->}D¯KßDˆkèU}¯

-6 byte terima kasih kepada @Arnauld dengan menggunakan port dari formulanya.

Output yang pertama $n+1$ nilai sebagai daftar (desimal).

Cobalah online (catatan ïkaki menghapus .0untuk membuat output lebih kompak, tetapi jangan ragu untuk menghapusnya untuk melihat hasil yang sebenarnya).

Penjelasan kode:

Xˆ             # Put integer 1 in the global_array (global_array is empty by default)
0U             # Set variable `X` to 0 (`X` is 1 by default)
F              # Loop the (implicit) input amount of times:
 3D(Ÿ          #  Push the list in the range [-3,3]: [-3,-2,-1,0,1,2,3]
     0K        #  Remove the 0: [-3,-2,-1,1,2,3]
       ã       #  Cartesian product with itself, creating each possible pair: [[3,3],[3,2],[3,1],[3,-1],[3,-2],[3,-3],[2,3],[2,2],[2,1],[2,-1],[2,-2],[2,-3],[1,3],[1,2],[1,1],[1,-1],[1,-2],[1,-3],[-1,3],[-1,2],[-1,1],[-1,-1],[-1,-2],[-1,-3],[-2,3],[-2,2],[-2,1],[-2,-1],[-2,-2],[-2,-3],[-3,3],[-3,2],[-3,1],[-3,-1],[-3,-2],[-3,-3]]
        ʒ   }  #  Filter this list of pairs by:
         Ä     #   Where the absolute values of the pair
          1¢   #   Contains exactly one 1
               #  (We now have the following pairs left: [[3,1],[3,-1],[2,1],[2,-1],[1,3],[1,2],[1,-2],[1,-3],[-1,3],[-1,2],[-1,-2],[-1,-3],[-2,1],[-2,-1],[-3,1],[-3,-1]])
 εX+}          #  Add the variable `X` (previous coordinate) to each item in the list
 D             #  Duplicate this list of coordinates
  ε            #  Map each `x,y`-coordinate to:
   ·           #   Double both the `x` and `y` in the coordinate
    n          #   Then take the square of each
     à         #   And then pop and push the maximum of the two
   Dt          #   Duplicate this maximum, and take its square-root
     yÆ        #   Calculate `x-y`
       +       #   And add it to the square-root
   yO          #   Calculate `x+y`
     ·         #   Double it
      <        #   Decrease it by 1
       .±      #   And pop and push its signum (-1 if < 0; 0 if 0; 1 if > 0)
   *           #   Multiply these two together
    -          #   And subtract it from the duplicated maximum
   >           #   And finally increase it by 1 to make it 1-based instead of 0-based
  }D           #  After the map: Duplicate that list with values
    ¯K         #  Remove all values that are already present in the global_array
      ß        #  Pop the list of (remaining) values and push the minimum
       Dˆ      #  Duplicate this minimum, and pop and add the copy to the global_array
         k     #  Then get its index in the complete list of values
          è    #  And use that index to get the corresponding coordinate
           U   #  Pop and store this coordinate in variable `X` for the next iteration
}¯             # After the outer loop: push the global_array (which is output implicitly)

Penjelasan umum:

Kami menyimpan semua hasil (dan oleh karena itu nilai yang sudah kami temui) di global_array, yang awalnya dimulai sebagai [1].
Kami menahan arus$x,y$-Koordinasikan dalam variabel X, yang awalnya [0,0].

Daftar koordinat yang bisa kita jangkau berdasarkan saat ini $x,y$-koordinat adalah:

[[x+3,y+1], [x+3,y-1], [x+2,y+1], [x+2,y-1], [x+1,y+3], [x+1,y+2], [x+1,y-2], [x+1,y-3], [x-1,y+3], [x-1,y+2], [x-1,y-2], [x-1,y-3], [x-2,y+1], [x-2,y-1], [x-3,y+1], [x-3,y-1]]

Daftar yang saya sebutkan dalam penjelasan kode di atas menyimpan nilai-nilai ini yang dapat kita lompati, setelahnya saat ini $x,y$(disimpan dalam variabel X) ditambahkan.

Maka itu akan menghitung nilai-nilai spiral berdasarkan ini $x,y$-Koordinasi. Itu melakukan ini dengan menggunakan rumus berikut untuk diberikan$x,y$-koordinat:

$${T = max((2 * x) ^ 2, (2 * y) ^ 2)}$$ $${R = T - (x - y + √T) * signum((x + y) * 2 - 1) + 1}$$

Yang merupakan rumus yang sama yang digunakan @Arnauld dalam jawabannya , tetapi ditulis secara berbeda untuk memanfaatkan bawaan 05AB1E untuk double, square, -1, +1, dll.

(Jika Anda ingin melihat bagian spiral dari kode ini dalam aksi: Cobalah secara online .)

Setelah kita mendapatkan semua nilai yang bisa kita raih untuk diberikan $x,y$-koordinasikan, kami menghapus semua nilai yang sudah ada dalam global_array, dan kami kemudian mendapatkan minimum dari nilai (yang tersisa).
Minimum ini kemudian ditambahkan ke global_array, dan variabel Xdiganti dengan$x,y$-Koordinasikan minimum ini.

Setelah kami mengulang inputjumlah kali, program akan menampilkan ini global_arraysebagai hasilnya.