পাইথনে অপারেশন প্রয়োগ কর লেক্সিকোগ্রাফিক্যালি ন্যূনতম স্ট্রিং বের করার প্রোগ্রাম

মান লিজিয়ে একটি স্ট্রিং আছে s যাতে শুধু নিউমেরিক ডিজিট রয়েছে এবং দুটি মান a ও b। আমরা নিচের দুটি অপারেশন যেকোনো ক্রমে যেকোনো সংখ্যকবার প্রয়োগ করতে পারি:

s-এর সব অড পজিশন (০-ইন্ডেক্সড) এ a যোগ করুন। ৯-এর সাথে কিছু যোগ করলে সাইক্লিক্যালি ০ হয়ে যায়।
s-কে ডানে b পজিশন রোটেট করুন।

উপরের অপারেশনগুলো যেকোনো সংখ্যকবার প্রয়োগ করে যে লেক্সিকোগ্রাফিক্যালি ন্যূনতম স্ট্রিং পাওয়া যায় সেটি বের করতে হবে।

যেমন, ইনপুট হলে s = "5323", a = 9, b = 2, তবে আউটপুট হবে 2050 কারণ: রোটেট: "5323" -> অ্যাড: "5222" -> অ্যাড: "5121" -> রোটেট: "2151" -> অ্যাড: "2050"।

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

seen := সেট, deq := deque([s])
deq খালি না থাকা পর্যন্ত:
- curr := deq.popleft(), seen.add(curr)
- ad := add_(curr, a), যদি ad not in seen হয়, তবে deq.append(ad), seen.add(ad)
- ro := rotate_(curr, b), যদি ro not in seen হয়, তবে deq.append(ro), seen.add(ro)
min(seen) রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

from collections import deque
def add_(s, a):
    res = ''
    for idx, i in enumerate(s):
        if idx % 2 == 1:
            num = (int(i) + a) % 10
            res += str(num)
        else:
            res += i
    return res
def rotate_(s, b):
    idx = len(s) - b
    return s[idx:] + s[:idx]
def solve(s, a, b):
    seen = set()
    deq = deque([s])
    while deq:
        curr = deq.popleft()
        seen.add(curr)
        ad = add_(curr, a)
        if ad not in seen:
            deq.append(ad)
            seen.add(ad)
        ro = rotate_(curr, b)
        if ro not in seen:
            deq.append(ro)
            seen.add(ro)
    return min(seen)

s = "5323"
a = 9
b = 2
print(solve(s, a, b))

ইনপুট

"5323", 9, 2