# Untitled

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")