Objetivo

Escriba una rutina que acepte una cadena de caracteres ASCII imprimibles, sy devuelva una cadena que contenga los mismos caracteres que s , reordenados para que no aparezca una subcadena de dos caracteres más de una vez. El programa debe procesar todas las cadenas de referencia (ver más abajo) en menos de un minuto cada una en una computadora moderna . También otorgaré una bonificación especial de 50 repeticiones a la respuesta con la puntuación más baja que procese cualquier cadena válida de 30 caracteres en menos de un minuto.

Por ejemplo, dada la entrada Mississippi, una salida válida sería issiMspiips(no aparecerían subcadenas de dos caracteres dos veces), mientras que una salida no válida sería ipMsispiiss(ya que la subcadena isaparece dos veces).

La rutina puede tomar la forma de:

• un programa completo que lee stdin(o equivalente) o la línea de comando, y que sale a stdout(o equivalente)
• una función que acepta un argumento de cadena única y devuelve una cadena

Puede suponer que la cadena de entrada siempre admite al menos una salida válida.

El reto

Su rutina debe comprender 5 o más líneas de código separadas por nuevas líneas. Las líneas vacías (que incluyen líneas que contienen solo espacios en blanco) se ignoran en todos los contextos y no cuentan para el recuento total de líneas.

Intercambiar dos líneas en su código fuente debe producir un error fatal. Por "error fatal", nos referimos a cualquiera de las siguientes condiciones:

• el código fuente no se compila, y el compilador / intérprete declara un error fatal
• la rutina aborta con un error fatal en tiempo de ejecución o una excepción de tiempo de ejecución no controlada
• la rutina se ve forzada a una terminación abrupta y anormal del programa que no produce ningún tipo de salida, excepto un posible mensaje de error y / o volcado de pila

Alternativamente , se pueden usar bloques contiguos de código que no contengan caracteres de nueva línea en lugar de líneas. Estos bloques deben mostrarse en su propia línea en el archivo fuente, con el entendimiento de que las nuevas líneas se eliminan antes de que se compile / interprete el código fuente.

Por ejemplo, el código

aaaa
bbbb
cccc

se condensaría a

aaaabbbbcccc

antes de ser evaluado.

En este modo, la condición de error fatal se aplica al intercambio de dos bloques de código (y, por lo tanto, al intercambio de líneas en el código fuente antes de eliminar las nuevas líneas). Por lo tanto, en el ejemplo anterior, las rutinas aaaaccccbbbb, bbbbaaaaccccy ccccbbbbaaaatodas deben producir errores fatales, ya sea en tiempo de compilación o en tiempo de ejecución.

Las presentaciones que utilizan este modo alternativo deben declarar su uso.

Puntuación

Sea n el número de líneas de texto no vacías en su archivo fuente, con n ≥ 5. Sea c el número de bytes comprendidos por la línea de texto más larga (por longitud de byte) en su archivo fuente, sin contar ninguna línea nueva final.

El puntaje de una presentación es dado por c ( n + 10).

La presentación con el puntaje más bajo es el ganador.

La mejor de las suertes. ;)

Cuerdas de referencia

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

PHP, puntaje = 289 (17 × (7 + 10))

Las funciones integradas de PHP hacen que sea bastante fácil hacer esto mal. El siguiente código simplemente baraja la cadena hasta obtener un resultado válido:

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

Puntos de referencia

Tiempos de ejecución promedio y máximo calculados usando el siguiente 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: Promedio: 0.0002460 segundos; Máx .: 0.0005491 segundos
• Elemento anticonstitucional: Promedio: 0.0001470 segundos; Máx .: 0.0002971 segundos
• Neumonoultramicroscopicsilicovolcanoconiosis: Promedio: 0.0587177 segundos; Máx .: 0.1668079 segundos
• Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft ^* : Promedio: 9.5642390 segundos; Máx .: 34.9904099 segundos
• baaacadaeafbbcbdbebfccdcecfdde ^† : Promedio: 5.0858626 segundos; Máx .: 9.8927171 segundos

