86 lines
2.7 KiB
Python
86 lines
2.7 KiB
Python
import sys
|
|
from collections import deque
|
|
|
|
class towersolve:
|
|
def __init__(self, matrix):
|
|
self.matrix = matrix
|
|
self.visited = set()
|
|
self.queue = deque([(matrix, [])])
|
|
|
|
def solve(self):
|
|
while self.queue:
|
|
c_matrix, steps = self.queue.popleft()
|
|
state = self.m2t(c_matrix)
|
|
|
|
if state in self.visited:
|
|
continue
|
|
self.visited.add(state)
|
|
|
|
if self.is_goal_state(c_matrix):
|
|
return steps
|
|
|
|
zero_pos = self.find0(c_matrix)
|
|
self.explore(c_matrix, steps, zero_pos)
|
|
|
|
return None
|
|
|
|
@staticmethod
|
|
def m2t(matrix):
|
|
return tuple(tuple(row) for row in matrix)
|
|
|
|
@staticmethod
|
|
def is_goal_state(matrix):
|
|
for col in range(len(matrix[0])):
|
|
non_zero_numbers = [row[col] for row in matrix if row[col] != 0]
|
|
if non_zero_numbers and non_zero_numbers.count(non_zero_numbers[0]) != len(non_zero_numbers):
|
|
return False
|
|
return True
|
|
|
|
@staticmethod
|
|
def rotate(matrix, row_index, vec):
|
|
row = matrix[row_index]
|
|
if vec == -1:
|
|
row = row[1:] + row[:1]
|
|
elif vec == 1:
|
|
row = row[-1:] + row[:-1]
|
|
matrix[row_index] = row
|
|
return matrix
|
|
|
|
@staticmethod
|
|
def move0(matrix, zero_pos, vec):
|
|
row, col = zero_pos
|
|
if vec == 1 and row > 0: # Swapped the directions
|
|
matrix[row][col], matrix[row - 1][col] = matrix[row - 1][col], 0
|
|
elif vec == -1 and row < len(matrix) - 1: # Swapped the directions
|
|
matrix[row][col], matrix[row + 1][col] = matrix[row + 1][col], 0
|
|
return matrix
|
|
|
|
@staticmethod
|
|
def find0(matrix):
|
|
for i, row in enumerate(matrix):
|
|
for j, value in enumerate(row):
|
|
if value == 0:
|
|
return i, j
|
|
return None
|
|
|
|
def explore(self, c_mat, steps, zero_pos):
|
|
for row_index in range(len(c_mat)):
|
|
for vec in [-1, 1]:
|
|
new_matrix = self.rotate([row[:] for row in c_mat], row_index, vec)
|
|
new_steps = steps + [f"r {row_index} {vec}"]
|
|
self.queue.append((new_matrix, new_steps))
|
|
|
|
for vec in [-1, 1]:
|
|
new_matrix = self.move0([row[:] for row in c_mat], zero_pos, vec)
|
|
new_steps = steps + [f"m {vec}"]
|
|
self.queue.append((new_matrix, new_steps))
|
|
|
|
def read_mat(file_path):
|
|
with open(file_path, "r") as file:
|
|
return [[int(num) for num in line.split()] for line in file]
|
|
|
|
if __name__ == "__main__":
|
|
_input = read_mat(sys.argv[1])
|
|
solver = towersolve(_input)
|
|
sol = solver.solve()
|
|
print(",".join(sol))
|