2015年03月29日

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

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

「C#でしりとりを続けるプログラムを書く」 の続きです。

前回示したプログラムでは、問題の趣旨どおり、もっとも長くしりとりができる単語列を作り出すことができましたが、使える単語数が増えると、極端に処理速度が遅くなるという欠点がありました。
そのため、今度は最長ではなく、しりとりをそれなりに長く続けることのできるプログラムを書いてみました。
つまり、前回はすべての手を読んで一番長くしりとりを続けられるものを解として求めたのですが、今度は、数手先まで読んで、その中から、もっとも良いと思われる一手(次の単語)を選ぼうというものです。
より現実的な時間で解が求まるはずです。ただし、最も長いしりとりとは限りませんが...

ここで重要なのは、選んだ単語が良い手かどうかを判断する評価関数をどうやって作成するかです。
この評価関数の良し悪しによって、結果が大きく変わってきます。

ここでは、現在の状態から、次に続けることができる単語の候補一覧を作成し、この候補ごとに、単語を4手先まで先読みし、5つ目にくる候補の単語がいくつあるかを数えてポイント化しています。
このポイントがもっとも高い手を選ぶようにすることで、解を求めています。
なお、4手先までしりとりが続かない場合は、見込みが無い手ということで、読んだ深さをマイナスした値をポイントとしてを返します。
この評価方法が果たしてよい評価関数なのかはなんともいえませんが、結果をみる限りそれなりに有効に動いているようです。

実際の実装では、MaxDepthという定数に 4を定義し、MaxDepth先まで読んでいます。
最初は、考慮すべき手が多いけれど、だんだんと考慮すべき手が少なくなってくるという性質を考慮すれば、すこしずつMaxDepth を増やしていくという方法も採れると思います。
そうすれば、もう少し良い解が得られるかもしれません。
ただ、急激にMaxDepthを増やすと現実的な時間で終わらなくなってしまうので注意か必要です。

このプログラムでは、単語リストが 400 でも、それなりの時間で解を得ることができました。
この記事の最後に、実行結果も載せておきます。

以下、実際に書いたコードです。前回と重複するクラスもありますが、それも含めて掲載します。
全部で、4つのCSファイルから成っています。
ちなみに評価関数Evaluateは、MaxDepth手まで先読みするのに、深さ優先の探索を行っています。

■Program.cs
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(400);
                Word startWord = list[0];
                WordChainThinker wc = new WordChainThinker(list);
                var ans = wc.Solve(startWord);
                ans.ToList().ForEach(w => Console.Write(w.Text + " - "));
                Console.WriteLine("\n{0}", ans.Count);
                Console.WriteLine(DateTime.Now - dt);
                Console.ReadLine();
        }
    }
}
ここでは、WordListの先頭の単語からしりとりを始めています。

■Word.cs
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();
        }

    }
}

■ WordChainThinker.cs  
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class WordChainThinker {
        private List<Word> WordList { get; set; }
        private const int MaxDepth = 4;

        public WordChainThinker(List<Word> wordList) {
            WordList = wordList.ToList();
        }

        public List<Word> Solve(Word word) {
            List<Word> ans = new List<Word>();
            Word next = word;
            while (next != null) {
                WordList.Remove(next);
                ans.Add(next);
                next = SelectNextWord(WordList,next);
            }
            return ans;
        }

        // 次に続く単語を決定する。
        private Word SelectNextWord(List<Word> wordList, Word curr) {
            //DepthX5++;

            var candidates = Candidate(curr).ToList();
            Word best = null;
            int topPoint = int.MinValue;
            foreach (var word in candidates) {
                int pt = Evaluate(wordList, word, MaxDepth);
                if (pt > topPoint) {
                    topPoint = pt;
                    best = word;
                }
            }
            return best;
        }

        // startで示した単語を評価し、ポイント化する
        private int Evaluate(List<Word> wordList, Word start, int depth) {
            var candidates = Candidate(start).ToList();
            if (depth == 0)
                return candidates.Count;
            if (candidates.Count == 0)
                return -depth;
            int maxPoint = int.MinValue;
            foreach (var word in candidates) {
                wordList.Remove(word);
                int pt = Evaluate(wordList, word, depth - 1);
                if (pt > maxPoint) {
                    maxPoint = pt;
                }
                wordList.Add(word);
            }
            return maxPoint;
        }

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

■WordsFile.cs
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();
        }
    }
}