^{* Cambié äpara aevitar problemas de varios bytes
† Esta fue la cadena de 30 caracteres más difícil que se me ocurrió. En realidad, son los primeros 30 caracteres de la secuencia De Bruijn para k = 'abcdef' yn = 2, con la primera 'b' movida para evitar una coincidencia instantánea.}

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

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

Prueba:

• Las líneas 1 y 5 unen la función. Intercambiar cualquier línea por esas resultaría en que ⍵ocurra fuera de una función, que es a SYNTAX ERROR.
• La línea 2 define b, por lo que no puede intercambiarse por líneas 3o 4, que dependen de b. Habría un VALUE ERROR. (Y obviamente no se puede intercambiar con 1o5 tampoco).
• La línea 3 define c, por lo que no se puede intercambiar por línea 4, que depende de c. (Y ya hemos demostrado que ninguna otra línea se puede intercambiar con línea 3).
• La línea 4 depende de las variables de las líneas 2 y 3 y, por lo tanto, debe ser la última.

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

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

Estoy usando la alternativa, entonces:

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

Este es el mismo algoritmo anterior.

La explicación
2,/⍵ da una matriz de pares de caracteres en la cadena de entrada
+/∘.≡⍨genera una matriz numérica de cuántos pares equivale cada par (incluido él mismo)
1∧.=verifica si cada elemento de esa matriz es igual a 1, y lógico Y los resultados juntos

:⍵Si eso es cierto ( 1), devuelve la cadena de entrada

∇⍵[?⍨⍴⍵] de lo contrario, codifique la cadena de entrada y realice una llamada recursiva

Intercambiando

Si la línea 1 se intercambia con la línea 2, entonces terminas con lo +/∘.≡⍨{...}que es solo un desastre de funciones y operadores que da SYNTAX ERROR.
Si la línea 1 se intercambia con la línea 3 o 4, entonces tiene ⍵fuera de una definición de función, y eso es a SYNTAX ERROR.
Si la línea 1 se intercambia con la línea 5, solo las llaves desequilibradas causarían SYNTAX ERROR, así que no se preocupe por los otros 4 errores de sintaxis.

Si la línea 5 se intercambia con la línea 2/3/4, otra vez usted tiene ⍵fuera de la definición de función. ( SYNTAX ERROR)

Si la línea 2 se intercambia con la línea 3, terminas con 1∧.=2,/⍵:⍵. Esta sintaxis se llama guardia (piense en ella como condicional). La condición de guardia debe evaluar a 0o 1o una matriz 1-elemento de 0o 1. Aquí, se evalúa como algo más complejo que eso (un escalar que contiene una matriz de 2 elementos). Entonces esta es una DOMAIN ERROR.
Si la línea 2 se intercambia con la línea 4, obtiene la instrucción 1∧.=, que intenta aplicar la función ∧.=sin el argumento izquierdo requerido. ( SYNTAX ERROR)

Si la línea 3 se intercambia con la línea 4, nuevamente obtienes un desorden de funciones y operadores ( 1∧.=+/∘.≡⍨) para obtener SYNTAX ERROR.

Puntos de referencia
(números en milisegundos)

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

Todavía estoy pensando en diferentes divisiones. También tengo una forma determinista y sistemática de hacer la tarea. Simplemente no puedo convertirlo en un algoritmo (eliminar la parte creativa de "hacer los números correctos") y no puedo asegurarme de que funcione todo el tiempo.

Haskell, 129 = 3x (33 + 10)

esto usa el 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

o en una forma legible:

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 es un lenguaje muy estricto. por ejemplo, el importprimero debe venir; las definiciones de sdeben unirse; todos los tipos deben estar de acuerdo y no hay forma de elegir entre ellos, y así sucesivamente. Esto lleva a tener un error no fatal casi imposible. de hecho, tener un error fatal en tiempo de ejecución es casi casi imposible.

tenga en cuenta que si ges una función válida pero tiene un tipo incorrecto (cualquier tipo diferente entonces [a]->[a]o String -> Stringsimilar), es un error fatal porque es imposible de aplicar ga las entradas.

salidas:

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