fundo
O incidente é uma linguagem de programação bastante incomum, pois sua lista de tokens não é predeterminada, mas inferida a partir da entrada. Como tal, tokenizar um programa de incidentes pode ser bastante difícil, especialmente se você quiser fazer isso com eficiência. Esta tarefa é sobre fazer você mesmo.
A tarefa
Seu programa receberá uma string como entrada. Aqui está o algoritmo que o Incident usa para tokenizá-lo:
- Identifique todas as strings que ocorrem como uma substring da entrada de exatamente três maneiras (ou seja, existem exatamente três ocorrências dessa string na entrada).
- Descarte qualquer uma dessas cadeias de caracteres que sejam uma subcadeia de outra cadeia de caracteres (por exemplo, para entrada
ababab
, a única cadeia restante seriaab
, nãoa
oub
, porquea
eb
são as duas subseqüências deab
). - Descarte quaisquer seqüências que se sobreponham na entrada. (Por exemplo,
aaaa
contém exatamente três cópias deaa
, mas essas cópias se sobrepõem ao segundo e terceiro caracteres, seria descartada. Da mesma forma, emabababa
, existem três cópiasab
e três cópias deba
, mas o segundo ao sexto caracteres estão cada um no sobreposição de anab
e aba
, então ambosab
eba
seriam descartados). - Quaisquer strings que permanecem nesse momento são os tokens usados pelo programa. Tokenize a entrada original em uma sequência desses tokens (devido ao descarte na etapa anterior, haverá apenas uma maneira de fazê-lo). Quaisquer caracteres na entrada que não façam parte de nenhum token são tratados como comentários e descartados.
Seu programa precisa pegar uma string como entrada e retornar a tokenização correspondente da string (uma lista de tokens, cada um dos quais é expresso como strings) como saída. Além disso, isso deve ser feito pelo menos moderadamente com eficiência; especificamente, o programa deve ser executado em tempo quadrático ("O (n²)") ou melhor. (Aliás, é quase certamente possível ir mais rápido que o quadrático, mas esse não é o algoritmo mais rápido , portanto, sinta-se à vontade para usar o algoritmo tersest que você achar que se encaixa dentro dos limites da complexidade.)
Esclarecimentos
- Embora os programas de incidentes possam, em teoria, conter qualquer um dos 256 octetos, é aceitável, para o objetivo deste desafio, que seu programa manipule apenas entradas formadas em ASCII imprimível (incluindo espaço), além de nova linha e guia. (Todos os programas de incidentes conhecidos se restringem a esse subconjunto). Observe que espaço / nova linha / guia não são especiais e podem aparecer no meio dos tokens; O incidente trata todos os 256 octetos como opacos.
- A definição de "tempo quadrático" é "se o tamanho da entrada for duplicado, o programa será executado mais devagar não mais que uma constante mais um fator de 4", ou seja, se t ( x ) for o tempo máximo que seu programa leva para processar uma entrada de tamanho x , então deve haver alguma constante k tal que t (2 x ) <4 t ( x ) + k para todo x . Lembre-se de que comparar cordas leva um tempo proporcional ao comprimento das cordas.
- Teoricamente, seu programa deve ser capaz de lidar com programas de entrada de qualquer tamanho, se for executado em uma variante (possivelmente hipotética) do seu idioma, com memória ilimitada e usar números inteiros ilimitados (tudo bem se o programa falhar em atingir esse objetivo quando for executado na prática devido a os números inteiros ou a memória do idioma são realmente finitos). Você pode supor (com o objetivo de calcular a complexidade) que números inteiros que não sejam maiores que o comprimento da entrada podem ser comparados em tempo constante (embora tenha em mente que, se você usar valores maiores, por exemplo, devido à conversão da entrada em um inteiro inteiro, eles levarão um tempo para comparar proporcionalmente ao número de dígitos que possuem).
- Você pode usar qualquer algoritmo que se enquadre nos limites da complexidade, mesmo que não siga as mesmas etapas do algoritmo postado acima, desde que produza os mesmos resultados.
- Este quebra-cabeça é sobre tokenizar a entrada, não realmente sobre formatar a saída. Se a maneira mais natural de gerar uma lista em seu idioma envolver um formato ambíguo (por exemplo, separados por novas linhas quando as strings contiverem novas linhas literais ou sem delimitadores entre as strings), não se preocupe com o fato de que a saída acaba sendo ambígua ( desde que a lista seja realmente construída). Convém fazer uma segunda versão do seu envio que produza uma saída inequívoca, para ajudar nos testes, mas a versão original é a que conta para a pontuação.
Caso de teste
Para a seguinte sequência de entrada:
aaabcbcbcdefdfefedghijghighjkllkklmmmmonono-nonppqpq-pqprsrsrstststuvuvu
seu programa deve produzir a seguinte lista de saída:
a a a bc bc bc d e f d f e f e d gh gh gh k l l k k l pq pq pq u u u
Condição de vitória
Este é o código-golfe , portanto o programa mais curto válido (isto é, comportamento correto de entrada / saída e suficientemente rápido para executar), medido em bytes, vence.
Respostas:
C (gcc), 324 bytes
A função
f
pega uma sequência terminada em nulo e imprime os tokens em stdout. Todas as novas linhas podem ser removidas do código abaixo.Esta versão antiga de 376 bytes é um pouco mais fácil de ler; a explicação abaixo se aplica a ele.
k(0)
gera a tabelat
para o padrãop
do algoritmo Knuth – Morris – Pratt.K(c)
processe o próximo caracterec
da sequência de pesquisa e as atualizaçõesm
, cujo comprimento do maior prefixop
pode ser encontrado terminando no caractere processado mais recentemente.No primeiro
for
loop, para cada índicea
da string, contamos o número de vezes que cada valor possívelm
ocorre ao pesquisar na string inteira a substring começando ema
. Em seguida, procuramos o maior, del
modo que al
subseqüência do comprimento iniciadaa
ocorreu exatamente 3 vezes. Se for curto o suficiente para ser totalmente contido por uma string encontrada para uma anteriora
, nós a ignoramos. Se ela se sobrepuser, excluiremos a string anteriorz
, a matriz de gravação da qual os tokens serão mantidos. Caso contrário, seu comprimento é armazenado emz
.Em seguida, usamos o KMP novamente para pesquisar na sequência os tokens registrados
z
. Se um deles for encontrado em um local com uma entrada 0z
, sabemos que esse token foi excluído devido à sobreposição. Se o token não foi excluído, ele é impresso.fonte
O(n^2)
ou mais rápido. E porque há!!
em!!z[x-m]
?*Z
é o tamanho do próximo token que precisa se tornar 0 se alguma das outras ocorrências do token tiver o valor 0 em seu índice na matriz ou manter o mesmo valor caso contrário (nesse caso,!!z[x-m]
deve ser 1.!!
disso.!!x
ainda deve serx
ou invoca um truque que não conheço?!!x
fazx
um booleano representando sua "veracidade". Então!!1 == true
e!!0 == false
. Eu não sei C especificamente, mas é assim que costuma acontecer #JavaScript,
878867842825775752717712704673664650641 bytesObrigado a @Kritixi Lithos por ajudar no código de golfe
Obrigado a @ User2428118 por jogar 14 bytes
(Não funcionará no IE7) (as novas linhas devem ser inseridas como "
\n
" e a tabulação como "\t
" na sequência de entrada, os caracteres unicode devem ser inseridos como\u####
)Experimente Online
Explicação de como funciona e código não destruído
Primeiro, o programa gera matrizes Knuth Morris Pratt para cada substring possível;
Em seguida, o programa encontra os comprimentos máximos correspondentes em cada índice da palavra com cada substring. (este é o tempo O (n ^ 2))
O programa usa esses dados para encontrar as substrings mais longas que aparecem três vezes para cada caractere inicial da string.
O programa usa esses dados para eliminar todas as substrings que não aparecem exatamente três vezes e todas as substrings das substrings válidas mais longas.
Em seguida, o programa define todas as substrings parciais ou sobrepostas a serem removidas.
Para cada um dos valores a serem removidos, todas as substrings equivalentes também são removidas.
Finalmente, o programa une a matriz de substrings e a produz.
fonte
while
eif
que possuem apenas 1 instrução dentro deles. Você pode remover os aparelhos{}
ao redor dessas instruções. Por exemplo,if(word.charAt(index+i)==word.charAt(index+j)){j++;}
pode se tornarif(word.charAt(index+i)==word.charAt(index+j))j++;
&&
s para substituirif
instruções, movi-as em loops para que elas terminassem com uma instrução abaixo delas, para que eu pudesse remover chaves. Eu usei ternários para substituir algumas declarações if. Mudei as coisas e acabei em 946 bytes . Se você não entender algo que eu fiz, não hesite em perguntar-me :)