2015年04月26日

C#で割り算の筆算をシミュレート

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

■問題 (出題者:不明)
整数 n, m を与えれば、 n ÷ m の筆算を出力するような プロシージャ(関数)を創ってください。

ウィンドウに描画するもよし、
コンソールに出力するもよし、です。

コンソールアプリで。
今回は、説明を省略します。 コメント書いてあるので、そっち見てください。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            while (true) {
                var str = Console.ReadLine();
                if (str == "")
                    break;
                var data = str.Split('/');
                int dividend = int.Parse(data[0].Trim());
                int divisor = int.Parse(data[1].Trim());

                DivisionByWriting d = new DivisionByWriting();
                var a = d.Divide(dividend, divisor);
                Console.WriteLine();
                foreach (var s in a)
                    Console.WriteLine(s);
            }
        }
    }

    class DivisionByWriting {
        private List<string> note = new List<string>();
        private string _space;
        private string _line;
        private string _originalDividend;  // 割られる数 (被除数) divisorは除数

        /// <summary>
        /// dividentをdivisorで割る
        /// </summary>
        /// <param name="dividend">被除数</param>
        /// <param name="divisor">除数</param>
        /// <returns></returns>
        public string[] Divide(int dividend, int divisor) {
            // 準備
            _space = new string(' ', divisor.ToString().Length + 1);
            _line = _space + new string('-', dividend.ToString().Length);

            // まず、割り算の問題を noteに書く
            _originalDividend = dividend.ToString();
            string s = divisor.ToString() + ")" + dividend.ToString();
            note.Add(new string(' ', s.Length));   //            ; 商を書ききれる場所
            note.Add(_line);                       //    -----
            note.Add(s);                           // xx)xxxxx

            // 筆算でdividendから最初に割られる数を求める
            // 例えば、123 / 8 ならば、12 を求める
            // 同時に、答えを書く最初の位置も求める
            // 例えば、823 / 5 ならば、0となる (8の位置)
            //         123 / 5 ならば、1となる (2の位置)
            //         123 / 50 ならば、2となる (3の位置)
            string dd = dividend.ToString();
            int i = 0;
            int n;
            do {
                i++;
                n = int.Parse(dd.Substring(0, i));
            } while (n / divisor == 0);

            // ここからが実際の割り算  (_divideは、再帰関数)           
            return _divide(n, divisor, i - 1);
        }

        private string[] _divide(int dividend, int divisor, int col) {
            // 部分的な割り算をする
            int q = dividend / divisor;    // 商
            int r = dividend % divisor;    // 余り

            // 先頭行をもとめ、そこに商を書き込む
            char[] array = note[0].ToCharArray();
            array[col + divisor.ToString().Length + 1] = q.ToString()[0];
            note[0] = new string(array);
            col++;

            // 商と序数を掛けた値を下に追加する
            if (q > 0) {
                note.Add(_space + FormatNumber(divisor * q, col));
                note.Add(_line);
            } else {
                // 商が0なら、最後の行をいったん取り消す。(後で、正しいものが追加される)
                note.RemoveAt(note.Count - 1);
            }
            if (col == _originalDividend.Length) {
                // 最後の一桁まで計算をした。
                // 最後の余りを書き込む 0の場合もある
                note.Add(_space + FormatNumber(r, col));
                return note.ToArray();
            }
            // 次の対象となる除数をNoteの最後に追加する
            int newdividend = r * 10 + (_originalDividend[col] - '0');
            note.Add(_space + FormatNumber(newdividend, col + 1));
            // 割り算を実施する。
            return _divide(newdividend, divisor, col);
        }

        // width が 3ならば、"{0,3}" という文字列を作成し、 numを整形する。
        private string FormatNumber(int num, int width) {
            string format = string.Format("{{0,{0}}}", width);
            return string.Format(format, num);
        }
     }
 }

実行例


6542/23

    284
   ----
23)6542
   46
   ----
   194
   184
   ----
    102
     92
   ----
     10

もうひとつの例。商の途中で0が入るパターン。


65436/603

      108
    -----
603)65436
    603
    -----
     5136
     4824
    -----
      312

ぴったり割り切れるパターン。


7200/32

    225
   ----
32)7200
   64
   ----
    80
    64
   ----
    160
    160
   ----
      0

いちおう、これで、「どう書く?orgに感謝を込めて」のシリーズを終わりにします。
読んでいただきありがとうございました。

といっても、このブログのアクセス解析みると、上位の記事はほとんどがWPF関連の記事なので、このシリーズはあまり人気がなかったようです。
まあ、当たり前と言えば当たり前ですが...
でも、こういったアルゴリズムの勉強になるコードを自分で書いてみるってとても大切だと思うんですよね。

調べてみたら、去年の4月から始めたので、なんと1年も続けていました。
自分でもびっくり。

さて、次は何を書こうかな。


  

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

2015年04月22日

C#で手持ちのコインを減らす払い方を求める

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

