Tag: রিকার্শন

সমস্যাঃ একটি সিঙ্গলি লিঙ্কড লিস্ট দেওয়া আছে, যেখানে প্রতিটি নোডের ডেটা ও পরবর্তী নোডের ঠিকানা থাকবে।

class SinglyLinkedListNode:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None

এখন একটি ফাংশন লিখতে হবে –

int getNode(SinglyLinkedListNode* head, int positionFromTail)

অর্থাৎ লিঙ্কড লিস্টের শুরুর নোড (হেড নোড) দেওয়া থাকবে, আর একটা সংখ্যা দেওয়া থাকবে, ওই সংখ্যার মান যত, লিঙ্কড লিস্টের শেষ থেকে ততঘর বা ততটি নোড আগে এসে যেই নোড পাওয়া যায়, তার মান রিটার্ন করতে হবে।

এটা বেশ সহজ একটি সমস্যা। ইন্টারভিউতে এই সমস্যা দিলে ইন্টারভিউয়ার আশা করবেন যে 10-12 মিনিট বা তার চেয়ে কম সময়ে এটি সমাধান করতে হবে।

কেউ সমস্যাটি সমাধান করতে চাইলে এখানে চেষ্টা করতে পারে – https://www.hackerrank.com/challenges/get-the-value-of-the-node-at-a-specific-position-from-the-tail/problem

সমাধানঃ আমরা রিকার্শন ব্যবহার করে সহজেই সমাধান করতে পারি। ইন্টারভিউতে শুরুতেই কোড লিখে ফেলা যাবে না। প্রথমে আলোচনা করে নিতে হবে যে, কাজটি কিভাবে করা হবে। যেমন, “আমি রিকার্শন ব্যবহার করে লিঙ্কড লিস্টের শেষে চলে আসবো, তারপরে শেষ থেকে শুরু করে কাউন্ট করে যাবো।”

পাইথনে রিকার্শন দিয়ে এভাবে কোড লেখা যেতে পারে –

def getNode(head, positionFromTail):
    count = 0
    value = None
    
    def traverse_ll(node):
        nonlocal count
        nonlocal value
        if node is None:
            return
        traverse_ll(node.next)
        if count == positionFromTail:
            value = node.data
        count += 1
        
    traverse_ll(head)
    
    return value

nonlocal-এর ব্যবহার লক্ষ করতে হবে। এ বিষয়ে আমি এখানে একটি আর্টিকেল লিখেছি।

এখন ইন্টারভিউয়ার বলতে পারেন, স্ট্যাক ব্যবহার করে সমস্যাটির সমাধান করতে। তখন সেভাবে করার চেষ্টা করতে হবে। তাহলে আমরা সবগুলো নোডের মান একটি স্ট্যাকে রেখে দেবো। তারপরে positionFromTail এর চেয়ে একবার বেশি স্ট্যাক থেকে পপ করবো। কোড বেশ সহজ হবে, এরকম –

def getNode(head, positionFromTail):
    value = None
    stk = []
    
    node = head
    while node:
        stk.append(node.data)
        node = node.next
        
    while positionFromTail >= 0:
        value = stk.pop()
        positionFromTail -= 1
       
    return value

আমরা তো দুটি পদ্ধতিতে সমস্যাটির সমাধান করলাম? দুটোর টাইম ও স্পেস কমপ্লেক্সিটির মধ্যে পার্থক্য কী?

 

টাওয়ার অফ হ্যানয় , কম্পিউটার বিজ্ঞানের মানুষদের কাছে খুবই পরিচিত একটি সমস্যার নাম। রিকার্শন দিয়ে সাধারণত আমরা এই সমস্যার সমাধান করে থাকি। এটি মূলত একটি গাণিতিক খেলা বা পাজল, যেখানে তিনটি খুঁটি এবং ছোটবড় বিভিন্ন আকারের অনেকগুলো চাকতি বা ডিস্ক দেয়া থাকে। খেলাটি হলো প্রথম খুঁটি থেকে তিন নাম্বার খুঁটিতে  সবগুলো চাকতি নিয়ে যাওয়া।

