Given  a width  and  a block  of
text containing possible hyphen-
ation points,  format it  fully-
justified (in monospace).

W pełni uzasadniony oznacza, że ​​jest wyrównany do lewej i prawej strony i jest osiągany przez zwiększenie odstępów między słowami, aż każda linia się dopasuje.

Związane z:

• Wyjustuj tekst, dodając spacje
• Wyrównaj tekst do bloku
• I w pewnym sensie można to uznać za kolejny krok w przetwarzaniu tekstu nr 1: dzielenie wyrazów (który wydaje się nigdy nie został opublikowany).

Wkład

Możesz pobierać dane w dowolnym formacie. Dostaniesz:

• Docelowa szerokość (w znakach), w zakresie 5-100 (włącznie);
• Blok tekstu zawierający możliwe słowa z łącznikami. Może to być ciąg oddzielony spacją, tablica słów lub tablica fragmentów słów (lub dowolna inna reprezentacja danych, której pragniesz).

Typowe dane wejściowe mogą być:

Width: 25
Text:  There's no bu-si-ne-ss lik-e s-h-o-w busine-ss, n-o bus-iness I know.

Gdzie łączniki oznaczają możliwe punkty dzielenia wyrazów, a spacje oznaczają granice słów. Możliwa alternatywna reprezentacja tekstu:

[["There's"], ["no"], ["bu", "si", "ne", "ss"], ["lik", "e"], (etc.)]

Wydajność

Tekst wejściowy ze spacjami dodanymi między słowami, nowymi liniami na szerokości kolumny i punktami dzielenia zaznaczonymi w celu pełnego wyrównania do szerokości kolumny. W przypadku funkcji zamiast tablicy rozdzielającej nowy wiersz można zwrócić tablicę ciągów (po jednym dla każdej linii).

Możliwe wyjście dla powyższych danych wejściowych może być:

There's no  business like
show  business,  no  bus-
iness I know.

Zauważ, że wszystkie myślniki zostały usunięte z wyjątkiem tego w ostatnim „bus-iness”, który jest utrzymywany, aby pokazać, że słowo zawija się do następnego wiersza, i został wybrany, aby drugi wiersz zawierał jak najwięcej tekstu.

Zasady

• W każdym wierszu liczba spacji między słowami nie może się różnić o więcej niż 1, ale w przypadku wstawienia dodatkowych spacji zależy od Ciebie:

  hello hi foo     bar    <-- not permitted (1,1,5)
  hello  hi foo    bar    <-- not permitted (2,1,4)
  hello  hi  foo   bar    <-- OK (2,2,3)
  hello  hi   foo  bar    <-- OK (2,3,2)
  hello   hi  foo  bar    <-- OK (3,2,2)
  

• Żadna linia nie może zaczynać się ani kończyć spacjami (z wyjątkiem ostatniej linii, która może kończyć się spacjami).

• Ostatni wiersz powinien być wyrównany do lewej strony, zawierający pojedyncze spacje między każdym słowem. W razie potrzeby może następować dowolna biała spacja / nowa linia, ale nie jest to wymagane.

