import gradio as gr
from itertools import permutations

def solve_cryptarithm(equation):
    try:
        # Parse the left and right parts of the equation
        left, right = equation.replace(" ", "").split("=")
        words = left.split("+") + [right]
    except ValueError:
        return "Invalid format. Use the format 'SEND + MORE = MONEY'."

    # Extract unique letters
    unique_letters = set("".join(words))
    if len(unique_letters) > 10:
        return "Error: Too many unique letters (more than 10), unsolvable with digits 0-9."

    # Function to convert words to numbers based on current letter-to-digit mapping
    def word_to_number(word, mapping):
        return int("".join(str(mapping[char]) for char in word))

    # Depth-First Search with pruning and backtracking
    def dfs(index, letter_to_digit, used_digits):
        # If all letters are assigned, check if the equation holds
        if index == len(unique_letters):
            left_sum = sum(word_to_number(word, letter_to_digit) for word in words[:-1])
            right_val = word_to_number(words[-1], letter_to_digit)
            return left_sum == right_val

        # Get current letter to assign
        letter = unique_letters_list[index]

        # Try assigning each digit to the letter
        for digit in range(10):
            # Skip used digits and avoid leading zero for multi-letter words
            if digit in used_digits or (digit == 0 and letter in leading_letters):
                continue

            # Assign the digit and proceed
            letter_to_digit[letter] = digit
            used_digits.add(digit)

            if dfs(index + 1, letter_to_digit, used_digits):
                return True  # Found a solution

            # Backtrack
            del letter_to_digit[letter]
            used_digits.remove(digit)

        return False  # No solution found along this path

    # Identify leading letters to avoid leading zeros
    leading_letters = {word[0] for word in words if len(word) > 1}
    unique_letters_list = list(unique_letters)
    letter_to_digit = {}
    used_digits = set()

    # Start DFS to find a solution
    if dfs(0, letter_to_digit, used_digits):
        # Format the result in the desired output format
        formatted_result = f"Input: {equation}\n\n"
        for i, word in enumerate(words):
            formatted_result += " ".join(str(letter_to_digit[char]) for char in word)
            if i < len(words) - 2:
                formatted_result += " + "
            elif i == len(words) - 2:
                formatted_result += " = "
        return formatted_result
    else:
        return f"No solution found for: {equation}"

def process_input(equations):
    results = []
    for equation in equations.splitlines():
        equation = equation.strip()
        if equation:
            result = solve_cryptarithm(equation)
            results.append(result)
    return "\n\n".join(results)

# Set up Gradio interface
interface = gr.Interface(
    fn=process_input,
    inputs=gr.Textbox(
        label="Enter Cryptarithm Equations (one per line)",
        placeholder="E.g., SEND + MORE = MONEY\nSEND + MORE = MONEY"
    ),
    outputs="text",
    title="Cryptarithm Solver",
    description="Enter cryptarithm equations (like SEND + MORE = MONEY) one per line to find solutions. Each letter represents a unique digit from 0-9."
)

# Launch the Gradio app
interface.launch()