80 lines
1.3 KiB
Text
80 lines
1.3 KiB
Text
repeat
|
|
s$ = input
|
|
until s$ = ""
|
|
words$[] &= s$
|
|
.
|
|
func hammingdist w1$ w2$ .
|
|
for i to len w1$
|
|
if substr w1$ i 1 <> substr w2$ i 1
|
|
cnt += 1
|
|
if cnt = 2
|
|
break 1
|
|
.
|
|
.
|
|
.
|
|
return cnt
|
|
.
|
|
proc ladder a$ b$ .
|
|
# BFS
|
|
h = len a$
|
|
for w$ in words$[]
|
|
if len w$ = h
|
|
w$[] &= w$
|
|
if w$ = a$
|
|
a = len w$[]
|
|
elif w$ = b$
|
|
b = len w$[]
|
|
.
|
|
.
|
|
.
|
|
if a = 0 or b = 0
|
|
print "Words are not in dictionary"
|
|
return
|
|
.
|
|
n = len w$[]
|
|
len prev[] n
|
|
todo[] = [ a ]
|
|
while len todo[] > 0
|
|
for cur in todo[]
|
|
if cur = b
|
|
break 2
|
|
.
|
|
for i to n
|
|
if prev[i] = 0 and hammingdist w$[cur] w$[i] = 1
|
|
todon[] &= i
|
|
prev[i] = cur
|
|
.
|
|
.
|
|
.
|
|
swap todon[] todo[]
|
|
todon[] = [ ]
|
|
.
|
|
if cur = b
|
|
while cur <> a
|
|
seq$ = " -> " & w$[cur] & seq$
|
|
cur = prev[cur]
|
|
.
|
|
seq$ = w$[cur] & seq$
|
|
print seq$
|
|
else
|
|
print "No path"
|
|
.
|
|
.
|
|
ladder "boy" "man"
|
|
ladder "girl" "lady"
|
|
ladder "jane" "john"
|
|
ladder "child" "adult"
|
|
ladder "ada" "god"
|
|
ladder "rust" "hell"
|
|
#
|
|
# the content of unixdict.txt
|
|
input_data
|
|
10th
|
|
.
|
|
ada
|
|
bay
|
|
ban
|
|
boy
|
|
god
|
|
man
|
|
.
|