• Słowa będą się składać z AZ, az, 0-9 i prostej interpunkcji ( .,'()&)

• Możesz założyć, że żaden fragment słowa nie będzie dłuższy niż szerokość docelowa i zawsze będzie możliwe wypełnienie wierszy zgodnie z regułami (tj. W każdym wierszu będą znajdować się co najmniej 2 fragmenty słów lub 1 fragment słowa, który wypełnia linię doskonale)

• Musisz wybrać punkty dzielenia wyrazów, które maksymalizują liczbę znaków słów we wcześniejszych wierszach (tzn. Słowa muszą być zachłannie konsumowane przez linie), na przykład:

  This is an input stri-ng with hyph-en-at-ion poi-nts.
  
  This     is     an     input    stri-      <-- not permitted
  ng with hyphenation points.
  
  This  is an  input string  with hyph-      <-- not permitted
  enation points.
  
  This is an input  string with hyphen-      <-- OK
  ation points.
  

• Najkrótszy kod w bajtach wygrywa

Przykłady

Width: 20
Text:  The q-uick brown fox ju-mp-s ove-r t-h-e lazy dog.

The quick  brown fox
jumps over the  lazy
dog.

Width: 32
Text: Given a width and a block of text cont-ain-ing pos-sible hyphen-ation points, for-mat it ful-ly-just-ified (in mono-space).

Given  a width  and  a block  of
text containing possible hyphen-
ation points,  format it  fully-
justified (in monospace).

Width: 80
Text:  Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.

Programming Puzzles &  Code Golf  is a question and answer  site for programming
puzzle enthusiasts  and code golfers.  It's built and run  by you as part of the
Stack Exchange network  of Q&A sites. With your help,  we're working together to
build a library of programming puzzles and their solutions.

Width: 20
Text:  Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.

Programming  Puzzles
&  Code  Golf  is  a
question and  answer
site for programming
puzzle   enthusiasts
and  code   golfers.
It's  built  and run
by  you  as  part of
the  Stack  Exchange
network    of    Q&A
sites.   With   your
help,  we're working
together to  build a
library of  program-
ming   puzzles   and
their solutions.

Width: 5
Text:  a b c d e f g h i j k l mm nn oo p-p qq rr ss t u vv ww x yy z

a b c
d e f
g h i
j k l
mm nn
oo pp
qq rr
ss  t
u  vv
ww  x
yy z

Width: 10
Text:  It's the bl-ack be-ast of Araghhhhh-hhh-h-hhh-h-h-h-hh!

It's   the
black  be-
ast     of
Araghhhhh-
hhhhhhhhh-
hhh!

JavaScript (ES6), 218 bajtów

w=>s=>s.map((c,i)=>c.map((p,j)=>(k+p)[l="length"]-w-(b=!i|j>0)+(j<c[l]-1)<0?k+=b?p:" "+p:(Array(w-k[l]-b).fill(h=k.split` `).map((_,i)=>h[i%(h[l]-1)]+=" "),o.push(h.join` `+(b?"-":"")),k=p)),o=[],k="")&&o.join`
`+`
`+k

Bierze argumenty w curry syntax ( f(width)(text)), a wprowadzanie tekstu jest w formacie podwójnej tablicy opisanym w wyzwaniu. Ciągi są konwertowane na ten format przez .split` `.map(a=>a.split`-`)). Ponadto nowe linie są dosłowne nowe linie w ciągach szablonów.

Nie grał w golfa i przestawiał

width=>string=> {
    out=[];
    line="";
    string.map((word,i)=> {
        word.map((part,j)=> {

            noSpaceBefore = i==0 || j>0;
            if ((line+part).length - width - noSpaceBefore + (j<word.length-1) < 0) {
                line += noSpaceBefore ? part : " "+part;
            }
            else {
                words=line.split` `;
                Array(width - line.length - noSpaceBefore).fill()
                    .map((_,i) => words[i % (words.length-1)] += " ");
                out.push(words.join(" ") + (noSpaceBefore? "-" : ""));
                line=part;
            }
        });
    });
    return out.join("\n") + "\n"+line
}

Chodziło o to, aby przejść przez każdą część całego łańcucha i zbudować każdą linię po jednej części na raz. Po zakończeniu linii zwiększa odstępy między wyrazami od lewej do prawej, aż zostaną wstawione wszystkie dodatkowe spacje.

Test Snippet

f=
w=>s=>s.map((c,i)=>c.map((p,j)=>(k+p)[l="length"]-w-(b=!i|j>0)+(j<c[l]-1)<0?k+=b?p:" "+p:(Array(w-k[l]-b).fill(h=k.split` `).map((_,i)=>h[i%(h[l]-1)]+=" "),o.push(h.join` `+(b?"-":"")),k=p)),o=[],k="")&&o.join`
`+`
`+k

<style>*{font-family:Consolas,monospace;}</style>
<div oninput="O.innerHTML=f(+W.value)(S.value.split` `.map(a=>a.split`-`))">
Width: <input type="number" size="3" min="5" max="100" id="W">
Tests: <select id="T" style="width:20em" oninput="let x=T.value.indexOf(','),s=T.value;W.value=s.slice(0,x);S.value=s.slice(x+2)"><option></option><option>20, The q-uick brown fox ju-mp-s ove-r t-h-e lazy dog.</option><option>32, Given a width and a block of text cont-ain-ing pos-sible hyphen-ation points, for-mat it ful-ly-just-ified (in mono-space).</option><option>80, Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.</option><option>20, Pro-gram-ming Puz-zles & Code Golf is a ques-tion and ans-wer site for pro-gram-ming puz-zle enth-usi-asts and code golf-ers. It's built and run by you as part of the St-ack Exch-ange net-work of Q&A sites. With your help, we're work-ing to-g-et-her to build a lib-rary of pro-gram-ming puz-zles and their sol-ut-ions.</option><option>5, a b c d e f g h i j k l mm nn oo p-p qq rr ss t u vv ww x yy z</option><option>10, It's the bl-ack be-ast of Araghhhhh-hhh-h-hhh-h-h-h-hh</option></select><br>
Text: &nbsp;<textarea id="S" cols="55" rows="4"></textarea>
</div>
<pre id="O" style="border: 1px solid black;display:inline-block;"></pre>

