プリキュアしりとりで遊ぶ【Go言語版】

久しぶりに Qiita を巡回してたら面白い記事があった。

Q. プリキュア名でしりとりをしたとき、最大で何人登場するか？ - Qiita

上の記事では C# で書いていたが，せっかくなので Go で解いてみよう。

問題

今回のお題は以下の通り。

プリキュア名でしりとりをしたとき、最大で何人登場するか？

これだけだとアレなので，もう少し詳しく見てみよう。

しりとりのルール

しりとり（shiritori）って外来語として通用するんだねぇ。

それはともかく，しりとりの基本的なルールは以下の通りとする。

最初の単語は任意
単語の最後の文字（Unicode 符号点単位）を先頭の文字とした単語を繋げていく
- 漢字・記号はそのまま解釈する
- 先頭・末尾の役物は無視する（役物のみの単語はないという前提）
  - 長音（ー）
  - 繰り返し記号（「々」など）
  - 句読点
  - 括弧類
- 濁点・半濁点は無視する（例：「へ」「べ」「ぺ」は同じとみなす）
- 拗音 (ようおん) および促音の文字は直音文字と同じとみなす（例：ュ→ユ，っ→つ）
各単語（文字列）は1回のみ使用可能（複数回使用は不可）
終了条件は以下の通り
- 単語の最後が「ん」または「ン」で終わった場合
- 次に繋げる単語が無くなった場合

「音」じゃなくて「文字」ベースなのでこんなところだろう。

今回「㍻ (U+337B)」や「㈱ (U+3231)」といった合成文字や半角カナ文字は Unicode 正規化の NFKC 変換したもので解釈することにした。たとえば「㍻」の先頭文字は「平」で末尾文字は「成」とみなす。また「㈱」では先頭・末尾の役物は無視するので先頭・末尾文字はいずれも「株」となる。

プリキュア特別ルール

プリキュアしりとりでは上の基本ルールに加えて以下の2つのルールを追加する。

単語として使える語はプリキュア名のみとする
プリキュア名の先頭の「キュア」は無視する

先頭の「キュア」を無視するのは「キュア◯◯」って名前が多すぎるため（笑）

プリキュア名のリスト

ぶっちゃけ「日アサ」の番組編成が変わってからプリキュアは観なくなったので¹，特に最近のシリーズは分からないのだが，幸いにも以下のリポジトリにデータがある。

sue445/rubicure: All about Japanese battle heroine “Pretty Cure (Precure)”

ただ，ここにあるデータ構造はちょっと使い辛かったので YAML ファイル中の precure_name 項目がある行だけを拾って一覧を作った。劇場版オリジナルキャラも併せて，以下の66人でいいはず²。

キュアアクア, キュアアムール, キュアアンジュ, キュアイーグレット, キュアウィンディ, キュアエコー, キュアエトワール, キュアエース, キュアエール, キュアカスタード, キュアグレース, キュアコスモ, キュアサニー, キュアサンシャイン, キュアショコラ, キュアジェラート, キュアスカーレット, キュアスター, キュアスパークル, キュアセレーネ, キュアソレイユ, キュアソード, キュアダイヤモンド, キュアトゥインクル, キュアドリーム, キュアハッピー, キュアハニー, キュアハート, キュアパイン, キュアパッション, キュアパルフェ, キュアビューティ, キュアビート, キュアピース, キュアピーチ, キュアフェリーチェ, キュアフォンテーヌ, キュアフォーチュン, キュアフローラ, キュアブライト, キュアブラック, キュアブルーム, キュアブロッサム, キュアプリンセス, キュアベリー, キュアホイップ, キュアホワイト, キュアマカロン, キュアマシェリ, キュアマジカル, キュアマリン, キュアマーチ, キュアマーメイド, キュアミューズ, キュアミラクル, キュアミルキー, キュアミント, キュアムーンライト, キュアメロディ, キュアラブリー, キュアリズム, キュアルージュ, キュアレモネード, キュアロゼッタ, シャイニールミナス, ミルキィローズ

「順列」の派生としてのしりとり

コードを考えながら思ったが，しりとりって順列（permutation）のバリエーションなんだね。順列といえば2年前に

日能研の問題をGo言語で力づくで解いてみた(2018/11) - Qiita

という記事を Qiita で書いたが，あれの応用と考えたら後は早かった。まぁ for 文まわして力ずくで解いてるんだけど（笑）

解答

