Objetivo

Escrever uma rotina que aceita uma cadeia de caracteres ASCII imprimíveis, é , e retorna um string contendo os mesmos caracteres que s , reordenadas de modo que não há dois caracteres substring aparece mais de uma vez. O programa deve processar todas as seqüências de referência (veja abaixo) em menos de um minuto cada, em um computador moderno . Também concederei um bônus especial de 50 repetições à resposta de pontuação mais baixa que processa qualquer sequência válida de 30 caracteres em menos de um minuto.

Por exemplo, dada a entrada Mississippi, uma saída válida seria issiMspiips(nenhuma substring de dois caracteres aparecerá duas vezes), enquanto uma saída inválida seria ipMsispiiss(já que a substring isaparece duas vezes).

A rotina pode assumir a forma de:

• uma leitura completa do programa stdin(ou equivalente) ou da linha de comando e saída para stdout(ou equivalente)
• uma função que aceita um argumento de string única e retorna uma string

Você pode assumir que a sequência de entrada sempre admite pelo menos uma saída válida.

O desafio

Sua rotina deve incluir 5 ou mais linhas de código separadas por novas linhas. Linhas vazias (que incluem linhas contendo apenas espaço em branco) são ignoradas em todos os contextos e não contam para a contagem total de linhas.

A troca de duas linhas no seu código-fonte deve gerar um erro fatal. Por "erro fatal", nos referimos a qualquer uma das seguintes condições:

• o código fonte falha ao compilar, com o compilador / intérprete declarando um erro fatal
• a rotina é interrompida com um erro fatal de tempo de execução ou uma exceção de tempo de execução não tratada
• a rotina é forçada a um encerramento abrupto e anormal do programa que não produz nenhum tipo de saída, exceto por uma possível mensagem de erro e / ou despejo de pilha

Como alternativa , blocos contíguos de código que não contêm caracteres de nova linha podem ser usados ​​no lugar de linhas. Esses blocos devem ser exibidos em sua própria linha no arquivo de origem, com o entendimento de que as novas linhas são removidas antes que o código-fonte seja compilado / interpretado.

Por exemplo, o código

aaaa
bbbb
cccc

condensaria a

aaaabbbbcccc

antes de ser avaliado.

Nesse modo, a condição de erro fatal se aplica à troca de dois blocos de código (e, portanto, à troca de linhas no código-fonte antes que as novas linhas sejam removidas). Daí, no exemplo acima as rotinas aaaaccccbbbb, bbbbaaaacccce ccccbbbbaaaadeve produzir todos os erros fatais, quer no compiletime ou tempo de execução.

Os envios que usam esse modo alternativo devem declarar seu uso.

Pontuação

Seja n o número de linhas de texto não vazias no seu arquivo de origem, com n ≥ 5. Seja c o número de bytes compreendidos pela linha de texto mais longa (pelo comprimento de bytes) no seu arquivo de origem, sem contar nenhuma nova linha à direita.

A pontuação de uma submissão é dada por c ( n + 10).

A finalização com a menor pontuação é a vencedora.

Boa sorte. ;)

Benchmark Strings

Abracadabra Alacazam
Is Miss. Mississauga Missing?
Ask Alaska's Alaskans
GGGGAAAATTTTCCCCgggaaatttccc
A Man A Plan A Canal Panama

PHP, pontuação = 289 (17 × (7 + 10))

As funções integradas do PHP facilitam bastante isso. O código a seguir apenas embaralha a sequência até que um resultado válido seja obtido:

function f($s){
while(preg_match(
'/(..).*?\1/',$s)
+preg_match('/(.'
.')\1\1/',$s))$s=
str_shuffle(
$s);return $s;}

Benchmarks

Tempos médios e máximos de execução calculados usando o seguinte código:

$s = 'Mississippi';
$t_total = 0;
$t_max = 0;
for ($i=0; $i<10; $i++) {
  $t0 = microtime(true);
  echo f($s);
  $t = microtime(true) - $t0;
  printf("  %10.7f\n",$t);
  $t_total += $t;
  if ($t > $t_max) $t_max = $t;
}
printf("Avg: %10.7f secs; Max: %10.7f secs\n",$t_total/$i, $t_max);

Resultados:

• Mississippi: Média: 0,0002460 segundos; Máx: 0,0005491 s
• Nelemento anti-substituição: Média: 0,0001470 segundos; Máx: 0,0002971 segundos
• Pneumonoultramicroscopicsilicovolcanoconiosis: Média: 0,0587177 segundos; Máx: 0,1668079 segundos
• Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft ^* : Avg: 9.5642390 segs; Máximo: 34,9904099 segundos
• baaacadaeafbbcbdbebfccdcecfdde ^† : Média: 5,0858626 segundos; Máximo: 9,8927171 segundos

^{* Alterei äpara aevitar problemas de vários bytes
† Essa foi a string mais difícil de 30 caracteres que eu consegui criar. Na verdade, são os primeiros 30 caracteres da sequência De Bruijn para k = 'abcdef' e n = 2, com o primeiro 'b' movido para evitar uma correspondência instantânea.}

Dyalog APL (11 (5 + 10) = 165)

