特典

Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

割引を受け取る

トラック

Common Lisp

演習

親族間の距離

中級

はじめに

今いちばん話題の、貴族向けの新しいマッチングアプリNoble Knotsの開発に携わることになりました！　何世紀にもわたる王族同士の結婚のせいで、事態は…_複雑_になってしまいました。おっと、私たち双子だった という事態を避けるために、2人がどれくらい近い親戚なのかを調べるシステムを作るのが仕事です。

Noble Knotsは、アイスランドの「Islendinga-App」に着想を得ています。これは、アイスランドへの入植の時代までさかのぼり、アイスランド人の間に知られているすべての親族関係をたどるデータベースに支えられています。このアルゴリズムは、王家の家系図の中で2人の間の血縁の度合いを求めます。

このアプリは、完璧な相手に王冠を授ける手助けになるでしょうか？

説明

課題は、家系図の中の2人の人物の間の隔たりの次数を求めることです。これは、ハリウッドの俳優は誰でもケビン・ベーコンから6次以内にいる、というポップカルチャーの考え方に似ています。

入力として、すべての親の名前とその子どもが与えられます。
それぞれの名前は一意で、子どもには親が1人または2人_いることもあります_。
隔たりの次数は、ある人から別の人へたどる接続の最短数として定義されます。
2人の人物がつながっていない場合は、「既知の関係がない」ことを表す値を返します。実際の実装については、テストケースを確認してください。

例

次のような家系図があるとします。

      ┌──────────┐            ┌──────────┐     ┌───────────┐
      │  Helena  │            │  Erdős   ├─────┤  Shusaku  │
      └───┬───┬──┘            └─────┬────┘     └────┬──────┘
      ┌───┘   └───────┐             └───────┬───────┘
┌─────┴────┐     ┌────┴───┐           ┌─────┴────┐
│   Isla   ├─────┤ Tariq  │           │   Kevin  │
└────┬─────┘     └────┬───┘           └──────────┘
     │                │
┌────┴────┐      ┌────┴───┐
│   Uma   │      │ Morphy │
└─────────┘      └────────┘

TariqとUmaの隔たりの次数は2です（Tariq → Isla → Uma）。 IslaとKevinの間には知られた関係がありません。与えられたデータに接続がないためです。 UmaとIslaの隔たりの次数は1です。

Note

IslaとTariqは兄弟で、隔たりの次数は1です。同じように、この実装では、自分と父の兄弟との隔たりの次数は2であると報告されます。