Last active
November 5, 2018 18:08
-
-
Save dionisos2/e405c0cd007116a56500f44ead10971b to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import sys | |
import random | |
def parse_input(): | |
lines = [line for line in sys.stdin] | |
ly, lx = int(lines[0]), int(lines[1]) | |
board = [] | |
for y in range(ly): | |
line = "".join(l for l in lines[y+2] if l in ["p", "P", " "]) | |
board.append(('{:' + str(lx) + '}').format(line)) | |
return tuple(board) | |
def best_score(s1, s2): | |
if s1 == 0: | |
return s2 | |
if s2 == 0: | |
return s1 | |
if (s1 < 0) == (s2 < 0): | |
return min(s1, s2) | |
else: | |
return max(s1, s2) | |
def next_moves(board, white_turn): | |
ally, opponent, d = ("P", "p", -1) if white_turn else ("p", "P", 1) | |
lx, ly = len(board[0]), len(board) | |
pawns = [] | |
for x in range(lx): | |
for y in range(ly): | |
if board[y][x] == ally: | |
pawns.append((x, y)) | |
possible_moves = [] | |
for pawn in pawns: | |
x, y = pawn | |
if 0 <= y+d < ly: | |
up_line = board[y+d] | |
if up_line[x] == " ": | |
possible_moves.append([(x, y), (x, y+d), " "]) | |
for new_x in [x-1, x+1]: | |
if (0 <= new_x < lx) and (up_line[new_x] == opponent): | |
possible_moves.append([(x, y), (new_x, y+d), opponent]) | |
return possible_moves | |
def do_move(board, move): | |
start, end = move[:2] | |
sx, sy = start | |
ex, ey = end | |
board = list(board) | |
board[ey] = board[ey][:ex] + board[sy][sx] + board[ey][ex+1:] | |
board[sy] = board[sy][:sx] + " " + board[sy][sx+1:] | |
return tuple(board) | |
def solve(board, white_turn=True, opp_best=0): | |
global counter | |
counter += 1 | |
key = hash((board, white_turn, opp_best)) | |
if key in solve.dp: | |
return solve.dp[key] | |
possible_moves = next_moves(board, white_turn) | |
# We try the "best" move first | |
# It also allow to keep the same order for the same board and so the same opp_best | |
possible_moves.sort(key = lambda move : (move[1][1], move) if white_turn else (-move[1][1], move)) | |
wining_line = 0 if white_turn else len(board)-1 | |
best = 0 | |
for move in possible_moves: | |
if (move[1][1] == wining_line) or (best == 1): # Instant win | |
solve.dp[key] = 1 | |
return 1 | |
opp_min = (-best + 1) if best <= 0 else (-best - 1) | |
if best_score(opp_min, opp_best) == opp_best: # Opp_best was already better than that | |
solve.dp[key] = best | |
return best | |
next_board = do_move(board, move) | |
opp_score = solve(next_board, not white_turn, best) | |
score = (-opp_score + 1) if opp_score <= 0 else (-opp_score - 1) | |
best = best_score(best, score) | |
solve.dp[key] = best | |
return best | |
solve.dp = dict() | |
counter = 0 | |
b = parse_input() | |
print(solve(b)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment