matsukawar's blog

個人的な技術ブログ。テクニカルアーキテクトを目指しています。Twitter : https://twitter.com/matsukawar

おねえさんのコンピュータ

午前中で仕事が終わったので、午後は、組み合わせ爆発の課題をC#でやってました。
昨日、茨城でべろっぱコミュニティの「第23 回プログラマのための勉強会」に参加予定で参加できなかったのですが、そこで出された課題らしいです。

お姉さんが人生を懸けて“組み合わせ爆発”を力説 動画「フカシギの数え方」が壮大すぎる
http://b.hatena.ne.jp/articles/201209/10490

アルゴリズムなんてまったく意識しないでやってたんですが、
計算させてみると、待てど待てど終わらない・・・

アルゴリズムが重要だってことを改めて気付かされました。
数学苦手なので、目を背けていたというのもあります。

最新のアルゴリズムだと、数秒で解けてしまうらしいです。
すごいですねー


私のプログラムじゃー何億年もかかりますねw

using System;
using System.Threading;
using System.Windows.Forms;
namespace WindowsFormsApplication3
{
    public partial class Form1 : Form
    {
        /// <summary>
        /// ルート数
        /// </summary>
        private int route;
        
        /// <summary>
        /// ルート数更新用ロックオブジェクト
        /// </summary>
        private object lockobj = new object();

        /// <summary>
        /// マップサイズ(2〜)
        /// </summary>
        private int mapsize;

        /// <summary>
        /// スレッド起動有無
        /// </summary>
        private bool isthread;

        /// <summary>
        /// コンストラクタ
        /// </summary>
        public Form1()
        {
            InitializeComponent();
            comboBox1.SelectedIndex = 0;
        }

        /// <summary>
        /// 計算開始ボタンイベント
        /// </summary>
        /// <param name="sender">オブジェクト</param>
        /// <param name="e">イベント</param>
        private void button1_Click(object sender, EventArgs e)
        {
            //ルート数初期化
            route = 0;

            //マップサイズ初期化
            mapsize = Convert.ToInt32(comboBox1.Text) + 1;
            isthread = false;
            bool[] m = new bool[mapsize * mapsize];

            this.Walk(new WalkStatus(m));
            timer1.Start();
        }

        /// <summary>
        /// 探索処理
        /// </summary>
        /// <param name="param">探索条件</param>
        private void Walk(object param)
        {
            WalkStatus status = param as WalkStatus;

            //位置の確認
            int x = status.posx;
            int y = status.posy;
            if (x < 0 || y < 0 || mapsize <= x || mapsize <= y)
            {
                //探索を諦める
                return;
            }

            //探索マップのクローン
            bool[] map = new bool[status.map.Length];
            status.map.CopyTo(map, 0);

            //現在地
            int location = x * mapsize + y;

            //探索
            if (true == map[location])
            {
                //すでに探索済
                return;
            }
            map[location] = true;

            //到着した?
            if (location == (map.Length - 1))
            {
                lock (lockobj)
                {
                    route++;
                }
                return;
            }

            //探索を続ける
            if (false == isthread)
            {
                isthread = true;

                //開始位置から右と下を探索する
                ThreadPool.QueueUserWorkItem(new WaitCallback(this.Walk), new WalkStatus(map, x + 1, y));
                ThreadPool.QueueUserWorkItem(new WaitCallback(this.Walk), new WalkStatus(map, x, y + 1));
                return;
            }

            //4方向を探索する
            this.Walk(new WalkStatus(map, x + 1, y));
            this.Walk(new WalkStatus(map, x - 1, y));
            this.Walk(new WalkStatus(map, x, y - 1));
            this.Walk(new WalkStatus(map, x, y + 1));
        }

        /// <summary>
        /// 結果表示用タイマ
        /// </summary>
        /// <param name="sender">オブジェクト</param>
        /// <param name="e">イベント</param>
        private void timer1_Tick(object sender, EventArgs e)
        {
            label1.Text = route.ToString();
        }
    }

    /// <summary>
    /// 探索条件クラス
    /// </summary>
    internal class WalkStatus
    {
        /// <summary>
        /// 探索マップ
        /// </summary>
        internal bool[] map;