今回用に組んだコードを以下のリポジトリに置いている。

spiegel-im-spiegel/precure-shiritori: Shiritori (Japanese Word Chain Game) with Precure (Pretty Cure)

しりとりのルールをできるだけ汎用に書こうとして思ったよりコード量が多くなっちゃたので，中身の解説は割愛する。速度的な効率は重視してなくて，愚直なだけのコードなので言語的に難しいところはない筈。強いて言うなら，順列探索の再帰処理で配列のコピーを渡す点がポイントかな。

package shiritori

//Remove メソッドは指定した語を抜いた残りのリストのコピーを返す
func (ws *Words) Remove(word *Word) *Words {
    if !ws.In(word) {
        return ws.Clone()
    }
    wss := make([]*Word, 0, cap(ws.words)-1)
    for _, w := range ws.words {
        if !w.Equal(word) {
            wss = append(wss, w)
        }
    }
    return NewWords(wss)
}

func Do(strs ...string) []*List {
    ws := NewWords(NewWordSlice(strs...))
    if ws.Len() == 0 {
        return []*List{}
    }

    slst := []*List{}
    w := ws.Begin()
    for {
        if w == nil {
            break
        }
        l := do(w, ws.Remove(w))
        slst = append(slst, l...)
        w = ws.Next()
    }
    return slst
}

func do(first *Word, rest *Words) []*List {
    if rest.Len() == 0 {
        return []*List{NewList(first.String())}
    }
    tail := first.Tail()
    if tail == 'ん' || tail == 'ン' {
        return []*List{NewList(first.String())}
    }
    wlst := rest.Filter(tail)
    if wlst.Len() == 0 {
        return []*List{NewList(first.String())}
    }

    slst := []*List{}
    next := wlst.Begin()
    for {
        if next == nil {
            break
        }
        ll := do(next, rest.Remove(next))
        for _, l := range ll {
            slst = append(slst, NewList(first.String()).AddList(l))
        }
        next = wlst.Next()
    }
    return slst
}

詳しくはリポジトリを見てください，ということで（笑）

で，最初のお題の解答は「9人」。コードの実行結果の詳細は以下の通り。