実行結果


アイアイ - イリフネ - ネンブツ - ツユザム - ムササビ - ビンソク - クミダシ - シ
タヅミ - ミミアテ - テイテツ - ツジツマ - マヤカシ - シャクナゲ - ゲレツサ - サ
ンバシ - ショウワル - ルイベツ - ツイタチ - チャクフク - クチブリ - リンセツ -
ツイスト - トリタテ - テキシツ - ツキビト - トリモノ - ノリニゲ - ゲジゲジ - ジ
ャアクサ - ササヤブ - ブツヨク - クシガタ - タンパツ - ツミビト - トシガス - ス
ナヤマ - マタシタ - タチノミ - ミズバナ - ナカワタ - タカダイ - イワブロ - ロコ
ツサ - サシズメ - メイフク - クロヌリ - リョウヒザ - ザイバツ - ツケヒゲ - ゲツ
ガク - クニガラ - ランギリ - リクアゲ - ゲイフウ - ウラガネ - ネリミソ - ソトブ
ロ - ロマンハ - ハラダチ - チチカタ - タマジャリ - リンカク - クセモノ - ノリコ
ミ - ミチシオ - オソジモ - モノグサ - サワガニ - ニシガワ - ワリシタ - タイギゴ
- ゴウユウ - ウスカワ - ワニガワ - ワカアユ - ユウナギ - ギンパイ - イヌジニ -
ニシカゼ - ゼンニチ - チマナコ - コシヌケ - ケツゴウ - ウシノヒ - ヒャクニチ -
チャブダイ - イシバシ - シールド - ドウナガ - ガイユウ - ウワバミ - ミチスジ -
ジカバキ - キンツバ - バシャウマ - マタガシ - シャクハチ - チョサクカ - カザアナ
- ナニゴト - トリツギ - ギタイゴ - ゴクボソ - ソデナシ - シラナミ - ミズヒキ -
キュウシキ - キャクヒキ - キジバト - トリヨセ - セイユウ - ウレユキ - キャクマチ
- チカヅキ - キュウヨウ - ウキフネ - ネガイデ - デハジメ - メンモク - クタビレ
- レイブン -
121
00:00:07.2880000

  

Posted by gushwell at 22:30Comments(0)TrackBack(0)

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();
        }
    }
}

  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年03月22日

C#で道順を数える

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

■問題 (出題者:E_Mattsan さん)
図.1のような。格子状の経路があるとします。
(1) このときPからQまでいくのに何通りの経路があるか数えてください。ただし遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。

