We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Play on benders
  5. Discussions

Play on benders

  • andy010725
     + 0 comments

    All pass with python. but need to add build_g_table() to main on the place before it call bendersPlay. Need the knowledge of grundy number and Game Theory

    G_table = []

def build_g_table(n, paths):
    global G_table
    next_table = [ [] for i in range(1+n) ]
    G_table = [ None for i in range(1+n) ]
    
    for a,b in paths:
        next_table[a].append(b)

    for i in range(1, 1+n):
        if not next_table[i]:
            G_table[i] = 0

    def calculate_g_val(i, G_table):
        if G_table[i] is not None:
            return G_table[i]
        check_list = [1]*100
        for next_ in next_table[i]:
            if G_table[next_] is None:
                calculate_g_val(next_, G_table)
            temp = G_table[next_]
            check_list[temp] = 0
        grundy_val = check_list.index(1)
        G_table[i] = grundy_val

    for i in range(1, 1+n):
        calculate_g_val(i, G_table)

def bendersPlay(n, paths, query):
    # Write your code here
    temp = 0
    for q in query:
        temp ^= G_table[q]
    
    if temp == 0 :
        return "Iroh"
    else:
        return "Bumi"