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

Полностью выровненный означает, что он выровнен по левому и правому краям и достигается путем увеличения расстояния между словами до тех пор, пока не совпадет каждая строка.

Связанный:

• Обоснуйте текст, добавив пробелы
• Выровнять текст по блоку
• И в некотором смысле это можно считать следующим шагом в Обработка текста № 1: переносы слов (который, кажется, никогда не был опубликован).

вход

Вы можете принять вход в любом формате, который вам нравится. Вам будет предоставлено:

• Целевая ширина (в символах), в диапазоне 5-100 (включительно);
• Блок текста, содержащий возможно дефисные слова. Это может быть строка, разделенная пробелом, массив слов или массив массивов фрагментов слов (или любое другое представление данных, которое вы пожелаете).

Типичный ввод может быть:

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

Где дефисы обозначают возможные точки переноса, а пробелы обозначают границы слов. Возможное альтернативное представление текста:

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

Выход

Входной текст с пробелами, добавленными между словами, символами новой строки по ширине столбца и точками переноса, выбранными для полного выравнивания по ширине столбца. Для функций массив строк (по одной на каждую строку) может быть возвращен вместо использования разделения новой строки.

Возможный вывод для вышеуказанного ввода может быть:

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

Обратите внимание, что все дефисы были удалены, кроме одного в последнем «bus-iness», которое используется, чтобы показать, что слово переносится на следующую строку, и было выбрано так, чтобы вторая строка содержала как можно больше текста.

правила

• В каждой строке количество пробелов между словами не может изменяться более чем на 1, но если вы вставляете лишние пробелы, это зависит от вас:

  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)
  

• Никакая строка не может начинаться или заканчиваться пробелами (кроме последней строки, которая может заканчиваться пробелами).

• Последняя строка должна быть выровнена по левому краю и содержать одинарные пробелы между каждым словом. За ним может следовать произвольный пробел / символ новой строки, если это необходимо, но это не обязательно.

• Слова будут состоять из AZ, az, 0-9 и простой пунктуации ( .,'()&)

• Можно предположить, что ни один фрагмент слова не будет длиннее целевой ширины, и всегда будет возможно заполнить строки в соответствии с правилами (т. Е. В каждой строке будет как минимум 2 фрагмента слова или 1 фрагмент слова, заполняющий строку в совершенстве)

• Вы должны выбрать точки переноса, которые максимизируют количество символов слова в более ранних строках (т.е. слова должны жадно потребляться строками), например:

  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.
  

• Самый короткий код в байтах выигрывает

Примеры

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 байт

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

Принимает аргументы в каррирующем синтаксисе ( f(width)(text)), а ввод текста осуществляется в формате двойного массива, описанного в задании. Строки конвертируются в этот формат через .split` `.map(a=>a.split`-`)). Кроме того, новые строки - это буквальные новые строки внутри строк шаблона.

Без игры в гольф и переставил

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
}

Идея состояла в том, чтобы пройти каждую часть всей строки и построить каждую строку по одной части за раз. После завершения строки увеличивается расстояние между словами слева направо, пока не будут помещены все лишние пробелы.

Тестовый фрагмент

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 байт

Принимает ввод в виде двух строк: ширину в качестве первого унарного числа и вторую строку.

Я уверен, что это может быть гораздо лучше, но я уже потратил слишком много времени на это.

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/

Попробуйте онлайн!

объяснение

Программа работает в два этапа: 1. Разделить и 2. Обоснуйте. Для ниже предположим, что наш вход:

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

Настроить

Сначала мы читаем ввод, перемещая первую строку (ширину как унарное число) в область удержания ( x), затем добавляя следующую строку ( N), а затем копируем ширину из области удержания ( G) в пространство образца. Так как Nоставил нам ведущий, \nмы заменим его !@, который мы будем использовать в качестве курсоров в Фазе 1.

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

Теперь содержимое пространства удержания равно 1111111111111(и не изменится впредь), а пространство образца - (в формате команды sed «print однозначно» l):

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

Фаза 1

На этапе 1 основной @курсор перемещается по одному символу за раз, и для каждого символа a 1удаляется из «счетчика» в конце пространства шаблона. Другими словами, @foo\n111$, f@oo\n11$, fo@o\n1$и т.д.

В !курсор Трассы позади @курсора, отмечая места , где мы могли бы сломаться , если счетчик достигает 0 в середине строки. Пара раундов будет выглядеть так:

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

Здесь есть образец, который мы распознаем: пробел, за которым сразу следует @курсор. Поскольку счетчик больше 0, мы продвигаем маркер разрыва, затем продолжаем продвигать основной курсор:

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$

Вот еще один шаблон: -@у нас все еще 7 в счетчике, поэтому мы снова перемещаем курсор разрыва и продолжаем двигаться вперед:

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

Вот другой шаблон: дефис, непосредственно предшествующий курсору разрыва, и другой, предшествующий основному курсору. Мы удаляем первый дефис, перемещаем курсор разрыва и, поскольку мы удалили символ, добавляем 1 к счетчику.

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

Мы продолжаем продвигать основной курсор:

I remem-!ber@ 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.\n1$
I remember !a@ time of cha-os, ru-ined dreams, this was-ted land.\n$

Наконец наш счетчик достиг нуля. Поскольку символ после основного курсора является пробелом, мы вставляем новую строку и ставим оба курсора сразу после нее. Затем мы пополняем счетчик ( G) и начинаем снова.

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

Фаза 1 продолжается, продвигая курсоры и сопоставляя различные шаблоны, пока @курсор не достигнет конца строки.

# 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

В конце фазы 1 наше пространство шаблонов выглядит так:

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

Или:

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

Фаза 2

На втором этапе мы используем %курсор и используем счетчик аналогичным образом, начиная примерно так:

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

Сначала мы подсчитываем символы в первой строке, перемещая курсор и удаляя 1 из счетчика, после чего имеем;

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

Поскольку счетчик равен 0, мы больше ничего не делаем в этой строке. Вторая строка также имеет то же количество символов, что и счетчик, поэтому давайте перейдем к третьей строке:

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

Счетчик больше 0, поэтому мы перемещаем курсор назад к началу строки. Затем мы находим первый пробел и добавляем пробел, уменьшая счетчик.

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

Счетчик больше 0; так как курсор уже находится в последнем (единственном) ряду пробелов в строке, мы перемещаем его обратно в начало строки и делаем это снова:

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

Теперь счетчик равен 0, поэтому мы перемещаем курсор в начало следующей строки. Мы повторяем это для каждой строки, кроме последней. Это конец фазы 2 и конец программы! Окончательный результат:

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 байт

Принимает вход как (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)

Попробуйте онлайн!

комментарии

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 байтов ^SBCS

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

Попробуйте онлайн!

Stax , 51 50 байт

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

Запустите и отладьте его

Python 2 , 343 байта

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

Попробуйте онлайн!

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.