(2) (1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。


P-+-+-+    P-+-+-+
| | | |    | | | |
+-+-+-+    +-+-+-+
| | | |    |   | |
+-+-+-+    +-+-+ +
| | | |    | | | |
+-+-+-+    +-+ +-+
| | | |    | | | |
+-+-+-Q    +-+-+-Q
   図.1       図.2

経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。

※問題は、野紾昭弘「離散数学『数え上げ理論』」(講談社 ブルーバックス)「第3章 道順を数える」から拝借させて頂きました。

プログラマらしく、再帰処理で愚直にカウントしています。つまり、(1) も (2) も同じコードで解を求めています。

上記「離散数学『数え上げ理論』」にはどのような解法が載っているのだろうか?
きっと、数学者は、僕には思いもよらない方法を導き出すんだろうな。

なお、左上にPがあることを前提としています。
データは、テキストファイルとして与えています。

using System;
using System.IO;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string[] lines = File.ReadAllLines("MapData.txt");

            Solver map = new Solver(lines);
            Console.WriteLine(map.CountPath());
        }
    }

    class Solver {
        private int xmax;
        private int ymax;
        private string[] lines;

        public Solver(string[] lines) {
            this.lines = lines;
            ymax = lines.Length;
            xmax = lines[0].Length;
        }

        public char this[int x, int y] {
            get { return lines[y][x]; }
        }

        public bool ExistsRight(int x, int y) {
            return (x + 1 < xmax && this[x + 1, y] != ' ');
        }
        public bool ExistsDown(int x, int y) {
            return (y + 1 < ymax && this[x, y + 1] != ' ');
        }

        public int CountPath(int x = 0, int y = 0) {
            if (this[x,y] == 'Q')
                return 1;
            int sum = 0;
            if (ExistsRight(x, y))
                sum += CountPath(x + 2, y);
            if (ExistsDown(x, y))
                sum += CountPath(x, y + 2);
            return sum;
        }
    }
}

実行結果です。

入力ファイル

P-+-+-+
| | | |
+-+-+-+
|   | |
+-+-+ +
| | | |
+-+ +-+
| | | |
+-+-+-Q

出力
15

  
Posted by gushwell at 21:30Comments(0)TrackBack(0)

2015年03月18日

C#であみだくじ

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その78
■問題 (出題者:greentea さん)
次のような書式で与えられた「あみだくじ」があります。 (あみだくじはコード中に埋め込んでも、標準入力や 外部ファイルから読み込んでも、書きやすい方法でかまいません)

A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |

このあみだくじをたどって
A B C D E
| | |-| |
|-| | |-|
| |-| |-|
|-| |-| |
|-| | | |
B D C A E
のように結果を表示させるプログラムを作ってください。

記号 '-' が「入れ替え」を意味するってことが分かれば、それほど難しい問題ではないですね。

using System;
using System.IO;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var lines = File.ReadAllLines("amidakuji.txt");
            Amidakuji amida = new Amidakuji(lines);
            string s = amida.Solve();

            foreach (var line in lines)
                Console.WriteLine(line);
            Console.WriteLine(s);
            Console.ReadLine();
        }
    }
   
    class Amidakuji {
        string[] lines;
        public Amidakuji(string[] lines) {
            this.lines = lines;
        }

        public string Solve() {
            // 先頭には、A,B,C,D,E といった文字が入っている。
            char[] head = lines[0].ToCharArray();
            for (int j = 1; j < lines.Length; j++) {
                for (int k = 1; k < lines[j].Length; k += 2)
                    if (lines[j][k] == '-') {
                        // - は 入れ替えに他ならない。- の左右を入れ替える。
                        char temp = head[k - 1];
                        head[k - 1] = head[k + 1];
                        head[k + 1] = temp;
                    }
            }
            return new string(head);
        }
    }
}

実行結果です。

入力

A B C D E F
| | |-| | |
|-| | |-| |
| |-| |-| |
|-| |-| |-|
| |-| |-| |
|-| | | |-|
| | | | | |

出力

A B C D E F
| | |-| | |
|-| | |-| |
| |-| |-| |
|-| |-| |-|
| |-| |-| |
|-| | | |-|
| | | | | |
C D B F E A

  
Posted by gushwell at 21:50Comments(0)TrackBack(0)

2015年03月15日

C#で総当たり戦の日程を作成する

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

■問題 (出題者:ryugate さん)
任意の偶数Nのチームの総当たり戦を最短日数(N-1日)で行う場合の日程表を1つ作成してください。

解はひとつではない場合もあります。
もし、余力があれば、全ての可能性も求めてください。

これは、スポーツスケジューリングと言う分野の問題で、数学的には、カークマンの問題と言うのが近いようです。

例えば、4チームであれば、
1-2 3-4
1-3 2-4
1-4 2-3

6チームであれば

