Próbuje uporać się z tym problemem od paru godzin, mimo to po za kilkoma brutowymi rozwiązaniami, które i tak nie działały nic nie zrobiłem.. Może ktoś ma jakiś pomysł?
No ale przecież w tym zadaniu jasno napisali że masz zrobić bruta "na pałe" bo plansza ma 8x8 a maksymalny poziom zagłębienia to 8. Więc testujesz wszystkie możliwe ruchy i wybierasz najlepszą sekwencje. Piszesz więc funkcje rekurencyjną:
def solve(board, moves=[], level=0):
score = calculate_score(board)
if score == 0:
return moves
elif level == 8:
return None
else:
shortest_sequence = [None for i in range(17)]
for possible_move in available_moves(board):
new_board = make_move(board, possible_move)
new_moves = solve(new_board, moves + possible_move, level + 1)
if new_moves is not None and len(new_moves) < len(shortest_sequence):
shortest_sequence = new_moves
return shortest_sequence
Czyli:
- Jeśli mamy już 0 kulek to zwracamy listę ruchów które nas do tego doprowadziły
- Jeśli jesteśmy już po 8 ruchach i nadal nie mamy 0, to zwracamy None, bo ta ścieżka jest zła
- Jeśli nie mamy jeszcze 0 ale mozemy wykonywać ruchy, to testujemy każdy możliwy ruch i sprawdzamy co dostaniemy jeśli go wykonamy. Jeśli dostaniemy jakąś listę ruchów (a nie None) to znaczy że dany ruch prowadzi do sytuacji gdzie dochodzimy do 0 kulek. Zapamiętujemy sobie najkrótszą taką sekwencje i zwracamy ją z funkcji.
Niemniej samo zadanie jest moim zdaniem dość głupie, bo algorytm rozwiązywania gry jest dość prosty, za to implementacja całej logiki do tego zadania jest mega żmudne tak na oko :)
Oo no tak, za bardzo sobie pokomplikowałem ten algorytm, teraz jest to dużo jaśniejsze, dzięki ;)
No tylko że to jest mimo wszystko dość skomplikowane ->
def print_board(board):
print("\n".join([" ".join(line) for line in board]) + "\n")
def calculate_score(board):
return sum([sum([1 for field in line if field != '.']) for line in board])
def available_moves(board):
moves = []
size = len(board)
for i in range(size):
for j in range(size - 1):
moves.append(((i, j), (i, j + 1)))
moves.append(((i, j + 1), (i, j)))
moves.append(((j, i), (j + 1, i)))
moves.append(((j + 1, i), (j, i)))
return moves
def swap(board, possible_move):
new_board = [[field for field in line] for line in board]
source, target = possible_move
tmp = board[target[0]][target[1]]
new_board[target[0]][target[1]] = board[source[0]][source[1]]
new_board[source[0]][source[1]] = tmp
return new_board
def simplify_rows(board):
to_remove = []
for row in range(len(board)):
identical = 1
for col in range(len(board[0]) - 1):
if board[row][col] != '.' and board[row][col] == board[row][col + 1]:
identical += 1
else:
identical = 1
if identical >= 3:
to_remove.extend([(row, col - c + 1) for c in range(identical)])
return set(to_remove)
def simplify_cols(board):
to_remove = []
for col in range(len(board)):
identical = 1
for row in range(len(board[0]) - 1):
if board[row][col] != '.' and board[row][col] == board[row + 1][col]:
identical += 1
else:
identical = 1
if identical >= 3:
to_remove.extend([(row - r + 1, col) for r in range(identical)])
return set(to_remove)
def gravity_drop(board):
size = len(board)
for row in range(size):
for col in range(size):
if board[size - row - 1][col] == '.':
for up_row in range(size - row - 1, -1, -1):
if board[up_row][col] != '.':
board[size - row - 1][col] = board[up_row][col]
board[up_row][col] = '.'
break
return board
def simplify(board):
to_remove = []
to_remove.extend(simplify_rows(board))
to_remove.extend(simplify_cols(board))
for x, y in to_remove:
board[x][y] = '.'
if len(to_remove) > 0:
board = gravity_drop(board)
return simplify(board)
return board
def make_move(board, possible_move):
new_board = swap(board, possible_move)
return simplify(new_board)
def to_text(moves):
return "".join(["".join(map(str, list(source))) + "".join(map(str, list(target))) for (source, target) in moves])
def is_lexicographically_smaller(solution1, solution2):
return to_text(solution1) < to_text(solution2)
def solve(board, moves=[], level=0):
score = calculate_score(board)
if score == 0:
return moves
elif level == 8:
return None
else:
shortest_sequence = [None for i in range(999)]
for possible_move in available_moves(board):
new_board = make_move(board, possible_move)
new_score = calculate_score(new_board)
if new_score == score:
continue
new_moves = solve(new_board, moves + [possible_move], level + 1)
if new_moves is not None:
if len(new_moves) < len(shortest_sequence):
shortest_sequence = new_moves
elif len(new_moves) == len(shortest_sequence) and is_lexicographically_smaller(new_moves, shortest_sequence):
shortest_sequence = new_moves
if None not in shortest_sequence:
return shortest_sequence
else:
return None
def main():
data = """........
........
........
........
........
.01.....
.10.....
.01....."""
board = [list(x) for x in data.split("\n")]
print(solve(board))
main()
(numeruje wiersze i kolumny od 0, więc ten wynik (6, 1), (6, 2)
to jest to co w przykładzie z zadania 7 2 7 3
).
Ale tak jak pisalem wcześniej, sama funkcja rekurencyjna jest dość prosta w porównaniu z tym usuwaniem wierszy/kolumn i przesuwaniem kulek w dół na wolne miejsca... ;]
Dzięki za zaklepanie tego algorytmu, mój nie był jednak wolny od błędów bo funkcja usuwająca kulki za pomocą grawitacji nie działała tak jak powinna ;d