f←{a←{⍴⍵}
b←a⌸2,/⍵
c←b⊢⍵[?⍨a⍵]
1∨.≠b:∇c⋄⍵
}

Prova:

• As linhas 1 e 5 vinculam a função. Trocar qualquer linha por elas resultaria em ⍵fora de uma função, que é a SYNTAX ERROR.
• A linha 2 define b, portanto, não pode ser trocada por linhas 3ou das 4quais dependem b. Haveria um VALUE ERROR. (E isso, obviamente, não pode ser trocado com 1ou 5qualquer um.)
• A linha 3 define c, portanto, não pode ser trocada por linha 4, da qual depende c. (E já provamos que nenhuma outra linha pode ser trocada por linha 3.)
• A linha 4 depende das variáveis ​​das linhas 2 e 3 e, portanto, deve ser a última.

APL (Dyalog), 6 (5 + 10) = 90

{1∧.=
+/∘.≡⍨
2,/⍵:⍵
⋄∇⍵[
?⍨⍴⍵]}

Estou usando a alternativa, então:

{1∧.=+/∘.≡⍨2,/⍵:⍵⋄∇⍵[?⍨⍴⍵]}

Este é o mesmo algoritmo antigo.

A explicação
2,/⍵ fornece que uma matriz de pares de caracteres na sequência de entrada
+/∘.≡⍨gera uma matriz numérica de quantos pares cada par é igual (incluindo a si próprio)
1∧.=verifica se cada elemento dessa matriz é igual a 1 e AND lógico os resultados juntos

:⍵Se isso for verdade ( 1), retorne a string de entrada

∇⍵[?⍨⍴⍵] caso contrário, embaralhe a sequência de entrada e faça uma chamada recursiva

Troca

Se a linha 1 é trocada pela linha 2, você acaba com +/∘.≡⍨{...}uma bagunça de funções e operadores que fornece SYNTAX ERROR.
Se a linha 1 for trocada pela linha 3 ou 4, você terá ⍵fora de uma definição de função, e isso é a SYNTAX ERROR.
Se a linha 1 for trocada pela linha 5, somente chaves não-balanceadas causariam SYNTAX ERROR, portanto, não se preocupe com os outros quatro erros de sintaxe.

Se a linha 5 for trocada pela linha 2/3/4, novamente você terá ⍵fora de uma definição de função. ( SYNTAX ERROR)

Se a linha 2 for trocada pela linha 3, você terminará 1∧.=2,/⍵:⍵. Essa sintaxe é chamada de guarda (pense nela como condicional). A condição de guarda deve avaliar para 0ou 1ou uma matriz de 1 elemento de 0ou 1. Aqui, ele avalia algo mais complexo que isso (um escalar contendo uma matriz de 2 elementos). Então este é um DOMAIN ERROR.
Se a linha 2 for trocada pela linha 4, você obtém a instrução 1∧.=, que tenta aplicar a função ∧.=sem o argumento esquerdo necessário. ( SYNTAX ERROR)

Se a linha 3 for trocada pela linha 4, novamente você terá uma confusão de funções e operadores ( 1∧.=+/∘.≡⍨) SYNTAX ERROR.

Valores de referência
(números em milissegundos)

Abracadabra Alacazam
11 1 3 5 2
Avg: 4.4

Is Miss. Mississauga Missing?
1260 2000 222 117 111
Avg: 742

Ask Alaska's Alaskans
7 2 3 3 4
Avg: 3.8

GGGGAAAATTTTCCCCgggaaatttccc
31 15 24 13 11
Avg: 18.8

A Man A Plan A Canal Panama
377 2562 23 301 49
Avg: 662.4

Ainda estou pensando em diferentes separações. Também tenho uma maneira sistemática e determinística de executar a tarefa. Eu simplesmente não consigo transformá-lo em um algoritmo (retire a parte criativa de "acertar os números") e não posso garantir que funcione sempre.

Haskell, 129 = 3x (33 + 10)

isso usa o modo alternativo.

imp
ort
 Da
ta.
Lis
t;a
%[]
=[[
]];
a%s
=[x
:j|
x<-
s,n
ot$
isI
nfi
xOf
[la
st 
a,x
]a,
j<-
(a+
+[x
])%
(s\
\[x
])]
;g 
s=[
]%s
!!0

ou de forma legível:

import Data.List
a%[]=[[]]
a%s=[x:j|x<-s,not$isInfixOf[last a,x]a,j<-(a++[x])%(s\\[x])]
g s=[]%s!!0

Haskell é uma linguagem muito estrita. por exemplo, o importdeve vir primeiro; as definições de sdevem se unir; todos os tipos devem concordar e não há como lançar entre eles, e assim por diante. isso leva a ter um erro não fatal quase impossível. de fato, ter um erro fatal em tempo de execução é quase quase impossível.

note que se gé uma função válida, mas tem um tipo errado (qualquer tipo diferente de então [a]->[a]ou String -> Stringsimilar), isso é um erro fatal, porque é impossível aplicar gàs entradas.

saídas:

Abracadabar Alaazcma
Is Miss. iMsiasusgsa sMniig?s
Ask Alasak's lAaankss
GGAGTGCAATACTTCCggagtaacttcc
A Man AP la nAC  aalnnaPama