ভূমিকা
আপনাকে Noble Knots তৈরি করার জন্য নিয়োগ দেওয়া হয়েছে, যা অভিজাতদের জন্য সবচেয়ে জনপ্রিয় নতুন ডেটিং অ্যাপ!
শতাব্দীর পর শতাব্দীর রাজকীয় আত্মীয়-বিবাহের ফলে ব্যাপারটা হয়ে উঠেছে… জটিল। যেকোনো উফ-আমরা-ত-যমজ পরিস্থিতি এড়াতে, আপনার কাজ হলো এমন একটি সিস্টেম তৈরি করা, যা যাচাই করে দুজন মানুষ কতটা ঘনিষ্ঠভাবে সম্পর্কিত।
Noble Knots অনুপ্রাণিত হয়েছে আইসল্যান্ডের "Islendinga-App" থেকে, যার পাশে রয়েছে একটি ডেটাবেস, যা আইসল্যান্ডে বসতি স্থাপনের সময় থেকে আইসল্যান্ডীয়দের মধ্যে সব জানা পারিবারিক সম্পর্কের সন্ধান দেয়। আপনার অ্যালগরিদম রাজপরিবারের বংশতালিকায় দুই ব্যক্তির মধ্যে ডিগ্রি অফ সেপারেশন নির্ণয় করবে।
আপনার অ্যাপ কি নিখুঁত জুটিকে মুকুট পরাতে সাহায্য করবে?
নির্দেশনা
আপনার কাজ হলো একটি পারিবারিক বৃক্ষে দুই ব্যক্তির মধ্যে সম্পর্কের মাত্রা নির্ণয় করা। এটি পপ সংস্কৃতির সেই ধারণার মতো, যেখানে বলা হয় প্রত্যেক হলিউড অভিনেতা কেভিন বেকনের ছয় ধাপের মধ্যে থাকেন।
- আপনার কাছে একটি ইনপুট দেওয়া হবে, যাতে সমস্ত পিতামাতার নাম ও তাদের সন্তানদের নাম থাকবে।
- প্রতিটি নাম অনন্য, এবং একটি সন্তানের এক বা দুইজন পিতামাতা থাকতে পারে।
- সম্পর্কের মাত্রা বলতে এক ব্যক্তি থেকে অন্য ব্যক্তির মধ্যে সংযোগের সবচেয়ে কম সংখ্যাকে বোঝানো হয়।
- দুই ব্যক্তি যদি সংযুক্ত না থাকে, তাহলে "no known relationship." বোঝায় এমন একটি মান রিটার্ন করুন।
প্রকৃত বাস্তবায়নের জন্য টেস্ট কেসগুলো দেখুন।
উদাহরণ
নিচের পারিবারিক বৃক্ষটি ধরুন:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
Tariq ও Uma-এর মধ্যে সম্পর্কের মাত্রা ২ (Tariq → Isla → Uma)।
Isla ও Kevin-এর মধ্যে কোনো পরিচিত সম্পর্ক নেই, কারণ প্রদত্ত তথ্যে কোনো সংযোগ নেই।
Uma ও Isla-এর মধ্যে সম্পর্কের মাত্রা ১।
Isla ও Tariq ভাইবোন, তাদের সম্পর্কের মাত্রা ১।
একইভাবে, এই বাস্তবায়ন আপনার থেকে আপনার বাবার ভাইয়ের মধ্যে সম্পর্কের মাত্রা ২ রিপোর্ট করবে।
ইঙ্গিত
ইঙ্গিতগুলো দেখুন
স্টাবের FamilyTree.(family_tree) নমিনাল টাইপটি আনর্যাপ করে, ফলে আপনি অন্তর্নিহিত Dict(Str, List(Str)) পান।
Dict.to_list এর এন্ট্রিগুলোকে (parent, children) টাপল হিসেবে প্রকাশ করে।
সম্পর্ক অনুসন্ধানের সময় একই ব্যক্তির কাছে বারবার ফিরে যাওয়া এড়াতে একটি Set(Str) আপনাকে সাহায্য করতে পারে।
