পাইথনে বাইনারি ট্রি কলারিং গেম

মনে করুন দুই খেলোয়াড় একটি বাইনারি ট্রিয়ে টার্ন-ভিত্তিক গেম খেলছে। আমাদের এই বাইনারি ট্রির রুট এবং নোডের সংখ্যা n দেওয়া আছে। এখানে n বিজোড়, এবং প্রতিটি নোডের ১ থেকে n পর্যন্ত уникаল ভ্যালু রয়েছে। প্রথমে প্রথম খেলোয়াড় একটি ভ্যালু x বলে যেখানে 1 <= x <= n, এবং দ্বিতীয় খেলোয়াড় একটি ভ্যালু y বলে যেখানে 1 <= y <= n এবং y != x। প্রথম খেলোয়াড় x ভ্যালুয়ुक्त নোডকে লাল রঙ দেয়, এবং দ্বিতীয় খেলোয়াড় y ভ্যালুয়ুক্ত নোডকে নীল রঙ দেয়। এরপর খেলোয়াড়রা টার্ন পাল্টা পাল্টা لعب করে, শুরু করবে প্রথম খেলোয়াড়। প্রতিটি টার্নে, খেলোয়াড় তার রঙের একটি নোড নেবে (লাল খেলোয়াড় ১ এর জন্য, নীল খেলোয়াড় ২ এর জন্য) এবং সেই নোডের একটি অনরঙিন প্রতিবেশী নোডকে রঙ করবে (বাম বা ডান চাইল্ড, অথবা পেরেন্ট)। যদি এবং কেবল যদি একজন খেলোয়াড় এইভাবে কোনো নোড নিতে না পারে, তবে সে তার টার্ন পাস করবে। যদি দুজন খেলোয়াড়ই পাস করে, তবে গেম শেষ হবে, এবং বিজয়ী হবে সে খেলোয়াড় যিনি অধিক নোড রঙ করেছেন।

মনে করুন আমরা দ্বিতীয় খেলোয়াড়। যদি এমন y বেছে নেওয়া সম্ভব হয় যাতে আমরা গেম জিতব, তবে true রিটার্ন করুন। যদি সম্ভব না হয়, তবে false রিটার্ন করুন।

যদি ট্রি নিচের মতো হয়:

এবং n = 11 এবং x = 3, তবে আউটপুট হবে true, কারণ দ্বিতীয় খেলোয়াড় ভ্যালু ২-য়ুক্ত নোড নিতে পারে।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব:

solve() নামক একটি মেথড ডিফাইন করুন, এটি node, x, l, r নেবে, এখানে l এবং r প্রাথমিকভাবে false, এটি নিচের মতো কাজ করবে:
- যদি node না থাকে, তবে রিটার্ন করুন।
- যদি l true হয়, তবে leftVal ১ বাড়ান, অন্যথায় যখন r true হয়, তবে rightVal ১ বাড়ান।
- যদি নোডের ভ্যালু x হয়, তবে solve(node.left, x, true, false) এবং solve(node.right, x, false, true) কল করুন।
- অন্যথায় solve(node.left, x, l, r) এবং solve(node.right, x, l, r) কল করুন।
মেইন মেথড হবে নিচের মতো:
- nodeToX := 0, leftVal := 0, rightVal := 0
- solve(root, x, false, false) কল করুন।
- nodeToX := n - leftVal - rightVal - 1
- temp := max(rightVal, nodeToX, leftVal)
- false রিটার্ন করুন যদি (nodeToX + leftVal + rightVal - (2*temp) >= 0), অন্যথায় true।

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

def insert(temp, data):
    que = []
    que.append(temp)
    while len(que):
        temp = que[0]
        que.pop(0)
        if not temp.left:
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if not temp.right:
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

class Solution(object):
    def btreeGameWinningMove(self, root, n, x):
        self.nodeToX = 0
        self.leftVal = 0
        self.rightVal = 0
        self.solve(root, x)
        self.nodeToX = n - self.leftVal - self.rightVal - 1
        temp = max(self.rightVal, max(self.nodeToX, self.leftVal))
        return not (self.nodeToX + self.leftVal + self.rightVal - (2*temp) >= 0)

    def solve(self, node, x, l=False, r=False):
        if not node:
            return
        if l:
            self.leftVal += 1
        elif r:
            self.rightVal += 1
        if node.data == x:
            self.solve(node.left, x, True, False)
            self.solve(node.right, x, False, True)
        else:
            self.solve(node.left, x, l, r)
            self.solve(node.right, x, l, r)

ob = Solution()
root = make_tree([1,2,3,4,5,6,7,8,9,10,11])
print(ob.btreeGameWinningMove(root, 11, 3))

ইনপুট

[1,2,3,4,5,6,7,8,9,10,11] 11 3

আউটপুট

true