Untitled

mail@pastecode.io avatar
unknown
python
a year ago
2.5 kB
21
Indexable
Never
import math

# Function to apply the necessary operations to a given number
def apply_ops(num, goal):
    # Initialize the resulting nodes
    floor_num, sqrt_num, factorial_num = None, None, None
    # If the goal is a smaller number than the start node, apply the floor operation
    if goal < num:
        floor_num = math.floor(num)
    # If the goal is a perfect square, apply the square root operation
    if math.isqrt(goal)**2 == goal:
        if math.isqrt(num)**2 == num:
            sqrt_num = math.isqrt(num)
    # If the goal is a factorial of an integer, apply the factorial operation
    if math.factorial(int(goal)) == goal:
        if num == int(num):
            factorial_num = math.factorial(int(num))
    # Return the floor of the number only if it has not been applied before
    if floor_num == num:
        floor_num = None
    return floor_num, sqrt_num, factorial_num

# Function to perform iterative deepening depth-first search
def iddfs(goal, visited, path, depth):
    # If the start node is the goal node, return the path
    if 4 == goal:
        return path
    # If the maximum depth is reached, return None
    if depth == 0:
        return None
    # Mark the start node as visited
    visited.add(4)
    # Apply the necessary operations to the start node
    floor_num, sqrt_num, factorial_num = apply_ops(4, goal)
    # Add the resulting nodes to the path if they are not visited
    if floor_num is not None and floor_num not in visited:
        result = iddfs(goal, visited, path+[("floor", floor_num)], depth-1)
        if result is not None:
            return result
    if sqrt_num is not None and sqrt_num not in visited:
        result = iddfs(goal, visited, path+[("sqrt", sqrt_num)], depth-1)
        if result is not None:
            return result
    if factorial_num is not None and factorial_num not in visited:
        result = iddfs(goal, visited, path+[("factorial", factorial_num)], depth-1)
        if result is not None:
            return result
    # Return None if the goal is not reached
    return None

# Test the function
goal = 5
result = None
depth = 1
while result is None:
    result = iddfs(goal, set(), [("start", 4)], depth)
    # Increment the depth limit
    depth += 1

# Print the results
if result is not None:
    print("The shortest path from 4 to {} is:".format(goal))
    for i, (op, num) in enumerate(result[1:]):
        print("Step {}: {} {}".format(i+1, op, num))
else:
    print("No solution found")