1-2 3-4 5-6
1-3 2-5 4-6
1-4 2-6 3-5
1-5 2-4 3-6
1-6 2-3 4-5

が解のひとつです。
参考: カークマンの組分け

すべての可能性は求めていません。日程表を一つ作成しています。

以下、はじめに書いたコードです。結構複雑になってしまいました。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            LeaguegameScheduling k = new LeaguegameScheduling();
            var sche = k.DoPlan(8);
            Console.WriteLine(sche);
            Console.ReadLine();
        }
    }

    class LeaguegameScheduling {
        public gameList DoPlan(int teams) {
            var nums = Enumerable.Range(1,teams);
            int days = teams - 1;

            // すべての試合を列挙する
            var q = (from a in nums
                     from b in nums
                     where a != b
                     select Game.Create(a, b))
                    .Distinct();
           
            // 1日の試合数
            int count = q.Count() / days;

            var games = new gameList(days, count);
            games = InnnerPlan(q.ToList(), games, 0, -1);
            return games;
        }

        // DoPlanの下請けメソッド (再帰処理をしている)
        private static gameList InnnerPlan(IEnumerable<Game> rest, gameList games, int day, int nth) {
            if (++nth >= games.NumberInOneDay) {
                day++;
                nth = 0;
            }
            if (rest.Count() == 0) {
                return games;
            }
            foreach (var g in rest) {
                if (games[day].Any(x => x.Contains(g.A) || x.Contains(g.B)))
                    // すでに試合 g のどちらかのチームが、その日、別のチームと試合することに
                    // なっているので、次の g を調べる。
                    continue;
                games[day][nth] = g;
                var result = InnnerPlan(rest.Except(new Game[] { g }), games, day, nth);
                if (result != null)
                    return result;
                games[day][nth] = new Game();
            }
            return null;
        }
    }

    public class gameList  {
        private Game[][] games;

        // 日数
        public int Days {get; set; }

        // 一日の試合数
        public int NumberInOneDay{get; set; }

         // インデクサーの定義
        public Game[] this[int day] {
            get { return games[day]; }
        }

        // コンストラクター
        public gameList(int days, int count) {
            games = new Game[days][];
            for (int i = 0; i < games.Length; i++ )
                games[i] = new Game[count];
            this.Days = days;
            this.NumberInOneDay = count;
        }

        // 文字列化
        public override string ToString() {
            StringBuilder sb = new StringBuilder();
            foreach (var oneday in games) {
                sb.AppendLine(oneday.Aggregate("", (r,x) => r + x + " "));
            }
            return sb.ToString();
        }
    }

    // 一致かどうかを簡単にするために、構造体にしている。
    public struct Game {
        public int A { get; private set; }
        public int B { get; private set; }

        // コンストラクタの代わりにこれを呼ぶ。
        public static Game Create(int a, int b) {
            var game = new Game();
            if (a < b) {
                game.A = a;
                game.B = b;
            } else {
                game.B = a;
                game.A = b;
            }
            return game;
        }

        public override string ToString() {
            return string.Format("{0}-{1}", A, B);
        }

        public bool Contains(int team) {
            return (this.A == team || this.B == team);
        }
    }
}

なんか複雑だなーということで、Webを調べていたら、すばらしい方法がありました。
参考URL 「リーグ戦の組み合わせ」http://www.geocities.co.jp/Berkeley-Labo/6317/league_01.htm

