morse-code.py

def decode(morse_string, target_checksum):
    """
    Decode a compact Morse code string and return all valid interpretations
    that match the given checksum.
    
    Args:
        morse_string: String of dots and dashes without pauses
        target_checksum: The expected checksum value
    
    Returns:
        List of valid decoded messages
    """
    # Morse code alphabet (ITU standard)
    morse_code = {
        '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': '--..',
        '1': '.----', '2': '..---', '3': '...--', '4': '....-',
        '5': '.....', '6': '-....', '7': '--...', '8': '---..',
        '9': '----.', '0': '-----'
    }
    
    # Create reverse mapping (morse -> character)
    char_to_morse = morse_code
    morse_to_char = {v: k for k, v in morse_code.items()}
    
    # Create alphabet ordered list for checksum calculation
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
    char_to_index = {c: i for i, c in enumerate(alphabet)}
    
    def calculate_checksum(message):
        """Calculate checksum for a given message."""
        checksum = 0
        for char in message:
            checksum = (checksum * 10 + char_to_index[char]) % 2048
        return checksum
    
    def find_interpretations(morse_str, current_message, current_checksum):
        """
        Recursively find all valid interpretations of the morse string.
        
        Args:
            morse_str: Remaining morse string to decode
            current_message: Message decoded so far
            current_checksum: Checksum computed so far
        
        Returns:
            List of valid complete messages
        """
        # Base case: if we've consumed all the morse string
        if not morse_str:
            if current_checksum == target_checksum:
                return [current_message]
            else:
                return []
        
        results = []
        
        # Try matching each possible morse code pattern from current position
        for length in range(1, min(6, len(morse_str) + 1)):  # Max morse length is 5
            prefix = morse_str[:length]
            
            if prefix in morse_to_char:
                char = morse_to_char[prefix]
                new_checksum = (current_checksum * 10 + char_to_index[char]) % 2048
                remaining = morse_str[length:]
                
                # Recursively process the remaining string
                results.extend(
                    find_interpretations(remaining, current_message + char, new_checksum)
                )
        
        return results
    
    # Start the recursive search
    return find_interpretations(morse_string, "", 0)


# Test with the provided example
if __name__ == "__main__":
    # Example: HELLO
    morse_input = "......-...-..---"
    checksum = 1496
    
    result = decode(morse_input, checksum)
    print(f"Input: {morse_input}")
    print(f"Checksum: {checksum}")
    print(f"Valid interpretations: {result}")
    
    # Verify the checksum calculation for HELLO
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
    message = "HELLO"
    check = 0
    for char in message:
        idx = alphabet.index(char)
        check = (check * 10 + idx) % 2048
        print(f"{char}: ({check // 10} × 10 + {idx}) mod 2048 = {check}")
    
    print(f"\nFinal checksum: {check}")