        /// <summary>
        /// 現在位置(X)
        /// </summary>
        internal int posx;

        /// <summary>
        /// 現在位置(Y)
        /// </summary>
        internal int posy;

        /// <summary>
        /// コンストラクタ
        /// </summary>
        /// <param name="m">探索マップ</param>
        /// <param name="x">現在位置(X)</param>
        /// <param name="y">現在位置(Y)</param>
        internal WalkStatus(bool[] m, int x = 0, int y = 0)
        {
            map = m;
            posx = x;
            posy = y;
        }
    }

    /// <summary>
    /// Form1デザイナクラス
    /// </summary>
    partial class Form1
    {
        /// <summary>
        /// 必要なデザイナー変数です。
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// 使用中のリソースをすべてクリーンアップします。
        /// </summary>
        /// <param name="disposing">マネージ リソースが破棄される場合 true、破棄されない場合は false です。</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows フォーム デザイナーで生成されたコード

        /// <summary>
        /// デザイナー サポートに必要なメソッドです。このメソッドの内容を
        /// コード エディターで変更しないでください。
        /// </summary>
        private void InitializeComponent()
        {
            this.components = new System.ComponentModel.Container();
            this.button1 = new System.Windows.Forms.Button();
            this.comboBox1 = new System.Windows.Forms.ComboBox();
            this.label1 = new System.Windows.Forms.Label();
            this.timer1 = new System.Windows.Forms.Timer(this.components);
            this.label2 = new System.Windows.Forms.Label();
            this.SuspendLayout();
            // 
            // button1
            // 
            this.button1.Location = new System.Drawing.Point(139, 10);
            this.button1.Name = "button1";
            this.button1.Size = new System.Drawing.Size(75, 23);
            this.button1.TabIndex = 0;
            this.button1.Text = "calc";
            this.button1.UseVisualStyleBackColor = true;
            this.button1.Click += new System.EventHandler(this.button1_Click);
            // 
            // comboBox1
            // 
            this.comboBox1.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
            this.comboBox1.FormattingEnabled = true;
            this.comboBox1.Items.AddRange(new object[] {
            "1",
            "2",
            "3",
            "4",
            "5",
            "6",
            "7",
            "8"});
            this.comboBox1.Location = new System.Drawing.Point(12, 12);
            this.comboBox1.Name = "comboBox1";
            this.comboBox1.Size = new System.Drawing.Size(121, 20);
            this.comboBox1.TabIndex = 1;
            // 
            // label1
            // 
            this.label1.AutoSize = true;
            this.label1.Location = new System.Drawing.Point(243, 15);
            this.label1.Name = "label1";
            this.label1.Size = new System.Drawing.Size(0, 12);
            this.label1.TabIndex = 2;
            // 
            // timer1
            // 
            this.timer1.Tick += new System.EventHandler(this.timer1_Tick);
            // 
            // label2
            // 
            this.label2.AutoSize = true;
            this.label2.Location = new System.Drawing.Point(258, 15);
            this.label2.Name = "label2";
            this.label2.Size = new System.Drawing.Size(0, 12);
            this.label2.TabIndex = 3;
            // 
            // Form1
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 12F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(379, 47);
            this.Controls.Add(this.label2);
            this.Controls.Add(this.label1);
            this.Controls.Add(this.comboBox1);
            this.Controls.Add(this.button1);
            this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.FixedSingle;
            this.MaximizeBox = false;
            this.MinimizeBox = false;
            this.Name = "Form1";
            this.ShowIcon = false;
            this.Text = "Form1";
            this.ResumeLayout(false);
            this.PerformLayout();

        }

        #endregion

        private System.Windows.Forms.Button button1;
        private System.Windows.Forms.ComboBox comboBox1;
        private System.Windows.Forms.Label label1;
        private System.Windows.Forms.Timer timer1;
        private System.Windows.Forms.Label label2;
    }

    /// <summary>
    /// エントリポイントクラス
    /// </summary>
    public static class Program
    {
        /// <summary>
        /// アプリケーションのメイン エントリ ポイントです。
        /// </summary>
        [STAThread]
        static void Main()
        {
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Application.Run(new Form1());
        }
    }
}