মনে হতে পারে চাকতি সরানো আর এমন কী ব্যাপার! কিন্তু সহজ হলে তো আর খেলার মজা থাকে না। চাকতি গুলো সরানোর জন্য রয়েছে তিনটি শর্ত। শর্তগুলো হলোঃ

১. চাকতিগুলো থেকে একবারে একটি করে চাকতি অন্য খুঁটিতে স্থানান্তর করতে হবে। একের অধিক চাকতি একবারে নেয়া যাবে না।

২. সবসময় সবার উপরে যে চাকতিটি থাকবে সেই চাকতিটিই সরিয়ে নিতে হবে, এবং যে খুঁটিতে স্থানান্তর করা হবে সেখানেও সবার উপরের স্থানেই তার জায়গা হবে।

৩. কখনোই ছোট চাকতির উপর বড় চাকতি রাখা যাবে না।

১৮৮৩ সালে ফরাসি গণিতবিদ, এ্যাডুইয়ার্ড লুকাস , টাউয়ার অফ হ্যানয় পাজল্‌টি আবিষ্কার করেন। টাওয়ার অফ হ্যানয়ের রয়েছে মজার একটি গল্প। জনশ্রুতি যে ভারতের কাশি বিশ্বনাথে একটি মন্দিরের একটি বিশাল কক্ষে ৬৪টি স্বর্ণের চাকতিসহ তিনটি স্তম্ভ আছে। একজন ব্রাহ্মণ পুরোহিত ব্রহ্মার নির্দেশ অনুসারে সেই চাকতিগুলোকে ক্রমাগত নিয়ম মেনে আদিকাল থেকে স্থানান্তর করে যাচ্ছে। কিংবদন্তীদের মতে যখন পাজলের ৬৪টি চাকতির শেষ চাকতিটি সফলভাবে স্থানান্তর করা যাবে, তখন পৃথিবী ধ্বংস হয়ে যাবে!

মজার ব্যাপার হচ্ছে যদি কিংবদন্তীদের কথা সত্যি হয়, এক সেকেন্ডে নিয়ম মেনে একটি চাকতি সঠিকভাবে সরানো গেলেও পুরোহিতের সময় লেগে যাবে ২^৬৪-১ সেকেন্ড মানে ২৪৫ বিলিয়ন বছর!

গল্পটি বিভিন্নভাবে প্রচলিত আছে। কোথাও বলা আছে, একটি বৌদ্ধদের আশ্রম এবং ভিক্ষুদের কথা। মন্দির বা আশ্রমের অবস্থান নিয়েও রয়েছে মতভেদ। কারো মতে মন্দিরটি ভারতে আবার কারো মতে আশ্রমটি ভিয়েতনামের রাজধানী হ্যানয়ে। আবার  অনেকের ধারণা টাওয়ারটি পৃথিবীর শুরু থেকেই আছে এবং পুরোহিতেরা রোজ একটি করে চাকতি সরিয়েই যাচ্ছেন।

কম্পিউটার বিজ্ঞানে রিকার্শন ধারণাটি ব্যবহার করে সাধারণত আমরা টাওয়ার অফ হ্যানয় সমস্যার সমাধান করে থাকি। সহজ বাংলায় রিকার্শন মানে হচ্ছে পুনরাবৃত্তি। রিকার্শন হচ্ছে এমন একটি পদ্ধতি যেখানে একটি ফাংশনকে এমনভাবে ব্যবহার করা হয় যেন ফাংশনটি নিজেই নিজের কাজে ব্যবহৃত হয় বা নিজের নাম ধরে নিজেই নিজেকে ডাকে। রিকার্শনের সাহায্যে বারবার একই কাজ করে একটা সমস্যার সমাধানে পৌঁছানো যায়।

টাওয়ার অফ হ্যানয়ের ক্ষেত্রে n  সংখ্যক চাকতির জন্য 2ⁿ -1 সংখ্যক স্থানান্তরc(Move) হয়ে থাকে। সবচেয়ে সহজ টাওয়ার অফ হ্যানয় সমস্যায় তিনটি চাকতি থাকে।   

N সংখ্যক চাকতির জন্য টাওয়ার অফ হ্যানয়ের এ্যালগোরিদমটি নিম্নরূপঃ

TOWER (N, BEG, AUX, END)

