পাইথনে ফিনিশ লাইন পৌঁছানোর জন্য न्यूनতম মুভ সংখ্যা বের করার প্রোগ্রাম

একটি এক-আয়ামী রোডে একটি গাড়ি ড্রাইভ করার পরিস্থিতি বিবেচনা করুন। আমরা বর্তমানে position = 0 এবং speed = 1 অবস্থানে আছি। আমরা নিম্নলিখিত দুটি অপারেশন থেকে যেকোনো একটি সম্পাদন করতে পারি:

• त्वরণ (Acceleration): position := position + speed এবং speed := speed * 2
• রিভার্স গিয়ার (Reverse Gear): যদি speed > 0 হয় তবে speed := -1, অন্যথায় speed := 1

লক্ষ্য (target) পৌঁছাতে কমপক্ষে কতগুলো মুভ (move) দরকার হবে তা বের করতে হবে।

উদাহরণস্বরূপ, যদি ইনপুট হয় target = 10, তবে আউটপুট হবে 7।

সমাধানের পদ্ধতি

এই সমস্যাটি সমাধানের জন্য আমরা গভীরতা-প্রথম অনুসন্ধান (DFS) এবং ব্যাকট্র্যাকিং (backtracking) কৌশল ব্যবহার করব। মূল ধারণা হল প্রতিটি ধাপে সম্ভাব্য সমস্ত পথ εξপ্লোর করা এবং সর্বোত্তম সমাধান খুঁজে বের করা।

এলগরিদমের ধাপসমূহ:

1. একটি dfs() ফাংশন সংজ্ঞায়িত করুন যা গ্রহণ করবে: digit, cost, pos, neg, target।
2. tot := cost + max(2*(pos-1), 2*(neg-1)) হিসাব করুন।
3. যদি tot >= ans হয়, তবে ফেরত যান (pruning)।
4. যদি target == 0 হয়, তবে ans := min(ans, tot) আপডেট করুন এবং ফেরত যান।
5. step := (2^digit) - 1 হিসাব করুন।
6. যদি step * 2 < |target| হয়, তবে ফেরত যান।
7. পাঁচটি সম্ভাব্য রিকারসিভ কল করুন:
   • dfs(digit-1, cost, pos, neg, target)
   • dfs(digit-1, cost+digit, pos+1, neg, target-step)
   • dfs(digit-1, cost+digit*2, pos+2, neg, target-step*2)
   • dfs(digit-1, cost+digit, pos, neg+1, target+step)
   • dfs(digit-1, cost+digit*2, pos, neg+2, target+step*2)
8. মূল ফাংশন থেকে:
   • ans := infinity আরম্ভ করুন।
   • hi := 1 সেট করুন।
   • যখন 2^hi < target, তখন hi := hi + 1 বাড়ান।
   • dfs(hi, 0, 0, 0, target) কল করুন।
   • ans রিটার্ন করুন।

পাইথন কোড উদাহরণ

class Solution:
    def solve(self, target):
        self.ans = int(1e9)
        hi = 1
        while (1 << hi) < target:
            hi += 1
        self.dfs(hi, 0, 0, 0, target)
        return self.ans

    def dfs(self, digit, cost, pos, neg, target):
        tot = cost + max(2 * (pos - 1), 2 * neg - 1)
        if tot >= self.ans:
            return
        if target == 0:
            self.ans = min(self.ans, tot)
            return
        step = (1 << digit) - 1
        if step * 2 < abs(target):
            return
        self.dfs(digit - 1, cost, pos, neg, target)
        self.dfs(digit - 1, cost + digit, pos + 1, neg, target - step)
        self.dfs(digit - 1, cost + digit * 2, pos + 2, neg, target - step * 2)
        self.dfs(digit - 1, cost + digit, pos, neg + 1, target + step)
        self.dfs(digit - 1, cost + digit * 2, pos, neg + 2, target + step * 2)

ob = Solution()
print(ob.solve(10))  # আউটপুট: 7

ইনপুট ও আউটপুট

ইনপুট: 10
আউটপুট: 7