Ceci est un puzzle de mots.

Votre programme doit accepter deux mots sur l'entrée standard.
Le premier mot est le mot de départ. Le mot deux est le mot de fin.

Depuis le mot de départ, vous devez atteindre le mot de fin en changeant / ajoutant / supprimant une lettre à la fois. Après chaque modification, il doit former un nouveau mot valide. Les lettres ajoutées sont ajoutées au début ou à la fin. Vous pouvez supprimer des lettres de n'importe quel endroit (mais le mot ne doit pas tomber en dessous de trois lettres). Remarque: vous ne pouvez pas réorganiser les lettres pour former un mot.

La sortie du programme est la séquence de mots à passer du mot de début au mot de fin.

Exemple:

Input:
    Post Shot

Output:
    Post
    cost
    coat
    goat
    got
    hot
    shot

Gagnant:

• Le programme doit s'exécuter dans un délai raisonnable (moins de 10 secondes).
• Le programme qui peut générer la séquence de sortie la plus courte pour les mots de prix.
  • Zink -> Silicium
• Si plusieurs programmes obtiennent la séquence la plus courte, alors le programme le plus court en caractères (en ignorant les espaces blancs).
• Si nous avons encore plus d'une date / heure de soumission du programme, celle-ci sera utilisée.

Remarques:

• La capitalisation n'est pas pertinente.
• Le code pour construire un dictionnaire ne compte pas dans le coût du code.
  • Les mots et la séquence des prix seront générés à partir de:
    http://dl.packetstormsecurity.net/Crackers/wordlists/dictionaries/websters-dictionary.gz

Python, 288 caractères

(sans compter la ligne de lecture du dictionnaire)

X=set(open('websters-dictionary').read().upper().split())

(S,E)=raw_input().upper().split()
G={S:0}
def A(w,x):
 if x not in G and x in X:G[x]=w
while E not in G:
 for w in G.copy():
  for i in range(len(w)):
   for c in"ABCDEFGHIJKLMNOPQRSTUVWXYZ":A(w,w[:i]+c+w[i+1:]);A(w,w[:i]+w[i+1:]);A(w,c+w);A(w,w+c)
s=''
while E:s=E+'\n'+s;E=G[E]
print s

pour le défi zinkde silicon:

ZINK
PINK
PANK
PANI
PANIC
PINIC
SINIC
SINICO
SILICO
SILICON

Il y a des mots étranges dans ce dictionnaire ...

traceroute - 10 caractères

traceroute 

détail

post#traceroute shot

Type escape sequence to abort.
Tracing the route to shot (1.1.4.2)

  1 pot (1.1.1.2) 40 msec 68 msec 24 msec
  2 hot (1.1.3.2) 16 msec 32 msec 24 msec
  3 shot (1.1.4.2) 52 msec *  92 msec

Les routeurs sont préconfigurés avec OSPF activé et organisés de cette façon.

Et oui, j'ai besoin de 233614 routeurs pour supporter pleinement tous les mots. :-)

PHP - 886 689 644 612

Chargement du dictionnaire:

<?php foreach(file('websters-dictionary') as $line) {
    $word = strtolower(trim($line));
    if (strlen($word) < 3) continue;
    $c[$word] = 1;
}

Code réel (juste concaténer les deux):

list($d,$e)=explode(' ',strtolower(trim(`cat`)));$f=range(@a,@z);function w($a,&$g){global$c;if(isset($c[$a]))$g[]=$a;}$h[$d]=$b=@levenshtein;$i=new SplPriorityQueue;$i->insert($d,0);$j[$d]=0;$k[$d]=$b($d,$e);while($h){if(isset($c[$l=$i->extract()])){unset($h[$l],$c[$l]);if($l==$e){for(;$m=@$n[$o[]=$l];$l=$m);die(implode("\n",array_reverse($o)));}for($p=strlen($l),$g=array();$p--;){w(substr_replace($q=$l,"",$p,1),$g);foreach($f as$r){$q[$p]=$r;w($q,$g);w($r.$l,$g);w($l.$r,$g);}}foreach($g as$m){$s=$j[$l]+1;if(!isset($h[$m])||$s<$j[$m]){$n[$m]=$l;$i->insert($m,-(($k[$m]=$b($m,$e))+$j[$m]=$s));}$h[$m]=1;}}}

usage:

php puzzle.php <<< 'Zink Silicon'
# or
echo 'Zink Silicon'|php puzzle.php

Résultat:

zink
pink
pank
pani
panic
pinic
sinic
sinico
silico
silicon
(0.23s)

