Python, найти все возможные комбинации букв в заданном азбуке Морзе

Question

Мне пришлось найти все возможные комбинации букв в заданном азбуке Морзе. Длина расшифрованного слова может составлять максимум 10 букв . Данный файл с буквами и кодом Морзе выглядит следующим образом:

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   --..

Данный код Морзе выглядит так:

morse = '-.----.-.-...----.-.-.-.----.-'

Мой код выглядит так:

def morse_file_to_dict(filename):
    with open(filename) as file:
        return dict(line.strip().split() for line in file)


def word_to_morse(s, my_dict):
    return ''.join([my_dict[w] for w in s])


def adding_to_set(given_morse, my_set, my_dict, word='', start=0):
    for char in my_dict:
        if my_dict[char] == given_morse[start:start + len(my_dict[char])] and len(word) < 10:
            start = start + len(my_dict[char])
            word = word + char
            adding_to_set(given_morse, my_set, my_dict, word, start)
            if word_to_morse(word, my_dict) == given_morse:
                my_set.add(word)


words = set()
morse = '-.----.-.-...----.-.-.-.----.-'
pairs = morse_file_to_dict('morse_alphabet.txt')
adding_to_set(morse, words, pairs)
print(len(words))
print(words)

Мой вывод:

5
{'KMCBMQRKMK', 'KMCBMGKRMQ', 'KMCBMGCKMK', 'KMNCEJCCMQ', 'KMCDAMCCMQ'}

НО, ответ должен быть: 10571 слово, а не 5

Что я должен изменить, чтобы получить все из них? Спасибо за ваше время и ответ!

Answer 1

Я бы предложил использовать рекурсию и словарь для отображения азбуки Морзе на буквы (не буквы на азбуку Морзе):

morseFile="""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   --.."""

morse = {code:letter for line in morseFile.split("\n") for letter,code in [line.split()]}

Функция может быть построена как генератор, чтобы избежать сохранения всех возможностей в большой список:

def decode(coded,maxLen=10):
    if not maxLen: return
    for size in range(1,min(4,len(coded))+1):
        code = coded[:size]
        if code not in morse: continue
        remaining = coded[size:]
        if not remaining: yield morse[code]
        for rest in decode(remaining,maxLen-1):
            yield morse[code] + rest

вывод:

print(sum(1 for _ in decode("-.----.-.-...----.-.-.-.----.-")))

10571

for string in decode("-.----.-.-...----.-.-.-.----.-"):
    if len(string)<9: print(string)

YQLWGCYQ
YQLWQRYQ
YQLJNCYQ
YQLJKRYQ
YQLJCNYQ
YQLJCKWQ
YQLJCKJK
YQLJCCMQ
YQLJCCOK

Answer 2

c ++ решение:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

char buffer[26];
int l=0;
char *Morse[26];
//initializing Morse Code array
void initMorse(){
Morse[0] = "._" ;            
Morse[1] = "_...";            
Morse[2] = "_._." ;            
Morse[3] = "_.." ;            
Morse[4] = "." ;   //E         
Morse[5] = ".._." ;            
Morse[6] = "__." ;            
Morse[7] = "...." ;  //H          
Morse[8] = ".." ;       //I     
Morse[9] = ".___" ;   //J         
Morse[10] = "_._" ;  //K            
Morse[11] = "._.." ;            
Morse[12] = "__" ;   //M         
Morse[13] = "_." ;            
Morse[14] = "___" ;     //O       
Morse[15] = ".__." ;  //P            
Morse[16] = "__._" ;            
Morse[17] = "._." ;   //R         
Morse[18] = "..." ;            
Morse[19] = "_" ;            
Morse[20] = ".._" ;            
Morse[21] = "..._" ;  //V          
Morse[22] = ".__" ;            
Morse[23] = "_.._" ;            
Morse[24] = "_.__" ;            
Morse[25] = "__.." ; //Z
}
int solution(char *s,int strt,char **Morse,int len){
    int i,j,noMatch=0,k,prev,tem;
    int mlen;
    if(strt!=len)
    for(i=0;i<26;i++){
    mlen=strlen(Morse[i]);
     if(strt+mlen<=len){
        for(j=strt,k=0;j<strt+mlen&&k<mlen;j++,k++){
            if(Morse[i][k]==s[j])
                continue;
            else {
                noMatch=1;
                break;
            }
        }
    }
    else{
        continue;   
    }
    if(noMatch==0){
         //print pattern when complete string matched
         if(strt+mlen==len){
          buffer[l]=i+65;
             printf("%s\n",buffer);
             buffer[l]=0;
        }
        else{
            noMatch=0;  
            buffer[l]=i+65;
            l++;
            solution(s,strt+mlen,Morse,len);
            l--;                 // while backtracking 
            buffer[l]=0;      //  clearing buffer just upto the previous location 
        }
    }
    else{
        noMatch=0;
    }
}
else{
    buffer[l]=0;
}
return 1;
}

int main() {

char s[100];
printf("Enter the input string of Morse code:\n");
scanf("%s",s);
initMorse();
printf("Possible translations are:\n");
solution(s,0,Morse,strlen(s));
for
return 0;
}