Latar Belakang
Saya ingin membangun pagar. Untuk itu, saya telah mengumpulkan banyak tiang, dan menancapkannya ke tanah. Saya juga telah mengumpulkan banyak papan yang akan saya paku ke tiang untuk membuat pagar yang sebenarnya. Saya cenderung terbawa ketika membangun barang-barang, dan kemungkinan besar saya akan terus menempelkan papan ke tiang sampai tidak ada lagi tempat untuk meletakkannya. Saya ingin Anda menyebutkan kemungkinan pagar yang bisa saya akhiri.
Memasukkan
Input Anda adalah daftar koordinat bilangan dua dimensi yang mewakili posisi kutub, dalam format apa pun yang nyaman. Anda dapat berasumsi bahwa itu tidak mengandung duplikat, tetapi Anda tidak dapat mengasumsikan apa pun tentang pesanannya.
Papan diwakili oleh garis lurus antara kutub, dan untuk kesederhanaan, kami hanya mempertimbangkan papan horizontal dan vertikal. Dua kutub dapat disatukan dengan papan jika tidak ada kutub atau papan lain di antara mereka, yang berarti bahwa papan tidak dapat saling bersilangan. Susunan tiang dan papan maksimal jika tidak ada papan baru dapat ditambahkan ke dalamnya (setara, ada baik tiang atau papan antara dua kutub horizontal atau vertikal).
Keluaran
Output Anda adalah jumlah pengaturan maksimal yang dapat dibangun menggunakan kutub.
Contoh
Pertimbangkan daftar input
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]
Dilihat dari atas, susunan kutub yang sesuai terlihat seperti ini:
o
o o
o o
o o
o
Tepat ada tiga pengaturan maksimal yang dapat dibangun menggunakan kutub ini:
o o o
o-o o|o o-o
o----o o||| o o| | o
o-o o|o o-o
o o o
Dengan demikian output yang benar adalah 3
.
Aturan
Anda dapat menulis fungsi atau program lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.
Uji Kasus
[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8
(0,-2)
, tangkapan yang bagus. Berubah sekarang.Jawaban:
Mathematica, 301 byte
Ini adalah fungsi tanpa nama yang mengambil koordinat sebagai bersarang
List
dan mengembalikan integer. Artinya, Anda bisa memberikannya nama dan memanggilnya, atau hanya menambahkanDengan lekukan:
Saya bahkan tidak bisa mulai menyatakan betapa naifnya implementasi ini ... pasti tidak bisa lebih kasar ...
o--o--o
menghasilkan hanya dua pagar, bukan tiga).Anehnya itu menyelesaikan semua kasus uji hampir secara langsung.
Trik yang sangat rapi yang saya temukan untuk ini adalah penggunaan
Orderless
untuk mengurangi jumlah pola yang harus saya cocokkan. Intinya, ketika saya ingin membuang pagar dengan pagar penyeberangan, saya perlu menemukan sepasang pagar vertikal dan horizontal dan memeriksa kondisinya. Tapi saya tidak tahu urutan apa yang akan muncul. Karena pola daftar biasanya tergantung pesanan, ini akan menghasilkan dua pola yang sangat panjang. Jadi alih-alih saya ganti dengan daftar sekitarnya dengan fungsit
dengant @@@
- yang tidak didefinisikan sehingga disimpan seperti apa adanya. Tapi fungsi ituOrderless
, jadi saya hanya bisa memeriksa satu urutan dalam pola, dan Mathematica akan memeriksanya terhadap semua permutasi. Setelah itu, saya mengembalikan daftar itu ke tempatnyaList @@@
.Saya berharap ada built-in yang a)
Orderless
, b) tidakListable
dan c) tidak didefinisikan untuk 0 argumen atau daftar argumen. Maka saya bisa menggantinyat
. Tapi sepertinya tidak ada operator seperti itu.sumber
Haskell, 318 byte
Penggunaan:
p [(1,0),(0,1),(-1,0),(0,-1)]
. Keluaran:2
Bagaimana itu bekerja:
sumber