Objectif

Écrivez une routine qui accepte une chaîne de caractères ASCII imprimables, s , et renvoie une chaîne contenant les mêmes caractères que s , réorganisée de sorte qu'aucune sous-chaîne à deux caractères n'apparaisse plus d'une fois. Le programme doit traiter toutes les chaînes de référence (voir ci-dessous) en moins d'une minute chacune sur un ordinateur moderne . J'accorderai également un bonus spécial de 50 répétitions à la réponse ayant obtenu le score le plus bas qui traite toute chaîne de 30 caractères valide en moins d'une minute.

Par exemple, étant donné l'entrée Mississippi, une sortie valide serait issiMspiips(aucune sous-chaîne à deux caractères n'apparaît deux fois), tandis qu'une sortie non valide le serait ipMsispiiss(puisque la sous-chaîne isapparaît deux fois).

La routine peut prendre la forme de:

• une lecture complète du programme à partir de stdin(ou équivalent) ou de la ligne de commande, et une sortie vers stdout(ou équivalent)
• une fonction acceptant un seul argument de chaîne et renvoyant une chaîne

Vous pouvez supposer que la chaîne d'entrée admet toujours au moins une sortie valide.

Le défi

Votre routine doit comprendre 5 lignes de code ou plus séparées par des retours à la ligne. Les lignes vides (qui incluent les lignes contenant uniquement des espaces blancs) sont ignorées dans tous les contextes et ne comptent pas dans le nombre total de lignes.

L'échange de deux lignes dans votre code source doit produire une erreur fatale. Par "erreur fatale", nous nous référons à l'une des conditions suivantes:

• le code source ne parvient pas à compiler, le compilateur / interprète déclarant une erreur fatale
• la routine s'interrompt avec une erreur fatale d'exécution ou une exception d'exécution non gérée
• la routine est forcée dans une interruption de programme anormale et abrupte qui ne produit aucune sortie d'aucune sorte, sauf pour un message d'erreur possible et / ou un vidage de pile

Alternativement , des blocs de code contigus ne contenant aucun caractère de nouvelle ligne peuvent être utilisés à la place des lignes. Ces blocs doivent chacun être affichés sur leur propre ligne dans le fichier source, étant entendu que les sauts de ligne sont supprimés avant que le code source soit compilé / interprété.

Par exemple, le code

aaaa
bbbb
cccc

se condenserait en

aaaabbbbcccc

avant d'être évalué.

Dans ce mode, la condition d'erreur fatale s'applique à l'échange de deux blocs de code (et donc à l'échange de lignes dans le code source avant la suppression des sauts de ligne). Par conséquent, dans l'exemple ci-dessus, les routines aaaaccccbbbb, bbbbaaaaccccet ccccbbbbaaaadoivent toutes produire des erreurs fatales, soit au moment de la compilation soit à l'exécution.

Les soumissions utilisant ce mode alternatif doivent déclarer son utilisation.

Notation

Soit n le nombre de lignes de texte non vides dans votre fichier source, avec n ≥ 5. Soit c le nombre d'octets compris par la ligne de texte la plus longue (par longueur d'octet) dans votre fichier source, sans compter les sauts de ligne de fin.

La note d'une soumission est donnée par c ( n + 10).

La soumission avec le score le plus bas est gagnante.

Bonne chance. ;)

Cordes de référence

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

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

Les fonctions intégrées de PHP facilitent assez mal cette opération. Le code suivant mélange simplement la chaîne jusqu'à ce qu'un résultat valide soit obtenu:

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

Repères

Temps d'exécution moyen et maximum calculés à l'aide du code suivant:

$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);

Résultats:

• Mississippi: Moy: 0,0002460 secondes; Max: 0,0005491 s
• Anticonstitutionnellement: Moy: 0,0001470 secondes; Max: 0,0002971 s
• Pneumonoultramicroscopicsilicovolcanoconiosis: Avg: 0,0587177 secondes; Max: 0,1668079 s
• Donaudampfschiffahrtselektrizitatenhauptbetriebswerkbauunterbeamtengesellschaft ^* : moyenne: 9,5642390 s; Max: 34,9904099 s
• baaacadaeafbbcbdbebfccdcecfdde ^† : moyenne: 5,0858626 s; Max: 9.8927171 s

