Ini adalah yang kedua dari serangkaian tantangan Island Golf. Tantangan sebelumnya
Dua pertapa telah tiba di pulau terpencil. Karena mereka datang mencari kesendirian, mereka ingin hidup sejauh mungkin dari satu sama lain. Di mana mereka harus membangun gubuk mereka untuk memaksimalkan jarak berjalan di antara mereka?
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.
, tetapi Anda dapat mengganti dua karakter berbeda yang Anda inginkan.
...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........
Akan selalu ada setidaknya dua tegel 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 akan terhubung secara diagonal: yaitu, Anda tidak akan pernah melihat sesuatu seperti itu
....
.#..
..#.
....
Keluaran
Kode Anda harus menampilkan kisi yang sama, dengan dua lokasi pondok ditandai di atasnya. Pada contoh di bawah ini, lokasi pondok ditandai dengan X, tetapi Anda dapat mengganti karakter apa pun asalkan berbeda dengan karakter tanah dan air Anda.
Lokasi pondok harus dua ubin tanah, dipilih untuk memaksimalkan jarak berjalan di antara mereka. Kami mendefinisikan jarak berjalan sebagai panjang jalur terpendek, seluruhnya di darat, antara dua titik. Ubin tanah dianggap berdekatan secara horizontal atau vertikal, tetapi tidak secara diagonal.
Solusi yang memungkinkan untuk pulau di atas:
...........
...X#......
..#####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........
Jarak berjalan antara dua titik ini adalah 11, yang merupakan jarak terbesar antara dua titik di pulau ini. Ada solusi lain jarak-11:
...........
...##......
..X####....
..#######..
.#########.
...#######.
...#####.X.
....####...
...........
Detail
Solusi Anda mungkin merupakan program atau fungsi lengkap . Salah satu metode input dan output default yang dapat diterima.
Input dan output Anda dapat berupa string multiline, daftar string, atau array 2D / daftar karakter yang bersarang / string karakter tunggal. Output Anda mungkin (secara opsional) memiliki satu baris baru. Seperti disebutkan di atas, Anda dapat menggunakan tiga karakter berbeda sebagai pengganti #.X
(harap tentukan dalam kiriman Anda karakter mana yang Anda gunakan).
Uji kasus
A. Kepulauan dengan penempatan gubuk unik:
....
.##.
....
....
.XX.
....
......
......
..##..
...#..
......
......
......
......
..X#..
...X..
......
......
........
.#####..
.##..##.
.#..###.
.##..##.
........
........
.#####..
.##..##.
.#..###.
.#X..#X.
........
.........
.#####.#.
.#...#.#.
.#.###.#.
.#.....#.
.#######.
.........
.........
.#####.X.
.#...#.#.
.#.X##.#.
.#.....#.
.#######.
.........
B. Contoh pulau dengan beberapa solusi yang memungkinkan:
........
....##..
...####.
..###...
.#####..
.#####..
..##....
........
Output yang mungkin:
........
....#X..
...####.
..###...
.#####..
.X####..
..##....
........
........
....#X..
...####.
..###...
.#####..
.#####..
..X#....
........
........
....##..
...###X.
..###...
.#####..
.X####..
..##....
........
........
....##..
...###X.
..###...
.#####..
.#####..
..X#....
........
C. Kasus uji besar sebagai Intisari
Ini adalah kode-golf : kode terpendek dalam setiap bahasa menang.
Jawaban:
Python 3,
249246 byteDicukur 3 byte, terima kasih DLosc.
Input dan output adalah string tunggal, dengan '.', '@', Dan 'X' masing-masing mewakili air, pondok, dan tanah.
Versi sebelumnya:
Input adalah string tunggal, dengan '.' dan '#' masing-masing mewakili air dan tanah. 'X' mewakili gubuk di output.
Penjelasan:
Ini pada dasarnya melakukan pencarian pertama yang luas dari setiap titik awal yang memungkinkan pada saat yang sama. Menyimpan kamus, d, panjang lintasan yang dikunci oleh awal dan akhir lintasan, misalnya, d [(k, i)] adalah jarak dari k ke i. Kemudian beralihlah ke tombol dalam kamus, d, dan buat kamus baru, u, dengan jalur yang 1 unit lebih panjang dengan memindahkan titik akhir 1 unit ke N, S, E, W, misalnya, u [(k, i + 1)] = d [(k, i)] + 1. Jangan sertakan path yang sudah ada di d. Jika Anda tidak kosong, maka tambahkan path baru yang lebih panjang ke d dan ulangi. Ketika kamu kosong, itu berarti tidak ada lagi jalan yang bisa dibuat. Sekarang d berisi semua jalur yang mungkin dan panjangnya. Jadi itu hanya masalah mendapatkan kunci dengan jalur terpanjang.
Versi kurang golf, berkomentar:
sumber
C #, 387 byte
Mari bola bergulir ...
Cobalah secara Online
Program yang lengkap, dibaca dari STDIN, menulis ke STDOUT. Ini hanya melewati setiap sel, dan menjalankan BFS untuk menghitung sel terjauh, merekam keduanya jika itu adalah yang terjauh pada catatan. Tidak ada yang benar-benar terjadi, dan sedikit sekali yang bisa saya temukan untuk bermain golf.
Kode yang diformat dan dikomentari:
sumber