مقدمه
شما استخدام شدهاید تا Noble Knots را توسعه دهید؛ داغترین اپلیکیشن دوستیابی تازه برای اشراف! با سدهها ازدواج میان خاندانهای سلطنتی، اوضاع… پیچیده شده است. برای اینکه از هر موقعیت وای، دوقلویمان درآمد دور بمانید، کار شما ساختن سامانهای است که بررسی کند دو نفر تا چه اندازه با هم خویشاوندند.
Noble Knots از «Islendinga-App» ایسلند الهام گرفته است، که پایگاهدادهای پشتیبان آن است و همهی پیوندهای خانوادگی شناختهشده میان ایسلندیها را از زمان اسکان ایسلند ردیابی میکند. الگوریتم شما «درجهی جدایی» میان دو فرد را در شجرهنامهی خاندان سلطنتی تعیین میکند.
آیا اپلیکیشن شما میتواند یک همتای بینقص را بر تخت بنشاند؟
دستورالعملها
وظیفهی شما تعیین درجهی جدایی بین دو نفر در یک شجرهنامه است.
این شبیه به ایدهی رایجی در فرهنگ عامه است که هر بازیگر هالیوودی در فاصلهی شش درجه از کوین بیکن قرار دارد.
- ورودیای دریافت میکنید که شامل اسم همهی والدین و فرزندانشان است.
- هر اسم منحصربهفرد است و یک فرزند میتواند یک یا دو والد داشته باشد.
- درجهی جدایی بهعنوان کوتاهترین تعداد ارتباط از یک نفر به نفر دیگر تعریف میشود.
- اگر دو نفر به هم مرتبط نباشند، مقداری را برگردانید که نشاندهندهی «هیچ رابطهی شناختهشدهای نیست» باشد.
برای پیادهسازی واقعی به موارد آزمون نگاه کنید.
مثال
با توجه به شجرهنامهی زیر:
┌──────────┐ ┌──────────┐ ┌───────────┐
│ Helena │ │ Erdős ├─────┤ Shusaku │
└───┬───┬──┘ └─────┬────┘ └────┬──────┘
┌───┘ └───────┐ └───────┬───────┘
┌─────┴────┐ ┌────┴───┐ ┌─────┴────┐
│ Isla ├─────┤ Tariq │ │ Kevin │
└────┬─────┘ └────┬───┘ └──────────┘
│ │
┌────┴────┐ ┌────┴───┐
│ Uma │ │ Morphy │
└─────────┘ └────────┘
درجهی جدایی بین Tariq و Uma برابر ۲ است (Tariq → Isla → Uma).
بین Isla و Kevin هیچ رابطهی شناختهشدهای وجود ندارد، چون در دادههای موجود هیچ ارتباطی نیست.
درجهی جدایی بین Uma و Isla برابر ۱ است.
Isla و Tariq خواهر و برادرند و درجهی جداییشان ۱ است.
به همین ترتیب، این پیادهسازی درجهی جدایی از شما تا برادر پدرتان را ۲ گزارش میکند.
