Latar Belakang
Segitiga Pythagoras adalah segitiga siku-siku di mana setiap panjang sisi adalah bilangan bulat (yaitu, panjang sisi membentuk tripel Pythagoras ):
Dengan menggunakan sisi-sisi segitiga ini, kita dapat melampirkan dua segitiga Pythagoras yang tidak kongruen sebagai berikut:
Kita dapat melanjutkan dengan pola ini sesuai keinginan, asalkan tidak ada dua segitiga yang bertumpang tindih, dan sisi penghubung memiliki panjang yang sama:
Pertanyaannya adalah, berapa banyak segitiga Pythagoras non-kongruen yang dapat kita muat di ruang tertentu?
Input
Anda akan menerima dua bilangan bulat sebagai input, W
dan H
, melalui argumen fungsi, STDIN, string, atau apa pun yang Anda suka. Bilangan bulat dapat diterima sebagai desimal, heksadesimal, biner, unary (semoga sukses, Retina ), atau basis integer lainnya. Anda mungkin menganggap itu max(W, H) <= 2^15 - 1
.
Hasil
Program atau fungsi Anda harus menghitung daftar segitiga Pythagoras terkoneksi yang tidak tumpang tindih dan menghasilkan daftar set tiga koordinat masing-masing, di mana koordinat dalam himpunan membentuk salah satu segitiga Pythagoras saat dihubungkan oleh garis. Koordinat harus bilangan real di ruang kita ( x
harus dalam interval [0, W]
dan y
harus dalam interval)[0, H]
), dan jarak harus akurat untuk mesin presisi. Urutan segitiga dan format yang tepat dari masing-masing koordinat tidak penting.
Harus mungkin untuk "berjalan" dari satu segitiga ke segitiga lainnya hanya melangkahi batas yang terhubung.
Menggunakan diagram di atas sebagai contoh, mari kita masukan kami menjadi W = 60
, H = 60
.
Output kami kemudian bisa menjadi daftar koordinat berikut:
(0, 15), (0, 21), (8, 15)
(0, 21), (14.4, 40.2), (8, 15)
(0, 15), (8, 0), (8, 15)
(8, 0), (8, 15), (28, 15)
(8, 15), (28, 15), (28, 36)
(28, 15), (28, 36), (56, 36)
Sekarang, 6 segitiga pastinya bukan yang terbaik yang bisa kita lakukan mengingat ruang kita. Bisakah kamu berbuat lebih baik?
Aturan dan Penilaian
Skor Anda untuk tantangan ini adalah jumlah segitiga yang dihasilkan oleh program Anda atas masukan dari
W = 1000, H = 1000
. Saya berhak mengubah input ini jika saya mencurigai seseorang melakukan hardcoding pada kasus ini.Anda tidak boleh menggunakan builtin yang menghitung tripel Pythagoras, dan Anda tidak boleh membuat hardcode daftar lebih dari 2 tripel Pythagoras (jika Anda hardcode program Anda untuk selalu memulai dengan segitiga (3, 4, 5), atau keadaan awal yang serupa, yang baik-baik saja).
Anda dapat menulis kiriman Anda dalam bahasa apa pun. Keterbacaan dan komentar sangat dianjurkan.
Anda dapat menemukan daftar tiga kali lipat Pythagoras di sini .
Celah Standar tidak diizinkan.
sumber
Jawaban:
Python 3, 109
Ini tentu saja merupakan tantangan yang sulit. Ada banyak kali menulis kode yang saya temukan mempertanyakan kemampuan geometri dasar saya. Yang sedang berkata, saya cukup senang dengan hasilnya. Saya tidak berusaha untuk menghasilkan algoritma yang kompleks untuk menempatkan segitiga, dan alih-alih kode saya hanya blunder karena selalu menempatkan yang terkecil yang dapat ditemukan. Saya harap saya dapat meningkatkan ini nanti, atau jawaban saya akan menolak orang lain untuk menemukan algoritma yang lebih baik! Secara keseluruhan, masalah yang sangat menyenangkan, dan menghasilkan beberapa gambar yang menarik.
Ini kodenya:
Berikut grafik output untuk
W = 1000
danH = 1000
dengan 109 segitiga:Inilah
W = 10000
danH = 10000
dengan 724 segitiga:Panggil
matplotlib_graph()
fungsi setelahbuild_all_triangles()
membuat grafik segitiga.Saya pikir kodenya berjalan cukup cepat: pada
W = 1000
danH = 1000
butuh 0,66 detik, dan padaW = 10000
danH = 10000
butuh 45 detik menggunakan laptop jelek saya.sumber
C ++, 146 segitiga (bagian 1/2)
Hasil sebagai Gambar
Deskripsi Algoritma
Ini menggunakan pencarian luas pertama dari ruang solusi. Di setiap langkah, itu dimulai dengan semua konfigurasi unik
k
segitiga yang sesuai di dalam kotak, dan membangun semua konfigurasi unikk + 1
segitiga dengan menyebutkan semua opsi menambahkan segitiga yang tidak digunakan ke salah satu konfigurasi.Algoritma pada dasarnya diatur untuk menemukan maksimum absolut dengan BFS lengkap. Dan itu berhasil untuk ukuran yang lebih kecil. Misalnya, untuk kotak 50x50, ia menemukan maksimum dalam sekitar 1 menit. Tetapi untuk 1000x1000, ruang solusi terlalu besar. Untuk menghentikannya, saya memotong daftar solusi setelah setiap langkah. Jumlah solusi yang disimpan diberikan oleh argumen baris perintah. Untuk solusi di atas, nilai 50 digunakan. Ini menghasilkan runtime sekitar 10 menit.
Garis besar langkah-langkah utama terlihat seperti ini:
Salah satu aspek penting dalam keseluruhan skema adalah bahwa konfigurasi umumnya akan dihasilkan beberapa kali, dan kami hanya tertarik pada konfigurasi unik. Jadi kita membutuhkan kunci unik yang mendefinisikan solusi, yang harus independen dari urutan segitiga yang digunakan saat menghasilkan solusi. Misalnya, menggunakan koordinat untuk kunci tidak akan berfungsi sama sekali, karena mereka bisa sangat berbeda jika kami tiba pada solusi yang sama dalam beberapa pesanan. Apa yang saya gunakan adalah kumpulan indeks segitiga dalam daftar global, ditambah satu set objek "konektor" yang menentukan bagaimana segitiga terhubung. Jadi kuncinya hanya mengkodekan topologi, terlepas dari urutan dan posisi konstruksi dalam ruang 2D.
Sementara lebih merupakan aspek implementasi, bagian lain yang tidak sepenuhnya sepele adalah memutuskan apakah dan bagaimana semuanya cocok ke dalam kotak yang diberikan. Jika Anda benar-benar ingin mendorong batas, jelas perlu untuk memungkinkan rotasi agar sesuai di dalam kotak.
Saya akan mencoba dan menambahkan beberapa komentar ke kode di bagian 2 nanti, kalau-kalau ada orang yang ingin merinci bagaimana ini semua bekerja.
Hasil dalam Format Teks Resmi
Kode
Lihat bagian 2 untuk kode. Ini dipecah menjadi 2 bagian untuk mengatasi batas ukuran posting.
Kode ini juga tersedia di PasteBin .
sumber
C ++, 146 segitiga (bagian 2/2)
Lanjutan dari bagian 1. Ini dibagi menjadi 2 bagian untuk mengatasi batas ukuran pos.
Kode
Komentar yang akan ditambahkan.
sumber