Cela devrait s'exécuter en moins de 0,5 seconde pour «Zink Silicon» et en moins de 1 seconde pour la plupart des cas (parfois plus longtemps lorsqu'aucune solution n'existe, mais elle revient).

Celui-ci utilise l' algorithme A * avec une distance de levenshtein pour estimer une borne inférieure des distances.

Quelques tests intéressants:

• vas arm-> vas bas bar barm arm(avec un mot plus long que début et fin)
• oxy pom -> oxy poxy poy pom
• regatta gyrally -> (aucun, mais le script se termine correctement)
• aal presolution -> +8 caractères
• lenticulated aal -> -9 caractères
• acarology lowness -> 46 houblons
• caniniform lowness -> 51 sauts
• cauliform lowness -> 52 houblons
• overfoul lowness -> 54 houblons
• dance facia -> certains mots du chemin ont 4 caractères de plus que les deux début / fin

Python

Comme je ne pouvais pas jouer au golf à des codes dijkstra pour les compresser en quelques centaines d'octets, voici ma version non golfée.

import sys, heapq, time

# dijkstra algorithm from 
# http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/
def dijkstra(G, start, end):
   def flatten(L):
      while len(L) > 0:
         yield L[0]
         L = L[1]

   q = [(0, start, ())]
   visited = set()
   while True:
      (cost, v1, path) = heapq.heappop(q)
      if v1 not in visited:
         visited.add(v1)
         if v1 == end:
            return list(flatten(path))[::-1] + [v1]
         path = (v1, path)
         for (v2, cost2) in G[v1].iteritems():
            if v2 not in visited:
               heapq.heappush(q, (cost + cost2, v2, path))

nodes = tuple(sys.argv[1:])

print "Generating connections,",
current_time = time.time()

words = set(x for x in open("websters-dictionary", "rb").read().lower().split() if 3 <= len(x) <= max(5, *[len(l)+1 for l in nodes]))

print len(words), "nodes found"

def error():
    sys.exit("Unreachable Route between '%s' and '%s'" % nodes)

if not all(node in words for node in nodes):
    error()

# following codes are modified version of
# http://norvig.com/spell-correct.html
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits(word):
   splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes = [a + b[1:] for a, b in splits if b]
   replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   prepends = [c+word for c in alphabet]
   appends = [word+c for c in alphabet]
   return words & set(deletes + replaces + prepends + appends)

# Generate connections between nodes to pass to dijkstra algorithm
G = dict((x, dict((y, 1) for y in edits(x))) for x in words)

print "All connections generated, %0.2fs taken" % (time.time() - current_time)
current_time = time.time()

try:
    route = dijkstra(G, *nodes)
    print '\n'.join(route)
    print "%d hops, %0.2fs taken to search shortest path between '%s' & '%s'" % (len(route), time.time() - current_time, nodes[0], nodes[1])
except IndexError:
    error()

Les tests

$ python codegolf-693.py post shot
Generating connections, 15930 nodes found
All connections generated, 2.09s taken
post
host
hot
shot
4 hops, 0.04s taken to search shortest path between 'post' & 'shot'

$ python codegolf-693.py zink silicon
Generating connections, 86565 nodes found
All connections generated, 13.91s taken
zink
pink
pank
pani
panic
pinic
sinic
sinico
silico
silicon
10 hops, 0.75s taken to search shortest path between 'zink' & 'silicon'

Ajout des tests de user300

$ python codegolf-693.py vas arm
Generating connections, 15930 nodes found
All connections generated, 2.06s taken
vas
bas
bam
aam
arm
5 hops, 0.07s taken to search shortest path between 'vas' & 'arm'

$ python codegolf-693.py oxy pom
Generating connections, 15930 nodes found
All connections generated, 2.05s taken
oxy
poxy
pox
pom
4 hops, 0.01s taken to search shortest path between 'oxy' & 'pom'

$ python codegolf-693.py regatta gyrally
Generating connections, 86565 nodes found
All connections generated, 13.95s taken
Unreachable Route between 'regatta' and 'gyrally'

Un peu plus

$ python codegolf-693.py gap shrend
Generating connections, 56783 nodes found
All connections generated, 8.16s taken
gap
rap
crap
craw
crew
screw
shrew
shrewd
shrend
9 hops, 0.67s taken to search shortest path between 'gap' & 'shrend'

$ python codegolf-693.py guester overturn
Generating connections, 118828 nodes found
All connections generated, 19.63s taken
guester
guesten
gesten
geste
gest
gast
east
ease
erse
verse
verset
overset
oversee
overseed
oversend
oversand
overhand
overhard
overcard
overcare
overtare
overture
overturn
23 hops, 0.82s taken to search shortest path between 'guester' & 'overturn'