話題のために：
「何もすることのない」二人の若い女性のために、ルイス・キャロルは「ダブレット」というゲームを考案し、1879年に、ロンドンの女性向け雑誌に掲載した。
単語を2つ与え、与えられた単語の文字を1字づつ置き換え、もう一つの与えられた単語に到達するゲームです。与えられた単語を「ダブレット」、途中の単語を「リンク」、ダブレットからダブレットまでを「チェーン」と言います。例えば、
head,heal,teal,tell,tall,tail
という風にです。チェーンが短いほどよいです。上記の例では、チェーンの長さは4です。
詳しくは、「不思議の国の論理学」（ルイス・キャロル：著、柳瀬尚紀：編訳）という本に載っています。
細かいルールもありますが、ここでは単語は辞書ファイルから自由に選択できるものとします。
コード
ChatGPTが出力したコードを少し手直ししました。
辞書ファイルはdictionaryという変数で指定します。
辞書ファイルを日本語のひらがなのファイルに置き換えると日本語用になりますが、日本語は拗音があるので、文字数では一致しても、拍が一致しないことがあるでしょう。
拍を合わせる場合、コードの改良が必要です。
chmod +x doublet.pyで実行権を与え、./doublet.py hate loveなどとして実行して下さい。
doublet.py
#!/usr/bin/python
from collections import deque
import sys
dictionary='/home/gar/dic/dic.txt'
def load_words(word_length):
# 単語リスト（辞書ファイルから読み込む）
with open(dictionary) as f:
words = set(word.strip().lower() for word in f if len(word.strip()) == word_length and word.strip().isalpha())
return words
def get_neighbors(word, word_set):
neighbors = []
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in word_set and new_word != word:
neighbors.append(new_word)
return neighbors
def solve_doublet(start, goal):
if len(start) != len(goal):
return None
word_set = load_words(len(start))
visited = set()
queue = deque([(start, [start])])
while queue:
current_word, path = queue.popleft()
if current_word == goal:
return path
for neighbor in get_neighbors(current_word, word_set):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # 解が見つからなかった場合
if __name__=='__main__':
start_word = sys.argv[1]
goal_word = sys.argv[2]
if len(start_word)!=len(goal_word):
print("長さが合っていません。")
exit(1)
result = solve_doublet(start_word, goal_word)
if result:
print("解:", len(result)-2, ";", ",".join(result))
else:
print("解が見つかりませんでした。")
日本語化したコード
拗音を一拍として数えるコードです。
辞書は、ひらがなに統一しておく必要があります。
doubletj.py
#!/usr/bin/python
from collections import deque
import sys
import unicodedata
import re
dictionary = '/home/gar/dic/jm.txt'
# 仮名の一覧（拗音含む）
kana_list = [
'あ','い','う','え','お',
'か','き','く','け','こ',
'が','ぎ','ぐ','げ','ご',
'さ','し','す','せ','そ',
'ざ','じ','ず','ぜ','ぞ',
'た','ち','つ','て','と',
'だ','ぢ','づ','で','ど',
'な','に','ぬ','ね','の',
'は','ひ','ふ','へ','ほ',
'ば','び','ぶ','べ','ぼ',
'ぱ','ぴ','ぷ','ぺ','ぽ',
'ま','み','む','め','も',
'や','ゆ','よ',
'ら','り','る','れ','ろ',
'わ','を','ん','ー',
'きゃ','きゅ','きょ',
'しゃ','しゅ','しょ',
'ちゃ','ちゅ','ちょ',
'にゃ','にゅ','にょ',
'ひゃ','ひゅ','ひょ',
'みゃ','みゅ','みょ',
'りゃ','りゅ','りょ',
'ぎゃ','ぎゅ','ぎょ',
'じゃ','じゅ','じょ',
'ぢゃ','ぢゅ','ぢょ',
'びゃ','びゅ','びょ',
'ぴゃ','ぴゅ','ぴょ',
]
# 長いものから順に並べて正規表現で抽出
kana_pattern = re.compile('|'.join(sorted(kana_list, key=len, reverse=True)))
def normalize(text):
return unicodedata.normalize('NFKC', text.strip().lower())
def split_kana(word):
return kana_pattern.findall(word)
def load_words(word_length):
with open(dictionary, encoding='utf-8') as f:
words = set()
for line in f:
word = normalize(line)
kana = split_kana(word)
if len(kana) == word_length and all(k in kana_list for k in kana):
words.add("".join(kana))
return words
def get_neighbors(word, word_set):
neighbors = []
kana = split_kana(word)
for i in range(len(kana)):
for k in kana_list:
if k != kana[i]:
new_kana = kana[:i] + [k] + kana[i+1:]
new_word = "".join(new_kana)
if new_word in word_set:
neighbors.append(new_word)
return neighbors
def solve_doublet(start, goal):
if len(split_kana(start)) != len(split_kana(goal)):
return None
word_set = load_words(len(split_kana(start)))
visited = set()
queue = deque([(start, [start])])
while queue:
current_word, path = queue.popleft()
if current_word == goal:
return path
for neighbor in get_neighbors(current_word, word_set):
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None
if __name__ == '__main__':
start_word = normalize(sys.argv[1])
goal_word = normalize(sys.argv[2])
if len(split_kana(start_word))!=len(split_kana(goal_word)):
print("長さが合っていません。")
exit(1)
result = solve_doublet(start_word, goal_word)
if result:
print("解:", len(result)-2, ";", ",".join(result))
else:
print("解が見つかりませんでした。")
実行例
% doubletj.py きゃべつ とまと
解: 3 ; きゃべつ,さべつ,さまつ,とまつ,とまと
%