9
\$\begingroup\$

This is a word puzzle.

Your program should accept two words on the standard input.
Word one is the start word. Word two is the end word.

From the start word you have to reach the end word changing/add/remove one letter at a time. After each modification it must form a new valid word. Added letters are added to the beginning or end. You can remove letters from any location (but word must not fall bellow three letters in length). Note: You can not rearrange the letters to form a word.

The output of the program is the sequence of words to get from the start word to the end word.

Example:

Input:
    Post Shot

Output:
    Post
    cost
    coat
    goat
    got
    hot
    shot

Winner:

  • The program must run in a reasonable time (less than a 10 seconds).
  • The program that can generate the shortest output sequence to the prize words.
    • Zink -> Silicon
  • If more than one program gets the shortest sequence then the shortest program in chars (ignoring white space).
  • If we still have more than one program submission date/time shall be used.

Notes:

\$\endgroup\$
  • \$\begingroup\$ may be "post->pot->hot->shot" is shorter. \$\endgroup\$ – YOU Feb 8 '11 at 9:21
  • \$\begingroup\$ @S.Mark: Then your algorithm beats mine and you win. The above is an example of a possible solution. A shorter solution beats a longer solution. \$\endgroup\$ – Martin York Feb 8 '11 at 9:24
  • \$\begingroup\$ intentionally? sorry, I just got it wrong. \$\endgroup\$ – YOU Feb 8 '11 at 9:25
  • 2
    \$\begingroup\$ Could I solve it in Whitespace for 0 program size? \$\endgroup\$ – user475 Feb 8 '11 at 12:12
  • \$\begingroup\$ @Tim Nordenfur: I would love to see a white space implementation. Note. there are two rules before program length to decide winner. But if you meet those requirements :-) \$\endgroup\$ – Martin York Feb 8 '11 at 15:56
2
\$\begingroup\$

Python, 288 characters

(not counting the dictionary reading line)

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

for the challenge zink to silicon:

ZINK
PINK
PANK
PANI
PANIC
PINIC
SINIC
SINICO
SILICO
SILICON

There are some strange words in that dictionary...

\$\endgroup\$
  • \$\begingroup\$ I did not actually check the content. I just tried to find a dictionary that everybody could use. \$\endgroup\$ – Martin York Feb 8 '11 at 18:56
  • \$\begingroup\$ try with guester overturn (takes some time) or regatta gyrally (does not returns) ;-) \$\endgroup\$ – Arnaud Le Blanc Feb 10 '11 at 20:57
  • \$\begingroup\$ Yes, some combinations take a while. The time gets longer as the shortest solution gets longer. And the last one has no solution - there's no spec for what should happen in that case :) It's pretty easy to modify to handle it though (save a handle to G.copy() and compare G against it at the end of the loop). \$\endgroup\$ – Keith Randall Feb 11 '11 at 23:47
16
\$\begingroup\$

traceroute - 10 chars

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

Routers are preconfigured with OSPF enabled and arranged this way.

enter image description here

And yes, I need 233614 routers to fully support all the words. :-)

\$\endgroup\$
  • \$\begingroup\$ Very clever but you fail the 10 second rule. It will take you excessively longer than 10 seconds to configure all the routers. :-) Whats the route from : Zink -> Silicon \$\endgroup\$ – Martin York Feb 8 '11 at 15:53
  • \$\begingroup\$ @Martin, please be ignore for configuration time, it just like building dictionary, heheh, routes for Zink -> Silicon is zink->pink->pank->pani->panic->pinic->sinic->sinico->silico->silicon I am really trying with Dijkstra algorithm (which is used in OSPF) and its can find that path around 1s, I will post it in seperate post later, once I golfed. \$\endgroup\$ – YOU Feb 8 '11 at 15:59
3
\$\begingroup\$

PHP - 886 689 644 612

Dictionary loading:

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

Actual code (just concat both) :

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

Result:

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

This should run in less than 0.5 second for 'Zink Silicon', and less than 1 second for most cases (sometimes longer when no solution exists, but it sill returns).

This uses the A* algorithm with levenshtein distance to estimate a lower bounds of the distances.

Some intersting tests:

  • vas arm -> vas bas bar barm arm (with a word longer than both start and end)
  • oxy pom -> oxy poxy poy pom
  • regatta gyrally -> (none, but the script correctly terminates)
  • aal presolution -> +8 chars
  • lenticulated aal -> -9 chars
  • acarology lowness -> 46 hops
  • caniniform lowness -> 51 hops
  • cauliform lowness -> 52 hops
  • overfoul lowness -> 54 hops
  • dance facia -> some words in the path have 4 more chars than both start/end
\$\endgroup\$
  • \$\begingroup\$ Try Zink Silicon \$\endgroup\$ – Martin York Feb 8 '11 at 10:46
  • \$\begingroup\$ This should work, now :-) \$\endgroup\$ – Arnaud Le Blanc Feb 8 '11 at 13:40
  • \$\begingroup\$ I will find a bigger machine: PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 71 bytes) \$\endgroup\$ – Martin York Feb 8 '11 at 16:48
  • \$\begingroup\$ You just hit the 128M memory_limit setting ;-) Try with php -dmemory_limit=256M. \$\endgroup\$ – Arnaud Le Blanc Feb 8 '11 at 16:55
  • \$\begingroup\$ had->hand is not a valid move, you can only add a letter to the beginning or end. Same for vest->verst :-) \$\endgroup\$ – Arnaud Le Blanc Feb 11 '11 at 8:52
3
\$\begingroup\$

Python

Since I couldn't golf dijkstra codes to compress to few hundreds bytes, here is ungolfed version of mine.

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'

Added user300's Tests

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

Some more

$ 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'
\$\endgroup\$
  • \$\begingroup\$ 3 <= len(x) <= max(map(len, [nodea, nodeb])) is it guaranteed that the path will never go through a word longer than both start and end words ? \$\endgroup\$ – Arnaud Le Blanc Feb 10 '11 at 19:10
  • \$\begingroup\$ Try with oxy pom; shortest path is oxy->poxy->poy->pom. Also is seems that you allow permutations and insertions at any place, which are not allowed :-) \$\endgroup\$ – Arnaud Le Blanc Feb 10 '11 at 19:46
  • \$\begingroup\$ @user300, fixed permutations and insertions parts, I copy-pasted too much, thanks ;-) and I am setting initial limit to 5 chars and allowing +1 more chars start and end words, let me know if that still be issue. thanks. \$\endgroup\$ – YOU Feb 11 '11 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.