■問題 (出題者:不明)
いま、あなたの財布の中にはコインがたくさん入っています。これを少しでも減らしたいと思います。
支払うべき金額と持っているコインの種類と数を与えられたときに、どのコインを何枚出せばおつりを受け取った後のコインの数が最も少なくなるか返す関数を作ってください。おつりは最も枚数が少なくなる方法で渡されます。
例えば、1円玉2枚、10円玉4枚、100円玉3枚を持っていて、147円支払う場合、 1円玉2枚と100円玉2枚を渡して50円玉1枚と5円玉1枚を受け取るのが2枚減で最も枚数を減らせます。


問題には、コインとあるが、1円玉から1万円札まで扱えるようにしてみる。
なお、渡したお金が返ってくるような渡し方は禁止することとする。
これは、このシリーズでこれまでに解いてきた問題の中で、一番梃子摺った問題だ。

まずは Walletクラスを作成。
初期バージョン

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

namespace NewVersion {
    class Wallet {
        public SortedDictionary<int, int> Coins { get; private set; }

        public Wallet() {
            Coins = new SortedDictionary<int, int>();
        }

        public Wallet(int yen1, int yen5, int yen10, int yen50, int yen100, int yen500,
                         int yen1000 = 0, int yen5000 = 0, int yen10000 = 0)
            : this() {
            Coins[1] = yen1;
            Coins[5] = yen5;
            Coins[10] = yen10;
            Coins[50] = yen50;
            Coins[100] = yen100;
            Coins[500] = yen500;
            Coins[1000] = yen1000;
            Coins[5000] = yen5000;
            Coins[10000] = yen10000;
        }

        public int Amount() {
            return Coins.Sum(x => x.Key * x.Value);
        }

        public int Count() {
            return Coins.Sum(x => x.Value);
        }

        public void Print() {
            foreach (var x in Coins.Reverse()) {
                Console.Write("{0}:{1} ", x.Key, x.Value);
            }
            Console.Write("=> {0:#,0}円, {1}枚", Amount(), Count());
            Console.WriteLine();
        }
    }
}

合計がいくらなのか Amountメソッドとコイン(札も含める)の枚数は何枚なのかを求める Countメソッドを作成。
コンストラクタの引数の数が多すぎるような気がするが、今回はこれで妥協する。
なお以降の説明では便宜上コインには札も含めることとする。

それと、財布の中を表示する Print()メソッドも定義しておいた。

まだ具体的に問題は考えていないが、たぶん、50円を1枚支払うといった処理が必要になりそうだ。
ただ、50円玉が無い場合もあるので、支払えたら true、支払えなかったらfalseを返すようにしてみよう。

書いたメソッドは以下の通り。もちろん、Walletクラスのメソッドとして定義する。

private bool PayOneUnit(int coinType) {
    if (Coins[coinType] <= 0)
        return false;
    Coins[coinType]--;
    return true;
}

さて、これができれば、今度は、10円を7枚支払うとか、50円を3枚支払うとかの機能が 実装できそうだ。

public bool PayPart(int coinType, int count) {
    var save = this.Clone();
    for (int i = 0; i < count; i++) {
        if (!PayOneUnit(coinType)) {
            Coins = save.Coins;
            return false;
        }
    }
    return true;
}

private Wallet Clone() {
    var obj = new Wallet();
    obj.Coins = new SortedDictionary<int, int>(this.Coins);
    return obj;
}

for文で繰り返しPayOneUnitを呼び出しているだけなので、単純なコードだ。
支払えなかったときに、財布の状態が変化しないように、Cloneメソッドを定義し、 元に戻すようにしている。

さて、これでだいぶ準備が整ってきたと思う。
それでは、問題を解くメソッドを書くことにする。
最初に書いたときは、1円の位、10円の位、100円の位と処理をしていたので、 5円,50円,500円の特別処理が必要だったけど、よくよく考えてみると、以下に示すように そんな個別処理を書かなくても、大丈夫だった。

実際に自分がどうやって支払っているかを考えてみる。
例えば、183円を支払うとする。
順に、1円を出せるか、5円を出せるか、10円を出せるか、50円を出せるか... とやっていけばよい。
つまり、1円を3枚出す。次に10円が3枚出す、50円を1枚出す、100円を1枚出せばよい。
しかし、出せない場合もあ。その場合は繰り上げ処理を行うことになる。
例えば、10円が2枚しかなければ、30円の支払いは行わずに次の硬貨の50円の支払いに繰り上げる。
なので、すでに3円を出しているとすれば、180-30-50=200 で200円の支払いの処理に置き換えるわけである。
さらに100円硬貨が1枚しか手元になければ、500円に支払いに繰り上げる。つまり 200-200+500 で、500円を支払う、さらに500円硬貨もなければ、500円にの支払いはせずに、次に大きい1000円の 支払いに繰り上げる。これをどんどん繰り返していけばよい。

このやり方をコードにしたのが以下のメソッドである。

public Wallet Pay(int payment) {
    if (this.Amount() < payment)
        return null;
    var save = this.Clone();
    int paid = 0;
    int workPayment = payment;
    foreach (var coinType in _coinTypes) {
        int nextType = NextCoinType(coinType);
        int currPayment = workPayment % nextType;
        if (PayPart(coinType, currPayment / coinType)) {
            paid += currPayment;
        } else {
            // 繰上げ処理
            workPayment += nextType;
        }
        workPayment -= currPayment;
        if (paid >= payment)
            break;
    }
    return save.Subtract(this);
}

