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

Sort by

recency

|

20 Discussions

|

  • barifacts202020
     + 0 comments

    Can we use this same technique on Wollongong Soft Play Hire too? Kindly help because i also made my soft play area for kids.

  • imre_palik
     + 0 comments

    Could someone explain me how could Iroh win the 2nd sample query? As far as I understand, 9 & 4 is already in a final state. So Bumi moves 1 to 8 or 10, and wins. What am I missing here?

  • thecodingsoluti2
     + 0 comments

    Here is Play on Benders problem solution in Python Java C++ and C programming - https://programs.programmingoneonone.com/2021/07/hackerrank-play-on-benders-problem-solution.html

  • stu14
     + 0 comments

    I've made a change to my Tree class so that I store parents as a list. But I'm still failing all the same case. I think I'm running into issues with the recurrence of the bendersPlay function, all the parent data is lost when this happens and the code goes into an infinite loop. Here's what I've got so far anyway.

    class Tree:
    def __init__(self, data, parents = []):
        self.branches = []
        self.data = data
        self.parents = parents

    def setChildren(self, paths):
        branches = []
        for path in paths:
            if self.data == path[0] and path[1] not in self.parents:
                branch = Tree(path[1], self.parents + [self.data])
                branch.setChildren(paths)
                self.branches.append(branch)
    
    def hasBranches(self):
        if(self.branches):
            return(True)
        else:
            return(False)
    
    def getDepth(self, depth):
        depths = []
        if(self.hasBranches()):
            depth = depth + 1
            for branch in self.branches:
                depths.append(branch.getDepth(depth))
        if(depths):
            return(max(depths))
        else:
            return(depth)

    def getBestMove(self):
        depths = {}
        max_key = 0
        if(self.branches):
            for branch in self.branches:
                depths[branch.data] = branch.getDepth(0)
            max_key = max(depths, key=depths.get)
        return(max_key)

#
# Complete the bendersPlay function below.
#
def bendersPlay(n, paths, query, player = 'Bumi'):
    #
    # Write your code here.
    #
    if(player == 'Bumi'):
        player = 'Iroh'
    else:
        player = 'Bumi'
    depths = {}
    bestMoves = {}
    for i in query:
        tree = Tree(i)
        tree.setChildren(paths)
        tree.getDepth(0)
        depths[i] = tree.getDepth(0)
        bestMoves[i] = tree.getBestMove()

    total = sum(depths.values())
    max_key = max(depths, key=depths.get)
    max_value = max(depths.values()) 

    if max_value:
        query[query.index(max_key)] = bestMoves[max_key]
        player = bendersPlay(n, paths, query, player, )

    return(player)

  • stu14
     + 0 comments

    So this is my function and a class for a tree data structure (python3). It works for the sample case but none of the other cases. I can't see why this wouldn't work.

    class Tree:
    def __init__(self, data):
        self.branches = []
        self.data = data

    def setChildren(self, paths):
        branches = []
        for path in paths:
            if self.data == path[0]:
                branch = Tree(path[1])
                branch.setChildren(paths)
                self.branches.append(branch)
    
    def hasBranches(self):
        if(self.branches):
            return(True)
        else:
            return(False)
    
    def getDepth(self, depth):
        depths = []
        if(self.hasBranches()):
            depth = depth + 1
            for branch in self.branches:
                depths.append(branch.getDepth(depth))
        if(depths):
            return(max(depths))
        else:
            return(depth)

    def getBestMove(self):
        depths = {}
        max_key = 0
        if(self.branches):
            for branch in self.branches:
                depths[branch.data] = branch.getDepth(0)
            max_key = max(depths, key=depths.get)
            # fptr.write('Branch Depths[' + str(self.data) + ']: ' + str(depths) + '\n')
        return(max_key)

#
# Complete the bendersPlay function below.
#
def bendersPlay(n, paths, query, player = 'Bumi'):
    #
    # Write your code here.
    #
    if(player == 'Bumi'):
        player = 'Iroh'
    else:
        player = 'Bumi'
    depths = {}
    bestMoves = {}
    for i in query:
        tree = Tree(i)
        tree.setChildren(paths)
        tree.getDepth(0)
        depths[i] = tree.getDepth(0)
        bestMoves[i] = tree.getBestMove()

    max_key = max(depths, key=depths.get)
    max_value = max(depths.values()) 

    if max_value:
        query[query.index(max_key)] = bestMoves[max_key]
        player = bendersPlay(n, paths, query, player)

    return(player)