Ini adalah Hole-3 dari The Autumn Tournament dari APL CodeGolf . Saya adalah penulis asli masalah di sana, dan dengan demikian diizinkan memposting ulang di sini.
Diberikan:
sejumlah belokan (sebutkan jika tidak ada gerakan adalah 0, kalau tidak kita akan menganggap itu disebut 1) dan
daftar satu atau lebih posisi awal (dalam bentuk apa pun, misalnya 0 atau 1 koordinat yang diindeks atau 64 angka / karakter berurutan atau A1 – H8 - sebutkan mana), pada papan catur 8-oleh-8,
mengembalikan (dalam urutan apa pun) daftar posisi unik (dalam format yang sama dengan input) yang dapat diberikan oleh knight setelah jumlah putaran yang diberikan.
Setiap ksatria harus bergerak dengan setiap belokan, tetapi Anda tidak perlu khawatir tentang beberapa ksatria yang menempati kotak yang sama.
Seorang kesatria hanya dapat bergerak ke posisi yang ditandai dengan X relatif terhadap posisi saat ini, ditandai dengan ♞:
Contoh (koordinat 1-diindeks)
1
pindah dari [[1,1]]
: [[2,3],[3,2]]
2
pindah dari [[1,1]]
: [[1,1],[1,3],[1,5],[2,4],[3,1],[3,5],[4,2],[4,4],[5,1],[5,3]]
1
pindah dari [[1,1],[5,7]]
: [[2,3],[3,2],[3,6],[3,8],[4,5],[6,5],[7,6],[7,8]]
2
pindah dari [[1,1],[5,7]]
: [[1,1],[1,3],[1,5],[1,7],[2,4],[2,6],[2,8],[3,1],[3,3],[3,5],[3,7],[4,2],[4,4],[4,6],[4,8],[5,1],[5,3],[5,5],[5,7],[6,4],[6,6],[6,8],[7,3],[7,7],[8,4],[8,6],[8,8]]
0
pindah dari [[3,4]]
: [[3,4]]
[[1,1]], 2 -> [[2,3],[3,2]]
Jawaban:
Bahasa Wolfram (Mathematica) , 45 byte
Karena solusi lain salah (lihat komentar Martin di bawah), jadi saya memutuskan untuk mengirim solusi saya:
Cobalah online!
Notasi pemasangan tertinggi ...
Mengambil 2 input, yang pertama adalah daftar angka dalam kisaran yang
[1,64]
menggambarkan posisi awal ksatria, yang kedua adalah jumlah langkah.Solusi ini bergantung pada kenyamanan ekstrem fungsi Mathematica builtin:
AdjacencyList
mungkin mengambil daftar simpul di sisi kanannya, dan mengembalikan daftar simpul yang berdekatan dengan salah satu dari mereka, sudah dihapus duplikat dan diurutkan .KnightTourGraph
adalah builtin. Tidak mengejutkan.Nest
mengambil argumen secara berurutanNest[f, expr, n]
, yang dapat kita percikkan di##
sisi kanannya sebagaiNest[f, ##]
.a~b~c~d~e
as(a~b~c)~d~e
, jadi tidak perlu tanda kurung siku. Tanpa notasi infix dan ratakan##
, itu akan menjadiNest[AdjacencyList[KnightTourGraph[8, 8], #] &, #, #2]&
.sumber
JavaScript (ES7), 99 byte
Format input / output: indeks kuadrat dalam [0 ... 63] .
Uji kasus
Cuplikan ini mencakup dua fungsi pembantu untuk menerjemahkan dari dan ke format yang disediakan oleh OP.
Tampilkan cuplikan kode
Bagaimana?
Sebuah perpindahan dari (x, y) ke (X, Y) adalah langkah ksatria yang valid jika kita memiliki salah satu dari:
Dengan mengkuadrat alih-alih menggunakan nilai absolut, ini dapat dinyatakan sebagai:
Karena 1 dan 4 adalah satu-satunya kotak sempurna yang memberikan 5 ketika XOR bersama, kami memiliki langkah ksatria yang valid jika:
(xX) ² XOR (yY) ² XOR 5 = 0
Kami menerapkan rumus ini untuk setiap kotak p = 8y + x di papan tulis dan setiap kotak ksatria P = 8Y + X untuk menyimpulkan kotak target ksatria baru yang mungkin, dan mengulangi proses ini secara n kali.
sumber
Oktaf, 69 byte
Demo online!
Input / output adalah konfigurasi board saat start / end sebagai matriks biner 8 * 8.
Penjelasan:
Untuk
n
langkah - langkah, ulangi pelebaran morfologis papan dengan topeng berikut:sumber
Retina ,
147102 byteCobalah online! Mengambil input sebagai papan 8x8
:
s dengan ksatria bertandaN
s, dengan digit untuk jumlah belokan pada baris berikutnya (tidak masuk akal memiliki lebih dari 9 putaran, tetapi jika Anda bersikeras saya dapat mendukungnya untuk tambahan byte). Perhatikan bahwa output berisi ruang putih tambahan. Sunting: Disimpan 45 byte berkat @MartinEnder. Penjelasan: Tahap pertama mengubah jumlah belokan ke unary, tetapi menggunakan karakter tab, sehingga mereka tidak dapat dicocokkan kemudian secara tidak sengaja, sedangkan tahap kedua menambahkan beberapa ruang di sebelah kanan papan untuk menghentikan regex dari membungkus tepi. Tahap ketiga menggantikan semuaN
s dan:
s yang merupakan langkah ksatria menjauh dariN
dengann
sementara tahap keempat menghapus sisaN
s, mengubahn
s keN
s, dan kurangi 1 dari jumlah langkah. Ini berulang sampai jumlah langkah nol.sumber
Jelly , 29 byte
Cobalah online!
Koordinat 0-diindeks. Hampir pasti ini suboptimal.
-1 byte terima kasih kepada pengguna202729
Penjelasan
sumber
Ç
.05AB1E ,
2725 byteTerima kasih kepada Emigna untuk menghemat 2 byte!
Menggunakan koordinat 1-diindeks.
Kode:
Menggunakan penyandian 05AB1E . Cobalah online!
Penjelasan:
Ini memberi kita array berikut:
Yang merupakan delta pergerakan ksatria.
sumber
•eĆ•SÍü‚
alih-alihƵ‡4в2ô<D(«
menyimpan 2 byte.Python 3, 105 byte
Harus menggunakan lambda bernama untuk rekursi. Tidak yakin apakah itu mendiskualifikasi. Lulus di posisi awal sebagai daftar nomor kotak terindeks 0. 0 dianggap tidak bergerak.
sumber
Java (OpenJDK 8) , 124 byte
Cobalah online!
Format Input / Output
Input / output direpresentasikan sebagai bit dalam
long
(64 bit): bit yang diset berarti kuda hadir, bit yang tidak disetel berarti tidak ada kuda. Contoh:Penjelasan
Kredit
(X-x)²+(Y-y)²==5
trik dari jawaban JavaScript Arnauldint[]
64-bitlong
.sumber
(m,p)->{for(;m-->0;){int i=64,a[]=p,x,y,u[]={1,3,5,9,15,19,21,23};for(p=new int[i];i-->0;)for(int z:u)if((((x=i/8+z/5-2)|(y=i%8+z%5-2))&-8)==0)p[x*8+y]|=a[i];}return p;}
(m,p)->{for(int i,j,a[],x;m-->0;)for(a=p,p=new int[i=64];i-->0;)for(j=64;j-->0;)p[j]|=(x=i%8-j%8)*x+(x=i/8-j/8)*x==5?a[i]:0;return p;}
int[]
denganlong
:(m,p)->{for(long i,j,a;m-->0;)for(a=p,p=i=0;i<64;i++)for(j=64;j-->0;)p|=(p=i%8-j%8)*p+(p=i/8-j/8)*p==5?(a>>i&1)<<j:0;return p;}
Jelly ,
2928 byteCobalah online!
Jumlah belokan adalah melalui STDIN, dan kuadrat adalah argumen.
Ini mengikat solusi Jelly @ HyperNeutrino, tetapi dengan pendekatan yang berbeda.Sekarang kalahkan @HyperNeutrino sebanyak 1 byte penuh!
Setiap saran untuk menjatuhkan beberapa byte diinginkan!
Tautan 1 (Papan catur)
Tautan 2 (Pindahkan generasi)
Tautan 3 (pengecekan kotak)
sumber
Sekam , 18 byte
Menggunakan pengindeksan kuadrat dan langkah 1 berbasis. Cobalah online!
Penjelasan
sumber
R ,
145183134 byteIni adalah hasil dari permainan golf Giuseppe yang bagus untuk algo awal saya yang tidak terlalu golf (lihat komentar di bawah)
Cobalah online!
Input dan output berbasis 1 ... 64. Mengambil vektor posisi menggunakan notasi 1 ... 64. Memetakannya ke notasi 1: 576, yaitu papan super yang terbuat dari sembilan papan. Dalam notasi ini, pada setiap iterasi, masing-masing ksatria harus dapat bergerak dengan +/- 22,26,47,49 Mengembalikan posisi masa depan kembali dalam notasi 1 ... 64, tidak termasuk yang jatuh dari papan pusat. Contoh TIO menampilkan hasilnya menggunakan matriks 8x8.
sumber
[0...63]
notasi.[1..64]
untuk input dan output. +1, meskipun demikian, ini adalah jawaban yang sangat bagus.