いやー、このアルゴリズムを考えた人は、すごいなー。これを自力で考え出せ!といわれても、たぶんできないと思います。
以下、そのアルゴリズムをC#で実装したコード。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var s = new Scheduling();
            var ans = s.DoPlan(8).ToList();
            ans.ForEach(x => Console.WriteLine(string.Join(" ", x.Select(y => y.ToString()))));
            Console.ReadLine();
        }
    }

    public class Pair {
        public int A { get; private set; }
        public int B { get; private set; }

        public Pair(int a, int b) {
            A = a;
            B = b;
        }

        public override string ToString() {
            return string.Format("{0}-{1}", A, B);
        }
    }

     class Scheduling {
        private List<int> Rotate(IEnumerable<int> ring) {
            var first = ring.Take(1);
            return ring.Skip(1).Concat(first).ToList();
        }

        public IEnumerable<IEnumerable<Pair>> DoPlan(int n) {
            List<int> ring = Enumerable.Range(2, n - 1).ToList();
            for (int i = 0; i < n - 1; i++) {
                List<Pair> games = new List<Pair>();
                games.Add(new Pair(1, ring[0]));
                int ix = 1;
                for (int diff = n - 3; diff > 0; diff -= 2) {
                    games.Add(new Pair(ring[ix], ring[ix + diff]));
                    ix++;
                }
                yield return games;
                ring = Rotate(ring);
            }
        }
    }

}

実行結果も示しておきます。
2つ目のプログラムでは、結果を縦方向に眺めると、上手い具合に循環しているのが見て取れます。

■最初のプログラムの実行結果
1-2 3-4 5-6 7-8
1-3 2-4 5-7 6-8
1-4 2-3 5-8 6-7
1-5 2-6 3-7 4-8
1-6 2-5 3-8 4-7
1-7 2-8 3-5 4-6
1-8 2-7 3-6 4-5

■2つめのプログラムの実行結果
1-2 3-8 4-7 5-6
1-3 4-2 5-8 6-7
1-4 5-3 6-2 7-8
1-5 6-4 7-3 8-2
1-6 7-5 8-4 2-3
1-7 8-6 2-5 3-4
1-8 2-7 3-6 4-5

  
Posted by gushwell at 21:49Comments(0)TrackBack(0)

2015年03月11日

C#でDawkins' weasel プログラムを書く

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

■問題 (出題者:ytakenaka さん)
ランダムな文字からMETHINKS IT IS A WEASELを作るプログラムを作れ。
簡単に流れを書いてみます。
1:ランダムな20文字を持つ文字列をもった300個作ります。
2:その文字列が"METHINKSITISAWEASEL"に近いものからソートします。
3:それぞれの文字列のなか1文字を別の文字に変化させたものを3つ用意します。
4:それを2:のソートをして上位300個残す。(900個あるうちで上位300個残すということです。)
5:以後3:と4:を繰り返す。
ランダムな文字変化は大文字だけでいいです。簡単にするために空白文字を外してあります。
METHINKS IT IS WEASELができたら終了。3と4の間でソートしたもので一番上位のものを毎回表示させると変化が楽しめます。:-)
Rickard Dawkinsがブラインドウォッチメイカー(現題:盲目の時計職人)の3章で書いていた有名なものです。さらに一般化してもらってもいいです。
参考

* http://home.pacbell.net/s-max/scott/weasel.html (JAVA アプレット)
* http://en.wikipedia.org/wiki/Weasel_program



巡回セールスマン問題を解く で示した遺伝的アルゴリズム(genetic algorithm)の簡易版といった感じですね。

「さらに一般化しても」とあるので、任意の文字列(すべて大文字)を与えられるようにしています。
でも、上記の通りコードを書いても、"METHINKSITISAWEASEL" よりも、すこし長めの文字列を与えると、僕の書き方が悪いのかいつになっても答えが求まりませんでした。

しかたないので、上記 3の処理をすこし変更しています。
示されたやり方だと、3つの子孫は、親の文字列よりも求める文字列との一致度が悪くなってしまう確率のほうが高いように思います。
そのため、自分自身も含めて3つを残すようにしています。こうすれば、生成した子孫は、求める文字列よりも類似度が親よりも悪くなることがありません。

うごかしてみると、直ぐに答えが見つかりました。

どのように文字列が変化していくのかを分かるように、途中結果を表示するようにしています。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Windows.Forms;
using System.Linq.Expressions;

