Word Spinner Puzzle

10

Dies ist ein Worträtsel.

Ihr Programm sollte zwei Wörter für die Standardeingabe akzeptieren.
Wort eins ist das Startwort. Wort zwei ist das Endwort.

Vom Startwort an müssen Sie das Endwort erreichen, indem Sie jeweils einen Buchstaben ändern / hinzufügen / entfernen. Nach jeder Änderung muss ein neues gültiges Wort gebildet werden. Hinzugefügte Buchstaben werden am Anfang oder Ende hinzugefügt. Sie können Buchstaben von jedem Ort entfernen (das Wort darf jedoch nicht drei Buchstaben lang sein). Hinweis: Sie können die Buchstaben nicht neu anordnen, um ein Wort zu bilden.

Die Ausgabe des Programms ist die Folge von Wörtern, die vom Startwort zum Endwort gelangen.

Beispiel:

Input:
    Post Shot

Output:
    Post
    cost
    coat
    goat
    got
    hot
    shot

Gewinner:

  • Das Programm muss in einer angemessenen Zeit (weniger als 10 Sekunden) ausgeführt werden.
  • Das Programm, das die kürzeste Ausgabesequenz für die Preiswörter generieren kann.
    • Zink -> Silizium
  • Wenn mehr als ein Programm die kürzeste Sequenz erhält, dann das kürzeste Programm in Zeichen (ohne Leerzeichen).
  • Wenn wir noch mehr als ein Programm haben, wird das Datum / die Uhrzeit der Programmeinreichung verwendet.

Anmerkungen:

Martin York
quelle
kann sein "post-> pot-> hot-> shot" ist kürzer.
SIE
@ S.Mark: Dann schlägt dein Algorithmus meinen und du gewinnst. Das Obige ist ein Beispiel für eine mögliche Lösung. Eine kürzere Lösung schlägt eine längere Lösung.
Martin York
absichtlich? Entschuldigung, ich habe es einfach falsch verstanden.
SIE
2
Könnte ich es in Whitespace für 0 Programmgröße lösen ?
@ Tim Nordenfur: Ich würde gerne eine White Space Implementierung sehen. Hinweis. Vor der Programmdauer gibt es zwei Regeln, um den Gewinner zu bestimmen. Aber wenn Sie diese Anforderungen erfüllen :-)
Martin York

Antworten:

2

Python, 288 Zeichen

(ohne die Wörterbuch-Lesezeile zu zählen)

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

für die Herausforderung zinkan silicon:

ZINK
PINK
PANK
PANI
PANIC
PINIC
SINIC
SINICO
SILICO
SILICON

Es gibt einige seltsame Wörter in diesem Wörterbuch ...

Keith Randall
quelle
Ich habe den Inhalt nicht überprüft. Ich habe nur versucht, ein Wörterbuch zu finden, das jeder benutzen kann.
Martin York
versuchen Sie es mit guester overturn(dauert einige Zeit) oder regatta gyrally(kehrt nicht zurück) ;-)
Arnaud Le Blanc
Ja, einige Kombinationen dauern eine Weile. Die Zeit wird länger, da die kürzeste Lösung länger wird. Und der letzte hat keine Lösung - es gibt keine Spezifikation dafür, was in diesem Fall passieren soll :) Es ist jedoch ziemlich einfach zu ändern, um damit umzugehen (speichern Sie ein Handle in G.copy () und vergleichen Sie G am Ende der Schleife damit ).
Keith Randall
16

Traceroute - 10 Zeichen

traceroute 

Detail

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

Router sind mit aktiviertem OSPF vorkonfiguriert und auf diese Weise angeordnet.

Geben Sie hier die Bildbeschreibung ein

Und ja, ich brauche 233614 Router, um alle Wörter vollständig zu unterstützen. :-)

SIE
quelle
Sehr klug, aber Sie scheitern an der 10-Sekunden-Regel. Die Konfiguration aller Router dauert übermäßig lange als 10 Sekunden. :-) Was ist die Route von: Zink -> Silicon
Martin York
@Martin, bitte ignorieren Sie die Konfigurationszeit, es ist genau wie beim Erstellen eines Wörterbuchs, heheh, Routen für Zink -> Silicon. zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->siliconIch versuche es wirklich mit dem Dijkstra-Algorithmus (der in OSPF verwendet wird) und kann diesen Pfad um 1s finden poste es später in einem separaten Post, sobald ich Golf gespielt habe.
SIE
3

PHP - 886 689 644 612

Wörterbuch wird geladen:

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

Aktueller Code (nur beides zusammenfassen):

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;}}}

Verwendungszweck:

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

Ergebnis:

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

Dies sollte für 'Zink Silicon' in weniger als 0,5 Sekunden und in den meisten Fällen in weniger als 1 Sekunde ablaufen (manchmal länger, wenn keine Lösung vorhanden ist, aber immer noch zurückkehrt).

Dies verwendet den A * -Algorithmus mit Levenshtein-Abstand , um eine Untergrenze der Abstände abzuschätzen.

Einige interessante Tests:

  • vas arm-> vas bas bar barm arm(mit einem Wort, das länger als Anfang und Ende ist)
  • oxy pom -> oxy poxy poy pom
  • regatta gyrally -> (keine, aber das Skript wird korrekt beendet)
  • aal presolution -> +8 Zeichen
  • lenticulated aal -> -9 Zeichen
  • acarology lowness -> 46 Hopfen
  • caniniform lowness -> 51 Hopfen
  • cauliform lowness -> 52 Hopfen
  • overfoul lowness -> 54 Hopfen
  • dance facia -> Einige Wörter im Pfad haben 4 Zeichen mehr als beide Start / Ende
300
quelle
Versuchen Sie Zink Silicon
Martin York
Das sollte jetzt funktionieren :-)
Arnaud Le Blanc
Ich werde eine größere Maschine finden:PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes)
Martin York
Du hast gerade die 128M memory_limit Einstellung getroffen ;-) Versuch es mit php -dmemory_limit=256M.
Arnaud Le Blanc
had->handist kein gültiger Zug, Sie können nur einen Buchstaben am Anfang oder Ende hinzufügen. Gleiches gilt für vest->verst:-)
Arnaud Le Blanc
3

Python

Da ich Golf-Dijkstra-Codes nicht auf einige hundert Bytes komprimieren konnte, ist hier eine ungolfed Version von mir.

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()

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'

Tests von user300 hinzugefügt

$ 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'

Etwas mehr

$ 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'
SIE
quelle
3 <= len(x) <= max(map(len, [nodea, nodeb]))Ist garantiert, dass der Pfad niemals länger als Start- und Endwörter durch ein Wort führt?
Arnaud Le Blanc
Versuchen Sie es mit oxy pom; kürzester Weg ist oxy->poxy->poy->pom. Es scheint auch, dass Sie Permutationen und Einfügungen an jedem Ort zulassen, die nicht erlaubt sind :-)
Arnaud Le Blanc
@ user300, feste Permutationen und Einfügungsteile, ich habe zu viel kopiert, danke ;-) und ich setze das Anfangslimit auf 5 Zeichen und erlaube +1 weitere Zeichen Start- und Endwörter, lass es mich wissen, wenn das noch ein Problem ist. Vielen Dank.
SIE