Porting and modifying doublet-solver from python2 to python3.

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 , the words in the middle are called , and the words from doublet to doublet are called . As long as you have a word, the shortest step of replacing one letter with a word that is n different is n times.

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 instead of the number of conversion steps. ④ Treat in lowercase And four corrections have been added.

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