$ go run main.go
9 : キュアホイップ, キュアブラック, キュアグレース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
9 : キュアホイップ, キュアフェリーチェ, キュアエース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアパルフェ, キュアエース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアフェリーチェ, キュアエース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアハッピー, キュアピース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアホイップ, キュアプリンセス, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアホイップ, キュアブラック, キュアグレース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアホイップ, キュアフェリーチェ, キュアエース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
8 : キュアブラック, キュアグレース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアハッピー, キュアピース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアプリンセス, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアミューズ, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアフェリーチェ, キュアエース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアエース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアホイップ, キュアフローラ, キュアラブリー, キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : シャイニールミナス, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアホイップ, キュアプリンセス, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアピース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : ミルキィローズ, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアパルフェ, キュアエース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアホイップ, キュアフェリーチェ, キュアエース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
7 : キュアグレース, キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアハッピー, キュアビューティ, キュアイーグレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアブラック, キュアグレース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
7 : キュアホイップ, キュアブラック, キュアグレース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
6 : キュアブラック, キュアグレース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
6 : キュアショコラ, キュアラブリー, キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアビューティ, キュアイーグレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアピース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアプリンセス, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : シャイニールミナス, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアホイップ, キュアブライト, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアグレース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアスター, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアロゼッタ, キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアハッピー, キュアピース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
6 : キュアホイップ, キュアフローラ, キュアラブリー, キュアリズム, キュアムーンライト, キュアドリーム
6 : キュアエース, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアホイップ, キュアプリンセス, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
6 : キュアホイップ, キュアブラック, キュアグレース, キュアスカーレット, キュアトゥインクル, キュアルージュ
6 : キュアホイップ, キュアフェリーチェ, キュアエース, キュアスカーレット, キュアトゥインクル, キュアルージュ
6 : キュアパルフェ, キュアエース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
6 : キュアメロディ, キュアイーグレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアウィンディ, キュアイーグレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアフェリーチェ, キュアエース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
6 : キュアミューズ, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアハッピー, キュアビート, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : ミルキィローズ, キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
6 : キュアフローラ, キュアラブリー, キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアスカーレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアハッピー, キュアピース, キュアスカーレット, キュアトゥインクル, キュアルージュ
5 : キュアホイップ, キュアフェリーチェ, キュアエース, キュアスパークル, キュアルージュ
5 : キュアミント, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアハッピー, キュアビューティ, キュアイーグレット, キュアトゥインクル, キュアルージュ
5 : キュアピース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアハート, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアダイヤモンド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアラブリー, キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアベリー, キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアソード, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアパルフェ, キュアエース, キュアスカーレット, キュアトゥインクル, キュアルージュ
5 : キュアホイップ, キュアブラック, キュアグレース, キュアスパークル, キュアルージュ
5 : キュアブラック, キュアグレース, キュアスカーレット, キュアトゥインクル, キュアルージュ
5 : キュアホイップ, キュアブルーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアプリンセス, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアジェラート, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアホイップ, キュアブロッサム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアショコラ, キュアラブリー, キュアリズム, キュアムーンライト, キュアドリーム
5 : キュアホイップ, キュアプリンセス, キュアスカーレット, キュアトゥインクル, キュアルージュ
5 : キュアビート, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : シャイニールミナス, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアグレース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアレモネード, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアカスタード, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアエース, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアマシェリ, キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアブライト, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアフローラ, キュアラブリー, キュアリズム, キュアムーンライト, キュアドリーム
5 : キュアフェリーチェ, キュアエース, キュアスカーレット, キュアトゥインクル, キュアルージュ
5 : キュアミューズ, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアイーグレット, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : ミルキィローズ, キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
5 : キュアホワイト, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
5 : キュアマーメイド, キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
4 : キュアハッピー, キュアビート, キュアトゥインクル, キュアルージュ
4 : キュアウィンディ, キュアイーグレット, キュアトゥインクル, キュアルージュ
4 : キュアフェリーチェ, キュアエース, キュアスパークル, キュアルージュ
4 : ミルキィローズ, キュアスカーレット, キュアトゥインクル, キュアルージュ
4 : キュアビューティ, キュアイーグレット, キュアトゥインクル, キュアルージュ
4 : キュアマシェリ, キュアリズム, キュアムーンライト, キュアドリーム
4 : キュアグレース, キュアスカーレット, キュアトゥインクル, キュアルージュ
4 : キュアメロディ, キュアイーグレット, キュアトゥインクル, キュアルージュ
4 : キュアピース, キュアスカーレット, キュアトゥインクル, キュアルージュ
4 : キュアエース, キュアスカーレット, キュアトゥインクル, キュアルージュ
4 : キュアブラック, キュアグレース, キュアスパークル, キュアルージュ
4 : キュアブルーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
4 : キュアホイップ, キュアプリンセス, キュアスパークル, キュアルージュ
4 : キュアブロッサム, キュアムーンライト, キュアトゥインクル, キュアルージュ
4 : キュアホイップ, キュアブロッサム, キュアムーンライト, キュアドリーム
4 : キュアプリンセス, キュアスカーレット, キュアトゥインクル, キュアルージュ
4 : キュアホイップ, キュアブルーム, キュアムーンライト, キュアドリーム
4 : キュアパルフェ, キュアエース, キュアスパークル, キュアルージュ
4 : キュアスター, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
4 : キュアロゼッタ, キュアダイヤモンド, キュアトゥインクル, キュアルージュ
4 : キュアミューズ, キュアスカーレット, キュアトゥインクル, キュアルージュ
4 : キュアベリー, キュアリズム, キュアムーンライト, キュアドリーム
4 : キュアホイップ, キュアフェリーチェ, キュアエコー, キュアコスモ
4 : キュアホイップ, キュアフェリーチェ, キュアエトワール, キュアルージュ
4 : キュアラブリー, キュアリズム, キュアムーンライト, キュアドリーム
4 : キュアリズム, キュアムーンライト, キュアトゥインクル, キュアルージュ
4 : キュアホイップ, キュアブライト, キュアトゥインクル, キュアルージュ
4 : キュアドリーム, キュアムーンライト, キュアトゥインクル, キュアルージュ
4 : キュアハッピー, キュアピース, キュアスパークル, キュアルージュ
4 : キュアホイップ, キュアフェリーチェ, キュアエール, キュアルージュ
4 : シャイニールミナス, キュアスカーレット, キュアトゥインクル, キュアルージュ
3 : キュアミント, キュアトゥインクル, キュアルージュ
3 : キュアアクア, キュアアムール, キュアルージュ
3 : キュアリズム, キュアムーンライト, キュアドリーム
3 : キュアブライト, キュアトゥインクル, キュアルージュ
3 : キュアレモネード, キュアトゥインクル, キュアルージュ
3 : キュアダイヤモンド, キュアトゥインクル, キュアルージュ
3 : キュアソード, キュアトゥインクル, キュアルージュ
3 : キュアパルフェ, キュアエコー, キュアコスモ
3 : キュアプリンセス, キュアスパークル, キュアルージュ
3 : キュアパルフェ, キュアエトワール, キュアルージュ
3 : キュアスカーレット, キュアトゥインクル, キュアルージュ
3 : キュアパルフェ, キュアエール, キュアルージュ
3 : キュアジェラート, キュアトゥインクル, キュアルージュ
3 : キュアブロッサム, キュアムーンライト, キュアドリーム
3 : キュアミューズ, キュアスパークル, キュアルージュ
3 : キュアカスタード, キュアトゥインクル, キュアルージュ
3 : ミルキィローズ, キュアスパークル, キュアルージュ
3 : キュアエース, キュアスパークル, キュアルージュ
3 : キュアブルーム, キュアムーンライト, キュアドリーム
3 : キュアホワイト, キュアトゥインクル, キュアルージュ
3 : キュアビート, キュアトゥインクル, キュアルージュ
3 : キュアハート, キュアトゥインクル, キュアルージュ
3 : シャイニールミナス, キュアスパークル, キュアルージュ
3 : キュアフェリーチェ, キュアエコー, キュアコスモ
3 : キュアフェリーチェ, キュアエトワール, キュアルージュ
3 : キュアフェリーチェ, キュアエール, キュアルージュ
3 : キュアイーグレット, キュアトゥインクル, キュアルージュ
3 : キュアマーメイド, キュアトゥインクル, キュアルージュ
3 : キュアピース, キュアスパークル, キュアルージュ
3 : キュアグレース, キュアスパークル, キュアルージュ
3 : キュアムーンライト, キュアトゥインクル, キュアルージュ
2 : キュアハッピー, キュアピーチ
2 : キュアマジカル, キュアルージュ
2 : キュアアクア, キュアアンジュ
2 : キュアミラクル, キュアルージュ
2 : キュアアムール, キュアルージュ
2 : キュアホイップ, キュアフォーチュン
2 : キュアホイップ, キュアフォンテーヌ
2 : キュアエコー, キュアコスモ
2 : キュアムーンライト, キュアドリーム
2 : キュアエトワール, キュアルージュ
2 : キュアエール, キュアルージュ
2 : キュアスパークル, キュアルージュ
2 : キュアトゥインクル, キュアルージュ
1 : キュアマリン
1 : キュアハニー
1 : キュアルージュ
1 : キュアパイン
1 : キュアソレイユ
1 : キュアセレーネ
1 : キュアパッション
1 : キュアサンシャイン
1 : キュアサニー
1 : キュアコスモ
1 : キュアピーチ
1 : キュアフォンテーヌ
1 : キュアフォーチュン
1 : キュアアンジュ
1 : キュアミルキー
1 : キュアマカロン
1 : キュアマーチ