private static int GetIndex(int coinType) {
    return Array.FindIndex(_coinTypes, x => x == coinType);
}

private static int NextCoinType(int coinType) {
    int index = GetIndex(coinType) + 1;
    if (index < _coinTypes.Length)
        return _coinTypes[index];
    else
        return 100000;
}

public Wallet Subtract(Wallet b) {
    var work = new Wallet();
    foreach (var currency in _coinTypes)
        work.Coins[currency] = this.Coins[currency] - b.Coins[currency];
    return work;
}

なお、_coinTypes というフィールドも新たに追加している。

private static int[] _coinTypes = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };

Payメソッドは、Walletオブジェクトを返すが、これは、支払うコインだけをWalletに入れたものを 返している。
Payメソッドが呼ばれると、自分自身のCoinsの値は更新され、支払った分だけが減っている。
このとき、おつりはまだ受け取っていないという状態である。
NextCoinTypeは、現在よりも一つ大きいコインを返すのだが、1万円が渡された場合は 便宜上、10万円を返している。5万円でも別に問題はない。

これで、動かしてみる。

int payment = 183;
Wallet bag = new Wallet(3, 1, 4, 1, 3, 0, 2, 1, 2);
bag.Print();

var paid = bag.Pay(payment);
paid.Print();

結果を以下に示す。

10000:2 5000:1 1000:2 500:0 100:3 50:1 10:2 5:1 1:3 => 27,378円, 15枚
10000:0 5000:0 1000:0 500:0 100:2 50:0 10:0 5:0 1:3 => 203円, 5枚

上が支払う前のWalletの内容、下が支払ったコインの内容だ。
この例はうまく動いている。では次の例はどうだろうか?

int payment = 183;
Wallet bag = new Wallet(3, 1, 2, 2, 3, 0, 2, 1, 2);
bag.Print();

var paid = bag.Pay(payment);
paid.Print();

10000:2 5000:1 1000:2 500:0 100:3 50:2 10:2 5:1 1:3 => 27,428円, 16枚
10000:0 5000:0 1000:0 500:0 100:2 50:0 10:0 5:0 1:3 => 203円, 5枚

同じ183円の支払いだが、最初の財布の中身が異なる。
本来ならば、50円を2枚出してほしいのだが、50円を出さずに100円を出してしまっている。
これはだめだ。
1円が13枚あれば、それを全部出してほしいところだが、残念ながら、そういったコードには なっていない。

そこで改良したのが以下のコード。
Payメソッドはそのままとし、下位メソッドである PayOneUnit に手を入れている。

これは、コインを1枚支払うメソッドということだが、もし、それよりも小さなコインで 支払えれば、そっちで支払うというものだ。
これを再帰で書いている。


private bool PayOneUnit(int payment, int currCoineType = 1) {
    if (payment == 0)
        return true;          // ぴったり払えた!
    var coins = _coinTypes.SkipWhile(x => x < currCoineType).TakeWhile(x => x <= payment);
    foreach (var coinType in coins) {
        if (payment % coinType != 0)
            break;  // 絶対にぴったりの支払いは無理。無駄な探索を打ち切る
        if (Coins[coinType] > 0) {
            Coins[coinType]--;
            payment -= coinType;
            bool r = PayOneUnit(payment, coinType);
            if (r == true)
                return true;
            Coins[coinType]++;
            payment += coinType;
        }
    }
    return false;
}

では、実行してみる。
ここでは、5円硬貨を沢山持っている例。

int payment = 247;
Wallet bag = new Wallet(2, 6, 6, 0, 3, 0, 2, 1, 2);
bag.Print();

var paid = bag.Pay(payment);
paid.Print();

10000:2 5000:1 1000:2 500:0 100:3 50:0 10:6 5:6 1:2 => 27,392円, 22枚
10000:0 5000:0 1000:0 500:0 100:2 50:0 10:2 5:5 1:0 => 245円, 9枚

ちゃんと5円硬貨を出してくれていることが分かる。

次に、実際にはおつりをもらうわけだから、その処理を書いてみる。
この場合は、常にコインは十分に用意してあるという前提だ。

public static Wallet Normalize(int amount) {
    var work = new Wallet();
    var workAmount = amount;
    foreach (var coinType in _coinTypes) {
        int nextType = NextCoinType(coinType);
        int amari = workAmount % nextType;
        work.Coins[coinType] = amari / coinType;
        workAmount -= amari;
    }
    return work;
}

最初はおつりを支払うという意味の名前にしようかと思ったのだが、 ここは、あえて、Normalizeという名前にした。金種表作る際にこの手のコードが使えますね。
やはり、戻り値はWalletだ。こうなると、Walletの名前が不適切になってくるが、 このままとする。

このおつりを財布に戻さないといけないので、Addメソッドも定義する。

public Wallet Add(Wallet b) {
    var work = new Wallet();
    foreach (var currency in _coinTypes)
        work.Coins[currency] = this.Coins[currency] + b.Coins[currency];
    return work;
}

