Ini adalah yang pertama dari serangkaian tantangan Island Golf. Tantangan selanjutnya
Diberi nama pulau dalam seni ASCII, menghasilkan jalur yang optimal untuk mengelilingi pulau itu.
Memasukkan
Input Anda akan berupa kotak persegi panjang yang terdiri dari dua karakter, mewakili tanah dan air. Dalam contoh di bawah ini, tanah adalah #
dan air adalah .
, tetapi Anda dapat mengganti dua karakter berbeda yang Anda inginkan.
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........
Akan selalu ada setidaknya satu ubin tanah. Ubin tanah semuanya akan bersebelahan (yaitu hanya ada satu pulau). Ubin air juga akan bersebelahan (yaitu tidak ada danau). Perbatasan luar dari grid semua akan menjadi ubin air. Ubin tanah tidak akan terhubung secara diagonal: yaitu, Anda tidak akan pernah melihat sesuatu seperti itu
....
.#..
..#.
....
Keluaran
Kode Anda harus menampilkan kisi yang sama, dengan navigasi keliling terpendek di atasnya. Pada contoh di bawah ini, jalur navigasi keliling digambar o
, tetapi Anda dapat mengganti karakter apa pun asalkan berbeda dari karakter tanah dan air Anda.
Sebuah mengelilingi adalah kurva tertutup sederhana, ditarik sepenuhnya pada ubin air, yang sepenuhnya mengelilingi semua ubin tanah di grid. Koneksi diagonal yang diperbolehkan. Misalnya, ini adalah penjelajahan dari pulau di atas (tetapi bukan yang terpendek):
.ooooo.....
o..##.oo...
o.#####.o..
o.#######o.
o#########o
ooo#######o
..o#####.#o
..oo####..o
....oooooo.
Panjang navigasi mengelilingi dihitung sebagai berikut: Untuk setiap pasangan ubin yang berdekatan di jalan, jika mereka terhubung secara horizontal atau vertikal, tambahkan 1; jika mereka terhubung secara diagonal, tambahkan √2. Panjang jalur di atas adalah 22 + 7√2 (≈ 31,9).
Sebuah terpendek mengelilingi adalah mengelilingi dengan panjang sesingkat mungkin. Program Anda harus menampilkan satu jalur yang memenuhi kondisi ini. Untuk sebagian besar pulau, akan ada beberapa kemungkinan solusi. Berikut adalah satu solusi untuk pulau di atas, dengan panjang 10 + 13√2 (≈ 28,4):
...oo......
..o##oo....
.o#####oo..
.o#######o.
o#########o
.o.#######o
..o#####.#o
...o####.o.
....ooooo..
Detail
Solusi Anda mungkin merupakan program atau fungsi lengkap . Salah satu input dan output metode standar yang dapat diterima.
Input dan output Anda mungkin berupa string multiline atau daftar string. Jika bahasa Anda memiliki tipe karakter yang berbeda dari string karakter tunggal, Anda dapat mengganti "daftar karakter" untuk "string" dalam kalimat sebelumnya. Jika bahasa Anda perlu memasukkan tinggi dan / atau lebar kisi, Anda dapat melakukannya. Output Anda mungkin (secara opsional) memiliki satu baris baru. Seperti disebutkan di atas, Anda dapat menggunakan tiga karakter berbeda sebagai pengganti #.o
(harap tentukan dalam kiriman Anda karakter mana yang Anda gunakan).
Uji kasus
A. Pulau dengan navigasi berkeliling terpendek yang unik:
...
.#.
...
.o.
o#o
.o.
......
.####.
......
.oooo.
o####o
.oooo.
......
......
..##..
...#..
......
......
......
..oo..
.o##o.
..o#o.
...o..
......
.......
.#####.
...#...
...#...
.#####.
.......
.ooooo.
o#####o
o..#..o
o..#..o
o#####o
.ooooo.
.......
...#...
...#...
.#####.
...#...
...#...
.......
...o...
..o#o..
.o.#.o.
o#####o
.o.#.o.
..o#o..
...o...
.......
.#####.
.##..#.
..#..#.
.......
.ooooo.
o#####o
o##..#o
.o#..#o
..oooo.
B. Contoh pulau dengan beberapa solusi yang memungkinkan:
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........
Output yang mungkin:
....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##oo..
..oo....
....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##.o..
..ooo...
....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##oo..
..oo....
....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##.o..
..ooo...
C. Kasus uji besar sebagai Intisari
Ini adalah kode-golf : kode terpendek dalam setiap bahasa menang.
Jawaban:
Mathematica (versi 9), 165 byte
Fungsi bagus dan pendek
ConvexHullMesh
yang digunakan Greg Martin hanya diperkenalkan di Mathematica versi 10, jadi saya pikir saya akan berusaha tanpanya, menggunakan Mathematica kuno saya versi 9. Namun saya berhasil membuatnya sedikit lebih pendek! Ini adalah fungsi yang mengambil dan mengembalikan daftar string (dengan.
,#
dano
sebagai simbol).Penjelasan:
Characters@# /. {"."->0, "#"->1}
mengubah input menjadi matriks0
s dan1
s."o"MorphologicalTransform[MorphologicalComponents[#,Method->"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&]+"#"#
kemudian menggunakan kemampuan pemrosesan gambar Mathematica yang kuat (tapi sangat byte-berat ...) untuk pertama-tama mengisi lambung cembung pulau (yang merupakan bentuk yang akan Anda dapatkan jika Anda merentangkan seutas tali di sekitarnya), dan kemudian mengambil batasnya. Kami kemudian mengalikan matriks ini dengan string"o"
untuk mendapatkan matriks0
s dan"o"
s (terima kasih kepada kemampuan adaptasi Matematika yang mengesankan tentang jenis), dan menambahkan ini ke"#"
kali matriks pulau.""<>#& /@ (... /. {0->"."})
ubah matriks"o"
s, s,"#"
dan0
s ini menjadi matriks"o"
s,"#"
s dan"."
s, dan gabungkan setiap baris menjadi string.Ketika kami menguji ini pada contoh B , kami mendapatkan output
[Sunting, terima kasih kepada Greg Martin:] Jika kami diizinkan menggunakan array karakter alih-alih daftar string, kami dapat memangkasnya hingga 144 byte:
sumber
MorphologicalComponents[#, Method->"ConvexHull"]
:) Anda dapat menyimpan lebih banyak byte dengan mengasumsikan bahwa input sudah dibagi menjadi karakter, dan dengan mengembalikan array karakter 2D juga.MorphologicalComponents
sampai hari ini!f[{"...",".#.","..."}]
dan mendapatkan beberapa kesalahan.f
. (Yah, sebenarnya itu adalah barang setelah titik koma.) Untuk memanggil fungsi, ketik semuanya ke dalam jendela Mathematica, diikuti oleh[
, input Anda, dan]
, sehingga akan terlihat sepertif@m_:=m(1-m[[2,2]]) . . . #/.{"."->0,"#"->1}]&[{"...", ".#.", "..."}]
(diringkas untuk ruang).(Tapi pilihlah solusi Notatree , lebih baik!)
Mathematica, 168 byte
Fungsi murni mengambil array karakter 2D sebagai input dan mengembalikan array karakter 2D. Versi yang lebih mudah dibaca:
Baris 1 mendefinisikan fungsi
n
yang menghasilkan jarak (terkecil) antara titikx
di pesawat dan satu sety
titik lainnya. Baris 2 menginisialisasi variabeli
ke input, baik untuk menyelesaikan ambiguitas currying nanti dan untuk dapat memodifikasinya untuk menghasilkan output akhirnya; baris 2 juga mendefinisikan fungsip
yang mengembalikan koordinat semua kemunculan inputnyai
.Pada baris 3,
p["#" | "."]
mewakili setiap koordinat tunggal dari peta input (karena semua karakternya adalah salah satu"#"
atau"."
), jadit
adalah fungsi yang memilih hanya koordinat yang memenuhi properti yang belum ditentukan. Pada baris 4,i~Part~## = "o"
akan mengubah banyak entrii
ke karakter"o"
; karakter-karakter itu akan dipilih dari himpunan koordinat yang mungkin menurut item pada baris 5-8. Dan baris 9 baru mengembalikan jawaban setelah dihitung.Oke, infrastruktur sudah selesai, sekarang untuk perhitungan yang sebenarnya.
ConvexHullMesh
adalah built-in Mathematica untuk menghitung lambung cembung dari satu set poin (poligon cembung terkecil yang mengandung titik-titik itu). Secara moral, ini harus "mengisi" teluk-teluk kecil dan teluk-teluk pulau (yangs = p@"#"
), untuk mengesampingkan mereka dari navigasi pusat kami. Ada sedikit masalah denganConvexHullMesh
kapan kumpulan poin itu berada dalam satu garis (terima kasih, test case # 2), yang kami selesaikan dengan menambahkan versi yang sedikit diimbangis
untuk dirinya sendiri di baris 7. Output ini adalah poligon, jadi baris 7 -9 (t[...~RegionMember~# &]
) menghasilkan daftar titik dengan koordinat bilangan bulat dalam poligon itu. Akhirnya, garis 5 dan akhir garis 9 menghitung semua titik yang berada pada jarak tepat 1 (karenanya bukan 0) dari kumpulan titik integer ini; set yang menjadi jalur mengelilingi.Di bawah ini adalah output untuk test case besar di tautan OP. Perhatikan di kiri atas, pilihan-pilihan yang tidak biasa kapan pergi ke barat versus barat daya mengisyaratkan fakta bahwa itu membayangi garis kemiringan tak terlihat -2/3 antara dua semenanjung (kata segmen garis menjadi bagian dari batas lambung cembung).
sumber
char
jenis yang berbeda ; dalam hal ini, sebuahchar
array dapat digunakan sebagai pengganti string.Python 3, 779 byte (indentasi dengan tab)
Ini adalah keseluruhan program. Bunyinya input dari stdin dan mencetaknya ke stdout. Stdin harus diakhiri dengan EOF. Contoh dijalankan dengan input besar: https://ideone.com/XIfYY0
Idenya sederhana: ia menghitung batas oktagonal terkecil, dan menarik sel-sel yang ada di dalam semua batas yang dikomputasi dan memotong setidaknya satu ujung.
sumber
sys.stdin
sebagai input.input()
, mendapatkan multiline akan melakukan pekerjaan dan biaya lebih sedikit byteR(0,x)
denganR(x)
P
danf
;L(generator expression)
=>[generator expression]
;F
,,r
danB
tampaknya hanya digunakan satu kali saja dan dengan demikian dapat diuraikan.JavaScript (ES6),
369343 bytePenjelasan: String dipecah menjadi array karakter (Saya tidak jelas apakah input array karakter dapat diterima). Array kemudian diulang dan posisi semua kotak tanah berada. Garis berlari diberikan oleh persamaan
x - y = o
,x = p
,x + y = q
,y = r
,y - x = t
,-x = u
,-x - y = v
,-y = w
ditentukan sedemikian rupa sehingga memungkinkan parameter maksimum dipilih mana semua kebohongan tanah di luar garis. Ini memiliki efek melampirkan pulau dalam segi delapan. Koordinat sudut-sudut oktagon siap dihitung dari parameter dan sel-sel di tepi diisi. Array kemudian bergabung kembali ke dalam string. Alasan octagon mencukupi adalah sebagai berikut:Pertimbangkan sudut segi delapan. Di beberapa titik di sepanjang dua sisi jalan akan dibatasi oleh tanah karena kami membangun segi delapan untuk menyentuh tanah sedekat mungkin. Jika tidak ada tanah di sudut itu sendiri, jalan bisa mengambil rute alternatif seperti yang ditunjukkan di sebelah kanan, tetapi itu masih jumlah yang sama dari langkah ortogonal dan diagonal, sehingga jaraknya tidak berubah.
sumber
rest of arguments
parameter....p
di tempat yang berbeda.) Penghancuran adalah sesuatu yang lain (meskipun operator spread dapat digunakan dalam penghancuran).Python 3.5,
224, 263, 234218 byteGolf 16 byte lainnya dengan menghilangkan fungsi bersarang dan menjadikannya satu-liner.
Golf off 29 byte:
Input adalah string tunggal menggunakan '~' untuk lautan, 'X' untuk tanah, dan 'o' untuk batas. (Menggunakan 'X' menyimpan byte untuk '>' alih-alih '==')
Versi yang kurang golf dengan komentar:
sumber
C # 7 -
414369327 byteSunting : beralih ke loop 1D, komputasi,
i
danj
on the flySunting : metode input yang diubah, tabel lookup yang diciutkan, dan beralih ke batas awal yang terdefinisi dengan baik ... dan menghilangkan ruang tak berujung di loop luar terakhir untuk-loop
Cobalah secara Online
Program lengkap, mengambil input ke dalam standar, mencetak ke luar standar, penggunaan
#
,.
dano
. Untuk setiap sel, ia menghitung 'profil' (yang merupakan jarak lebih dari 8 arah (tampaknya menghitung kesembilan untuk kenyamanan, tetapi ini selalu0
), dan mencatat maksimum masing- masing sel . Ia kemudian menulis seluruh peta lagi, dan mengganti sel apa saja yang berada di batas dan tidak di luar dengan 'o' .Komentari yang dikomentari di bawah ini menjelaskan cara kerjanya.Sesuai jawaban saya untuk Menyelamatkan Angsa dari Kepunahan , ini menghasilkan oktagon terkecil (navigasi mengelilingi dengan wilayah terbesar) yang membatasi pulau.
Catatan : bahwa untuk sekali dalam hidup saya, saya menggunakan sesuatu dari dekade ini, dan kode ini membutuhkan C # 7 untuk dikompilasi. Jika Anda tidak memiliki C # 7, ada satu baris yang perlu diganti, yang ditandai dengan jelas dalam kode.
Contoh penggunaan dan output:
Kode yang diformat dan dikomentari:
sumber