Tantangan ini terinspirasi oleh aplikasi ini . Kasing uji dipinjam dari aplikasi itu.
Ini adalah tantangan kode tercepat , di mana tujuannya adalah untuk menyelesaikan kasus uji terbesar dalam jumlah waktu paling sedikit. Tersedia beberapa kasus uji yang lebih kecil, sehingga orang dapat menguji algoritme mereka lebih cepat.
Anda akan diberi kotak input persegi, dengan dimensi n-oleh-n di mana 9 <= n <= 12 . Kotak ini akan dibagi menjadi n area, di mana sel-sel di setiap area memiliki pengidentifikasi unik (saya akan menggunakan huruf kecil dari al dalam teks di sini, tetapi Anda dapat memilih apa pun yang Anda suka, misalnya bilangan bulat 1-12 ) .
Input mungkin terlihat seperti ini (format input opsional):
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
Atau, lebih mudah untuk divisualisasikan:
Tantangan:
Anda harus menempatkan 2 * n pohon di taman ini, sesuai dengan aturan berikut:
- Tepatnya akan ada 2 pohon per kolom, dan 2 pohon per baris
- Semua area harus memiliki tepat 2 pohon.
- Tidak ada pohon yang dapat berbatasan dengan pohon lain, secara vertikal, horizontal atau diagonal
Solusi untuk tata letak di atas adalah:
Catatan: Hanya ada satu solusi untuk setiap puzzle
Aturan tambahan:
- Format input dan output adalah opsional
- Keluaran mungkin misalnya berupa daftar indeks, kisi dengan 1/0 yang menunjukkan apakah ada pohon di posisi itu, atau versi input yang dimodifikasi di mana pohon ditunjukkan
- Waktu pelaksanaan harus deterministik
- Program harus selesai dalam 1 menit di komputer @ isaacg
- Spesifikasi: 4 CPU, CPU i5-4300U @ 1,9 GHz, RAM 7,5G.
- Jika program Anda tidak dapat menyelesaikan dua test case terbesar dalam satu menit masing-masing maka waktu untuk terbesar kedua ( n = 11 ) akan menjadi skor Anda. Anda akan kalah terhadap solusi yang memecahkan kasus terbesar.
Kasus uji:
Saya mungkin mengedit daftar ini jika pengajuan tampaknya disesuaikan agar sesuai dengan kasus pengujian ini.
12-oleh-12 :
--- Input ---
aaaaabccccdd
aaaaabccccdd
aaaaabbbbddd
eeeafffgbghh
eeaafffgbghh
eefffffggghh
eeefijffghhh
iieiijjjjkhh
iiiiijjjjkhk
lljjjjjjjkkk
llllllkkkkkk
llllllkkkkkk
--- Solution ---
aaaaabcccCdD
aaaaaBcCccdd
aAaaabbbbdDd
eeeaffFgBghh
eeAaFffgbghh
eefffffGgGhh
EeefijffghhH
iiEiIjjjjkhh
IiiiijjjjkHk
lljJjJjjjkkk
lLllllkkKkkk
lllLllKkkkkk
11-oleh-11 :
--- Input ---
aaaaaaabbcc
adddabbbbcc
edddbbbbbbc
eddddbbbbbb
effffggghhh
effffgghhii
eefffjjhhii
eeeejjjhhii
eeejjjjkiii
jjjjjjkkiii
jjjjjkkkiii
--- Solution ---
aaAaaaabbCc
adddAbBbbcc
eDddbbbbbbC
eddDdBbbbbb
effffggGhHh
eFfffGghhii
eefFfjjhHii
EeeejjjhhiI
eeEjjjjKiii
JjjjJjkkiii
jjjjjkKkIii
10-kali-10
--- Input ---
aaaaabccdd
aeaabbbccd
aeaabfbgcd
eeeaafggcd
eeeaafghcd
eeeiifghcd
ieiiigghcd
iiijighhcd
jjjjighhcd
jjjggghhdd
--- Solution ---
aaAaabccdD
aeaaBbBccd
aEaabfbgcD
eeeaaFgGcd
eEeAafghcd
eeeiiFghCd
IeiIigghcd
iiijigHhCd
JjJjighhcd
jjjgGghHdd
9-oleh-9
--- Input ---
aabbbbbcc
adddbbbcc
adeeecccc
adddefgcc
hhhdifggg
hdddifffg
hhhiifffg
hihiifffg
iiiiiiggg
--- Solution ---
aAbBbbbcc
adddbbBcC
adEeEcccc
AdddefgCc
hhhDiFggg
hDddifffG
hhhiIfFfg
HiHiifffg
iiiiiIgGg
--- Input ---
aaabbbccc
aaaabbccc
aaaddbcce
ffddddcce
ffffddeee
fgffdheee
fggfhhhee
iggggheee
iiigggggg
--- Solution ---
aaAbBbccc
AaaabbcCc
aaaDdBcce
fFddddcCe
fffFdDeee
fGffdheeE
fggfHhHee
IggggheeE
iiIgggGgg
sumber
There shall be exactly 2 trees per column, and 2 trees per row
sehingga kekuatan kasar mungkin tidak mungkin.Jawaban:
JavaScript (ES6), 271 byte
Mengambil input sebagai array array karakter. Mengembalikan array bitmask (bilangan bulat) yang menggambarkan posisi pohon di setiap baris, di mana bit paling signifikan adalah posisi paling kiri.
Diformat dan dikomentari
Uji kasus
Cuplikan ini mencakup fungsi tambahan untuk menampilkan hasil dalam format yang lebih mudah dibaca. Terlalu lambat untuk menyelesaikan kasus uji terakhir.
Runtime yang diharapkan: ~ 5 detik.
Tampilkan cuplikan kode
sumber
C, waktu resmi: 5ms untuk 12x12
Dikompilasi dengan GCC 7 menggunakan tanda
-O3
dan-fopenmp
. Seharusnya memiliki hasil yang serupa pada versi GCC dengan OpenMP diinstal.Format input dan output seperti yang diberikan dalam pertanyaan.
Pada komputer saya ini membutuhkan
0,009s0,008s0,005s untuk contoh 12x12, dan0,022s0,020s0,019s untuk menjalankan semua contoh. Pada mesin benchmark, isaacg melaporkan 5ms untuk contoh 12x12 menggunakan versi kode asli (non-berulir).Pemakaian:
Hanya pemecah brute-force sederhana, mengerjakan satu baris sekaligus. Ini berjalan dengan kecepatan yang baik dengan mengenali situasi-situasi yang mustahil sejak dini (mis. Tidak ada sel wilayah yang tersisa, tetapi kurang dari 2 pohon di wilayah itu).
Pembaruan pertama meningkatkan hit cache dengan menempatkan data terkait berdekatan dalam memori, dan membuat kalkulasi kemungkinan-tree-tersisa-di-segmen sedikit lebih pintar (sekarang memperhitungkan fakta bahwa pohon tidak dapat berdekatan). Itu juga mengekstrak loop terluar sehingga kasus khusus lebih sedikit diperlukan di bagian terpanas dari algoritma.
Pembaruan kedua membuat loop terluar berjalan paralel di seluruh prosesor yang tersedia (menggunakan OpenMP), memberikan peningkatan kecepatan linier. Ini hanya diaktifkan untuk n> = 11, karena overhead dari spawning threads lebih besar daripada manfaatnya untuk grid yang lebih kecil.
sumber
Java (OpenJDK 8) , Waktu Resmi: 1.2s pada 12x12
sunting: tidak ada lagi kode golf
Cobalah online!
TIO link adalah untuk test case 12x12. TIO melaporkan 2,429 untuk jangka waktu berjalan.
Mengambil array bilangan bulat sebagai input dan memodifikasi array berisi 1s untuk pohon dan 0s untuk non-pohon.
Ini berjalan untuk semua testcases. Testcase terbesar berjalan pada mesin saya dalam waktu kurang dari satu detik, meskipun saya memiliki mesin yang cukup kuat
Kode uji untuk 12x12, dapat dimodifikasi untuk orang lain
Menghasilkan ini di mesin saya:
sumber
Clingo , ≈ 7 ms untuk 12 × 12, 116 byte
(Baris baru bersifat opsional dan tidak dihitung.)
Jalankan dengan di
clingo plant.lp - -c n=<n>
mana<n>
ukuran kisi. Format masukan adalah daftarc(X,Y,Z).
pernyataan untuk setiap sel (X
,Y
) berwarnaZ
, dengan 1 ≤X
,Y
,Z
≤n
, dipisahkan oleh spasi opsional. Output termasukt(X,Y)
untuk setiap pohon di (X
,Y
).Waktu ini sangat tidak berarti karena ini pada dasarnya hanya waktu startup, jadi pertimbangkan ini suara untuk kasus uji yang lebih besar.
Demo
Untuk membuat format input / output lebih mudah ditangani, berikut adalah program Python untuk mengkonversi dari dan ke format yang diberikan dalam tantangan.
Memasukkan
Keluaran
sumber