Latar Belakang
Dalam tipografi, sungai adalah kesenjangan visual dalam blok teks, yang terjadi karena penyelarasan spasi secara kebetulan. Ini sangat menjengkelkan karena otak Anda tampaknya mengambilnya dengan lebih mudah dalam penglihatan tepi, yang terus-menerus mengganggu mata Anda.
Sebagai contoh, ambil blok teks berikut ini, garis-garis patah sehingga lebar garis tidak melebihi 82 karakter :
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui
officia deserunt mollit anim id est laborum. Lorem ipsum dolor sit amet,
consectetur adipisicing elit, sed do eismod tempor incididunt ut labore et dolore
maga aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris
nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in
voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint
occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id
est laborum.
Ada sungai yang membentang enam garis di bagian kanan bawah, yang saya soroti di blok berikut:
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute
irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla
pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui
officia deserunt mollit anim id est laborum. Lorem█ipsum dolor sit amet,
consectetur adipisicing elit, sed do eismod tempor█incididunt ut labore et dolore
maga aliqua. Ut enim ad minim veniam, quis nostrud█exercitation ullamco laboris
nisi ut aliquip ex ea commodo consequat. Duis aute█irure dolor in reprehenderit in
voluptate velit esse cillum dolore eu fugiat nulla█pariatur. Excepteur sint
occaecat cupidatat non proident, sunt in culpa qui█officia deserunt mollit anim id
est laborum.
Kami dapat mengurangi ini dengan memilih lebar kolom yang sedikit berbeda. Misalnya, jika kita tata letak teks yang sama menggunakan baris tidak lebih dari 78 karakter , tidak ada sungai lebih dari dua baris:
Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eismod tempor
incididunt ut labore et dolore maga aliqua. Ut enim ad minim veniam, quis
nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.
Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore
eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt
in culpa qui officia deserunt mollit anim id est laborum. Lorem ipsum dolor
sit amet, consectetur adipisicing elit, sed do eismod tempor incididunt ut
labore et dolore maga aliqua. Ut enim ad minim veniam, quis nostrud
exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis
aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu
fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in
culpa qui officia deserunt mollit anim id est laborum.
Perhatikan bahwa untuk keperluan pertanyaan ini, kami hanya mempertimbangkan font monospasi, sehingga sungai hanyalah kolom spasi vertikal. Panjang sungai adalah jumlah garis yang terbentang.
Selain itu: Jika Anda tertarik dalam deteksi sungai dalam font proporsional, ada beberapa posting menarik di sekitar jaringan.
Tantangan
Anda diberi serangkaian karakter ASCII yang dapat dicetak (titik kode 0x20 hingga 0x7E) - yaitu satu baris. Cetak teks ini, dengan lebar garis antara 70 dan 90 karakter (termasuk), sehingga panjang maksimum dari sungai mana pun dalam teks dapat diminimalkan. Jika ada beberapa lebar teks dengan panjang sungai maksimum yang sama (minimal), pilih lebar yang lebih sempit. Contoh di atas dengan 78 karakter adalah output yang benar untuk teks itu.
Untuk memecah garis, Anda harus mengganti karakter spasi (0x20) dengan jeda baris, sehingga garis yang dihasilkan memiliki karakter sebanyak mungkin, tetapi tidak lebih dari lebar teks yang dipilih. Perhatikan bahwa jeda baris yang dihasilkan itu sendiri bukan bagian dari penghitungan itu. Sebagai contoh, di blok terakhir di atas, Lorem[...]tempor
berisi 78 karakter, yang juga lebar teks.
Anda dapat berasumsi bahwa input tidak akan berisi spasi berurutan, dan tidak akan memiliki spasi di depan atau di belakang. Anda juga dapat mengasumsikan bahwa tidak ada kata (substring non-spasi berturut-turut) akan berisi lebih dari 70 karakter.
Anda dapat menulis program atau fungsi, mengambil input melalui STDIN, argumen baris perintah atau argumen fungsi dan mencetak hasilnya ke STDOUT.
Ini kode golf, jadi jawaban tersingkat (dalam byte) menang.
sumber
Jawaban:
CJam,
116 106 99 84 7772 byteMengambil input baris tunggal dan mencetak output yang benar ke STDOUT.
PEMBARUAN : Banyak ditingkatkan dan dihapus loop berlebihan dengan melakukan semua perhitungan dalam loop penyortiran itu sendiri. Juga memperbaiki bug dalam perhitungan panjang sungai.
Penjelasan segera (setelah saya golf lebih jauh)
Coba di sini
sumber
ea~
bukannyaX
setiap kali. Menghemat dua byte.Ruby
162 160 158 152 160 160157 ( demo )Versi tidak golf:
sumber
%r{...}
memungkinkan saya menggunakan interpolasi string. Saya baru saja mencoba21.times
, tetapi memiliki beberapa implikasi di jalan, dan saya belum berhasil mencapai solusi yang lebih pendek.APL (105)
Penjelasan:
(K⊂⍨' '=K←' ',⍵)
: Tambahkan spasi di depan⍵
, lalu pisah⍵
pada spasi. Setiap kata mempertahankan ruang yang dimulai.∘{
...}¨70+⍳21
: dengan nilai itu, untuk setiap angka dalam rentang[71, 91]
: (Karena cara kata-kata terpecah, masing-masing 'garis' berakhir dengan ruang ekstra di awal, yang akan dihapus kemudian. Rentang digeser oleh satu untuk mengimbangi ruang ekstra.)×⍴⍺:
: jika masih ada kata yang tersisa,z←⍵>+\≢¨⍺
: dapatkan panjang untuk setiap kata, dan hitung total panjangnya, per kata. Tandai dengan1
semua kata yang dapat diambil untuk mengisi baris berikutnya, dan simpan diz
.(⊂z/⍺),⍵∇⍨⍺⍨~z
: ambil kata-kata itu, lalu proseskan apa yang tersisa dari daftar.⋄⍺
: jika tidak, kembali⍺
(yang sekarang kosong).G←
: menyimpan daftar daftar garis dalamG
(satu untuk setiap panjang garis yang mungkin).V←{
...}¨G
: untuk setiap kemungkinan, hitung panjang sungai terpanjang dan simpan diV
:+\↑≢¨¨⍵
: dapatkan panjang setiap kata (lagi), dan buat matriks dari panjangnya. Hitung total yang berjalan untuk setiap baris pada baris matriks. (Dengan demikian, ruang ekstra di awal setiap baris diabaikan.)2≠⌿
: untuk setiap kolom matriks, lihat apakah panjang garis saat ini pada titik itu tidak cocok dengan garis setelahnya. Jika demikian, tidak ada sungai di sana.⊂⍨¨↓⍉
: pisahkan setiap kolom dari matriks dengan sendirinya (pada1
s). Ini memberikan daftar daftar, di mana untuk setiap sungai akan ada daftar[1, 0, 0, ...]
, tergantung pada panjang sungai. Jika tidak ada sungai, daftarnya akan ada[1]
.⌈/≢¨
: dapatkan panjang setiap sungai, dan dapatkan nilai maksimumnya.⊃G/⍨V=⌊/V
: fromG
, pilih item pertama dengan panjang sungai terpanjang sama dengan minimum untuk semua item.{1↓∊⍵,3⊃⎕TC}¨
: untuk setiap baris, gabungkan semua kata bersama, hapus item pertama (ruang ekstra dari awal), dan tambahkan baris baru ke akhir.∊
: gabungkan semua baris bersama.sumber
Bash + coreutils,
236157 byteDiedit dengan pendekatan yang berbeda - sedikit lebih pendek dari sebelumnya:
Membaca string input dari baris perintah.
Dengan 3 jenis bersarang, saya ngeri memikirkan apa kompleksitas waktu-O besar untuk ini, tetapi tidak menyelesaikan contoh di bawah 10 detik pada mesin saya.
sumber
Python, 314 byte
Terima kasih banyak untuk SP3000, grc, dan FryAmTheEggman:
sumber
JavaScript (ES6) 194
202Solusi berulang, mungkin lebih pendek jika dibuat rekursif
Dijelaskan
Uji di konsol FireFox / FireBug.
Keluaran
sumber
Python 3, 329 byte
Versi tidak disatukan:
sumber