Sejarah
Perusahaan saya mengirimkan buletin mingguan kepada semua orang di dalam perusahaan. Termasuk dalam buletin ini adalah teka-teki, bersama dengan teriakan kepada siapa pun di perusahaan adalah orang pertama yang mengirim email / memberikan solusi untuk teka-teki minggu lalu. Sebagian besar teka-teki ini cukup sepele, dan sejujurnya cukup membosankan untuk sebuah perusahaan teknologi, tetapi ada satu, beberapa bulan yang lalu, yang menarik perhatian saya.
Teka-teki Asli:
Diberikan bentuk di bawah ini:
Anda memiliki Bilangan Alami dari 1 hingga 16. Paskan semuanya ke dalam bentuk ini, sehingga semua baris dan kolom yang berdekatan berjumlah hingga 29.
Misalnya, salah satu solusi untuk teka-teki ini (yang merupakan solusi "kanonik" yang saya kirimkan ke buletin) adalah sebagai berikut:
Namun, dalam penyelesaiannya, saya menemukan beberapa informasi yang agak menarik:
- Ada jauh lebih banyak solusi daripada hanya satu itu; sebenarnya, ada 9.368 Solusi.
- Jika Anda memperluas aturan hanya mensyaratkan bahwa baris dan kolom sama satu sama lain, belum tentu 29, Anda mendapatkan 33.608 solusi:
- 4.440 Solusi dengan jumlah 27.
- 7.400 Solusi dengan jumlah 28.
- 9.368 Solusi dengan jumlah 29.
- 6.096 Solusi dengan jumlah 30.
- 5.104 Solusi dengan jumlah 31.
- 1.200 Solusi dengan jumlah 32.
Jadi saya dan rekan kerja saya (meskipun sebagian besar hanya manajer saya, karena ia adalah satu-satunya orang selain saya yang memiliki keterampilan pemrograman "Tujuan Umum") memulai sebuah tantangan, yang berlangsung hampir sepanjang bulan — kami memiliki pekerjaan lain yang sebenarnya - kewajiban terkait yang harus kami hadiri — untuk mencoba menulis sebuah program yang akan menemukan setiap solusi dengan cara tercepat yang mungkin.
Statistik Asli
Program pertama yang saya tulis untuk memecahkan masalah cukup memeriksa solusi acak berulang-ulang, dan berhenti ketika menemukan solusi. Jika Anda sudah melakukan analisis matematika pada masalah ini, Anda mungkin sudah tahu bahwa ini seharusnya tidak berhasil; tapi entah bagaimana saya beruntung, dan butuh program hanya satu menit untuk menemukan solusi tunggal (yang saya posting di atas). Pengulangan program seringkali memakan waktu 10 atau 20 menit, jadi jelas ini bukan solusi yang tepat untuk masalah ini.
Saya beralih ke Solusi Rekursif yang berulang melalui setiap permutasi yang mungkin dari teka-teki, dan membuang banyak solusi sekaligus dengan menghilangkan jumlah yang tidak bertambah. Yaitu jika baris / kolom pertama yang saya bandingkan sudah tidak sama, saya bisa berhenti memeriksa cabang itu segera, mengetahui bahwa tidak ada hal lain yang dimasukkan ke dalam puzzle akan mengubah itu.
Dengan menggunakan algoritma ini, saya mendapatkan kesuksesan "layak" pertama: program ini dapat menghasilkan dan mengeluarkan semua 33.608 solusi dalam waktu sekitar 5 menit.
Manajer saya memiliki pendekatan yang berbeda: mengetahui berdasarkan pekerjaan saya bahwa satu-satunya solusi yang mungkin memiliki jumlah 27, 28, 29, 30, 31, atau 32, ia menulis solusi multi-utas yang memeriksa jumlah yang mungkin hanya untuk nilai-nilai spesifik tersebut. Dia berhasil menjalankan programnya hanya dalam 2 menit. Jadi saya mengulangi lagi; Saya hash semua kemungkinan jumlah 3/4 digit (pada awal program; ini dihitung dalam runtime total) dan menggunakan "jumlah parsial" dari sebuah baris untuk mencari nilai yang tersisa berdasarkan pada baris yang sebelumnya diselesaikan, daripada menguji semua nilai yang tersisa, dan membawa waktu ke 72 detik. Kemudian dengan beberapa logika multi-threading, saya mendapatkannya hingga 40 detik. Manajer saya membawa pulang program, melakukan beberapa optimasi tentang bagaimana program berjalan, dan menurunkannya menjadi 12 detik. Saya memesan kembali evaluasi baris dan kolom,
Yang tercepat dari kami mendapatkan program kami setelah sebulan adalah 0,15 detik untuk manajer saya, dan 0,33 detik untuk saya. Saya akhirnya mengklaim bahwa program saya lebih cepat, karena program manajer saya, sementara itu menemukan semua solusi, tidak mencetaknya ke dalam file teks. Jika dia menambahkan logika itu ke kodenya, seringkali butuh waktu 0,4-0,5 detik.
Sejak itu kami membiarkan tantangan intra-pribadi kami bertahan, tetapi tentu saja, pertanyaannya tetap: bisakah program ini dibuat lebih cepat?
Itulah tantangan yang akan saya ajukan kepada kalian.
Tantangan Anda
Parameter yang kami kerjakan melonggarkan aturan "jumlah 29" sebagai gantinya "jumlah semua baris / kolom sama", dan saya akan menetapkan aturan itu juga untuk kalian. Tantangannya, oleh karena itu, adalah: Menulis program yang menemukan (dan Mencetak!) Semua solusi untuk teka-teki ini dalam waktu sesingkat mungkin. Saya akan menetapkan batas pada solusi yang diajukan: Jika program membutuhkan lebih dari 10 detik pada komputer yang relatif baik (<8 tahun), mungkin terlalu lambat untuk dihitung.
Juga, saya punya beberapa Bonus untuk puzzle:
- Bisakah Anda menggeneralisasi solusi sehingga berfungsi untuk set angka 16, bukan hanya
int[1,16]
? Skor waktu akan dievaluasi berdasarkan set angka prompt yang asli, tetapi melewati codepath ini. (-10%) - Bisakah Anda menulis kode dengan cara yang anggun menangani dan menyelesaikan dengan angka duplikat? Ini tidak semudah kelihatannya! Solusi yang "identik secara visual" harus unik dalam set hasil. (-5%)
- Bisakah Anda menangani angka negatif? (-5%)
Anda juga dapat mencoba menghasilkan solusi yang menangani Angka Titik Apung, tetapi tentu saja, jangan kaget jika itu gagal total. Jika Anda menemukan solusi yang kuat, itu mungkin bernilai bonus besar!
Untuk semua maksud dan tujuan, "Rotasi" dianggap sebagai solusi unik. Jadi solusi yang hanya merupakan rotasi dari solusi yang berbeda dianggap sebagai solusi sendiri.
IDE yang saya kerjakan di komputer saya adalah Java dan C ++. Saya dapat menerima jawaban dari bahasa lain, tetapi Anda mungkin juga perlu memberikan tautan ke tempat saya bisa mendapatkan lingkungan runtime yang mudah diatur untuk kode Anda.
sumber
Jawaban:
C - hampir 0,5 detik
Program yang sangat naif ini memberikan semua solusi dalam setengah detik pada laptop saya yang berumur 4 tahun. Tidak ada multithread, tidak ada hashing.
Windows 10, Visual Studio 2010, CPU core I7 64 bit
Coba online di ideone
sumber
int inuse[16];
dengan adilint inuse;
lalu gunakan operator bitwise untuk memanipulasinya. Ini tampaknya tidak meningkatkan kecepatan yang banyak, tapi membantu sedikit a.dumbbench --precision=.01 -vvv --initial=500 ./solve
C ++ - 300 Milidetik
Per permintaan, saya telah menambahkan kode saya sendiri untuk menyelesaikan teka-teki ini. Di komputer saya, jam di rata-rata 0,310 detik (310 milidetik) tetapi tergantung pada varian dapat berjalan secepat 287 milidetik. Saya sangat jarang melihatnya naik di atas 350 milidetik, biasanya hanya jika sistem saya macet dengan tugas yang berbeda.
Waktu ini didasarkan pada pelaporan diri yang digunakan dalam program, tetapi saya juga diuji menggunakan pengatur waktu eksternal dan mendapatkan hasil yang serupa. Overhead dalam program ini sepertinya menambah sekitar 10 milidetik.
Juga, kode saya tidak cukup menangani duplikat dengan benar. Itu dapat menyelesaikan penggunaannya, tetapi tidak menghilangkan solusi "identik secara visual" dari set solusi.
sumber
0.1038s +/- 0.0002
Dan inilah waktu untuk kode Anda dengan output yang disederhanakan:0.0850s +/- 0.0001
Jadi, Anda dapat menyimpan ~ 18ms, setidaknya di komputer saya. Saya menjalankan kedua versi 500+ kali dengan outlier yang dibuang, menggunakan dumbbenchProlog - 3 menit
Teka-teki semacam ini tampaknya seperti kasus penggunaan yang sempurna untuk Prolog. Jadi, saya membuat solusi di Prolog! Ini dia:
Sayangnya, ini tidak secepat yang saya harapkan. Mungkin seseorang yang lebih berpengalaman dalam pemrograman deklaratif (atau Prolog khusus) dapat menawarkan beberapa tips pengoptimalan. Anda bisa menjalankan aturan
puzzle
dengan perintah berikut:Cobalah online di sini . Anda dapat mengganti angka apa saja dengan
29
huruf s dalam kode untuk menghasilkan semua solusi. Seperti berdiri, semua 29 solusi ditemukan dalam waktu sekitar 30 detik, jadi untuk menemukan semua solusi yang mungkin harus sekitar 3 menit.sumber