これらのメソッドを使った例を以下に示す。


int payment = 3288;
Wallet bag = new Wallet(2, 6, 6, 0, 3, 0, 2, 1, 2);
bag.Print();

// 支払う
var paid = bag.Pay(payment);
paid.Print();

// おつりを求める
Wallet change = Wallet.Normalize(paid.Amount() - payment);
change.Print();

// おつりを財布に戻す
Wallet newBag = bag.Add(change);
newBag.Print();


10000:2 5000:1 1000:2 500:0 100:3 50:0 10:6 5:6 1:2 => 27,392円, 22枚
10000:0 5000:1 1000:0 500:0 100:2 50:0 10:6 5:6 1:0 => 5,290円, 15枚
10000:0 5000:0 1000:2 500:0 100:0 50:0 10:0 5:0 1:2 => 2,002円, 4枚
10000:2 5000:0 1000:4 500:0 100:1 50:0 10:0 5:0 1:4 => 24,104円, 11枚

最後に、Wallletの全体を掲載しなおす。
クラス名は、SmartWalletとかにして、Payなどの戻り値、Subtractなどの引数は、 IDictionary < int, int > にしても良かったかも。

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

namespace Doukaku.Org {
    class Wallet {
        public SortedDictionary<int, int> Coins { get; private set; }
        private static int[] _coinTypes;

        public Wallet() {
            Coins = new SortedDictionary<int, int>();
        }

        public Wallet(int yen1, int yen5, int yen10, int yen50, int yen100, int yen500,
                         int yen1000 = 0, int yen5000 = 0, int yen10000 = 0)
            : this() {
            Coins[1] = yen1;
            Coins[5] = yen5;
            Coins[10] = yen10;
            Coins[50] = yen50;
            Coins[100] = yen100;
            Coins[500] = yen500;
            Coins[1000] = yen1000;
            Coins[5000] = yen5000;
            Coins[10000] = yen10000;
            _coinTypes = Coins.Keys.ToArray();  // = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000 };
        }

        public int Amount() {
            return Coins.Sum(x => x.Key * x.Value);
        }

        public int Count() {
            return Coins.Sum(x => x.Value);
        }

        public void Print() {
            foreach (var x in Coins.Reverse()) {
                Console.Write("{0}:{1} ", x.Key, x.Value);
            }
            Console.Write("=> {0:#,0}円, {1}枚", Amount(), Count());
            Console.WriteLine();
        }

        public Wallet Pay(int payment) {
            if (this.Amount() < payment)
                return null;
            var save = this.Clone();
            int paid = 0;
            int workPayment = payment;
            foreach (var coinType in _coinTypes) {
                int nextType = NextCoinType(coinType);
                int currPayment = workPayment % nextType;
                if (PayPart(coinType, currPayment / coinType)) {
                    paid += currPayment;
                } else {
                    // 繰上げ処理
                    workPayment += nextType;
                }
                workPayment -= currPayment;
                if (paid >= payment)
                    break;
            }
            return save.Subtract(this);
        }


        public Wallet Subtract(Wallet b) {
            var work = new Wallet();
            foreach (var currency in _coinTypes)
                work.Coins[currency] = this.Coins[currency] - b.Coins[currency];
            return work;
        }

        public Wallet Add(Wallet b) {
            var work = new Wallet();
            foreach (var currency in _coinTypes)
                work.Coins[currency] = this.Coins[currency] + b.Coins[currency];
            return work;
        }

        public static Wallet Normalize(int amount) {
            var work = new Wallet();
            var workAmount = amount;
            foreach (var coinType in _coinTypes) {
                int nextType = NextCoinType(coinType);
                int amari = workAmount % nextType;
                work.Coins[coinType] = amari / coinType;
                workAmount -= amari;
            }
            return work;
        }

        private bool PayOneUnit(int payment, int currCoineType = 1) {
            if (payment == 0)
                return true;          // ぴったり払えた!
            var coins = _coinTypes.SkipWhile(x => x < currCoineType).TakeWhile(x => x <= payment);
            foreach (var coinType in coins) {
                if (payment % coinType != 0)
                    break;  // 絶対にぴったりの支払いは無理。無駄な探索を打ち切る
                if (Coins[coinType] > 0) {
                    Coins[coinType]--;
                    payment -= coinType;
                    bool r = PayOneUnit(payment, coinType);
                    if (r == true)
                        return true;
                    Coins[coinType]++;
                    payment += coinType;
                }
            }
            return false;
        }

        public bool PayPart(int coinType, int count) {
            var save = this.Clone();
            for (int i = 0; i < count; i++) {
                if (!PayOneUnit(coinType)) {
                    Coins = save.Coins;
                    return false;
                }
            }
            return true;
        }

        private Wallet Clone() {
            var obj = new Wallet();
            obj.Coins = new SortedDictionary<int, int>(this.Coins);
            return obj;
        }

        private static int GetIndex(int coinType) {
            return Array.FindIndex(_coinTypes, x => x == coinType);
        }

