2015年03月25日

C#でしりとりを続けるプログラムを書く

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その80

■問題 (出題者:greentea さん)
単語のリストを読み込んで、そのリストにある単語で「しりとり」をします。
一番長くしりとりを続けるためのプログラムを書いてください。
また、単語数に対して、計算量がどのように増えていくかも考えて下さい。

なお、単語リストの一例として
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/index-j.html で公開されている
http://www.ais.riec.tohoku.ac.jp/lab/wordlist/fam55_40.txt があります。

ただし、
・一度使った単語は使わないこと(リストに重複がある可能性は考えなくてよい)
・「ん」で終わる単語を使用するか、リスト内にしりとりを続けられる単語がなくなったときに、しりとりは終了する
・一番最初は、好きな単語から初めてもよい
・「一番長くしりとりを続ける」とは、しりとりが終了するまでに使用する単語数が最大になるよう、しりとりの単語を選ぶことをいう

参考: 難聴者のための単語了解度試験用単語リスト

一番最初の単語は、単語リストの先頭にある単語としました。
幅優先探索ですべてのパターンを探索しています。

まずは、単語を表すWordクラスを定義。First, Last プロパティで、先頭文字と、最後の文字を得ることができます。


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    // 単語を表すクラス (最初と最後の文字を取得する機能がある)
    // ちょうちょ、きしゃ などは、「や」が最後の文字とする。
    public class Word {
        public string Text { get; set; }
        private char first;
        private char last;
        public Word(string word) {
            Text = word;
            first = ToChokuon(Text[0]);
            last = ToChokuon(Text[Text.Length - 1]);
            // 長音一文字の単語はない前提
            if (last == 'ー' || last == '−')
                last = ToChokuon(Text[Text.Length - 2]);
        }
        public char First {
            get {
                return first;
            }
        }
        public char Last {
            get {
                return last;
            }
        }

        // ッは促音だが、拗音(Youon)という変数名とする
        private const String Youon = "ァィゥェォヵヶッャュョヮ";
        private const String Chokuon = "アイウエオカケツヤユヨワ";
        private char ToChokuon(char c) {
            int ix = Youon.IndexOf(c);
            if (ix > 0)
                return Chokuon[ix];
            return c;
        }

        public override string ToString() {
            return this.Text.ToString();
        }

    }
}

次が、このWordクラスを使って、問題を解く WordChainSolver クラス。
既出の単語かどうかの判断は、その都度結果リストにあるかどうかで判断しています。
ちょっと非効率かなと思います。
とはいえ、大元の単語リストから既出の単語を取り除く方法は、幅優先探索アルゴリズムの性質上 そのときの状態を記憶しておかなくてはならなくなるので、それはそれで、コストがかかります。
でも、それほど多くの要素を探索することにはならないと思うので、まあこれで良しとしました。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Doukaku.Org {
    class WordChainSolver {
        public List<Word> WordList { get; set; }
        public WordChainSolver(List<Word> wordList) {
            WordList = wordList.ToList();
        }

        private Queue<WordChainList> _queue = new Queue<WordChainList>();
        public WordChainList Solve(Word word) {
            WordChainList firstState = new WordChainList(WordList);
            firstState.Add(word);
            WordChainList ans = firstState;
            _queue.Enqueue(firstState);
            while (_queue.Count > 0) {
                var curr = _queue.Dequeue();
                ans = curr;
                 foreach (var w in Candidate(curr.LastWord)) {
                    if (ans.Find(x => x == w) != null)
                        continue;
                    curr.Add(w);
                    _queue.Enqueue(curr.Clone());
                    curr.RemoveAt(curr.Count - 1);
                }

            }
            return ans;
        }
        // 候補の単語を列挙する
        private IEnumerable<Word> Candidate(Word word) {
            return WordList.Where(x => word.Last == x.First).ToList();
        }
    }


    // しりとりした結果を覚えておくクラス
    public class WordChainList {
        private List<short> _chain = new List<short>();
        private List<Word> AllWords { get; set; }

        public WordChainList(List<Word> wordList) {
            this.AllWords = wordList;
        }

        public Word LastWord {
            get {
                int ix = _chain[_chain.Count - 1];
                return AllWords[ix];
            }
        }

        public WordChainList Clone() {
            var wcl = new WordChainList(this.AllWords);
            wcl._chain = _chain.ToList();
            return wcl;
        }

        public void Add(Word word) {
            short ix = (short)AllWords.FindIndex(x => x.Text == word.Text);
            _chain.Add(ix);
        }

        public Word Find(Func<Word, bool> pred) {
            foreach (var w in GetWordList())
                if (pred(w) == true)
                    return w;
            return null;
        }

        public IEnumerable<Word> GetWordList() {
            foreach (var ix in _chain) {
                yield return AllWords[ix];
            }
        }

        public int Count {
            get { return _chain.Count; }
        }

        internal void RemoveAt(int index) {
            _chain.RemoveAt(index);
        }
    }
}

最後が、Mainメソッド。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;


namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            DateTime dt = DateTime.Now;
            var list = WordsFile.GetWordList(120);
            Word startWord = list[0];
            WordChainSolver wc = new WordChainSolver(list);
            var ans = wc.Solve(startWord);
            ans.GetWordList().ToList().ForEach(w => Console.WriteLine(w.Text));
            Console.WriteLine("{0}", ans.Count);
            Console.WriteLine(DateTime.Now - dt);
            Console.ReadLine();
        }
    }
}

僕のPCだと単語リストの単語数が120程度ならば直ぐにもとまりますが、140になると、一分以上かかります。150だと、いつまでも終わらないので、終わるのを待てずに途中で終了させてしまいました。
「一番長くしりとりを続ける」という制約があるので仕方ないかな。
「一番長くしりとりを続ける」ではなく、「ベター」な方法というのならば、もう少し速度を稼ぐ方法もあるとは思うのですが...

あっそうだ。WordsFileクラスを載せるのを忘れました。
単語ファイルは、上記問題文の参考URLにあるファイルをダウンロードして、そのままの形式で利用しています。
引数で指定した数だけ、先頭から取得して返しています。

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    // 単語ファイルの読み込み
    // tab, カンマ、空白で区切る。
    static class WordsFile {
        static public List<Word> GetWordList(int count) {
            List<Word> list = new List<Word>();
            using (StreamReader sr = new StreamReader(@"WordFile.Txt")) {
                while (sr.EndOfStream == false) {
                    string s = sr.ReadLine();
                    var words = s.Split('\t', ' ', ',');
                    list.AddRange(words.Where(t => !string.IsNullOrEmpty(t)).Select(w => new Word(w)));
                }
            }
            return list.Take(count)
                       .ToList();
        }
    }
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52411742