^{* J'ai changé äpour aéviter les problèmes multi-octets
† Il s'agit de la chaîne de 30 caractères la plus difficile que j'ai pu trouver. Il s'agit en fait des 30 premiers caractères de la séquence De Bruijn pour k = 'abcdef' et n = 2, avec le premier 'b' déplacé pour éviter une correspondance instantanée.}

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

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

Preuve:

• Les lignes 1 et 5 délimitaient la fonction. L'échange de n'importe quelle ligne pour ceux-ci ⍵se produirait en dehors d'une fonction, qui est a SYNTAX ERROR.
• La ligne 2 définit b, elle ne peut donc pas être échangée contre des lignes 3ou 4, qui en dépendent b. Il y aurait un VALUE ERROR. (Et il ne peut évidemment pas être échangé avec 1ou 5non.)
• La ligne 3 définit c, donc elle ne peut pas être échangée contre la ligne 4, ce qui dépend c. (Et nous avons déjà prouvé qu'aucune autre ligne ne peut être échangée avec la ligne 3.)
• La ligne 4 dépend des variables des lignes 2 et 3 et doit donc être la dernière.

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

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

J'utilise l'alternative, donc:

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

Il s'agit du même ancien algorithme.

L'explication
2,/⍵ donne un tableau de paires de caractères dans la chaîne d'entrée
+/∘.≡⍨génère un tableau numérique de combien de paires chaque paire égale (y compris elle-même)
1∧.=vérifie si chaque élément de ce tableau est égal à 1, et logique ET les résultats ensemble

:⍵Si c'est vrai ( 1), retournez la chaîne d'entrée

∇⍵[?⍨⍴⍵] sinon brouiller la chaîne d'entrée et faire un appel récursif

Échange

Si la ligne 1 est échangée avec la ligne 2, vous vous retrouvez avec +/∘.≡⍨{...}ce qui n'est qu'un désordre de fonctions et d'opérateurs qui donne SYNTAX ERROR.
Si la ligne 1 est échangée avec la ligne 3 ou 4, alors vous avez en ⍵dehors d'une définition de fonction, et c'est a SYNTAX ERROR.
Si la ligne 1 est remplacée par la ligne 5, les accolades asymétriques seules causeraient SYNTAX ERROR, alors ne vous inquiétez pas des autres erreurs de syntaxe 4.

Si la ligne 5 est remplacée par la ligne 2/3/4, vous avez encore une fois en ⍵dehors d'une définition de fonction. ( SYNTAX ERROR)

Si la ligne 2 est remplacée par la ligne 3, vous vous retrouvez avec 1∧.=2,/⍵:⍵. Cette syntaxe est appelée garde (pensez-y comme conditionnelle). La condition de garde doit être évaluée à 0ou 1ou à un tableau à 1 élément de 0ou 1. Ici, il s'évalue à quelque chose de plus complexe que cela (un scalaire contenant un tableau à 2 éléments). C'est donc un DOMAIN ERROR.
Si la ligne 2 est remplacée par la ligne 4, vous obtenez l'instruction 1∧.=, qui tente d'appliquer la fonction ∧.=sans l'argument gauche requis. ( SYNTAX ERROR).

Si la ligne 3 est remplacée par la ligne 4, vous obtenez à nouveau un désordre de fonctions et d'opérateurs ( 1∧.=+/∘.≡⍨) donc vous obtenez SYNTAX ERROR.

Repères
(nombres en millisecondes)

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

Je pense toujours à différentes répartitions. J'ai aussi une façon déterministe et systématique de faire la tâche. Je ne peux tout simplement pas en faire un algorithme (enlevez la partie créative de «faire les bons chiffres») et je ne peux pas m'assurer que cela fonctionne à chaque fois.

Haskell, 129 = 3x (33 + 10)

cela utilise le mode alternatif.

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 sous une forme lisible:

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 est un langage très strict. par exemple, le importdoit venir en premier; les définitions de sdoivent se réunir; tous les types doivent s'accorder et il n'y a aucun moyen de lancer entre eux, et ainsi de suite. cela conduit à une erreur non fatale presque impossible. en fait, avoir une erreur fatale d'exécution est presque presque impossible.

notez que si gest une fonction valide mais a un mauvais type (tout type différent alors [a]->[a]ou String -> Stringsimilaire), il s'agit d'une erreur fatale car il est impossible de l'appliquer gaux entrées.

les sorties:

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