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

Recommended Posts

Porting and modifying doublet-solver from python2 to python3.
From Python to using MeCab (and CaboCha)
Changes from Python 3.0 to Python 3.5
Changes from Python 2 to Python 3.0
[Python] How to read data from CIFAR-10 and CIFAR-100
Post from Python to Slack
Cheating from PHP to Python
Porting from argparse to hydra
Tips and precautions when porting MATLAB programs to Python
Switch from python2.7 to python3.6 (centos7)
Connect to sqlite from python
Python regular expression basics and tips to learn from scratch
How to connect to various DBs from Python (PEP 249) and SQLAlchemy
Go language to see and remember Part 8 Call GO language from Python
[Introduction to Python3 Day 1] Programming and Python
Python, yield, return, and sometimes yield from
Create folders from '01' to '12' with python
[Lambda] [Python] Post to Twitter from Lambda!
Read and use Python files from Python
About Python, from and import, as
Connect to utf8mb4 database from python
Python (from first time to execution)
Post images from Python to Tumblr
Python logging and dump to json
How to access wikipedia from python
Python to switch from another language
Selenium and python to open google
Did not change from Python 2 to 3
Update Python on Mac from 2 to 3
How to get followers and followers from python using the Mastodon API
[Python] Try to recognize characters from images with OpenCV and pyocr
[Python] Fluid simulation: From linear to non-linear
How to package and distribute Python scripts
Bind methods to Python classes and instances
How to update Google Sheets from Python
Send a message from Python to Slack
Fractal to make and play with Python
I want to use jar from python
Connecting from python to MySQL on CentOS 6.4
How to access RDS from Lambda (python)
Read Python csv and export to txt
python: How to use locals () and globals ()
Python> Output numbers from 1 to 100, 501 to 600> For csv
[Python] How to calculate MAE and RMSE
How to use Python zip and enumerate
Compress python data and write to sqlite
Convert from Markdown to HTML in Python
[Amazon Linux] Switching from Python 2 series to Python 3 series
API explanation to touch mastodon from python
How to use is and == in Python
Connect to coincheck's Websocket API from Python
C language to see and remember Part 2 Call C language from Python (argument) string
Migration from Python2 to Python3 (Python2 is rebuilt as a virtual environment and coexists)
C language to see and remember Part 1 Call C language from Python (hello world)
Connect to postgreSQL from Python and use stored procedures in a loop.
Try to write python code to generate go code --Try porting JSON-to-Go and so on
C language to see and remember Part 4 Call C language from Python (argument) double
[python] Send the image captured from the webcam to the server and save it
C language to see and remember Part 5 Call C language from Python (argument) Array
Send a message from Slack to a Python server
Try porting the "FORTRAN77 Numerical Computing Programming" program to C and Python (Part 1)