namespace Doukaku.Org {
    public  class Program  {
        public static void Main() {
            Solver solver = new Solver();
            //var s = solver.Execute("METHINKS IT IS A WEASEL");
            var s = solver.Execute("THE PEN IS MIGHTER THAN THE SWORD");
            Console.WriteLine(s);
            Console.ReadLine();
            s = solver.Execute("The quick brown fox jumps over the lazy dog".ToUpper());
            Console.WriteLine(s);
            Console.ReadLine();
        }
    }

    public class Solver {
        private const string alphabets = "ABCDEFGHIJKLMNOPQRSTUVWXYZ ";
        private const int SetSize = 300;
        private const int IncreaseCount = 3;
        private readonly int CharCount = alphabets.Length;

        private string target;
        private Random rnd = new Random();

        public string Execute(string target) {
            this.target = target;
            var lines = CreateLines(target.Length);
            while (lines[0] != target) {
                lines = Survive(IncreaseLines(lines));
                Console.WriteLine("{0} {1}", lines[0], Distance(lines[0]));
            }
            return lines[0];
        }

        private IEnumerable<string> IncreaseLines(IEnumerable<string> list) {
            foreach (var s in list) {
                yield return s;   // 自分自身も残す。
                // 新たに作るのは2つの文字列。
                for (int i = 0; i < IncreaseCount - 1; i++)
                    yield return Mutate(s);
            }
        }

        // 文字列の変異
        private string Mutate(string s) {
            var ary = s.ToCharArray();
            ary[rnd.Next(target.Length)] = RnadomChar();
            return new string(ary);
        }

        // 生き延びる  上位setSize個だけを残す
        private IList<string> Survive(IEnumerable<string> list) {
            return list.OrderBy(s => Distance(s)).Take(SetSize).ToList();
        }

        // 長さlengthの文字列をsetSize個ランダムに生成する。
        private IList<string> CreateLines(int length) {
            return Enumerable.Range(1, SetSize)
                             .Select(n => MakeRandomString(length))
                             .OrderBy(s => Distance(s))
                             .ToList();
        }

        // 長さlengthの文字列をランダムに生成する。
        private string MakeRandomString(int length) {
            return Enumerable.Range(1, length)
                             .Aggregate("", (r, i) => r + RnadomChar());
        }

        // 求めたい文字列との差異を数値化して返す。0 ならば 一致。
        private int Distance(string s) {
            return s.Select((c, ix) => c == target[ix] ? 0 : 1).Sum();
        }

        // ランダムに一文字を返す。
        private char RnadomChar() {
            return alphabets[rnd.Next(CharCount)];
        }
    }
}

  
Posted by gushwell at 21:30Comments(0)TrackBack(0)

2015年03月08日

C#でリングノードベンチマーク

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

■問題 (出題者:tsuwabukiさん)
N個のノードを作り、1番目のノードに送られたメッセージは2番目のノードに、
2番目のノードに送られたメッセージは3番目のノードに、・・・、
N番目のノードに送られたメッセージは1番目のノードに送られるようにリングを形成し、
そのリング上を一つのメッセージがM回まわるのにかかる時間を計測してください。


M回の情報は、Nodeに持たせるべきなのか? Messageに持たせるべきなのか?すこし悩みましたが、 ここでは Node に持たせてみました。
なお、普通にメソッド呼び出しで、メッセージ送信を書くと、最後のメッセージを送った後に、処理はメソッドの呼び出し元に順に逆戻りしていくことになります。
これだととても無駄なことしているように思えてしまいます。それと、n,mの数が多いと、Stack Overflow の可能性もあります。
そのため、メソッド呼び出しでメッセージ送信するのではなく、Taskクラスを使い、タスクを非同期に起動する方法にしてみました。

でも、Waitの方法がちょっと気に入らないです。
ちなみに、最後までメッセージが渡ったら、そのメッセージをコンソールに出力させています。

あなたならどう書く?

