Discussion on A Chessboard Game Challenge

4 months ago+ 0 comments

I implemented a solution using a more intuitive and naive way for me where i explicitly coded both player logic which player1 always choose the wining position and player2 always choose the losing position. It's kinda mind blowing to me you can completly hide player2's logic by defining it to be player1 always force the next state to lose state after reading editorial. Just going to share my code here:

'''
1 = win, 0 = lose
p0 = player 1 choose any win state 
p1 = player 2 choose any lose state
'''
def is_inbound(x, y):
    n = 15
    if x > n or y > n or x < 1 or y < 1:
        return False
    return True

hm = {}
def helper(x, y, p):        
    nxt_p = not p
    delta = [(-2, 1), (-2, -1), (1, -2), (-1, -2)]
    states = []
    nxt_pos = []
    res = 0
    # check next possible moves
    for d in delta:
        xd, yd = x+d[0], y+d[1]
        if is_inbound(xd, yd):
            nxt_pos.append((xd, yd))
    # no possible move
    if not nxt_pos:
        if p:
            return 1
        else:
            return 0 
    # recurse every valid move with memo
    for pos in nxt_pos:
        cur = (pos[0],pos[1],nxt_p)
        if cur in hm:
            state = hm[cur]
        else:
            state = helper(*cur)
            hm[cur] = state
        states.append(state)
    # logic of optimal play
    res = all(states) if p else any(states)
    return res

def chessboardGame(x, y):
    # Write your code here
    res = helper(x,y, 0)
    return  'First' if res else 'Second'

Cookie support is required to access HackerRank