Discussion on Play on benders Challenge

Sort 17 Discussions, By:

2 years ago+ 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)

2 years ago+ 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)

4 years ago+ 0 comments

Can both players play the same soldier when their turn comes?

4 years ago+ 0 comments

C++ solution, passes all test cases without using recursion. Computes the nimber for node x as the smallest non-negative integer not equal to the nimbers of any nodes in x's adjacency list. This can be done non-recursively using DFS with a stack. Once you have the nimbers, just take the cumulative XOR of all the initial positions, and you get the answer.

#include <iostream>
#include <vector>
#include <queue>

using std::vector;

vector<vector<int>> adjacency(int n, const vector<int> &u, const vector<int> &v){
  vector<vector<int>> adj(n);
  for(int i=0;i<u.size();++i){
    adj[u[i]].push_back(v[i]);
  }
  return adj;
}

int excludant(const vector<int> &nim, const vector<int> &subadj){
  int res=0;
  std::priority_queue<int> q;
  for(int x: subadj){
    if(nim[x]==res){
      ++res;
      while(!q.empty() && -res==q.top()){
	++res;
	while(!q.empty() && -q.top()<res) q.pop();
      }
    }else if(nim[x]>res) q.push(-nim[x]);
  }
  return res;
}

vector<int> nimber(const vector<vector<int>> &adj){
  const int n=adj.size(), unvis=-1;
  vector<int> nim(n,unvis), ind(n,0), dfs;
  for(int i=0;i<n;){
    dfs.push_back(i);
    while(!dfs.empty()){
      const int x=dfs.back(), nx=adj[x].size();
      int &i=ind[x];
      while(i!=nx && nim[adj[x][i]]!=unvis) ++i;
      if(i==nx){
	nim[x]=excludant(nim,adj[x]);
	dfs.pop_back();
      }else dfs.push_back(adj[x][i++]);
    }
    while(i<n && nim[i]!=unvis) ++i;
  }
  return nim;
}

bool win(const vector<int> &b, const vector<int> &nim){
  int nimsum=0;
  for(int x: b) nimsum^=nim[x];
  return nimsum!=0;
}

int main(){
  int n=0, m=0; std::cin >> n >> m;
  vector<int> u,v;
  while(m--){
    int x=0,y=0; std::cin >> x >> y;
    u.push_back(--x);
    v.push_back(--y);
  }
  auto adj=adjacency(n,u,v);
  vector<int> nim{nimber(adj)};
  int q=0; std::cin >> q;
  while(q--){
    int k=0; std::cin >> k;
    vector<int> b;
    while(k--){
      int x=0; std::cin >> x;
      b.push_back(--x);
    }
    std::cout << (win(b,nim)?"Bumi\n":"Iroh\n");
  }
}

4 years ago+ 0 comments

Got a rather neat solution using trees, DFS and GS numbers. However getting wrong answer on just two TC's (8 and 10).... Probably some weird edge case I haven't catered for. No timeouts :) Pity some of the challenges don't show actual processing time...

Load more conversations