しりとりで最長を得るアルゴリズムなんて研究しつくされてるんだろうけど、まぁ思いつかんので、力業。
ちょっと雑。間違ってるかも... (間違ってたので修正した)
public void Test02() { Node_t[] nodes = Directory.GetFiles(@"C:\home\画像\HPキャラ立ち絵\ウマ娘") .Select(file => Path.GetFileNameWithoutExtension(file)) .Select(name => name.Substring(name.IndexOf('_') + 1)) // "イラスト_佐岳メイ" -> "佐岳メイ" .DistinctOrderBy(SCommon.Comp) .Select(name => new Node_t() { Word = name }) .ToArray(); foreach (Node_t node in nodes) node.EndPtn = GetEndPtn(node.Word); LongestNodeArray = new Node_t[0]; foreach (Node_t node in nodes) Search(nodes, node); foreach (Node_t node in LongestNodeArray) Console.WriteLine(node.Word); } private Node_t[] LongestNodeArray; private class Node_t { public string Word; public string EndPtn; public bool Reached; } private string GetEndPtn(string name) { int p = name.Length - 1; int q = name.Length; if (name[p] == 'ー') // 長音 { p--; q--; } if ("ッャュョァィゥェォ".Contains(name[p])) // 拗促音 p--; return name.Substring(p, q - p); } private void Search(Node_t[] nodes, Node_t startNode) { foreach (Node_t node in nodes) node.Reached = false; S_Nodes = nodes; S_Route = new List<Node_t>(); S_Route.Add(startNode); startNode.Reached = true; S_Next(); S_Nodes = null; S_Route = null; } private Node_t[] S_Nodes; private List<Node_t> S_Route; private void S_Next() { if (LongestNodeArray.Length < S_Route.Count) LongestNodeArray = S_Route.ToArray(); Node_t lastNode = S_Route[S_Route.Count - 1]; foreach (Node_t node in S_Nodes) { if (!node.Reached && node.Word.StartsWith(lastNode.EndPtn)) { node.Reached = true; S_Route.Add(node); S_Next(); node.Reached = false; S_Route.RemoveAt(S_Route.Count - 1); } } }
出力
ホッコータルマエ エルコンドルパサー サムソンビッグ グラスワンダー ダイイチルビー ビターグラッセ セイウンスカイ イクノディクタス スイープトウショウ ウイニングチケット トランセンド ドゥラメンテ テイエムオペラオー オグリキャップ
2024.6.15 バグがあったので修正
2024.6.25 追記ここから
なんか増えたので少し長くなった。
ホッコータルマエ エルコンドルパサー サムソンビッグ グラスワンダー ダイイチルビー ビリーヴ ヴィルシーナ ナカヤマフェスタ タマモクロス スイープトウショウ ウオッカ カツラギエース スティルインラブ ブエナビスタ タニノギムレット トランセンド ドリームジャーニー ニシノフラワー ワンダーアキュート トウカイテイオー オグリキャップ
2024.6.25 追記ここまで
モブも追加して総勢801人でやってみようと思ったんだけど、こんな総当たり処理が終わるはずもないので
貪欲法でやってみようと思う。(注意：アルゴリズムは精査してないし、実装も雑也)
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; using Charlotte.Commons; namespace Charlotte.Tests { public class Test0008 { #region RES_NAMES /// <summary> /// 公式(https://umamusume.jp/character)に紹介されているウマ娘＋モンジュー (125名) @ 2024.6.15 /// </summary> private string RES_NAMES = @" アイネスフウジン アグネスタキオン アグネスデジタル " +----------------+ | 長いので途中省略 | +----------------+ @" ヴィブロス ヴィルシーナ ヴェニュスパーク ; 佐岳メイ ; 秋川やよい ; 駿川たづな ; ここから追加 ; ノーザンテースト ; トキノミノル ; ディクタス モンジュー ; ブロワイエ ; サ【佐岳メイ】イ ; ア【秋川やよい】イ ; ハ【駿川たづな】ナ ; オ【乙名史悦子】コ ; キ【桐生院葵】イ ; ア【安心沢刺々美】ミ ; カ【樫本理子】コ ; ツ【都留岐涼花】カ ; ア【赤坂美里】ト ; ホ【細江順子】コ ; オッチャホイ "; #endregion #region RES_MOB_NAMES /// <summary> /// モブウマ娘一覧(https://mobumamusume.net/name_list)に紹介されているモブウマ娘 (615名) @ 2024.6.15 /// </summary> private string RES_MOB_NAMES = @" アーケードチャンプ アートルムグリモア アーリースプラウト " +----------------+ | 長いので途中省略 | +----------------+ @" ワクワクリボン ワルツステップ ワンインチオブラブ "; #endregion #region RES_KAIGAI_MOB_NAMES /// <summary> /// 海外のモブウマ娘一覧(https://mobumamusume.net/abroad)に紹介されている海外モブウマ娘 (61名) @ 2024.6.16 /// </summary> string RES_KAIGAI_MOB_NAMES = @" アジーザ アルトピャーノ アルビコッコ " +----------------+ | 長いので途中省略 | +----------------+ @" プロムス ボールス レイナーディン "; #endregion public void Test01() { string[] names = SCommon.TextToLines(RES_NAMES) .Where(line => !line.StartsWith(";")) .Select(line => line.Trim()) .Where(line => line != "") .ToArray(); // モブ・海外モブ { string[] mobNames = SCommon.TextToLines(RES_MOB_NAMES) .Concat(SCommon.TextToLines(RES_KAIGAI_MOB_NAMES)) .Where(line => !line.StartsWith(";")) .Select(line => line.Trim()) .Where(line => line != "") .ToArray(); names = names.Concat(mobNames).ToArray(); } EndlessSearch(names); } // ==== // ==== // ==== private void EndlessSearch(string[] names) { //names = names.DistinctOrderBy(SCommon.Comp).ToArray(); #if true // 入力が正しいかチェック { string ZEN_KATAKANA = "ァアィイゥウェエォオカガキギクグケゲコゴサザシジスズセゼソゾタダチヂッツヅテデトドナニヌネノハバパヒビピフブプヘベペホボポマミムメモャヤュユョヨラリルレロワヰヱヲンヴ" + "ー" // 長音 ; foreach (string name in names) { if (name.Length < 3) // "キャー" 以上を想定 throw null; foreach (char name_chr in name) if (!ZEN_KATAKANA.Contains(name_chr)) throw null; } if (SCommon.HasSame(names, (a, b) => a == b)) throw null; } #endif Array.Sort(names, SCommon.Comp); string[] longest = new string[0]; for (; ; ) { string[] ret = new ShiritoriDONYOKU_Md().GetLongest(names); #if true // 出力が正しいかチェック { for (int index = 1; index < ret.Length; index++) { string name1 = ret[index - 1]; string name2 = ret[index]; string name1EndPtn = Shiritori_Md.GetEndPtn(name1); if (!name2.StartsWith(name1EndPtn)) throw null; } if (SCommon.HasSame(ret, (a, b) => a == b)) throw null; } #endif ProcMain.WriteLog("しりとりの長さ：" + ret.Length); // cout if (longest.Length <= ret.Length) { ProcMain.WriteLog("★記録更新またはトップタイ！"); // cout string outFile = string.Format(@"C:\temp\Shiritori_{0:D4}_{1}.txt", ret.Length, SimpleDateTime.Now().ToTimeStamp()); outFile = SCommon.ToCreatablePath(outFile); File.WriteAllLines(outFile, ret, SCommon.ENCODING_SJIS); longest = ret; } } } private class ShiritoriDONYOKU_Md { private const int JISHO_MAX = 100; //private const int JISHO_MAX = 110; //private const int JISHO_MAX = 120; //private const int JISHO_MAX = 130; private const int JOINT_NUM = 20; //private const int JOINT_NUM = 30; //private const int JOINT_NUM = 40; //private const int JOINT_NUM = 50; public string[] GetLongest(string[] names) { string[] longest = GetLongest_NEST(new string[0], names); // 01_まだまだイケるやろループ【後】 { //bool iketaFlag = false; for (; ; ) // まだまだイケるやろ！ループ { names = names .Where(name => !longest.Contains(name)) .ToArray(); string lastName = longest[longest.Length - 1]; string lastNameEndPtn = Shiritori_Md.GetEndPtn(lastName); List<string> ikeruNames = new List<string>(); foreach (string name in names) if (name.StartsWith(lastNameEndPtn)) ikeruNames.Add(name); if (ikeruNames.Count == 0) break; //iketaFlag = true; string ikeruNextName = SCommon.CRandom.ChooseOne(ikeruNames); longest = longest .Concat(new string[] { ikeruNextName }) .ToArray(); } //if (iketaFlag) ProcMain.WriteLog("まだまだイケるやろ成功！【後】(01)"); // cout } // 02_まだまだイケるやろループ【前】 { //bool iketaFlag = false; for (; ; ) // まだまだイケるやろ！ループ { names = names .Where(name => !longest.Contains(name)) .ToArray(); List<string> ikeruNames = new List<string>(); foreach (string name in names) if (longest[0].StartsWith(Shiritori_Md.GetEndPtn(name))) ikeruNames.Add(name); if (ikeruNames.Count == 0) break; //iketaFlag = true; string ikeruNextName = SCommon.CRandom.ChooseOne(ikeruNames); longest = new string[] { ikeruNextName } .Concat(longest) .ToArray(); } //if (iketaFlag) ProcMain.WriteLog("まだまだイケるやろ成功！【前】(02)"); // cout } return longest; } private string[] GetLongest_NEST(string[] route, string[] names) { string lastName = route.Length == 0 ? null : route[route.Length - 1]; string[] longest; if (JISHO_MAX < names.Length) { longest = new string[0]; for (int c = 1; ; c++) { string[] ret = GetLongest_PART(lastName, names); if (longest.Length < ret.Length) longest = ret; if (5 <= c && longest.Length != 0) break; if (30 <= c) { names = names.ToArray(); // clone SCommon.CRandom.Shuffle(names); names = names.Take(JISHO_MAX).ToArray(); goto finalPart; // 最後のダメ押し } } route = route .Concat(longest) .ToArray(); names = names .Where(name => !route.Contains(name)) .ToArray(); return GetLongest_NEST(route, names); } finalPart: longest = new Shiritori_Md().GetLongest(names, lastName, 0); route = route .Concat(longest) .ToArray(); return route; } private string[] GetLongest_PART(string lastName, string[] wholeNames) { List<string> names = new List<string>(); for (int c = 0; c < JISHO_MAX; c++) { names.Add(SCommon.CRandom.ChooseOne(wholeNames)); wholeNames = wholeNames .Where(name => !names.Contains(name)) .ToArray(); } return new Shiritori_Md().GetLongest(names.ToArray(), lastName, JOINT_NUM); } } private class Shiritori_Md { public string[] GetLongest(string[] names, string lastName, int numOfJoint) // lastName: null == 制限なし, numOfJoint: 0 == 制限なし { Node_t[] nodes = names .Select(name => new Node_t() { Word = name }) .ToArray(); foreach (Node_t node in nodes) node.EndPtn = GetEndPtn(node.Word); foreach (Node_t node in nodes) node.NextNodes = nodes .Where(v => v.Word.StartsWith(node.EndPtn)) .ToArray(); SCommon.CRandom.Shuffle(nodes); for (int index = 0; index < nodes.Length; index++) nodes[index].JointFlag = index < numOfJoint; LongestNodeArray = new Node_t[0]; JointSeigenNASHIFlag = numOfJoint == 0; string startPtn = lastName == null ? null : GetEndPtn(lastName); foreach (Node_t node in nodes) if (startPtn == null || node.Word.StartsWith(startPtn)) Search(nodes, node); string[] ret = LongestNodeArray .Select(node => node.Word) .ToArray(); #if false // 出力が正しいかチェック { for (int index = 1; index < ret.Length; index++) { string name1 = ret[index - 1]; string name2 = ret[index]; string name1EndPtn = Shiritori_Md.GetEndPtn(name1); if (!name2.StartsWith(name1EndPtn)) throw null; } if (SCommon.HasSame(ret, (a, b) => a == b)) throw null; } #endif return ret; } private Node_t[] LongestNodeArray; private bool JointSeigenNASHIFlag; private class Node_t { public string Word; public string EndPtn; public Node_t[] NextNodes; public bool Reached; public bool JointFlag; } public static string GetEndPtn(string name) { int p = name.Length - 1; int q = name.Length; if (name[p] == 'ー') // 長音 { p--; q--; } if ("ッャュョァィゥェォ".Contains(name[p])) // 拗促音 p--; return name.Substring(p, q - p); } private void Search(Node_t[] nodes, Node_t startNode) { foreach (Node_t node in nodes) node.Reached = false; S_Nodes = nodes; S_Route = new List<Node_t>(); S_Route.Add(startNode); startNode.Reached = true; S_Next(); S_Nodes = null; S_Route = null; } private Node_t[] S_Nodes; private List<Node_t> S_Route; private void S_Next() { Node_t lastNode = S_Route[S_Route.Count - 1]; if (LongestNodeArray.Length < S_Route.Count && (JointSeigenNASHIFlag || lastNode.JointFlag)) LongestNodeArray = S_Route.ToArray(); foreach (Node_t node in lastNode.NextNodes) { if (!node.Reached) { node.Reached = true; S_Route.Add(node); S_Next(); node.Reached = false; S_Route.RemoveAt(S_Route.Count - 1); } } } } } }
結果
実行時間：6時間くらい
最長の長さ：133 (貪欲法なので真の最長とは限らない)
ヒッグススプレイ イツツバクローバー バイトアルヒクマ マラルメ メジロパーマー マリタイムシッパー パンパグランデ デザートベイビー ビワハヤヒデ デュオペルテ テイエムオペラオー オグリキャップ プチフォークロア アンコールワンモア アンロックザキー キンダーシャッツ ツウカア アップツリー リードエスエフ フライフィールド ドカドカ カワカミプリンセス スカンダ ダイタクヘリオス スリヴァッサ サムソンビッグ グリードホロウ ウィストクラフト トコトコ コスモスクレイパー パンパシフィック クリエイトセンド ドラグーンスピア アートルムグリモア アテーメ メジロブライト トゥージュール ルンバステップ プリメーラチーカ カツラギエース ステンツ ツーリングバイク クレセントエース スターリープライド ドミツィアーナ ナイスネイチャ チャタリングチーク クスタウィ ウィズカスパール ルーラルレジャー ジャーマンケーキ キュラキュラ ライスシャワー ワガハドウ ウィキッドレディ ディアレストギフト トゥトゥヌイ インディアンブレス スピーチレスハック クンバカルナ ナジュワー ワークフェイスフル ルミナスエスクード ドルジェ ジェンティルドンナ ナビゲートライト トーチアンドブック クレイジーインラブ ブラングリモア アルトピャーノ ノワールグリモア アクアレイク クピドズシュート トウカイテイオー オボロイブニング グーテンベルク クラースナヤ ヤマニンゼファー ファイネストデイ イズカリ リトルトラットリア アクアリバー バイタルダイナモ モンジュー ジュエルルビー ビアンコグリモア アルケカンジュ ジュエルオニキス スノーフロスト トラフィックライツ ツルマルツヨシ シナモンミルク クラシックコメディ ディスティネイト トランセンド ドミナントパワー ワンインチオブラブ ブリーズチョッパー パイケア アングータ タイドアンドフロウ ウイニングチケット トランペットリズム ムルジャーナ ナリタトップロード ドリコスランナー ナカヤマフェスタ タヴァティムサ サラサーテオペラ ラピッドビルダー ダイイチルビー ビーティングパルス スペインジェラート トラッドパルフェ フェアリーズエコー コードオブハート トロピカルスカイ イッツコーリング グリンタンニ ニシノフラワー ワンダーアキュート トンネリングボイス スティルインラブ ブリテンプライム ムーンポップ プレザントクラーク クリッカー カウリラリス スクイーズアウト トゥプシマティ ティッピングタップ プカプカ カラフルパステル
2024.9.23 追記
なんとなしにアルゴリズムをシンプルにしてみたら記録が伸びた。
モブ含め総勢 807 名
using System; using System.Collections.Generic; using System.Linq; using System.Text; using Charlotte.Commons; namespace Charlotte.Tests { public class Test0012 { #region RES_NAMES /// <summary> /// 公式(https://umamusume.jp/character)に紹介されているウマ娘＋モンジュー (131名) @ 2024.9.22 /// </summary> private string RES_NAMES = @" アイネスフウジン アグネスタキオン アグネスデジタル " +----------------+ | 長いので途中省略 | +----------------+ @" ヴィブロス ヴィルシーナ ヴェニュスパーク ; ここから追加 モンジュー ; ---- ; 2024.6.25 公式に追加されたウマ娘 カルストンライトオ デュランダル ドリームジャーニー ビリーヴ ブエナビスタ ; ---- ; 更に公式に追加されたウマ娘 (2024.9.22 現在) バブルガムフェロー ; ---- "; #endregion #region RES_MOB_NAMES /// <summary> /// モブウマ娘一覧(https://mobumamusume.net/name_list)に紹介されているモブウマ娘 (615名) @ 2024.6.15 /// </summary> private string RES_MOB_NAMES = @" アーケードチャンプ アートルムグリモア アーリースプラウト " +----------------+ | 長いので途中省略 | +----------------+ @" ワクワクリボン ワルツステップ ワンインチオブラブ "; #endregion #region RES_KAIGAI_MOB_NAMES /// <summary> /// 海外のモブウマ娘一覧(https://mobumamusume.net/abroad)に紹介されている海外モブウマ娘 (61名) @ 2024.6.16 /// </summary> string RES_KAIGAI_MOB_NAMES = @" アジーザ アルトピャーノ アルビコッコ " +----------------+ | 長いので途中省略 | +----------------+ @" プロムス ボールス レイナーディン "; #endregion private class Word_t { public string Word; public string EndPtn; public Word_t(string word) { this.Word = word; this.EndPtn = GetEndPtn(word); } private static string GetEndPtn(string word) { int i = word.Length - 1; if (word[i] == 'ー') // ? 長音符 i--; int s = i; int e = i + 1; if ("ァィゥェォッャュョヮヵヶ".Contains(word[i])) // ? 拗促音 s--; return word.Substring(s, e - s); } // 作業用 // public bool Reached; public Word_t[] ConnectableWords; } public void Test01() { Word_t[] words = SCommon.TextToLines(RES_NAMES + "\r\n" + RES_MOB_NAMES + "\r\n" + RES_KAIGAI_MOB_NAMES ) .Select(line => line.Trim()) .Where(line => line != "" && line[0] != ';') .Select(line => new Word_t(line)) .ToArray(); foreach (Word_t word in words) { word.ConnectableWords = words .Where(w => w.Word.StartsWith(word.EndPtn)) .ToArray(); } Word_t[] best = new Word_t[0]; for (; ; ) { Word_t[] curr = TryShiritori(words); if (best.Length < curr.Length) { best = curr; curr = null; // 2bs foreach (Word_t word in best) Console.WriteLine(word.Word); Console.WriteLine(best.Length); } } } // マジックナンバー // もっと調整すれば伸びるかも... // private const int MAGIC_NUMBER_01 = 4; private const int MAGIC_NUMBER_02 = 4; private Word_t[] TryShiritori(Word_t[] words) { Word_t[] best = new Word_t[] { SCommon.CRandom.ChooseOne(words) }; for (int depth = 1; ; depth++) { Word_t[] aFewBack = best.Take(Math.Max(1, best.Length - MAGIC_NUMBER_01)).ToArray(); Word_t[] aFewBackBest = null; for (int trycnt = 0; trycnt < depth * MAGIC_NUMBER_02; trycnt++) { Word_t[] curr = Search(words, aFewBack); if (aFewBackBest == null || aFewBackBest.Length < curr.Length) aFewBackBest = curr; } if (aFewBackBest.Length <= best.Length) break; best = aFewBackBest; } return best; } private Word_t[] Search(Word_t[] words, Word_t[] destLead) { foreach (Word_t word in words) word.Reached = false; foreach (Word_t word in destLead) word.Reached = true; List<Word_t> dest = destLead.ToList(); for (; ; ) { Word_t lastWord = dest[dest.Count - 1]; Word_t[] nextWords = lastWord.ConnectableWords.Where(w => !w.Reached).ToArray(); if (nextWords.Length == 0) break; Word_t nextWord = SCommon.CRandom.ChooseOne(nextWords); nextWord.Reached = true; dest.Add(nextWord); } return dest.ToArray(); } } }
結果
実行時間：8時間くらい
最長の長さ：216 (貪欲法なので真の最長とは限らない)
ゴールドシュシュ シュヴィークザーム ムシャムシャ シャープアトラクト トーチアンドブック クラシックコメディ ディヴィニティー ティッピングタップ プリスティンソング グリーンシュシュ シュプールムーバー バシレイオンタッチ チルウェイヴ ヴァッサゴ ゴドルフィンバルブ ブラボーツヴァイ イマジンサクセス スノーフロスト トランセンド ドミナントパワー ワークフェイスフル ルンバステップ プニプニ ニシノフラワー ワイスマネージャー ジャドプラーテ テトラビブロス スプリングハッピー ピンクシュシュ シュガーニンフェ フェニキアディール ルーラルレジャー ジャッジョーロ ロイスアンドロイス ステンツ ツーリングバイク クンバカルナ ナルキッソス スプーキーナイト トランペットリズム ムルーガ ガーリースマイル ルミナスエスクード ドゥラメンテ テンダーステップ プロペライザー ザオバアー アメティースタ タップステップ プレダトリス スリヴァッサ サイレンススズカ カジュアルスナップ プチフォークロア アクアガイザー ザンバーハ ハープアルファ ファイネストデイ イースタンダイナー ナリタトップロード ドルジェ ジェンティルドンナ ナイスネイチャ チャタリングチーク クピドズシュート トンネリングボイス スターリープライド ドロッピングリンク クリッカー カウリラリス スクイーズアウト トコトコ コインシデンス スーペリアブルーム ムルジャーナ ナーイリズム ムーンポップ プリメーラチーカ カワカミプリンセス スーパークリーク クレセントエース スウィートパルフェ フェアリーズエコー コロッセオファイト トゥトゥヌイ インディアンブレス スピーチレスハック クスタウィ ウィキッドレディ ディスティネイト トラフィックライツ ツインターボ ボウアンドシールド ドミツィアーナ ナジュワー ワンインチオブラブ ブラボーセカンド ドリコスランナー ナカヤマフェスタ タイドアンドフロウ ウカルディ ディアレストギフト トロピカルスカイ インテンスリマーク クロニクルオース スカンダ ダディーズブーツ ツウカア アンチェンジング グラスワンダー ダイイチルビー ビワハヤヒデ デュオバックラー ラピッドビルダー ダブルサラウンド ドラグーンスピア アンコールワンモア アイスホッパー パワフルトルク クラヴァット トンボロ ロディーナ ナターレノッテ テルパンダー ダークグリモア アウトオブブラック クラースナヤ ヤッピーラッキー キタサンブラック クレイジーインラブ ブリッジコンプ プロムス スティルインラブ ブリーズエアシップ プレザントクラーク クリシュマルド ドカドカ カツラギエース スイープトウショウ ウミディタ タヴァティムサ サムソンビッグ グリードホロウ ウォーキートーキー キララウス ストレートバレット トウカイテイオー オジュルデュイ イズカリ リボンヴィルレー レアキンスリー リードポエトリー リフレクター タイムティッキング グレイトハウス スペシャルウィーク クライネキステ テイエムオペラオー オレッキーノ ノワールグリモア アクアリバー バイタルダイナモ モンジュー ジュエルサファイア アップツリー リボンララバイ イラッパ パスタイムジョイ インサラータ ターボデトネーター タマシチ チーフパーサー サンフィッシュレイ イツツバクローバー バードアンドクリフ フィールフロイデ デュオジャヌイヤ ヤエノムテキ キュラキュラ ライスシャワー ワルツステップ プカプカ カルストンライトオ オグレッセ セイウンスカイ インサイトキャッチ チョコチョコ コパノリッキー キンダーシャッツ ツルマルツヨシ シャンソンジェンヌ ヌュアージュ ジュエルルビー ビヨンドレブリミ ミスターシービー ビームオブラブ ブリーズチョッパー パイケア アルビコッコ コスモスクレイパー パンパグランデ デュアリングステラ ラトウィゥジ ジャリアー アイタンリ リーフリーフ フリルドチェリー リードエスエフ フリルドベリー リボンエレジー ジャーマンケーキ キングヘイロー ローズブーケトス スペインジェラート トゥプシマティ ティップオブタン
