Tugas
Diberikan input N, hasilkan dan hasilkan kisi NxN di mana setiap baris, kolom, dan kedua diagonal berisi angka 1 hingga N
(atau 0 hinggaN
−1 jika itu lebih mudah).
Memasukkan
Inputnya adalah bilangan bulat positif N
. Ini mewakili jumlah kolom dan baris dalam kisi. Untuk masalah ini, Anda dapat menganggap N
ukurannya masuk akal, 4 ≤ N ≤ 8
atau (1 ≤ N ≤ 8
jika Anda memilih bonus di bawah ini).
Keluaran
Outputnya adalah N
× N
grid. Dalam kisi, setiap baris hanya berisi angka 1 hingga N
, setiap kolom hanya berisi angka 1 hingga N
, dan dua diagonal panjang N
(satu dari (0,0)
ke (N-1,N-1)
dan satu dari (0,N-1)
ke (N-1, 0)
) hanya berisi angka 1 hingga N
. Anda dapat menggunakan angka 0 hingga N−1
. Untuk setiapN
, ada banyak solusi yang mungkin, Anda hanya perlu mencetak yang pertama yang Anda temukan. Anda tidak perlu mencetak spasi di antara angka-angka.
Kendala
Kode Anda harus dapat menghasilkan hasil secara berulang N >= 7
. Artinya, jika Anda benar-benar dapat menjalankan dan mendapatkan solusi N = 7
dari kode Anda setiap kali, Anda baik. Dalam hal batas absolut, kode Anda harus dapat diselesaikan N = 7
dalam waktu kurang dari 10 menit setiap kali Anda menjalankannya (yaitu, jika Anda bergantung pada angka acak, untuk kasus terburuk, kode Anda masih harus selesai di bawah 10 menit untuk N = 7
) .
Contohnya
Memasukkan:
4
Satu kemungkinan keluaran:
1 2 3 4 3 4 1 2 4 3 2 1 2 1 4 3
Memasukkan:
5
Satu kemungkinan keluaran:
1 2 3 4 5 5 3 1 2 4 2 5 4 3 1 4 1 2 5 3 3 4 5 1 2
Memasukkan:
8
Satu kemungkinan keluaran:
1 2 3 4 5 6 7 8 2 3 1 5 4 8 6 7 4 1 2 3 7 5 8 6 6 4 7 8 1 2 3 5 7 5 8 2 6 3 4 1 5 8 4 6 2 7 1 3 8 7 6 1 3 4 5 2 3 6 5 7 8 1 2 4
Mencetak gol
Ini adalah kode-golf , jadi kode terpendek dalam byte menang, dengan satu pengecualian. Untuk input N = 2, 3
tidak ada solusi yang valid. Jika kode Anda dapat menangani ini (jalankan sampai selesai tanpa mengeluarkan apa pun untuk kasus ini, atau mengeluarkan string kosong), dan masih menangani N = 1
(menghasilkan 1
untuk itu), ambil 20% dari jumlah byte Anda.
sumber
N
. Kode JavaScript ini berfungsiN = 1, 5 or 7
meskipun jika itu membantu siapa pun:for(o="",y=N;y--;o+="\n")for(x=N;x--;)o+=(((N-y)*2+x)%N)+1
N = 1
kasus ini: jawaban yang bertujuan untuk bonus harus dikembalikan1
, bukan string kosong.Jawaban:
Python 3,
275260 Bytes * 0.8 =220208 BytesPendekatan rekursif / mundur.
R
adalah fungsi rekursif,l
adalah kolom,w
adalah roW,K
adalah entri berikutnya.Saya memilih untuk meletakkannya di array 1d dan cukup mencetaknya di akhir untuk membuat indeks lebih sederhana.
Versi tidak disatukan:
sumber
Funciton , tidak kompetitif
MEMPERBARUI! Peningkatan kinerja besar-besaran! n = 7 sekarang selesai dalam waktu kurang dari 10 menit! Lihat penjelasan di bawah!
Ini menyenangkan untuk ditulis. Ini adalah brute-force solver untuk masalah ini yang ditulis dalam Funciton. Beberapa factoids:
3 2 1 0
daripada di mana baris atas dibaca0 1 2 3
.0
(satu-satunya solusi) untuk n = 1.Tanpa basa-basi:
Penjelasan dari versi pertama
Versi pertama membutuhkan waktu sekitar satu jam untuk menyelesaikan n = 7. Berikut ini sebagian besar menjelaskan bagaimana versi lambat ini bekerja. Di bagian bawah saya akan menjelaskan perubahan apa yang saya buat untuk mendapatkannya di bawah 10 menit.
Tamasya menjadi bit
Program ini membutuhkan bit. Perlu banyak bit, dan membutuhkannya di semua tempat yang tepat. Pemrogram Funciton berpengalaman sudah tahu bahwa jika Anda membutuhkan n bit, Anda dapat menggunakan rumus
yang dalam Funciton dapat dinyatakan sebagai
Ketika melakukan optimasi kinerja saya, terpikir oleh saya bahwa saya dapat menghitung nilai yang sama lebih cepat menggunakan rumus ini:
Saya harap Anda memaafkan saya bahwa saya tidak memperbarui semua grafik persamaan dalam posting ini.
Sekarang, katakanlah Anda tidak ingin blok bit yang berdekatan; sebenarnya, Anda ingin n bit secara berkala setiap k -th bit, seperti:
Formula untuk ini cukup mudah setelah Anda mengetahuinya:
Dalam kode, fungsi tersebut
Ӝ
mengambil nilai n dan k dan menghitung rumus ini.Melacak nomor yang digunakan
Ada n ² angka dalam kisi terakhir, dan setiap angka dapat berupa n nilai yang mungkin. Untuk melacak nomor mana yang diizinkan dalam setiap sel, kami mempertahankan nomor yang terdiri dari n ³ bit, di mana bit diatur untuk menunjukkan bahwa nilai tertentu diambil. Awalnya angka ini adalah 0, jelas.
Algoritma dimulai di sudut kanan bawah. Setelah "menebak" angka pertama adalah 0, kita perlu melacak fakta bahwa 0 tidak lagi diizinkan di sel mana pun di sepanjang baris, kolom, dan diagonal yang sama:
Untuk tujuan ini, kami menghitung empat nilai berikut:
Baris saat ini: Kami perlu n bit setiap n bit th (satu per sel), dan kemudian beralih ke baris saat ini r , mengingat setiap baris berisi n ² bit:
Kolom saat ini: Kami membutuhkan n bit setiap n ²-th bit (satu per baris), dan kemudian menggesernya ke kolom saat ini c , mengingat setiap kolom berisi n bit:
Maju diagonal: Kami membutuhkan n bit setiap ... (apakah Anda memperhatikan? Cepat, cari tahu!) ... n ( n +1)-bit (dilakukan dengan baik!), Tetapi hanya jika kami benar-benar aktif maju diagonal:
Backward diagonal: Dua hal di sini. Pertama, bagaimana kita tahu kalau kita berada di diagonal mundur? Secara matematis, kondisinya adalah c = ( n - 1) - r , yang sama dengan c = n + (- r - 1). Hei, apakah itu mengingatkanmu pada sesuatu? Itu benar, itu pelengkap dua, jadi kita bisa menggunakan negasi bitwise (sangat efisien di Funciton) alih-alih pengurangan. Kedua, rumus di atas mengasumsikan bahwa kita ingin bit yang paling tidak signifikan untuk diatur, tetapi di diagonal mundur kita tidak, jadi kita harus menggesernya dengan ... apakah Anda tahu? ... Itu benar, n ( n - 1).
Ini juga satu-satunya di mana kita berpotensi membagi dengan 0 jika n = 1. Namun, Funciton tidak peduli. 0 ÷ 0 hanya 0, tahukah Anda?
Dalam kode, fungsi
Җ
(yang terbawah) mengambil n dan indeks (dari mana ia menghitung r dan c berdasarkan pembagian dan sisanya), menghitung keempat nilai ini danor
menyatukannya.Algoritma brute-force
Algoritma brute-force diimplementasikan oleh
Ӂ
(fungsi di atas). Dibutuhkan n (ukuran kisi), indeks (di mana dalam kisi kita saat ini menempatkan nomor), dan diambil (angka dengan n ³ bit memberi tahu kita nomor mana yang masih bisa kita tempatkan di setiap sel).Fungsi ini mengembalikan urutan string. Setiap string adalah solusi lengkap untuk grid. Ini adalah pemecah yang lengkap; itu akan mengembalikan semua solusi jika Anda membiarkannya, tetapi mengembalikannya sebagai urutan malas yang dievaluasi.
Jika indeks telah mencapai 0, kami telah berhasil mengisi seluruh grid, jadi kami mengembalikan urutan berisi string kosong (solusi tunggal yang tidak mencakup sel). String kosong adalah
0
, dan kami menggunakan fungsi pustaka⌑
untuk mengubahnya menjadi urutan elemen tunggal.Pemeriksaan yang dijelaskan dalam peningkatan kinerja di bawah ini terjadi di sini.
Jika indeks belum mencapai 0, kami menurunkannya dengan 1 untuk mendapatkan indeks di mana sekarang kita perlu menempatkan nomor (sebut itu ix ).
Kami menggunakan
♫
untuk menghasilkan urutan malas yang berisi nilai dari 0 hingga n - 1.Kemudian kami menggunakan
ɓ
(ikatan monadik) dengan lambda yang melakukan hal berikut secara berurutan:0
(urutan kosong).Җ
untuk menghitung bit yang sesuai dengan baris, kolom, dan diagonal saat ini. Bergeser dengan saya dan kemudianor
itu ke diambil .Ӂ
untuk mengambil semua solusi untuk sel yang tersisa, meneruskannya dengan yang baru diambil dan ix yang dikurangi . Ini mengembalikan urutan string tidak lengkap; setiap string memiliki karakter ix (kotak diisi hingga indeks ix ).ɱ
(peta) untuk pergi melalui solusi yang ditemukan dan gunakan‼
untuk menggabungkan saya ke akhir masing-masing. Tambahkan baris baru jika indeks adalah kelipatan n , jika tidak spasi.Menghasilkan hasilnya
Panggilan program utama
Ӂ
(brute forcer) dengan n , index = n ² (ingat kita mengisi grid mundur) dan mengambil = 0 (awalnya tidak ada yang diambil). Jika hasil dari ini adalah urutan kosong (tidak ada solusi yang ditemukan), output string kosong. Kalau tidak, output string pertama dalam urutan. Perhatikan bahwa ini berarti ia hanya akan mengevaluasi elemen pertama dari urutan, itulah sebabnya pemecah tidak melanjutkan sampai ia menemukan semua solusi.Peningkatan performa
(Bagi mereka yang sudah membaca versi lama dari penjelasan: program tidak lagi menghasilkan urutan urutan yang perlu secara terpisah diubah menjadi string untuk output; itu hanya menghasilkan urutan string secara langsung. Saya telah mengedit penjelasan sesuai Tapi itu bukan peningkatan utama. Ini dia.)
Di komputer saya, exe yang dikompilasi dari versi pertama hanya membutuhkan waktu 1 jam untuk menyelesaikan n = 7. Ini tidak dalam batas waktu yang diberikan 10 menit, jadi saya tidak beristirahat. (Yah, sebenarnya, alasan aku tidak beristirahat adalah karena aku punya ide tentang cara mempercepatnya secara masif.)
Algoritme seperti dijelaskan di atas menghentikan pencarian dan backtracks setiap kali menemukan sel di mana semua bit dalam jumlah yang diambil ditetapkan, menunjukkan bahwa tidak ada yang dapat dimasukkan ke dalam sel ini.
Namun, algoritme akan terus mengisi grid dengan sia-sia hingga ke sel tempat semua bit diatur. Akan jauh lebih cepat jika bisa berhenti begitu setiap sel yang belum diisi sudah memiliki semua bit yang ditetapkan, yang sudah menunjukkan bahwa kita tidak akan pernah bisa menyelesaikan sisa grid tidak peduli berapa nomor yang kita masukkan saya t. Tetapi bagaimana Anda secara efisien memeriksa apakah ada sel yang memiliki n bit yang diset tanpa melalui semuanya?
Caranya dimulai dengan menambahkan satu bit per sel ke nomor yang diambil . Alih-alih apa yang ditunjukkan di atas, sekarang tampilannya seperti ini:
Alih-alih n ³, sekarang ada n ² ( n +1) bit dalam angka ini. Fungsi yang mengisi baris / kolom / diagonal saat ini telah diubah sesuai (sebenarnya, sepenuhnya ditulis ulang untuk jujur). Fungsi itu masih akan mengisi hanya n bit per sel, jadi bit tambahan yang baru saja kita tambahkan akan selalu
0
.Sekarang, katakanlah kita setengah jalan dalam perhitungan, kita baru saja menempatkan sebuah
1
di sel tengah, dan jumlah yang diambil terlihat seperti ini:Seperti yang Anda lihat, sel kiri atas (indeks 0) dan sel kiri tengah (indeks 10) sekarang tidak mungkin. Bagaimana kita menentukan ini dengan paling efisien?
Pertimbangkan angka di mana bit ke-0 dari setiap sel diatur, tetapi hanya sampai indeks saat ini. Angka seperti itu mudah dihitung menggunakan rumus yang sudah dikenal:
Apa yang akan kita dapatkan jika kita menambahkan dua angka ini bersama?
Hasilnya adalah:
Seperti yang Anda lihat, penambahan melimpah ke bit ekstra yang kami tambahkan, tetapi hanya jika semua bit untuk sel itu ditetapkan! Karenanya, yang harus dilakukan hanyalah menutupi bit-bit itu (rumus yang sama seperti di atas, tetapi << n menutup ) dan periksa apakah hasilnya 0:
Jika bukan nol, kisi tidak mungkin dan kita bisa berhenti.
sumber
Haskell, 790 * 0,80 = 632 byte
Saya perhatikan masalah ini sangat mirip dengan sudoku. Saya ingat pemecah sudoku tua yang saya tulis di Haskell berdasarkan yang lain ini di Python. Ini adalah posting atau usaha golf kode pertama saya.
Ini memenuhi bonus karena ia mengembalikan
Nothing
untukn=2,3
danJust <result>
untukn>=4
, di mana<result>
adalah array 2D nilai integral.Lihat di sini untuk penerjemah online. Kode itu sebenarnya lebih panjang dari yang ada di pos karena penerjemah online memiliki persyaratan yang lebih ketat untuk apa yang membentuk program yang lengkap (aturan mengatakan pengiriman dapat menjadi fungsi). Kiriman ini mengambil input sebagai argumen fungsi.
sumber
c=[1..r]
, sehingga Anda dapat menggunakannya di dalamo
danw
. b)minimumBy(\(a,_)(b,_)->compare a b)[...]
adalahhead$sortOn fst[...]
. c)v
dalamv=g0!s
hanya digunakan sekali, jadi jangan menentukan sama sekali:l=length$g0!s
. d) Anda masih memiliki beberapa nama parameter dua huruf. e) gantiTrue
dengan1<2
danFalse
dengan2<1
. f)and[case g0!s of{[_]->True;_->False}|s<-u]
adalahall((==1).length.(g0!))u
.(&)m k=
dapat didefinisikan infiks:m&k=
. h)not(d
Elem(g0!p))
adalahnotElem d$g0!p
. i)concat(...)
adalahid=<<(...)
. j) menggunakan operator infiks untukh
, misas%bs=
.``like`this``
!Pyth, 41 byte
Brute force ftw!
Karena ini pada dasarnya terus mencoba acak acak hingga berfungsi (ya, itu terus mencoba
n * [shuffle(range(n))]
), butuh waktu yang sangat, sangat lama. Berikut ini beberapa uji coba untuk memberi Anda gambaran tentang berapa lama waktu yang dibutuhkan:Itu hanya 4x4, dan berjalan dalam waktu kurang dari setengah detik. Saya sebenarnya curang karena ini adalah yang terbaik dari beberapa cobaan — kebanyakan dari mereka mengambil satu atau dua detik.
Saya belum mendapatkan waktu pada 5x5 (berlari sampai selesai sekali, tapi itu dalam REPL dan saya tidak menghitung waktu itu).
Perhatikan bahwa aturan untuk batas waktu hanya diedit ke pertanyaan setelah jawaban ini diposting.
sumber
SWI-Prolog, 326 * 0,80 = 260,8 byte
Sunting: disimpan 16 byte berkat @Mat
Pemakaian
Hubungi
a(5).
juru bahasa Anda untukN=5
. Ini mengembalikanfalse
untukN=2
atauN=3
.Karena menggunakan perpustakaan CLPFD ini bukan bruteforce murni. Program ini dapat menemukan solusi untuk
N=20
dalam waktu sekitar 15 detik di komputer saya.Penjelasan + tidak dikumpulkan:
Ini pada dasarnya bekerja seperti pemecah Sudoku, kecuali bahwa batasan balok diganti dengan kendala diagonal.
sumber
maplist(maplist(all_distinct), [R,C,D,E])
[R,C,[D,E]]
, karenaE
danD
daftar sederhana.N=20
CJam, 87 byte - bonus 20% = 69,6 byte
Hardcode jawabannya. Berisi beberapa unsintables. Bekerja
N = 1
melaluiN = 8
.Pada dasarnya, setiap baris dalam string misterius berisi indeks ke dalam daftar permutasi
range(N)
, dikodekan sebagai karakter Unicode.=:i0+\,m!f=
mengindeks ke dalam daftar permutasi, menambahkan 0 ke akhir daftar indeks terlebih dahulu, mewakili baris bawah0 1 2 ... N-1
. SebabN < 4
, array 2D yang dihasilkan adalah omong kosong.`1LL]
membuat daftar[N, pretty output, 1, "", ""]
. Kemudian,(4e<=
muncul elemen pertama dari daftar iniN
,, dan ambilmin(N, 4) % 4
elemen th dari sisanya. KarenaN >= 4
, itulah outputnya, dan jika tidak, itu adalah output case khusus untuk tiga case pertama.Coba di sini .
sumber
C ++,
672 * 0.80645 * 0.80 = 516 byteCobalah online di sini
Karena beberapa jawaban telah diposting, saya pikir saya akan memposting versi golf dari kode yang saya gunakan untuk menghasilkan output untuk contoh. Ini adalah pertama kalinya saya menjawab a kode-golf , jadi semua umpan balik disambut. :)
Penjelasan + tidak dikumpulkan:
Pada dasarnya, kode ini memaksa solusi. Itu dimulai di baris pertama, dengan 0. Dimulai di tempat pertama, jika tempat itu melewati semua cek, ia pindah ke nomor berikutnya. Jika mengisi baris, ia bergerak ke baris berikutnya. Jika dilakukan semua baris, itu berarti solusi telah ditemukan. Jika tempat tidak lulus semua cek, itu pindah ke tempat berikutnya. Jika dilakukan baris, maka backtracks, karena angka di salah satu baris sebelumnya mencegah kemungkinan solusi.
sumber
if (x[r][p]) return f(c+1,r);
. Saya sedang berusaha memperpendeknya.Clojure,
(215 + 258) * 0.8 = 378.4(174 + 255) * 0.8 = 343.2Dibagi menjadi dua bagian: penghitungan kesalahan
S
dan fungsi anonim yang melakukan optimasi sebenarnya melalui pencarian Tabu .Pembaruan: lebih pendek
S
(menghitung nilai berbeda dalam grup), status awal yang kurang optimal (tanpa acak).Benchmark inti tunggal (dalam milidetik) untuk 4, 5, 6 dan 7 berjalan 3 kali:
Asli:
Saya berharap
S
lebih pendek, tetapi karena hanya menghitung kejadian lebih dari satu / partisi kriteria berhenti adalah sederhana(= s 0)
.Banyak siklus CPU yang terbuang untuk swap yang tidak berguna, misalnya itu tidak meningkatkan skor jika Anda bertukar
2
dengan2
, dan Anda tidak perlu nomor pertukaran antara baris karena mereka semua memiliki nilai yang berbeda untuk memulai.Tolak ukur dengan Intel 6700K (dalam milidetik):
Multithreaded dengan
pmap
:sumber