পাইথনে ক্রিয়াকলাপ প্রয়োগ করার পরে অভিধানিকভাবে সবচেয়ে ছোট স্ট্রিং খুঁজে বের করার জন্য প্রোগ্রাম

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

এ

s(0-সূচীকৃত) এর সমস্ত বিজোড় অবস্থানের আইটেমগুলিতে 'a' যোগ করুন। যদি অঙ্কটি 9 হয়, তাহলে এর সাথে কিছু যোগ করলে সাইকেলটি 0-এ ফিরে আসবে।
b অবস্থান দ্বারা ডানদিকে 's' ঘোরান।

সুতরাং আমাদেরকে s-তে যেকোন সংখ্যক বার উপরোক্ত ক্রিয়াকলাপ প্রয়োগ করে অভিধানগতভাবে সবচেয়ে ছোট স্ট্রিংটি খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি s ="5323" a =9 b =2 এর মত হয়, তাহলে আউটপুট হবে 2050 কারণ যদি আমরা অনুসরণ করি

ঘোরান:"5323"
যোগ করুন:"5222"
যোগ করুন:"5121"
ঘোরান:"2151"
যোগ করুন:"2050"

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

দেখেছি :=একটি নতুন সেট
deq :=একটি উপাদান 's' সহ একটি নতুন সারি
যদিও deq খালি না থাকে, কর
- curr :=deq এর প্রথম মুছে ফেলা উপাদান
- দেখা সেটে curr ঢোকান
- ad :=curr-এ প্রদত্ত অ্যাড অপারেশন সম্পাদন করুন
- যদি বিজ্ঞাপন দেখা না হয়, তাহলে
  - deq-এর শেষে বিজ্ঞাপন ঢোকান
  - দেখা সেটে বিজ্ঞাপন ঢোকান
- ro :=curr-এ ঘোরানো অপারেশন সম্পাদন করুন
- যদি ro দেখা না যায়, তাহলে
  - deq-এর শেষে ro ঢোকান
  - দেখা সেটে ro ঢোকান
নূন্যতম দেখা রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

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
   res = s[idx:] + s[0:idx]
   return res

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