GNU sed -r, 621 bajtów

Pobiera dane wejściowe jako dwa wiersze: szerokość jako liczba jednoargumentowa jako pierwsza, a łańcuch jako druga.

Jestem pewien, że można by grać w golfa o wiele więcej, ale wrzuciłem już za dużo czasu.

x;N
G
s/\n/!@/
:
/@\n/bZ
s/-!(.*)@ /\1 !@/
s/!(.*[- ])(@.*1)$/\1!\2/
s/@(.)(.*)1$/\1@\2/
s/-!(.*-)(@.*)\n$/\1!\2\n1/
s/(\n!@) /\1/
s/-!(.* )(@.*)\n$/\1!\2\n1/
s/-!(.*-)(@.*1)$/\1!\21/
s/!(.*)-@([^ ]) /\1\2!@ /
t
s/ !@(.*)\n$/\n!@\1#/
s/!(.*-)@(.*)\n$/\1\n!@\2#/
s/!(.*)(@ | @)(.*)\n$/\1\n!@\3#/
s/-!(.*[^-])@([^ ]) (.*)\n$/\1\2\n!@\3#/
s/!(.+)@([^ ].*)\n$/\n!@\1\2#/
/#|!@.*\n$/{s/#|\n$//;G;b}
:Z
s/-?!|@.*//g
s/ \n/\n/g
s/^/%/
:B
G
/%.*\n.+\n/!bQ
:C
s/%([^\n])(.*)1$/\1%\2/
tC
s/([^\n]+)%\n/%\1\n/
:D
s/%([^ \n]* )(.*)1$/\1 %\2/
tD
s/(^|\n)([^\n]+)%(.*1)$/\1%\2\3/
tD
s/%([^\n]*)\n(.*)\n$/\1\n%\2/
tB
:Q
s/%(.*)\n1*$/\1/

Wypróbuj online!

Wyjaśnienie

Program działa w dwóch fazach: 1. Podziel i 2. Uzasadnij. Poniżej załóżmy, że nasz wkład to:

111111111111
I re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.

Ustawiać

Najpierw czytamy dane wejściowe, przenosząc pierwszy wiersz (szerokość jako liczba jednoczęściowa) do przestrzeni wstrzymania ( x), a następnie dołączając następny wiersz ( N), a następnie kopię szerokości z przestrzeni wstrzymania ( G) do przestrzeni wzorców. Ponieważ Npozostawiło nam przewagę \n, zastępujemy go !@, którego użyjemy jako kursorów w fazie 1.

x;N
G
s/\n/!@/

Teraz zawartość przestrzeni wstrzymania jest 1111111111111(i nie będzie się odtąd zmieniać), a przestrzeń wzorca jest (w formacie polecenia sed „drukuj jednoznacznie” l):

!@I re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n111111111111$

Faza 1

W fazie 1 główny @kursor przesuwa się o jeden znak na raz, a dla każdego znaku a 1jest usuwany z „licznika” na końcu obszaru wzorów. Innymi słowy @foo\n111$, f@oo\n11$, fo@o\n1$, itd.

Te !szlaki kursora tył @kursora, oznakowanie miejsc mogliśmy przełamać jeśli licznik osiągnie 0 w środku linii. Kilka rund wyglądałoby tak:

!@I re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n111111111111$
!I@ re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n11111111111$
!I @re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111111111$

Oto rozpoznany przez nas wzór: spacja, po której następuje @kursor. Ponieważ licznik jest większy niż 0, przesuwamy znacznik przerwy, a następnie przesuwamy główny kursor:

I !@re-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111111111$
I !r@e-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n111111111$
I !re@-mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n11111111$
I !re-@mem-ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111111$

Oto kolejny wzorzec: -@i nadal mamy 7 w liczniku, więc ponownie przesuwamy kursor przerwania i kontynuujemy:

I re-!mem-@ber a time of cha-os, ru-ined dreams, this was-ted land.\n111$

Oto inny wzorzec: łącznik bezpośrednio poprzedzający kursor podziału i inny poprzedzający główny kursor. Usuwamy pierwszy łącznik, przesuwamy kursor przerwania, a ponieważ usunęliśmy znak, dodajemy 1 do licznika.

I remem-!@ber a time of cha-os, ru-ined dreams, this was-ted land.\n1111$

Przesuwamy główny kursor:

I remem-!ber@ a time of cha-os, ru-ined dreams, this was-ted land.\n1$