        private static int NextCoinType(int coinType) {
            int index = GetIndex(coinType) + 1;
            if (index < _coinTypes.Length)
                return _coinTypes[index];
            else
                return 100000;
        }
    }
}

なぜか今回は、である調で書いちゃいました。
である調にすると、なんだかいかにも偉そうだ(^^;;

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

2015年04月15日

C#でトランプの和と積のパズルを解く

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

■問題 (出題者:光成さん)
ここにトランプが一組あります.
司会者がそこから二枚抜いて,その積をAさんに,その和をBさんに教えました.

#トランプにジョーカーはなく、1〜13までの数字が書かれたカードであると考えて構いません.
#たとえば,二枚のトランプの数字が2と5なら,Aさんには10,Bさんには7を教えます.
#二つの数は同じかもしれません.

司会者がAさん,Bさんに二つの数字が分かるかと質問しました.
Aさん「(この情報だけでは)分かりません」
Bさん「私も分かりません.ただ,Aさんが『分かりません』というのは分かっていました」
それを聞いたAさん「それなら,分かりました」
それを聞いたBさん「それなら,私も分かりました」
元の二つの数はなんだったのでしょうか.

この「2つの数」を求めるプログラムを作ってください。解が複数個ある場合はすべて求めてください。
参考URL
http://www12.ocn.ne.jp/~kumo/trump.html


この問題を解くにあたり、帰納的に良い方法がないものかと具体的な例で考えはじめたら、 僕の頭は完全にオーバーフローを起こし、思考停止に陥りました(笑)
なので、具体例は考えるのはあきらめて、あくまでもこの問題にある質問を素直にコードに落とすことにしました。
同じ質問(メソッド)が同じ値(引数)に対して何回も呼ばれることになるので、効率が悪いですが、1から13までのペアならば、 瞬時に答えが表示されます。
GetAllPairメソッドの引数の 13 を 100とかにすれば、1から100のペアで答えを見つけることができます。

実行結果は、あえて載せないでおこうと思います。
それと、参考URLには別の方法が載っているようですので興味があるかたは、そちらも参考にしてみてください。

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            var sol = new Solver();
            var q = sol.Execute();
            foreach (var a in q)
                Console.WriteLine(a);
            Console.ReadLine();
        }
    }

    class Solver {
        private IList<Pair> allpair = GetAllPair(13);

        public IEnumerable<Pair> Execute() {
          foreach (var p in allpair) {
                if (ADidYouFind(p.X * p.Y) &&
                    BDidYouFind(p.X + p.Y) &&
                    AThenDidYouFind(p.X * p.Y) &&
                    BThenDidYouFind(p.X + p.Y))
                    yield return p;
            }
        }

        // Aさん「(この情報だけでは)分かりません」 と答えるか
        private bool ADidYouFind(int n) {
            var pairs = allpair.Where(t => t.Product == n).ToList();
            return (pairs.Count() >= 2);
        }

        // Bさん「私も分かりません.ただ,Aさんが『分かりません』というのは分かっていました」と答えるか
        private bool BDidYouFind(int n) {
            var pairs = allpair.Where(t => t.Sum == n).ToList();
            if (pairs.Count() == 1)
                return false;
            return (pairs.All(t => ADidYouFind(t.Product) == true)); // Aはすべてが分からない
        }

        // それを聞いたAさん「それなら,分かりました」と答えるか
        private bool AThenDidYouFind(int n) {
            var pairs = allpair.Where(t => t.Product == n).ToList();
            return (pairs.Count(t => BDidYouFind(t.Sum) == true) == 1);
        }

        // それを聞いたBさん「それなら,私も分かりました」と答えるか
        private bool BThenDidYouFind(int n) {
            var pairs = allpair.Where(t => t.Sum == n).ToList();
            return (pairs.Count(t => AThenDidYouFind(t.Product) == true) == 1);
        }

        private static IList<Pair> GetAllPair(int n) {
            var cards = Enumerable.Range(1, n);
            // すべてのカードの組み合わせ
            var q = from c1 in cards
                    from c2 in cards
                    where c1 <= c2
                    select new Pair(c1, c2);
            return q.ToList();
        }
    }

    class Pair {
        public int X { get; set; }
        public int Y { get; set; }
        public override string ToString() {
            return string.Format("({0}, {1})", X, Y);
        }

        public Pair(int x, int y) {
            this.X = x;
            this.Y = y;
        }
        public int Product {
            get { return X * Y; }
        }
        public int Sum {
            get { return X + Y; }
        }
    }
}

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

2015年04月12日

C#で水の移し替えパズルを解く

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

■問題 (出題者:光成さん)
A, B, Cの容器があり,それぞれ水が4L, 2L, 10L入っている. ここで次の操作を繰り返す.

(*)「A, B, Cのどれか二つの容器から水を1Lずつくみ上げ,残りの容器に移す.」
たとえばA, Bから1Lずつくみ上げて移せばA=3L, B=1L, C=12Lとなる. くみ上げる前の容器には必ず水が入っているとする.
(*)を繰り返してどれか一つの容器にのみ水がはいっている状態にする最小手数を求めよ.
可能ならA=827392L,B=65536L,C=122880Lのときも求めよ.

