[しあわせのために]１〜２文字置換のダブレット[python]

「ふこうだ」と言う言葉と、「しあわせ」と言う言葉が１字置換のダブレットではどうしても繋がらなかったため(多分、大きい辞書を使っても無理でしょう）、１〜２文字置換のダブレットを解くプログラムをChatGPTに出力させました。最初は、辞書にない単語をstart,goalに指定するとエラーがでていましたが、辞書にない単語を指定されても自動的に内部辞書に登録し、正常に動作するようにしました。

`jm.txt`というのが辞書ファイルで、ひらがなの単語が一行に一つづつ並んだフォーマットになっています。

```plaintext:dbltj.py
#!/usr/bin/python
from collections import deque, defaultdict
import sys
import unicodedata
import re

dictionary = '/home/gar/org/doublet/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 add_word_dictionary(word,length_dict):
    k=split_kana(word)
    if all(j in kana_list for j in k):
        length=len(k)
        length_dict[length].add(word)
    return length_dict

def load_words_all():
    length_dict = defaultdict(set)
    with open(dictionary, encoding='utf-8') as f:
        for line in f:
            word = normalize(line)
            kana = split_kana(word)
            if all(k in kana_list for k in kana):
                length = len(kana)
                length_dict[length].add(word)
    return length_dict

def build_neighbor_index(words, max_diff=2):
    length = len(next(iter(words)))
    index = defaultdict(set)

    for word in words:
        kana = split_kana(word)
        for i in range(length):
            key1 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:])
            index[key1].add(word)

        if max_diff == 2:
            for i in range(length):
                for j in range(i+1, length):
                    key2 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:j]) + ("*",) + tuple(kana[j+1:])
                    index[key2].add(word)

    return index

def get_neighbors_fast(word, neighbor_index, max_diff=2, word_set=None):
    kana = split_kana(word)
    length = len(kana)
    candidates = set()

    for i in range(length):
        key1 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:])
        candidates.update(neighbor_index.get(key1, set()))

    if max_diff == 2:
        for i in range(length):
            for j in range(i+1, length):
                key2 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:j]) + ("*",) + tuple(kana[j+1:])
                candidates.update(neighbor_index.get(key2, set()))

    results = []
    for candidate in candidates:
        if candidate == word:
            continue
        if candidate not in word_set:
            continue
        candidate_kana = split_kana(candidate)
        if len(candidate_kana) != length:
            continue
        diff = sum(k1 != k2 for k1, k2 in zip(candidate_kana, kana))
        if 1 <= diff <= max_diff:
            results.append(candidate)

    return results

def solve_doublet(start, goal, words_by_length, max_diff=2):
    start_kana = split_kana(start)
    goal_kana = split_kana(goal)

    if len(start_kana) != len(goal_kana):
        return None

    length = len(start_kana)
    word_set = words_by_length[length]

    neighbor_index = build_neighbor_index(word_set, max_diff)

    visited = set([start])
    queue = deque([(start, [start])])

    while queue:
        current_word, path = queue.popleft()
        if current_word == goal:
            return path

        for neighbor in get_neighbors_fast(current_word, neighbor_index, max_diff, word_set):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None

if __name__ == '__main__':
    if len(sys.argv) != 3:
        print("使い方: python dbltj.py スタート単語 ゴール単語")
        sys.exit(1)

    start_word = normalize(sys.argv[1])
    goal_word = normalize(sys.argv[2])

    words_by_length = load_words_all()
    words_by_length = add_word_dictionary(start_word,words_by_length)
    words_by_length = add_word_dictionary(goal_word,words_by_length)

    if len(split_kana(start_word)) != len(split_kana(goal_word)):
        print("長さが合っていません。")
        sys.exit(1)

    result = solve_doublet(start_word, goal_word, words_by_length)

    if result:
        print("解:", len(result) - 2, ";", ",".join(result))
    else:
        print("解が見つかりませんでした。")

```

##### 実行例

```
% dbltj ふこうだ しあわせ
解: 3 ; ふこうだ,かこうひ,かしうり,かしわせ,しあわせ
% dbltj ふこうだ こうふく
解: 2 ; ふこうだ,ふううん,こうらん,こうふく
% dbltj しんどい しあわせ
解: 1 ; しんどい,しんみせ,しあわせ
% dbltj くるしい しあわせ
解: 2 ; くるしい,くるとん,しるわん,しあわせ
% dbltj こいこい しあわせ
解: 2 ; こいこい,こいとる,しあとる,しあわせ
% dbltj ごうもん しあわせ
解: 2 ; ごうもん,しつもん,しるわん,しあわせ
% dbltj ほいーる しあわせ
解: 2 ; ほいーる,しいする,しあがる,しあわせ
% dbltj さいあく しあわせ 
解: 2 ; さいあく,めいわく,めあわす,しあわせ
% dbltj がんばれ しあわせ
解: 2 ; がんばれ,しんばん,しんみせ,しあわせ
% dbltj とくれい まるちん 
解: 2 ; とくれい,りくれん,ばくちん,まるちん
% dbltj にくしみ しあわせ
解: 2 ; にくしみ,にくわえ,にがわせ,しあわせ
% dbltj あくれい しあわせ
解: 2 ; あくれい,しんれい,しんみせ,しあわせ
% dbltj わざわい しあわせ
解: 1 ; わざわい,わあわあ,しあわせ
% dbltj まるちん しあわせ
解: 1 ; まるちん,しるわん,しあわせ
% dbltj なんとか しあわせ
解: 2 ; なんとか,なおとき,しおわき,しあわせ
% dbltj くるしい しあわせ
解: 2 ; くるしい,くるわす,しるわん,しあわせ
% dbltj ぐたいてき くりすます
解: 5 ; ぐたいてき,さくいてき,とくいさき,とくいがる,とりすがる,くりすたる,くりすます
% dbltj たんじょうび なつかしい
解: 5 ; たんじょうび,きんようび,はんようき,はんかわき,はんかがい,はずかしい,なつかしい
% dbltj くりすます なつかしい
解: 5 ; くりすます,ききすます,ききすてる,なきすがる,ないすがい,ないかてい,なつかしい
% dbltj いきじごく くりすます
解: 5 ; いきじごく,いきじびき,いきのびる,いきかえる,とりかえる,くりかえす,くりすます
% dbltj いーすたー くりすます
解: 2 ; いーすたー,くらすたー,くりすたる,くりすます
% dbltj れおなるど いーすたー
解: 6 ; れおなるど,れおたーど,かすたーど,かんたーた,いんたーん,もんすーん,もんすたー,いーすたー
% dbltj かたやなぎ くりすます
解: 4 ; かたやなぎ,かたくなる,かたよせる,くりよせる,くりすたる,くりすます
% dbltj くりすます ありがとう
解: 5 ; くりすます,くりまわす,いいまわす,いいわたす,いいがたい,ありがたい,ありがとう
% dbltj ふこう かんしゃ 
解: 1 ; ふこう,かとう,かんしゃ
% dbltj つらい かんしゃ
解: 1 ; つらい,べんい,かんしゃ
% dbltj のろい かんしゃ
解: 1 ; のろい,じゅんい,かんしゃ
% dbltj うらみ かんしゃ
解: 1 ; うらみ,うんざ,かんしゃ
% dbltj あくま かんしゃ
解: 1 ; あくま,はくしゃ,かんしゃ
% doubletj きせき かんしゃ
解: 2 ; きせき,かせき,かんき,かんしゃ
% doubletj うんこ きせき 
解: 2 ; うんこ,きんこ,きんき,きせき
% dbltj ふるいゆめはおいていくがいい ふるいゆめはもっていくがいい
解: 0 ; ふるいゆめはおいていくがいい,ふるいゆめはもっていくがいい
% dbltj おまえをのろってやる おまえをすくってやる
解: 0 ; おまえをのろってやる,おまえをすくってやる
```

## 英字版

文字リストをちょっと変えただけですが。ASCIIコードはutf-8のサブセットなので、問題はありません。日本語版に、アルファベットを追加すると、かなとアルファベットが混交する単語はまずないので、一つのプログラムでできますが、辞書ファイルも違うし、出力するメッセージも違うので、別にしました。

```plaintext:dblt.py
#!/usr/bin/python
from collections import deque, defaultdict
import sys
import unicodedata
import re

dictionary = 'dic.txt'

kana_list = [
    'a','b','c','d','e','f','g','h','i','j','k','l','m',
    'n','o','p','q','r','s','t','u','v','w','x','y','z' ]

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 add_word_dictionary(word,length_dict):
    k=split_kana(word)
    if all(j in kana_list for j in k):
        length=len(k)
        length_dict[length].add(word)
    return length_dict

def load_words_all():
    length_dict = defaultdict(set)
    with open(dictionary, encoding='utf-8') as f:
        for line in f:
            word = normalize(line)
            kana = split_kana(word)
            if all(k in kana_list for k in kana):
                length = len(kana)
                length_dict[length].add(word)
    return length_dict

def build_neighbor_index(words, max_diff=2):
    length = len(next(iter(words)))
    index = defaultdict(set)

    for word in words:
        kana = split_kana(word)
        for i in range(length):
            key1 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:])
            index[key1].add(word)

        if max_diff == 2:
            for i in range(length):
                for j in range(i+1, length):
                    key2 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:j]) + ("*",) + tuple(kana[j+1:])
                    index[key2].add(word)

    return index

def get_neighbors_fast(word, neighbor_index, max_diff=2, word_set=None):
    kana = split_kana(word)
    length = len(kana)
    candidates = set()

    for i in range(length):
        key1 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:])
        candidates.update(neighbor_index.get(key1, set()))

    if max_diff == 2:
        for i in range(length):
            for j in range(i+1, length):
                key2 = tuple(kana[:i]) + ("*",) + tuple(kana[i+1:j]) + ("*",) + tuple(kana[j+1:])
                candidates.update(neighbor_index.get(key2, set()))

    results = []
    for candidate in candidates:
        if candidate == word:
            continue
        if candidate not in word_set:
            continue
        candidate_kana = split_kana(candidate)
        if len(candidate_kana) != length:
            continue
        diff = sum(k1 != k2 for k1, k2 in zip(candidate_kana, kana))
        if 1 <= diff <= max_diff:
            results.append(candidate)

    return results

def solve_doublet(start, goal, words_by_length, max_diff=2):
    start_kana = split_kana(start)
    goal_kana = split_kana(goal)

    if len(start_kana) != len(goal_kana):
        return None

    length = len(start_kana)
    word_set = words_by_length[length]

    neighbor_index = build_neighbor_index(word_set, max_diff)

    visited = set([start])
    queue = deque([(start, [start])])

    while queue:
        current_word, path = queue.popleft()
        if current_word == goal:
            return path

        for neighbor in get_neighbors_fast(current_word, neighbor_index, max_diff, word_set):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None

if __name__ == '__main__':
    if len(sys.argv) != 3:
        print("Usage: python dblt.py start goal")
        sys.exit(1)

    start_word = normalize(sys.argv[1])
    goal_word = normalize(sys.argv[2])

    words_by_length = load_words_all()
    words_by_length = add_word_dictionary(start_word,words_by_length)
    words_by_length = add_word_dictionary(goal_word,words_by_length)

    if len(split_kana(start_word)) != len(split_kana(goal_word)):
        print("Word length mismatch")
        sys.exit(1)

    result = solve_doublet(start_word, goal_word, words_by_length)

    if result:
        print("solution:", len(result) - 2, ";", ",".join(result))
    else:
        print("Solution can not be found.")

```

#### 実行例

```
% dblt.py woe joy
solution: 0 ; woe,joy
```