using System;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            RingNodeBench(300, 50);
            Console.ReadLine();
        }

        static void RingNodeBench(int n, int m) {
            Stopwatch sw = new Stopwatch();
            sw.Start();
            // n個のノードを作成し、リングを形成。
            Node node1 = new Node(m);
            Node curr = node1;
            for (int i = 1; i < n; i++) {
                curr.Next = new Node(m);
                curr = curr.Next;
            }
            curr.Next = node1;

            // 一つ目のノードにメッセージを送信
            Message msg = new Message { Text = "メッセージ"  };

            node1.Post(msg);
            Node.Wait();

            sw.Stop();

            Console.WriteLine(sw.ElapsedMilliseconds);
        }
  

    }

    class Message {
        public string Text { get; set; }
    }

    class Node {
         private static AutoResetEvent _autoResetEvent = new AutoResetEvent(false);

        public static void Wait() {
            _autoResetEvent.WaitOne();
        }

        private int _count;
        public Node(int count) {
            _count = count;
        }
        public Node Next { get; set; }

        public void Post(Message message) {
            if (_count-- <= 0) {
                _autoResetEvent.Set();
                Console.WriteLine(message.Text);
                return;
            }
            Task.Factory.StartNew(() => this.Next.Post(message));
        }
    }
 }
  
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年03月04日

C#でケブンッリジ関数

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

■問題 (出題者:lunlumo さん)
与えた文章の各単語の最初と最後の文字以外の文字を入れ替えた文章を出力する処理を実装して下さい。元の文章の与え方は特に問いません。
参考: 確かに"読めてしまう"コピペ http://www.itmedia.co.jp/news/articles/0905/08/news021.html

単語を順に取り出し、文字を入れ替えるというだけの なんの変哲もない普通のコードだと思うので、特筆すべき点はないです。
EnumWordsで返すのを string ではなく、StringBuilderにして、 Changeメソッドには、その StringBuilderオブジェクトをそのまま渡して 処理したほうがすこしは効率的かなと思いますが、分かりやすさ優先ということで。


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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string s =
    @"こんにちは みなさん おげんき ですか? わたしは げんき です。
この ぶんしょう は いぎりす の ケンブリッジ だいがく の けんきゅう の けっか
にんげん は もじ を にんしき するとき その さしいょ と さいご の もじさえ
あっていれば じゅんばん は めちゃくちゃ でも ちゃんと よめる という けんきゅう
に もとづいて わざと もじの じゅんばん を いれかえて あります。
どうです? ちゃんと よめちゃう でしょ?
ちゃんと よめたら はんのう よろしく。";
            CambridgeFunction cf = new CambridgeFunction();
            string result = cf.Convert(s);
            Console.WriteLine(result);
            Console.ReadLine();
        }
    }

    class CambridgeFunction {

        public string Convert(string s) {
            Random rnd = new Random();
            string t = s.Replace("\r\n", "\n");
            StringBuilder sb = new StringBuilder();
            foreach (var word in EnumWords(t)) {
                int len = word.Length;
                string cambridgeWord = (len > 3) ? Change(word, len) : word;
                sb.Append(cambridgeWord);
            }
            return sb.ToString();
        }

        // 単語を順に列挙。単語と単語の間の空白も列挙の中に含める。
        private IEnumerable<string> EnumWords(string s) {
            string word = "";
            foreach (var c in s) {
                if (IsDelimiter(c)) {
                    if (word.Length > 0)
                        yield return word;
                    yield return c.ToString();
                    word = "";
                } else {
                    word += c;
                }
            }
            yield return word;
        }

        private bool IsDelimiter(char c) {
            return "。、? \n".Contains(c);
        }

        private static Random rnd = new Random();
        private static string Change(string word, int len) {
            var list = word.ToList();
            int ix = rnd.Next(2, len - 1);
            char c = list[ix];
            list.RemoveAt(ix);
            list.Insert(1, c);
            return new string(list.ToArray());
        }
    }
}

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)