まず、移動を表す Moveクラスと、現在の3つの容器の状態を表す State クラスを定義します。


class State {
    public State(int[] buckets, State prev) {
        Buckets = (int[])buckets.Clone();
        PrevState = prev;
        Times = (prev == null) ? 0 : prev.Times + 1;
    }
    public int Times { get; private set; }
    public State PrevState { get; private set; }
    public int[] Buckets { get; private set; }
}

class Move {
    public byte From1 { get; set; }
    public byte From2 { get; set; }
    public byte To { get; set; }
}

次に、これを使って、愚直に幅優先の探索で解を求める BfSolver クラスを定義してみました。

class BfSolver  {
    public State Search(State state) {

        // 最初に訪問するノードをキューに入れる
        Queue<State> queue = new Queue<State>();
        queue.Enqueue(state);
        while (queue.Count != 0) {
            //キューの先頭からノード currentNode を取り出す
            State current = queue.Dequeue();
            if (IsFinish(current.Buckets)) {
                return current;
            }

            foreach (var mv in GetMoves()) {
                if (!IsOK(mv, current.Buckets))
                    continue;
                int[] next = new int[3];
                next[mv.From1] = current.Buckets[mv.From1] - 1;
                next[mv.From2] = current.Buckets[mv.From2] - 1;
                next[mv.To] = current.Buckets[mv.To] + 2;
                State newstate = new State(next, current);
                if (IsLoop(current, newstate))
                    continue;
                if (ExistsInQueue(queue, newstate))
                    continue;
                queue.Enqueue(newstate);
            }
        }
        // 見つからなかった。
        return null;
    }

    private bool IsFinish(int[] buckets) {
        return buckets.Count(n => n == 0) == 2;
    }

    private IEnumerable<Move> GetMoves() {
        yield return new Move { From1 = 0, From2 = 1, To = 2 };
        yield return new Move { From1 = 0, From2 = 2, To = 1 };
        yield return new Move { From1 = 1, From2 = 2, To = 0 };
    }
    private bool IsOK(Move mv, int[] buckets) {
        if (buckets[mv.From1] <= 0)
            return false;
        if (buckets[mv.From2] <= 0)
            return false;
        return true;
    }

    private bool ExistsInQueue(Queue<State> queue, State state) {
        return queue.Any(x => x.Buckets.SequenceEqual(state.Buckets));
    }

    private bool IsLoop(State state1, State state2) {
        if (state1 == null)
            return false;
        if (state1.Buckets.OrderBy(n => n).SequenceEqual(state2.Buckets.OrderBy(n => n)))
            return true;
        return IsLoop(state1.PrevState, state2);
    }
}

Searchメソッドの戻り値は、 Stateオブジェクトとなり、この Times プロパティを見れば、移動回数が分かります。
Stateがnull の時には、解が見つからなかったことを示しています。

今回は、回数だけを求めればいいので、その状態推移を表示するコードは書いていませんが、 Stateには、PrevStateがあるので、これを辿れば、容器のリットル数がどう変化していったのかが分かるようになっています。

しかし、このプログラムは、A=3L, B=1L, C=12L 程度ならば、問題ないですが、 A=827392L,B=65536L,C=122880Lとなると、調べる手があまりにも多すぎて、永遠に終わりそうにありません。
試しに、A=171L, B=162L, C=180L と3桁の値でやってみたら、10分経っても終わらないので、 あきらめて途中で終了させてしまいました。

そこで、コンピュータに考えさせるのではなく、もうすこし自分で考えてみました。
そうしたら、意外と単純な問題であることに気が付きました。
そのコードを以下に示します。

class SmartSolver {
    public int Calc(State state) {
        var nums = state.Buckets.OrderBy(n => n).ToArray();
        if ((nums[1] - nums[0]) % 3 == 0)
            return nums[1];
        if ((nums[2] - nums[1]) % 3 == 0)
            return nums[2];
        if ((nums[2] - nums[0]) % 3 == 0)
            return nums[2];
        return -1;
    }
}

なんと、これだけでした。これならば、A=827392L,B=65536L,C=122880Lのときも 一瞬で求まります。
答えは 827392です。

ざっと説明すると、
例えば、最終的な状態が、

A=0L, B=0L, C=xL
のような状態になるのですから、そのひとつ前は、

A=1L, B=1L, C=(x-2)L

そのひとつ前は

A=2L, B=2L, C=(x-4)L

そのひとつ前は

A=3L, B=3L, C=(x-6)L or A=3L, B=0L, C=(x-3)L

つまり、最終的に 0になる AとBの、水の増減は (+1,+1) (+1,-2) (-2,+1) となるわけです。 ここから、A =B か、A と B の差が3の倍数かのどちらかであることが分かります。
そして、水は1Lずつしか減らないので、どんなに頑張っても、A とBの大きい数だけ、水の移動回数が 必要となります。
これらのことから、上のコードが導きだせるということになります。

これが正しいかを確認するために、最初に書いた BfSolver と SmartSolver の結果が同じになるか 確認してみました。
以下が、そのコードと実行結果です。

