পাইথনে সাপ-সিড়ি খেলার ন্যূনতম মুভ বের করার প্রোগ্রাম

সাপ-সিড়ি খেলায় আমরা ডাইস রোল করে ০ থেকে ১০০ পর্যন্ত যেতে চাই। ডাইসে যেকোনো নম্বর (১-৬) আসতে পারে। সাপ এবং সিড়ির পজিশন দেওয়া আছে। লক্ষ্য হলো ন্যূনতম ডাইস রোল দিয়ে ১০০-এ পৌঁছানো।

উদাহরণ

ইনপুট:

ladders = [(11, 40), (37,67), (47, 73), (15, 72)]
snakes = [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

আউটপুট: 8

সমাধানের ধাপসমূহ (BFS পদ্ধতি)

সাপ এবং সিড়ি দুটোকে একসাথে মর্জ করুন।
edges ম্যাপ তৈরি করুন যেখানে কী = স্টার্ট, ভ্যালু = এন্ড।
BFS용 u (ভিজিটেড), v (কারেন্ট লেভেল) সেট তৈরি করুন।
v.add(1) (শুরু ১ থেকে)।
m := 0 (মুভ কাউন্ট)।
যখন 100 not in v:
- m += 1
- w := new set (নেক্সট লেভেল)
- প্রতিটি f in v এর জন্য:
  - প্রতিটি i in 1..6 (ডাইস রোল) এর জন্য:
    - n := f + i
    - যদি n in edges: n := edges[n] (সাপ/সিড়ি নেওয়া)
    - যদি n in u: continue (ইতিমধ্যে ভিজিটেড)
    - u.add(n), w.add(n)
- v := w
m রিটার্ন করুন।

পাইথন কোড

def solve(ladders, snakes):
    ladders.extend(snakes)
    edges = {}
    for f, t in ladders:
        edges[f] = t
    u = set()
    v = set()
    v.add(1)
    m = 0
    while 100 not in v:
        m += 1
        w = set()
        for f in v:
            for i in range(1, 7):
                n = f + i
                if n in edges:
                    n = edges[n]
                if n in u:
                    continue
                u.add(n)
                w.add(n)
        v = w
    return m

print(solve([(11, 40), (37,67), (47, 73), (15, 72)],
            [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

ইনপুট

[(11, 40), (37,67), (47, 73), (15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

আউটপুট

ব্যাখ্যা: BFS দিয়ে লেভেল বাই লেভেল এক্সপ্লোর করা হয়েছে। প্রতিটি মুভে ডাইস ১-৬ রোল করুন এবং সাপ/সিড়ি হ্যান্ডেল করুন। ৮টি মুভে ১০০-এ পৌঁছানো সম্ভব।