Podobnie jak poprzednio, ale tym razem główny kursor poprzedza spację, a nie myślnik. Usuwamy łącznik, ale ponieważ przesuwamy również główny kursor, nie zwiększamy ani nie zmniejszamy licznika.

I remember !@a time of cha-os, ru-ined dreams, this was-ted land.\n1$
I remember !a@ time of cha-os, ru-ined dreams, this was-ted land.\n$

Wreszcie nasz licznik osiągnął zero. Ponieważ znak za kursorem głównym jest spacją, wstawiamy nowy wiersz i umieszczamy oba kursory zaraz po nim. Następnie uzupełniamy licznik ( G) i zaczynamy od nowa.

I remember a\n!@ time of cha-os, ru-ined dreams, this was-ted land.\n111111111111$

Faza 1 trwa, przesuwając kursory i dopasowując różne wzory, aż @kursor dotrze do końca łańcucha.

# Phase 1
:
  # End of string; branch to :Z (end of phase 1)
  /@\n/bZ

  # Match -!.*@_
  s/-!(.*)@ /\1 !@/

  # Match [-_]@ and >0
  s/!(.*[- ])(@.*1)$/\1!\2/

  # Advance cursor
  s/@(.)(.*)1$/\1@\2/

  # Match -!.*-@ and 0; add 1
  s/-!(.*-)(@.*)\n$/\1!\2\n1/

  # Match \n!@_
  s/(\n!@) /\1/

  # Match -!.*_@ and 0; add 1
  s/-!(.* )(@.*)\n$/\1!\2\n1/

  # Match -!.*-@ and >0; add 1
  s/-!(.*-)(@.*1)$/\1!\21/

  # Match -@[^_]_
  s/!(.*)-@([^ ]) /\1\2!@ /

  # If there were any matches, branch to `:`
  t

  # Match _!@ and 0
  s/ !@(.*)\n$/\n!@\1#/

  # Match -@ and 0
  s/!(.*-)@(.*)\n$/\1\n!@\2#/

  # Match @_|_@ and 0
  s/!(.*)(@ | @)(.*)\n$/\1\n!@\3#/

  # Match -!.*[^-]@[^_]_ and 0
  s/-!(.*[^-])@([^ ]) (.*)\n$/\1\2\n!@\3#/

  # Match !.+@[^_] and 0
  s/!(.+)@([^ ].*)\n$/\n!@\1\2#/

  # Match marked line (#) or !@ and 0
  /#|!@.*\n$/{
    # Remove mark; append width and branch to `:`
    s/#|\n$//
    G
    b
  }

:Z

# Cleanup
s/-?!|@.*//g
s/ \n/\n/g

Pod koniec fazy 1 nasza przestrzeń wzorów wygląda następująco:

I remember a\ntime of cha-\nos, ruined\ndreams, this\nwasted land.

Lub:

I remember a
time of cha-
os, ruined
dreams, this
wasted land.

Faza 2

W fazie 2 używamy %jako kursora i używamy licznika w podobny sposób, zaczynając w ten sposób:

%I remember a\ntime of cha-\nos, ruined\ndreams, this\nwasted land.\n111111111111$

Najpierw liczymy znaki w pierwszym wierszu, przesuwając kursor i usuwając 1s z licznika, po czym mamy;

I remember a%\ntime of cha-\nos, ruined\ndreams, this\nwasted land.\n$

Ponieważ licznik wynosi 0, nie robimy nic więcej na tej linii. Drugi wiersz ma również tę samą liczbę znaków co licznik, więc przejdźmy do trzeciego wiersza:

I remember a\ntime of cha-\nos, ruined%\ndreams, this\nwasted land.\n11$

Licznik jest większy niż 0, więc przesuwamy kursor z powrotem na początek linii. Następnie znajdujemy pierwszy ciąg spacji i dodajemy spację, zmniejszając licznik.

I remember a\ntime of cha-\nos, % ruined\ndreams, this\nwasted land.\n1$

Licznik jest większy niż 0; ponieważ kursor znajduje się już w ostatnim (jedynym) przebiegu spacji w linii, przenosimy go z powrotem na początek linii i robimy to ponownie:

I remember a\ntime of cha-\nos,  % ruined\ndreams, this\nwasted land.\n$

Teraz licznik wynosi 0, więc przesuwamy kursor na początek następnego wiersza. Powtarzamy to dla każdej linii oprócz ostatniej. To koniec fazy 2 i koniec programu! Ostateczny wynik to:

I remember a
time of cha-
os,   ruined
dreams, this
wasted land.

