tło

W typografii rzeki są wizualnymi lukami w bloku tekstu, które występują z powodu przypadkowego wyrównania przestrzeni. Są to szczególnie denerwujące, ponieważ mózg zdaje się łatwiej je wychwytywać w widzeniu peryferyjnym, które nieustannie rozprasza wzrok.

Jako przykład weźmy następujący blok tekstu, linie podzielone tak, aby szerokość linii nie przekraczała 82 znaków :

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.

W prawym dolnym rogu jest rzeka rozciągająca się na sześciu liniach, które podkreśliłem w następującym bloku:

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.

Możemy to złagodzić, wybierając nieco inną szerokość kolumny. Np. Jeśli układamy ten sam tekst za pomocą linii nie dłuższych niż 78 znaków , nie ma rzeki dłuższej niż dwie linie:

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.

Zauważ, że dla celów tego pytania rozważamy tylko czcionki o stałej szerokości, tak że rzeki są po prostu pionowymi kolumnami spacji. Długość rzeki to liczba linii, które obejmuje.

_{Poza tym: Jeśli interesuje Cię wykrywanie rzek w czcionkach proporcjonalnych, w sieci jest kilka interesujących postów .}

Wyzwanie

Otrzymałeś ciąg znaków ASCII do wydrukowania (punkt kodowy od 0x20 do 0x7E) - tj. Pojedynczy wiersz. Wydrukuj ten tekst, o szerokości linii od 70 do 90 znaków (włącznie), tak aby zminimalizować maksymalną długość dowolnej rzeki w tekście. Jeśli istnieje wiele szerokości tekstu o tej samej (minimalnej) maksymalnej długości rzeki, wybierz węższą szerokość. Powyższy przykład z 78 znakami jest poprawnym wyjściem dla tego tekstu.

Aby łamać linie, należy zastąpić znaki spacji (0x20) podziałami linii, tak aby linie wynikowe miały jak najwięcej znaków, ale nie więcej niż wybraną szerokość tekstu. Zauważ, że wynikowy podział linii sam w sobie nie jest częścią tej liczby. Na przykład w ostatnim bloku powyżej Lorem[...]temporzawiera 78 znaków, co jest również szerokością tekstu.

Możesz założyć, że dane wejściowe nie będą zawierać kolejnych spacji i nie będą mieć spacji wiodących ani końcowych. Możesz także założyć, że żadne słowo (kolejne podciągi spacji) nie będzie zawierało więcej niż 70 znaków.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN, argument wiersza poleceń lub argument funkcji i wypisując wynik do STDOUT.

To jest kod golfowy, więc wygrywa najkrótsza odpowiedź (w bajtach).

CJam, 116 106 99 84 77 72 bajtów