class Program {
    static void Main(string[] args) {
        Test(4, 2, 10);
        Test(5, 2, 10);
        Test(2, 8, 11);
        Test(1, 2, 3);
        Test(12, 8, 11);
        Test(7, 16, 51);
        Test(44, 22, 15);
        Test(53, 22, 1);
        Test(8, 8, 7);
        Test(20, 20, 23);
        Console.ReadLine();
    }

    private static void Test(int n1, int n2, int n3) {
        State state = new State(new int[] { n1, n2, n3 }, null);

        var sol = new SmartSolver();
        int n = sol.Calc(state);
        Console.Write("{0}\t",n);

        BfSolver s = new BfSolver();
        State last = s.Search(state);
        if (last == null)
            Console.WriteLine(-1);
        else
            Console.WriteLine(last.Times);       
    }
}

■実行結果
10      10
5       5
8       8
-1      -1
11      11
16      16
-1      -1
22      22
8       8
20      20

途中結果を表示する機能がありませんが、原理が分かっているので、 SmartSolver に途中結果を表示させる機能をつけるのも、それほど難しくはないですね。

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

2015年04月08日

C#でマップの通り抜け

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

■問題 (出題者:にしお さん)
ここにピリオド(.)とプラス(+)と改行で構成された入力ファイルがあります。
ピリオドは通れないマス、プラスは通れるマスを表現しています。 上から下へたどり着く道があるかどうかを判定するコードを書いてください。
通り抜けられる例
.+.....
.+.+++.
.+.+.+.
.+++.+.
.....+.

通り抜けられない例

..+...+
++.+++.
.+...++
++++.+.
.+..+.+


このところ、探索系のプログラムが続きいています。 今回は、深さ優先探索で求めています。
Debugモードでビルドした場合は、その探索過程がわかるようにしています。
そういえば、このシリーズで、Conditional属性を使ったのは始めてかも。

今回作成したプログラムでは、Mapクラスをまず理解すれば、たどり着く道があるかどうかを判定する PassThroughMapクラスを理解するのは、それほど難しくないと思います。
再帰処理と深さ優先探索が分かっているという前提ですが...

すでに通った箇所は、+ を * に変えることで、逆戻りしないようにしています。
最初作成したときは、再帰呼び出しの度に、Mapオブジェクトのクローンを作成し、それを引数として渡していたのですが、それだと、メモリ効率が悪いので、クローンを作成せずに、元の状態に戻れるよう、TurnBackを定義し、メソッドから戻るときにこれを呼び出すようにしています。

