fundo
Na tipografia, os rios são lacunas visuais em um bloco de texto, que ocorrem devido ao alinhamento coincidente de espaços. Isso é particularmente irritante, pois seu cérebro parece captá-los mais facilmente na visão periférica, que constantemente distrai os olhos.
Como exemplo, considere o seguinte bloco de texto, linhas quebradas para que a largura da linha não exceda 82 caracteres :
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.
Há um rio que mede seis linhas na parte inferior direita, que destaquei no bloco a seguir:
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.
Podemos atenuar isso escolhendo uma largura de coluna ligeiramente diferente. Por exemplo, se traçarmos o mesmo texto usando linhas com mais de 78 caracteres , não haverá rio com mais de duas linhas:
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.
Observe que, para o propósito desta pergunta, estamos considerando apenas fontes monoespaçadas, de modo que os rios sejam simplesmente colunas verticais de espaços. O comprimento de um rio é o número de linhas que ele abrange.
Além disso: se você é interessante na detecção de rios em fontes proporcionais, existem algumas postagens interessantes na rede.
O desafio
Você recebe uma sequência de caracteres ASCII imprimíveis (pontos de código 0x20 a 0x7E) - ou seja, uma única linha. Imprima este texto, com uma largura de linha entre 70 e 90 caracteres (inclusive), de modo que o comprimento máximo de qualquer rio no texto seja minimizado. Se houver várias larguras de texto com o mesmo comprimento mínimo (mínimo) do rio, escolha a largura mais estreita. O exemplo acima com 78 caracteres é a saída correta para esse texto.
Para quebrar linhas, você deve substituir caracteres de espaço (0x20) por quebras de linha, para que as linhas resultantes tenham o máximo de caracteres possível, mas não mais do que a largura do texto escolhido. Observe que a quebra de linha resultante em si não faz parte dessa contagem. Como exemplo, no último bloco acima, Lorem[...]tempor
contém 78 caracteres, que também é a largura do texto.
Você pode assumir que a entrada não conterá espaços consecutivos e não terá espaços à esquerda ou à direita. Você também pode assumir que nenhuma palavra (substring consecutivo de não-espaços) conterá mais de 70 caracteres.
Você pode escrever um programa ou função, inserindo STDIN, argumento da linha de comando ou argumento da função e imprimindo o resultado em STDOUT.
Isso é código de golfe, então a resposta mais curta (em bytes) vence.
fonte
Respostas:
CJam,
116 106 99 84 7772 bytesPega a entrada de linha única e imprime a saída correta em STDOUT.
UPDATE : Aprimorou muito e removeu loops redundantes fazendo todos os cálculos no próprio loop de classificação. Também foi corrigido um erro no cálculo do comprimento do rio.
Explicação em breve (depois de eu jogar ainda mais)
Experimente aqui
fonte
ea~
vez deX
cada vez. Salva dois bytes.Ruby
162 160 158 152 160 160157 ( demo )A versão sem golfe:
fonte
%r{...}
me permite usar a interpolação de strings. Eu apenas tentei21.times
, mas isso tem mais implicações no futuro e não consegui chegar a uma solução mais curta.APL (105)
Explicação:
(K⊂⍨' '=K←' ',⍵)
: Adicione um espaço na frente⍵
e depois divida⍵
nos espaços. Cada palavra mantém o espaço com o qual começa.∘{
...}¨70+⍳21
: com esse valor, para cada número no intervalo[71, 91]
: (devido à maneira como as palavras são divididas, cada 'linha' termina com um espaço extra no início, que será removido posteriormente. O intervalo é alterado por um para compensar o espaço extra.)×⍴⍺:
: se ainda houver palavras,z←⍵>+\≢¨⍺
: obtenha o comprimento de cada palavra e calcule um total em execução do comprimento, por palavra. Marque com1
todas as palavras que podem ser usadas para preencher a próxima linha e armazene-az
.(⊂z/⍺),⍵∇⍨⍺⍨~z
: pegue essas palavras e processe o que resta da lista.⋄⍺
: caso contrário, retorne⍺
(que agora está vazio).G←
: armazena a lista de listas de linhas emG
(uma para cada comprimento de linha possível).V←{
...}¨G
: para cada possibilidade, calcule o comprimento do rio mais longo e armazene-o emV
:+\↑≢¨¨⍵
: obtenha o comprimento de cada palavra (novamente) e faça uma matriz com os comprimentos. Calcule o total em execução para cada linha nas linhas da matriz. (Portanto, o espaço extra no início de cada linha é ignorado.)2≠⌿
: para cada coluna da matriz, veja se o comprimento atual da linha nesse ponto não corresponde à linha após ela. Nesse caso, não há rio lá.⊂⍨¨↓⍉
: divida cada coluna da matriz sozinha (no (1
s)). Isso fornece uma lista de listas, onde para cada rio haverá uma lista[1, 0, 0, ...]
, dependendo da extensão do rio. Se não houver rio, a lista será[1]
.⌈/≢¨
: obtenha o comprimento de cada rio e obtenha o valor máximo disso.⊃G/⍨V=⌊/V
: fromG
, selecione o primeiro item para o qual o comprimento do rio mais longo é igual ao mínimo para todos os itens.{1↓∊⍵,3⊃⎕TC}¨
: para cada linha, junte todas as palavras, remova o primeiro item (o espaço extra desde o início) e adicione uma nova linha ao final.∊
: junte todas as linhas.fonte
Bash + coreutils,
236157 bytesEditado com uma abordagem diferente - um pouco mais curta do que antes:
Lê a sequência de entrada da linha de comando.
Com três tipos aninhados, estremeço ao pensar qual é a complexidade do grande tempo para isso, mas ele completa o exemplo em menos de 10 segundos na minha máquina.
fonte
Python, 314 bytes
Muito obrigado ao SP3000, grc e FryAmTheEggman:
fonte
JavaScript (ES6) 194
202Solução iterativa, talvez mais curta se tornada recursiva
Explicado
Teste no console do FireFox / FireBug.
Resultado
fonte
Python 3, 329 bytes
Versão não destruída:
fonte