l:X;93,72>{:D;OOXS/{S+_2$+,D<{+}{@@);a+\}?}/a+}%{z'K*S/:!0a/1fb$W=}$0=N*

Pobiera wejście jednowierszowe i drukuje prawidłowe wyjście do STDOUT.

AKTUALIZACJA : Znacznie poprawiono i usunięto zbędne pętle, wykonując wszystkie obliczenia w samej pętli sortowania. Naprawiono także błąd w obliczaniu długości rzeki.

Wyjaśnienie wkrótce (po tym, jak jeszcze zagrałem w golfa)

Wypróbuj tutaj

Ruby 162 160 158 152 160 157 ( demo )

i=gets+' '
(69..s=r=89).map{|c|w=i.scan(/(.{1,#{c}}\S) /).flatten
m=(0..c).map{|i|w.map{|l|l[i]}+[?x]}.join.scan(/ +/).map(&:size).max
m<s&&(s=m;r=w)}
puts r

Wersja bez gry w golfa:

input = gets+' '

result = ''

(69..smallest_max=89).each{|w|
  #split text into words of at most w characters
  wrap = (input+' ').scan(/(.{1,#{w}}\S) /).flatten

  #transpose lines and find biggest "river"
  max_crt_river = (0..99).map{|i| wrap.map{|l|l[i]} }.flatten.join.scan(/ +/).max_by(&:size).size

  if max_crt_river < smallest_max
    smallest_max = max_crt_river
    result = wrap.join ?\n
  end
}
puts result

APL (105)

{∊{1↓∊⍵,3⊃⎕TC}¨⊃G/⍨V=⌊/V←{⌈/≢¨⊂⍨¨↓⍉2≠⌿+\↑≢¨¨⍵}¨G←(K⊂⍨' '=K←' ',⍵)∘{×⍴⍺:(⊂z/⍺),⍵∇⍨⍺/⍨~z←⍵>+\≢¨⍺⋄⍺}¨70+⍳21}

Wyjaśnienie:

• (K⊂⍨' '=K←' ',⍵): Dodaj spację przed ⍵, a następnie podziel ⍵na spacje. Każde słowo zachowuje miejsce, od którego zaczyna się.
• ∘{... }¨70+⍳21: z tą wartością dla każdej liczby w zakresie [71, 91]: (Ze względu na sposób podziału słów, każda „linia” kończy się dodatkową spacją na początku, która zostanie usunięta później. Zakres jest przesuwany o jeden, aby zrekompensować dodatkową przestrzeń.)
  • ×⍴⍺:: jeśli nadal pozostały słowa,
    • z←⍵>+\≢¨⍺: uzyskaj długość każdego słowa i obliczyć bieżącą sumę długości dla każdego słowa. Zaznacz 1wszystkie słowa, które można wypełnić, aby wypełnić następny wiersz, i zapisz je z.
    • (⊂z/⍺),⍵∇⍨⍺⍨~z: weź te słowa, a następnie przetworz resztę listy.
  • ⋄⍺: jeśli nie, zwróć ⍺(który jest teraz pusty).
• G←: zapisz listę list linii w G(jeden dla każdej możliwej długości linii).
• V←{... }¨G: dla każdej możliwości oblicz długość najdłuższej rzeki i zapisz ją w V:
  • +\↑≢¨¨⍵: uzyskaj długość każdego słowa (ponownie) i utwórz macierz z długości. Oblicz sumę bieżącą dla każdego wiersza w wierszach macierzy. (W związku z tym dodatkowe miejsce na początku każdej linii jest ignorowane).
  • 2≠⌿: dla każdej kolumny macierzy sprawdź, czy bieżąca długość linii w tym punkcie nie pasuje do linii po niej. Jeśli tak, to nie istnieje rzeka.
  • ⊂⍨¨↓⍉: podziel każdą kolumnę macierzy samodzielnie (na 1s). Daje to listę list, gdzie dla każdej rzeki będzie lista [1, 0, 0, ...], w zależności od długości rzeki. Jeśli nie ma rzeki, lista będzie [1].
  • ⌈/≢¨: uzyskaj długość każdej rzeki i uzyskaj jej maksymalną wartość.
• ⊃G/⍨V=⌊/V: z G, wybierz pierwszy element, dla którego długość najdłuższej rzeki jest równa minimum dla wszystkich elementów.
• {1↓∊⍵,3⊃⎕TC}¨: dla każdego wiersza połącz wszystkie słowa razem, usuń element pięści (dodatkowe miejsce od początku) i dodaj nowy wiersz na końcu.
• ∊: połącz wszystkie linie razem.

Bash + coreutils, 236 157 bajtów

Edytowane z innym podejściem - nieco krótszym niż wcześniej:

a=(`for i in {71..91};{
for((b=1;b++<i;));{
fold -s$i<<<$@|cut -b$b|uniq -c|sort -nr|grep -m1 "[0-9]  "
}|sort -nr|sed q
}|nl -v71|sort -nk2`)
fold -s$a<<<$@

Odczytuje ciąg wejściowy z wiersza poleceń.

Przy 3 rodzajach zagnieżdżonych wzdrygam się, aby pomyśleć o tym, jak duża jest złożoność czasu „O”, ale przykład kończy się na moim komputerze w niecałe 10 sekund.

Python, 314 bajtów

Ogromne podziękowania dla SP3000, grc i FryAmTheEggman:

b=range;x=len
def p(i):
 l=[];z=''
 for n in t:
  if x(z)+x(n)<=i:z+=n+' '
  else:l+=[z];z=n+' '
 return l+[z]*(z!=l[x(l)-1])
t=input().split();q=[]
for i in b(70,91):l=p(i);q+=[max(sum(x(l[k+1])>j<x(l[k])and l[k][j]is' '==l[k+1][j]for k in b(x(l)-1))for j in b(i))]
print(*p(q.index(min(q))+70),sep='\n')

JavaScript (ES6) 194 202

Iteracyjne rozwiązanie, może krótsze, jeśli zostanie rekurencyjne

F=s=>{
  for(m=1e6,b=' ',n=70;n<91;n++)
    l=b+'x'.repeat(n),x=r=q='',
    (s+l).split(b).map(w=>
      (t=l,l+=b+w)[n]&&(
        l=w,r=r?[...t].map((c,p)=>x<(v=c>b?0:-~r[p])?x=v:v,q+=t+'\n'):[]
      )
    ),x<m&&(o=q,m=x);
  alert(o)
}

Wyjaśniono

F=s=> {
  m = 1e9; // global max river length, start at high value
  for(n=70; n < 91; n++) // loop on line length
  {
    l=' '+'x'.repeat(n), // a too long first word, to force a split and start
    x=0, // current max river length
    q='', // current line splitted text
    r=0, // current river length for each column (start 0 to mark first loop)
    (s+l) // add a too long word to force a last split. Last and first row will not be managed
    .split(' ').map(w=> // repeat for each word 
      (
        t=l, // current partial row in t (first one will be dropped)
        (l += ' '+w)[n] // add word to partial row and check if too long
        &&
        (
          l = w, // start a new partial row with current word
          r=r? // update array r if not at first loop
          ( 
            q+=t+'\n', // current row + newline added to complete text 
            [...t].map((c,p)=>( // for each char c at position p in row t
              v = c != ' ' 
                ? 0 // if c is not space, reset river length at 0
                : -~r[p], // if c is space, increment river length
              x<v ? x=v : v // if current > max, update max
            ))
          ):[]  
        )  
      )
    )
    x < m && ( // if current max less than global max, save current text and current max
      o = q,
      m = x
    )
  }
  console.log(o,m)
}

Przetestuj w konsoli FireFox / FireBug.

F('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.')

Wynik

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.

Python 3, 329 bajtów

import re,itertools as s
def b(t,n):
 l=0;o=""
 for i in t.split():
  if l+len(i)>n:o=o[:-1]+'\n';l=0
  l+=len(i)+1;o+=i+' '
 return o
t=input();o={}
for n in range(90,69,-1):o[max([len(max(re.findall('\s+',x),default='')) for x in ["".join(i) for i in s.zip_longest(*b(t,n).split('\n'),fillvalue='')]])]=n
print(b(t,o[min(o)]))

Wersja bez golfa:

# Iterates over words until length > n, then replaces ' ' with '\n'
def b(t,n):
    l = 0
    o = ""
    for i in t.split():
        if l + len(i) > n:
            o = o[:-1] + '\n'
            l = 0
        l += len(i) + 1
        o += i + ' '
    return o

t = input()
o = {}
# range from 90 to 70, to add to dict in right order
for n in range(90,69,-1):
    # break text at length n and split text into lines
    temp = b(t,n).split('\n')
    # convert columns into rows
    temp = itertools.zip_longest(*temp, fillvalue='')
    # convert the char tuples to strings
    temp = ["".join(i) for i in temp]
    # findall runs of spaces, get longest run and get length
    temp = [len(max(re.findall('\s+',x),default='')) for x in temp]
    # add max river length as dict key, with line length as value
    o[max(temp)] = n

print(b(t,o[min(o)]))