Porting Doublet-Solver from python2 to python3 on Github. Also serves as an introduction.
A doublet is a puzzle that replaces words one by one and connects them. The two given words are called
It seems that the first word, the last word and << required number of links >> are specified. Lewis Carroll is said to have been serialized in a weekly magazine for women in London. It is published in the book "Logic in Wonderland".
The transplant works in the following three ways. (1) Delete import urllib2 because it is not needed. ② Change xrange () to range (). ③ Add () to print.
In the code here
① To be able to take arguments from the command line
(2) To handle even undefined arguments in the dictionary
③ According to the historical method, output by
Doublet-solver can be written so simply in python, isn't it? surprised.
It also supports Japanese. The English dictionary'dic.txt' and the Japanese dictionary'jd.txt' can be found at here . To change the dictionary, change the file name that #dictionary opens in the code.
CODE
doublet.py
#!/usr/bin/python3
import sys
from collections import defaultdict
def allwordsoflength(l, all):
return set([x.lower().strip() for x in all if len(x.lower().strip()) == l])
def wildcard(s, idx):
return s[:idx] + '?' + s[idx+1:]
def wildcarded(s):
for idx in range(len(s)):
yield wildcard(s, idx)
def buildindex(all):
index = defaultdict(list)
for w in all:
for wild in wildcarded(w):
index[wild.lower()].append(w)
return index
def oneaway(word, index):
ret = []
for w in wildcarded(word):
ret += index[w]
return ret
def srch(start, end, all, maxdepth = 100):
ftree = [(start, 0, [])]
done = [start]
alloflen = allwordsoflength(len(start), all)
index = buildindex(alloflen)
for e in ftree:
if e[1] > maxdepth:
return 'Reached Max Depth.'
children = oneaway(e[0], index)
children = list(set(children) - set(done))
if children == [] and e == ftree[-1]:
return 'Search Exhausted.'
if end in children:
return (e[1] , ' '.join(e[2] + [e[0], end]))
for n in children:
ftree.append((n, e[1] + 1, e[2] + [e[0]]))
done = list(set(done) | set(children))
words = [ x for x in open("dic.txt") ] # dictionary
args = sys.argv
a = args[1].lower()
b = args[2].lower()
if len(a)!=len(b):
print("Length of strings mismatch!")
exit(1)
words.append(a)
words.append(b)
print (srch(a,b, words))
Execution example
$ doublet.py alice maria
(6, 'alice aline cline caine maine marne marie maria')
$ doublet.py hate love
(2, 'hate have lave love')
$ doublet.py work rest
(3, 'work wort wert west rest')
$
$ dbltj.py sanji snack
(2, 'Sanji Onji Oyaji Snack')
$ dbltj.py apple mandarin
(3, 'Apples Apples')
$ dbltj.py Hiruma kettle
(3, 'Hiruma Hida Hida Hikan Kettle')
$ dbltj.py greeting good morning
(6, 'Greetings Greetings Heisou Hesso Hesso Hesso Hessou Good morning Good morning')
$
Recommended Posts