# Phase 2
# Insert cursor
s/^/%/
:B
  # Append counter from hold space
  G
  # This is the last line; branch to :Q (end of phase 1)
  /%.*\n.+\n/!bQ

  :C
    # Count characters
    s/%([^\n])(.*)1$/\1%\2/
    tC

  # Move cursor to beginning of line
  s/([^\n]+)%\n/%\1\n/

  :D
    # Add one to each space on the line as long as counter is >0
    s/%([^ \n]* )(.*)1$/\1 %\2/
    tD

    # Counter is still >0; go back to beginning of line
    s/(^|\n)([^\n]+)%(.*1)$/\1%\2\3/
    tD

    # Counter is 0; move cursor to next line and branch to :B
    s/%([^\n]*)\n(.*)\n$/\1\n%\2/
    tB

:Q

# Remove cursor, any remaining 1s
s/%(.*)\n1*$/\1/

JavaScript (ES6), 147 bajtów

Pobiera dane wejściowe jako (width)(text).

w=>F=(s,p=S=' ')=>(g=([c,...b],o='',h=c=='-')=>c?o[w-1]?c==S&&o+`
`+F(b):o[w+~h]?o+c+`
`+F(b):c>S?g(b,h?o:o+c):g(b,o+p)||g(b,o+p+c):o)(s)||F(s,p+S)

Wypróbuj online!

Skomentował

w =>                              // w = requested width
  F = (                           // F is a recursive function taking:
    s,                            //   s = either the input string (first iteration) or an
                                  //       array of remaining characters (next iterations)
    p =                           //   p = current space padding
    S = ' '                       //   S = space character
  ) => (                          //
    g = (                         // g is a recursive function taking:
      [c,                         //   c   = next character
          ...b],                  //   b[] = array of remaining characters
      o = '',                     //   o   = output for the current line
      h = c == '-'                //   h   = flag set if c is a hyphen
    ) =>                          //
      c ?                         // if c is defined:
        o[w - 1] ?                //   if the line is full:
          c == S &&               //     fail if c is not a space
          o + `\n` + F(b)         //     otherwise, append o + a linefeed and process the
                                  //     next line
        :                         //   else:
          o[w + ~h] ?             //     if this is the last character and c is a hyphen:
            o + c + `\n` + F(b)   //       append o + c + a linefeed and process the next
                                  //       line
          :                       //     else, we process the next character:
            c > S ?               //       if c is not a space:
              g(b, h ? o : o + c) //         append c if it's not a hyphen
            :                     //       else:
              g(b, o + p) ||      //         append either the current space padding
              g(b, o + p + c)     //         or the current padding and one extra space
      :                           // else:
        o                         //   success: return o
  )(s)                            // initial call to g() with s
  || F(s, p + S)                  // in case of failure, try again with a larger padding

APL (Dyalog Unicode) , 129 123 121 118 111 109 107 104 100 95 bajtów ^SBCS

{⊃⌽m←⍺≥-⌿c⍪+\⊢⌿c←' -'∘.≠⍵:⊂⍵/⍨⊢⌿c⋄(⊂∊l⊣l[(⍺-≢l)⍴⍸' '=l],←⊃0⍴l←⍵/⍨n×⊣⌿c⊖⍨1⌽n),⍺∇⍵/⍨~n←⌽∨\⌽m>×⌿c}

Wypróbuj online!

Stax , 51 50 bajtów

éS┴k╖♀╡¶┐'▼jÆD╨◙♠ß╒└╧rî{♀EÜ╢a┌ùLiƒ7ÉøΩS╜╪åⁿM◙┴,○9H

Uruchom i debuguj

Python 2 , 343 bajty

W,T=input()
T+=' '
L,l=[],len
while T:
 p,r=0,''
 for i in range(l(T)):
  s=T[:i].replace('-','')
  if'-'==T[i]:s+='-'
  if T[i]in' -'and W-l(s)>=0:p,r=i,s
 R=r.split()
 if R:
  d,k=W-l(''.join(R)),0
  for j in range(d):
   R[k]+=' '
   k+=1
   if k==l(R)-1:k=0
  L+=[''.join(R)]
  T=T[p+1:]
print'\n'.join(L[:-1])
print' '.join(L[-1].split())

Wypróbuj online!

The  input  is a block of text
containing possibly hyphenated
words.  For  each space/hyphen
position  p  the code computes
l(p)  the  length  of the line
induced  by  slipping the text
to this space/hyphen. Then the
code choses the position p for
which  the  length l(p) is the
closest  to  the given width W
(and  l(p)<=W).  If l(p)<W the
code  adds spaces  fairly  in-
between  the  words to achieve
the length W.