経路は、Stackに保存しています。そのほうが、経路を追加したり、取り除いたりする操作が簡単です。 ただし、Stackなので、経路を取り出す際は、反転させています。


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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string[] map = File.ReadAllLines("Map.txt");
            PassThroughMap p = new PassThroughMap();
            var answer = p.Solve(map);
            Console.WriteLine(answer.Count > 0);
            // 経路を表示する
            foreach (var pt in answer)
                Console.WriteLine(pt);
        }
    }

    public class PassThroughMap {
        private Map map;
        public List<Point> Solve(string[] arg) {
            map = new Map(arg);
            // 開始地点を求め、求まったら SolveInnnerメソッドを呼び出し、解があるかを求める。
            for (int x = 0; x < map.Width; x++) {
                Point p = new Point(x, 0);
                if (map.CanPass(p)) {
                    if (SolveInnner(p) == true)
                        break;
                }
            }
            return map.Route.Reverse().ToList();
        }

        private bool SolveInnner(Point now) {
            if (map.LeavesFootprint(now))
                return true;

            foreach (var p in map.Candidates()) {
                if (SolveInnner(p))
                    return true;
            }
            map.TurnBack(now);
            return false;
        }
    }

    public class Map {
        private char[][] lines;
        private Point _current = new Point(-1,-1);
        public Stack<Point> Route { get; set; }

        public int Width { get; private set; }
        public int Height { get; private set; }

        public Map(string[] lines) {
            Width = lines[0].Length;
            Height = lines.Length;
            this.lines = new char[Height][];
            int y = 0;
            foreach (var line in lines)
                this.lines[y++] = line.ToCharArray();
            Route = new Stack<Point>();
        }

        public bool LeavesFootprint(Point pt) {
            lines[pt.Y][pt.X] = '*';
            _current = pt;
            Route.Push(pt);
            Print();
            return (_current.Y == Height - 1); // 出口か?
        }

        public void TurnBack(Point pt) {
            lines[pt.Y][pt.X] = '+';
            Route.Pop();
            if (Route.Count > 0)
                _current = Route.Peek();
            else
                _current = new Point(-1, -1);
            Print();
        }

        public bool CanPass(Point px) {
            return CanPass(px.X, px.Y);
        }

        private bool CanPass(int x, int y) {
            return (this.lines[y][x] == '+');
        }

        public IEnumerable<Point> Candidates() {
            if (_current.Y + 1 < Height && CanPass(_current.X, _current.Y + 1))
                yield return new Point(_current.X, _current.Y + 1);
            if (_current.X + 1 < Width && CanPass(_current.X + 1, _current.Y))
                yield return new Point(_current.X + 1, _current.Y);
            if (_current.X - 1 >= 0 && CanPass(_current.X - 1, _current.Y))
                yield return new Point(_current.X - 1, _current.Y);
            if (_current.Y - 1 >= 0 && CanPass(_current.X, _current.Y - 1))
                yield return new Point(_current.X, _current.Y - 1);
        }

        [Conditional("DEBUG")]
        public void Print() {
            for (int y = 0; y < Height; y++) {
                for (int x = 0; x < Width; x++) {
                    Console.Write(lines[y][x]);
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }

    public class Point {
        public int X { get; set; }
        public int Y { get; set; }
        public Point(int x, int y) {
            X = x;
            Y = y;
        }
        public override string ToString() {
            return String.Format("({0},{1})", X, Y);
        }
    }
}

以下、実行結果です。

入力ファイル

.+..+.....
.+.+++++..
.+.+...+..
.+.+.++++.
..+...+.+.
..+..++.+.
....++....
....+.....

出力 (Releaseモード)
True
(4,0)
(4,1)
(5,1)
(6,1)
(7,1)
(7,2)
(7,3)
(6,3)
(6,4)
(6,5)
(5,5)
(5,6)
(4,6)
(4,7)
Debugモードで実行したときは、探索途中のMapの状態が見られるので、 どのように経路を求めているのかが理解しやすいと思います。   
Posted by gushwell at 22:30Comments(0)TrackBack(0)

2015年04月05日

C#で島の数をカウントする

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

■問題 (出題者:ckbx さん)
m×nの長方形のマス目のうちいくつかを黒く塗りつぶします。
このとき、白の島、黒の島がそれぞれいくつあるかをカウントしてください。

ただし、2つのマスは、同色マスの上下左右の移動で移れるとき、
同じ島にあると定義します。

例:
□■■□
□□■□
□■□□
□■■□
白の島は2つ
黒の島は2つ

例:
□□□□
■□■□
□■□□
□□□□
白の島は1つ
黒の島は3つ
 

すでに数えた島かどうかを判定するために、違う色で塗りつぶすという方法で島の数をカウントしています。
以下のコードでは、Paintメソッドが塗りつぶすメソッドです。
そのジ上位メソッドで、塗りつぶせれば +1 し、すでに塗りつぶされたならばそのまま、 カウントしたい島とは別の色ならば、そのまま何もしません。
これで、簡単にカウントすることができます。
ちなみに、塗りつぶしは、再帰処理を使っています。

塗りつぶしには、Color.Markというメンバーを定義し、この値で塗りつぶしています。 Colorクラスなのに、Markというのも変ですが...

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

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            string[] tbl = Data.Table();
            Field sample = new Field(tbl);

            int cnt = sample.Count(Color.White);
            Console.WriteLine("白の島は{0}",cnt);
            int cnt2 = sample.Count(Color.Black);
            Console.WriteLine("黒の島は{0}", cnt2);
        }
    }

    static class Color {
        public const int White = 0;
        public const int Black = 1;
        public const int Mark = 5;
    }
    struct Point {
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        private int x;
        private int y;
        public int X { get { return x; } }
        public int Y { get { return y; } }
    }

    public class Field {
        private int[,] table;
        private int width;
        private int height;
        public Field(string[] lines) {
            width = lines[0].Length;
            height = lines.Length;
            table = new int[width, height];
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++) {
                    table[x, y] = (lines[y][x] == '□') ? Color.White : Color.Black;
                }
            }
            Print();
        }

        public int Count(int color) {
            int count = 0;
            int[,] save = (int[,])table.Clone();
            for (int x = 0; x < width; x++) {
                for (int y = 0; y < height; y++) {
                    if (table[x, y] == color) {
                        Paint(x, y,color);
                        count++;
                    }
                }
            }
            return count;
        }

        // (x,y)とその連続する場所をcolorで塗りつぶす
        private void Paint(int x, int y,int color) {
            table[x, y] = Color.Mark;  // マークを付ける
            foreach (var p in Around(x, y)) {
                if (table[p.X, p.Y] == color)
                    Paint(p.X, p.Y,color);
            }
        }

        private IEnumerable<Point> Around(int x, int y) {
            if (y > 0)
                yield return new Point(x, y - 1);
            if (y < height - 1)
                yield return new Point(x, y + 1);
            if (x > 0)
                yield return new Point(x - 1, y);
            if (x < width - 1)
                yield return new Point(x + 1, y);
        }

        // デバッグ用
        private void Print() {
            for (int y = 0; y < height; y++) {
                for (int x = 0; x < width; x++)
                    Console.Write(table[x, y]);
                Console.WriteLine();
            }
            Console.WriteLine();
        }
    }

    public static class Data {
        public static string[] Table() {
            return File.ReadAllLines("Islands.txt");
        }
    }
}

以下のファイルを読み込ませれば、

白の島は3
黒の島は4

と表示されます。

■読み込ませるファイルの内容
□□■□□□
□■■□■■
□□■■□□
□□□□■□
□□■□■■
□■■□□□
□■□□□□
  
Posted by gushwell at 21:30Comments(0)TrackBack(0)

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)