we have the middle states of all 3 pegs and we have to make an algorithm to find the initial peg on which these all disks was in the start. we have all 3 middle states and the number of moves it takes from initial state to reach the current state. For example we have middle states value peg A = 1, peg B = 2, Peg C = 3 and the number of moves it takes from starting position to reach this state is 2. Like given is 1,2,3 and we can see that place B=2 on C=3 that will become C=3,2 and after it place A=1 on C=3,2 so that will become C=3, 2, 1 on Peg 3. We can see exact after 2 moves we get our initial position where we started. Now in the same way we can give A= 1 2 3, B= 4,5 and C = 7,8,9 Now each Peg have 3,2,3 disks respectively and we have to place all disks on 1 Peg and find where they were before they moved to all three Pegs. If there is no way to reach that position then simply return impossible.
I am trying to find the initial Peg by this approach but not getting the correct Peg as shown in the sample output
def find_initial_state(current_state, moves):
# Initialize the initial state as an empty list
initial_state = [[] for _ in range(3)]
# Create a function to check if a state is valid
def is_valid_state(state):
total_disks = sum(len(peg) for peg in state)
return total_disks > 0 and max(max(peg) for peg in state) < len(state)
# Create a function to simulate a move
def simulate_move(state, peg1, peg2):
disk = state[peg1].pop()
state[peg2].append(disk)
# Create a function to undo a move
def undo_move(state, peg1, peg2):
disk = state[peg2].pop()
state[peg1].append(disk)
# Simulate the given number of moves
state = current_state.copy()
for _ in range(moves):
# Choose the peg with the largest disk
max_peg = max(range(3), key=lambda x: state[x][-1] if state[x] else 0)
# Find the next largest disk that can be moved
for peg in range(3):
if state[peg] and state[peg][-1] < state[max_peg][-1]:
break
else:
# If all disks are on the largest peg, move the largest disk
peg = max_peg
# Simulate the move
simulate_move(state, peg, max_peg)
# Check if the current state is valid
if is_valid_state(state):
# If the current state is valid, it is the initial state
return state
# Undo the move
undo_move(state, peg, max_peg)
# If no valid initial state is found, return "impossible"
return "impossible"
Here is the complete question for better understanding The Tower of Hanoi is a mathematical puzzle invented by the French mathematician Édouard Lucas in 1883. There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it, surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks in accordance with the immutable rules of Brahma since that time. The puzzle configuration and rules are as follows: • There are n disks and three pegs: A, B, C. The n disks are different in size, and all disks are initially placed on peg A that their sizes increase from top to bottom. • Only one disk can be moved at a time, from the top of a peg to an empty peg or to a peg with a larger disk than itself on top. • The goal is to move all n disks from peg A to either peg B or peg C – this is the goal of the original tower of Hanoi puzzle, but our goal in this question is slightly different.
It is easy to prove that the minimum number of moves needed to complete the puzzle with n disks is 2n-1 using recursion. Given a state with all disks on peg A, A simple algorithm to move all disks to another peg with the minimum number of moves is to move the smallest disk (disk 1: D1) on odd moves (the 1st, 3rd, 5th… moves) in a circular manner ABCABC… (clockwise, as shown left); and make the only possible move which does not involve disk 1 on even moves (the 2nd, 4th, 6th… moves). For example, with 3 disks initially placed on peg A, 5 moves will lead to a state of having D1 on A, D2 on C and D3 on B as shown left. According to the simple algorithm above, the 5 moves are: (D1:A→B), (D2:A→C), (D1:B→C), (D3:A→B) and (D1:C→A) where D1 is the smallest disk, D3 is the largest disk and (D2:A→C) means disk 2 (the middle disk) is moved from peg A to peg C. In this question, the above moving procedure can start from any of three pegs, A, B, or C, and the first task is to discover which peg these disks were originally on given the current state of n disks placed on pegs A, B and C with their sizes increasing from top to bottom. The second task is to determine the state from the current input state after m moves where m is the additional input.
Each set of test inputs begins with a number indicating the number of test cases below, and each test case is described by a line describing the state with disks on pegs A, B, C separated by commas, followed by the number of moves m. Within the segment separated by commas are the disks on the same peg in ascending order separated by space. For each test case, output (i) the initial peg, and (ii) the state after m moves following the same format as the input. Output “impossible” if no matter which peg to start with, the described state is non-reachable. The number of moves should be between 0 and 2n-1 both inclusive, and if the ending state has reached, i.e., all disks are on the same peg, the moving process ends and no further moves are possible. For the special case that all disks are on the same peg as an input state, as this state can be an initial state or an ending state, please take it as an initial state.
You need to modify the function tower_hanoi. The total number of disks is between 3 and 64.
Sample Input
10
1, 2, 3, 2
1, 3, 2, 3
2 3 6 7 8 9, 1 4, 5 10, 362
2 3 8 9, 1 4 5 6, 7, 40
1 10 13 16, 9 14 17 18, 2 3 4 5 6 7 8 11 12 15, 134966
5 10 11 14 15 16, 1 2 3 4 13 18, 6 7 8 9 12 17, 52720
, 1 2 3 4 5, , 31
4 7 8 11 12 15 18, 3 6 9 14 19, 1 2 5 10 13 16 17, 328156
8 11 12, 1 4 5 6, 2 3 7 9 10 13, 4563
1 4 5 10, 7 8 11 12 13, 2 3 6 9, 4258
Sample Output
C, 3, 1 2,
A, , 1 2 3,
C, 3 4 7, 6 9 10, 1 2 5 8
C, 1 6 7 8 9, , 2 3 4 5
B, 4 7 8 9 10 15 18, 1 2 3 16, 5 6 11 12 13 14 17
B, 1 2 3 4 5 6 7 8 9 10, 12 13 18, 11 14 15 16 17
B, , , 1 2 3 4 5
B, 5 6 9 10 13 16, 1 2 3 4 7 12 15, 8 11 14 17 18 19
impossible
B, 3 8 11 12, 4 5 6 7, 1 2 9 10 13
And here is the provided code
import sys
def state_to_str(state):
s = [' '.join([str(j) for j in state[i]]) for i in range(3)]
return ', '.join(s).strip()
def tower_hanoi(n, state):
print('You may use this function to print a state:', state_to_str(state))
return 'impossible'
num_case = int(sys.stdin.readline())
for _ in range(num_case):
s = sys.stdin.readline().split(',')
state, mm = [[int(r) for r in t.split()] for t in s[:3]], int(s[3])
n = len(state[0]) + len(state[1]) + len(state[2])
print(tower_hanoi(n, state))