いやぁ，キュアホイップから始まるしりとり最強！そしてキュアルージュで終わるパターン大杉（笑）

でも最初に挙げた記事としりとりの内容がだいぶ違うんだよなぁ。違う理由は何となく想像がつくけど… まぁ，いいか。

今後の課題

いや，ちゃんと YAML 勉強しようかと思って。

gopkg.in/yaml.v3 パッケージを使えば YAML のアンカーとかも解釈できるようなので，調べてみたい。

参考図書

プログラミング言語Go (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES): Alan A.A. Donovan (著), Brian W. Kernighan (著), 柴田芳樹 (翻訳); 丸善出版 2016-06-20; 単行本（ソフトカバー）; 4621300253 (ASIN), 9784621300251 (EAN), 4621300253 (ISBN), 9784621300251 (ISBN); 評価

著者のひとりは（あの「バイブル」とも呼ばれる）通称 “K&R” の K のほうである。この本は Go 言語の教科書と言ってもいいだろう。

reviewed by Spiegel on 2016-07-13 (powered by PA-APIv5)

なんで「題名のない音楽会」を土曜日に移動したんだ。ぶつぶつぶつ。まぁ実家では私にテレビ・チャンネル権はないので，そもそもテレビを観ないのだが。 ↩︎
今回は 2020-03-28 コミット時のものを使っている。 ↩︎