BFS-based Solver for the Game Beltmatic

beltmatic_solver.py

#!/usr/bin/python3

from collections import deque

MAX_NUMBER = 18

# Define operations as functions
def add(x, y): return x + y
def sub(x, y): return x - y
def mul(x, y): return x * y
def exp(x, y): return x ** y
def div(x, y):
    if y == 0: return None
    q, r = divmod(x, y)
    return (q, r)

operations = [
    ('+', add),
    ('-', sub),
    ('*', mul),
    ('^', exp),
    ('/', div)
]

def construct_number(target):
    # Initialize BFS queue with initial numbers and their operations
    queue = deque([(num, [(num, '')]) for num in range(1, MAX_NUMBER) if num != 10])
    seen = set(num for num in range(1, MAX_NUMBER) if num != 10)

    while queue:
        current_value, operations_list = queue.popleft()

        if current_value == target:
            return operations_list

        for num in [num for num in range(1, MAX_NUMBER) if num != 10]:
            for symbol, operation in operations:
                if symbol == '/':
                    result = operation(current_value, num)
                    if result:
                        quotient, remainder = result
                        if quotient not in seen:
                            seen.add(quotient)
                            queue.append((quotient, operations_list + [(quotient, symbol, num)]))
                        if remainder not in seen and remainder != 0:
                            seen.add(remainder)
                            queue.append((remainder, operations_list + [(remainder, '%', num)]))
                else:
                    result = operation(current_value, num)
                    if result not in seen:
                        seen.add(result)
                        queue.append((result, operations_list + [(result, symbol, num)]))

    return []

def format_operations(operations_list):
    formatted = []
    for i, operation in enumerate(operations_list):
        if i == 0:
            formatted.append(str(operation[0]))
        else:
            formatted.append(f"{operations_list[i-1][0]} {operation[1]} {operation[2]} = {operation[0]}")
    return formatted

if __name__ == "__main__":
    target_number = int(input("Enter the target number: "))
    sequence = construct_number(target_number)
    if sequence:
        print("Sequence of operations:", format_operations(sequence))
    else:
        print("No sequence found to construct the target number.")