ここ数日、Sling Blade Runner として知られるアーカイブされたITA Softwareのパズルを解こうとしています。パズルの要点は次のとおりです。
「スリング ブレード ランナーのように、重複する一連の映画のタイトルをどのくらい見つけられますか?」
次の映画タイトルのリストを使用します: MOVIES.TXT。「モッキンバードを殺すライセンス」のように、複数の単語が重複することは許されます。ソリューション内で同じタイトルを複数回使用することはできません。常に最大数のタイトルを生成するとは限らないヒューリスティックなソリューションが受け入れられます。効率と最適性の合理的なトレードオフを求めてください。
ファイルMOVIES.TXTには、6561 の映画タイトルがアルファベット順に含まれています。
私の解決策の試みには、いくつかの部分があります。
グラフの構築:
私がしたことは、すべての映画のタイトルを、チェーンできる他のすべての映画のタイトルにマップすることでした (右側にあります)。私のグラフはMap[String, List[String]]. このプロセスを使用して作成されたグラフは、こちら で確認できます。
グラフ トラバーサル:
すべてのノード (マップ内のすべてのキー) を検索の開始ノードとして使用して、深さ優先検索を実行しました。検索中に各ノードが訪問された深さを追跡し、これは DFS によって返されたノードでタグ付けされました。私が最終的に得たのは、リスト内のList[List[Node]]すべてList[Node]が特定の検索からの DFS ツリーであるということでした。
最長のチェーンを見つける:
前のステップですべてのグラフ トラバーサルの結果を取得し、すべてについて、List[Node]以前にノードにタグ付けした深さの値でリストを降順で並べ替えました。次に、リストの先頭 (これにより、DFS でアクセスされた最も深いノードが得られます) から始めて、ノードをバックトラックしてチェーンを構築します。これにより、リスト内のList[List[String]]すべてList[String]がその特定の DFS の最長のチェーンであることがわかりました。List[List[String]]それぞれのサイズで並べ替えてList[String]頭をつかむと、最大のチェーンが得られました。
結果：
私のアルゴリズムで見つかった最長のチェーンは、217 タイトルの長さでした。出力はここで見ることができます。
私はグーグルで他のいくつかの試みしか見つけることができませんでした.他のすべての試みは、私が達成できたものよりも長いチェーンを生み出したようです. たとえば、この投稿では、Eric Burke が 245 タイトルの長さのチェーンを見つけ、 Reddit の icefox という名前のユーザーが 312 タイトルの長さのチェーンを見つけたと述べています。
他の人がより長いチェーンを見つけたことを考えると、私のアルゴリズムがどこで最長のチェーンを見つけられなかったのか考えられません。ヘルプ/ガイダンスは大歓迎です。私のコードを確認したい場合は、ここで見つけることができます(これは Scala で書かれており、Scala の学習を始めたばかりなので、初歩的な間違いを犯した場合はご容赦ください)。
アップデート：
アルゴリズムにいくつかの変更を加えたところ、長さが 240 以上のチェーンが検出されるようになりました。こちらをご覧ください