1. If N=1, then:
   1. Write: BEG—>END
   2. Return
2. Call TOWER (N-1, BEG, END, AUX)
3. Write: BEG—>END
4. Call TOWER(N-1, AUX,BEG,END)
5. Return

ধরা যাক, খুটি তিনটি যথাক্রমে A, B, C এবং N=3 ( যেহেতু আমরা তিনটি চাকতির জন্য সমাধান করবো।) সেক্ষেত্রে আমাদের স্থানান্তর সংখ্যা হবে 2³ -1 = 7  . একদম শুরুতে আমাদের চিত্রটি হবে এমনঃ

---

 এখানে A , B এবং C যথাক্রমে BEG, AUX এবং END.  এ্যালগোরিদম এর ফাংশন মতে আমরা লিখতে পারি, TOWER (3, A, B, C) . যেহেতু আমাদের N এর মান 1 এর থেকে বেশি তাই এ্যালগোরিদমের 1 নাম্বার পয়েন্ট আপাতত আমাদের কাজে লাগবে না। আমরা চলে যাই এ্যালগরিদমের 2,3 এবং 4 নাম্বার পয়েন্টের কাছে। সহজ  এবং নির্ভুলভাবে টাওয়ার অফ হ্যানয় সমস্যাটি সমাধান করা জন্য আমরা নিচের তিনটি জিনিস মাথায় রাখবো।

Call Tower (N-1, BEG, END, AUX)

Write:  BEG—>END

Call Tower (N-1, AUX, BEG, END)

যেকোন সংখ্যক চাকতির জন্য কতগুলো স্থানান্তর(movement) এবং স্থানান্তরের ক্রম বের করার জন্য TOWER (N, BEG, AUX, END) এর ডানদিকে আমরা রাখবো TOWER (N-1, BEG, END, AUX ) স্টেটমেন্টটিকে এবং বামদিক রাখবো TOWER (N-1, AUX, BEG, END) .  এটার বেসিক স্ট্রাকচারটি হবে নিম্নরূপঃ

 প্রতিবারেই আমাদের আউটপুট হবে BEG —> END . এক্ষেত্রে লক্ষণীয় ব্যাপার হচ্ছে এখানে BEG,  AUX, END এগুলো জায়গা বদলালে এদের নাম বদলাবে। যেমনঃ বামদিকে TOWER (N-1, AUX, BEG, END)  এ AUX কিন্তু আসলে BEG হয়ে গেছে কারণ সে প্রথমে।

এখন N=3 এর জন্য আমরা পাইঃ

 উপরের চিত্রের প্রতিবার TOWER ফাংশন থেকে আমরা BEG—->END হিসেবে আউটপুট পাবো, যেটা হবে আমাদের টাওয়ার অফ হ্যানয় সমস্যার এক একটি স্থানান্তর। যেমনঃ

TOWER (3, A, B, C) ————————————— BEG —-> END —– A—>C

TOWER (3-1, B, A, C) = TOWER (2, B, A, C) ———- BEG—->END —– B—>C

ঠিক এভাবে N = 1 না হওয়া পর্যন্ত TOWER  ফাংশনটি কাজ করেই যাবে। শেষ পর্যন্ত আমরা নিম্নরূপ আউটপুট পাবো যেগুলো প্রত্যেকটি টাওয়ার অফ হ্যানয়ের এক একটি স্থানান্তর। এভাবে প্রতিবার টাওয়ার অফ হ্যানয়ের এ্যালগরিদম ব্যবহার করে আমরা নিম্নোক্ত সমাধান পাইঃ

 এই ছবিটিতে যে “MOVE” গুলো দেখা যাচ্ছে সেগুলো উপর থেকে নিচ পর্যন্ত পরপর সাজালেই আমরা তিনটি চাকতির জন্য টাওয়ার অফ হ্যানয়ের স্থানান্তরগুলো পেয়ে যাবো

টাওয়ার অফ হ্যানয় সমস্যার সমাধানের ক্ষেত্রে এই নিয়মটি দ্বারা N এর যেকোন মানের জন্য খুব সহজেই এর স্থানান্তর (Movement) বের করা সম্ভব।

 লেখক : তামান্না নিশাত রিনি