পাইথনে র‍েগুলার পলিগনে কালার্ড ভার্টেক্স থেকে আইসোসিলিস ট্রায়্যাঙ্গেল কাউন্ট করার প্রোগ্রাম

ধরুন আমাদের একটি র‍েগুলার পলিগন আছে যার n সাইড, এটি একটি বাইনারি স্ট্রিং হিসেবে রিপ্রেজেন্ট করা হয়েছে সাইজ n। ভার্টেক্সগুলো ব্লু (0) বা রেড (1) कलার্ড হতে পারে। সেগুলো ক্লকওয়াইজ দিকেই কলার্ড। আমাদের সেই আইসোসিলিস ট্রায়্যাঙ্গেলের সংখ্যা কাউন্ট করতে হবে যাদের ভার্টেক্সগুলো পলিগনের ভার্টেক্স এবং তাদের কালার একই।

উদাহরণস্বরূপ, যদি ইনপুট polygon = "111010" হয়, তবে আউটপুট হবে 2 কারণ দুটি ট্রায়্যাঙ্গেল ACE এবং AFE।

সমাধানের ধাপসমূহ

all(n) ফাংশন: মোট আইসোসিলিস ট্রায়্যাঙ্গেলের সংখ্যা বের করুন
non(a, n) ফাংশন: কালার ভিন্ন হলে বাদ দিন
n ওড/ইভেন এবং ৩ দিয়ে বিভাজ্যতা অনুযায়ী ফর্মুলা অ্যাপ্লাই করুন
চূড়ান্ত ফলাফল all(n) - non(polygon, n)/2

উদাহরণ

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

def all(n):
    if n % 2 == 1:
        no = n*(n-1)/2
    else:
        no = n*(n/2-1)
    if n % 3 == 0:
        no -= n/3*2
    return no

def non(a, n):
    if n % 2 == 1:
        s0 = s1 = 0
        i = 0
        while i < n:
            if a[i] == '0':
                s0 += 1
            else:
                s1 += 1
            i += 1
        s = s0*s1*6
        if n % 3 == 0:
            n1 = n/3
            n2 = n1*2
            i = 0
            while i < n:
                if a[i] != a[int((i+n1)%n)]:
                    s -= 2
                if a[i] != a[int((i+n2)%n)]:
                    s -= 2
                i += 1
    else:
        s00 = s01 = s10 = s11 = s = 0
        i = 0
        while i < n:
            if a[i] == '0':
                s00 += 1
            else:
                s01 += 1
            i += 2
        i = 1
        while i < n:
            if a[i] == '0':
                s10 += 1
            else:
                s11 += 1
            i += 2
        s += s00 * s01 * 8
        s += s10 * s11 * 8
        s += s00 * s11 * 4
        s += s10 * s01 * 4
        n1 = n/2
        i = 0
        while i < n:
            if a[i] != a[int((i + n1)%n)]:
                s -= 2
            i += 1
        if n % 3 == 0:
            n1 = n/3
            n2 = n1*2
            i = 0
            while i < n:
                if a[i] != a[int((i+n1)%n)]:
                    s -= 2
                if a[i] != a[int((i+n2)%n)]:
                    s -= 2
                i += 1
    return s/2

def solve(polygon):
    n = len(polygon)
    no = all(n) - non(polygon, n)/2
    return int(no)

polygon = "111010"
print(solve(polygon))