Hintergrund

In der Typografie sind Flüsse visuelle Lücken in einem Textblock, die durch zufällige Ausrichtung von Räumen entstehen. Diese sind besonders ärgerlich, da Ihr Gehirn sie in der peripheren Sicht leichter zu erfassen scheint, was Ihre Augen ständig ablenkt.

Nehmen Sie als Beispiel den folgenden Textblock, wobei die Zeilen so unterbrochen sind, dass die Zeilenbreite 82 Zeichen nicht überschreitet :

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.

Im unteren rechten Teil gibt es einen Fluss, der sich über sechs Linien erstreckt, die ich im folgenden Block hervorgehoben habe:

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.

Wir können dies abschwächen, indem wir eine etwas andere Spaltenbreite wählen. Wenn wir beispielsweise denselben Text mit Zeilen von nicht mehr als 78 Zeichen gestalten , gibt es keinen Fluss, der länger als zwei Zeilen ist:

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.

Beachten Sie, dass wir für diese Frage nur Schriften mit einem einheitlichen Abstand betrachten, sodass Flüsse einfach vertikale Spalten von Räumen sind. Die Länge eines Flusses ist die Anzahl der Zeilen, die er überspannt.

_{Nebenbei: Wenn Sie an der Flusserkennung in proportionalen Schriftarten interessiert sind, gibt es einige interessante Beiträge im Netzwerk.}

Die Herausforderung

Sie erhalten eine Zeichenfolge mit druckbaren ASCII-Zeichen (Codepunkt 0x20 bis 0x7E) - dh eine einzelne Zeile. Drucken Sie diesen Text mit einer Zeilenbreite zwischen 70 und 90 Zeichen (einschließlich) aus, sodass die maximale Länge eines Flusses im Text minimiert wird. Wenn es mehrere Textbreiten mit derselben (minimalen) maximalen Flusslänge gibt, wählen Sie die schmalere Breite. Das obige Beispiel mit 78 Zeichen ist die richtige Ausgabe für diesen Text.

Um Zeilen umzubrechen, sollten Sie Leerzeichen (0x20) durch Zeilenumbrüche ersetzen, sodass die resultierenden Zeilen so viele Zeichen wie möglich enthalten, jedoch nicht mehr als die ausgewählte Textbreite. Beachten Sie, dass der resultierende Zeilenumbruch selbst nicht Teil dieser Anzahl ist. Beispielsweise Lorem[...]temporenthält der letzte Block oben 78 Zeichen, was auch der Breite des Texts entspricht.

Sie können davon ausgehen, dass die Eingabe keine aufeinander folgenden Leerzeichen und keine führenden oder nachfolgenden Leerzeichen enthält. Sie können auch davon ausgehen, dass kein Wort (aufeinanderfolgende Teilzeichenfolge von Nicht-Leerzeichen) mehr als 70 Zeichen enthält.

Sie können ein Programm oder eine Funktion schreiben, Eingaben über STDIN, ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis in STDOUT ausgeben.

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

CJam, 116 106 99 84 77 72 Bytes

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

Nimmt die einzeilige Eingabe und druckt die korrekte Ausgabe an STDOUT.

UPDATE : Viele Verbesserungen und überflüssige Schleifen wurden entfernt, indem alle Berechnungen in der Sortierschleife selbst durchgeführt wurden. Außerdem wurde ein Fehler in der Flusslängenberechnung behoben.

Erklärung bald (nachdem ich noch weiter Golf gespielt habe)

Probieren Sie es hier aus

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

Die nicht golfene Version:

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}

Erläuterung:

• (K⊂⍨' '=K←' ',⍵): Fügen Sie ein Leerzeichen vor ⍵und teilen Sie es ⍵auf. Jedes Wort behält den Raum bei, mit dem es beginnt.
• ∘{... }¨70+⍳21: mit diesem Wert für jede Zahl im Bereich [71, 91]: (Aufgrund der Art und Weise, wie die Wörter aufgeteilt werden, endet jede 'Zeile' am Anfang mit einem zusätzlichen Leerzeichen, das später entfernt wird. Der Bereich wird um verschoben ein, um den zusätzlichen Platz zu kompensieren.)
  • ×⍴⍺:: Wenn noch Worte übrig sind,
    • z←⍵>+\≢¨⍺: Ermitteln Sie die Länge für jedes Wort und berechnen Sie eine laufende Summe der Länge pro Wort. Markieren Sie 1alle Wörter, die zum Ausfüllen der nächsten Zeile verwendet werden können, und speichern Sie diese in z.
    • (⊂z/⍺),⍵∇⍨⍺⍨~z: nimm diese Wörter und verarbeite dann, was von der Liste übrig ist.
  • ⋄⍺: wenn nicht, kehre zurück ⍺(was jetzt leer ist).
• G←: Speichern Sie die Liste der Zeilenlisten in G(eine für jede mögliche Zeilenlänge).
• V←{... }¨G: Berechnen Sie für jede Möglichkeit die Länge des längsten Flusses und speichern Sie ihn in V:
  • +\↑≢¨¨⍵: Ermitteln Sie die Länge jedes Wortes (erneut) und bilden Sie eine Matrix aus den Längen. Berechnen Sie die laufende Summe für jede Zeile in den Zeilen der Matrix. (Daher wird das zusätzliche Leerzeichen am Anfang jeder Zeile ignoriert.)
  • 2≠⌿: Prüfen Sie für jede Spalte der Matrix, ob die aktuelle Länge der Linie an diesem Punkt nicht mit der Linie danach übereinstimmt. Wenn ja, gibt es dort keinen Fluss.
  • ⊂⍨¨↓⍉: Teilen Sie jede Spalte der Matrix für sich (auf dem 1s). Dies gibt eine Liste von Listen, wobei für jeden Fluss eine Liste vorhanden ist [1, 0, 0, ...], abhängig von der Länge des Flusses. Wenn es keinen Fluss gibt, wird die Liste sein [1].
  • ⌈/≢¨: Ermitteln Sie die Länge jedes Flusses und den maximalen Wert davon.
• ⊃G/⍨V=⌊/V: von G, wählen Sie das erste Element aus, für das die Länge des längsten Flusses für alle Elemente dem Minimum entspricht.
• {1↓∊⍵,3⊃⎕TC}¨: Füge für jede Zeile alle Wörter zusammen, entferne das erste Element (das zusätzliche Leerzeichen am Anfang) und füge eine neue Zeile am Ende hinzu.
• ∊: füge alle Zeilen zusammen.

Bash + Coreutils, 236 157 Bytes

Mit einem anderen Ansatz bearbeitet - viel kürzer als zuvor:

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<<<$@

Liest die Eingabezeichenfolge von der Befehlszeile.

Bei 3 verschachtelten Sortierungen schaudert es mich zu überlegen, wie komplex die O-Zeit dafür ist, aber das Beispiel ist auf meinem Computer in weniger als 10 Sekunden abgeschlossen.

Python, 314 Bytes

Vielen Dank an SP3000, grc und 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

Iterative Lösung, möglicherweise kürzer, wenn sie rekursiv gemacht wird

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)
}

Erklärt

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)
}

Test in der FireFox / FireBug-Konsole.

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

Ausgabe

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 Bytes

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)]))

Ungolfed-Version:

# 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)]))