hIDDEN bLOG » DevQuiz2011ソース晒し祭り

2011/9/12 月曜日

DevQuiz2011ソース晒し祭り

このエントリをはてなブックマークに追加
Filed under: .NET — @ 13:59:17

今年もGoogle Developer Day参加のためのハンター試験が無事終了。
ある程度で見切りつけちゃったんで参加できる自信がすげく薄いんですが…
スライドパズルの探索部分だけ、ソース晒してみますよー。

using System;
using System.Collections.Generic;
 
namespace SlidePuzzle
{
    class StageBreaker
    {
        // ctors
 
        public StageBreaker( Stage stage )
        {
            this.stage = stage;
            this.startTime = Environment.TickCount;
         }
 
        // Public Methods
 
        public string Break()
        {
            GC.Collect( GC.MaxGeneration );
 
            List<Stage> nextStages = new List<Stage>();
 
            string[] movables = stage.GetMovables();
            foreach ( string movable in movables )
            {
                Stage nextStage = stage.MakeClone();
                nextStage.Move( movable );
 
                this.snapShots[ nextStage.Data ] = true;
 
                if ( nextStage.Check() )
                {
                    return stage.MovedOperations;
                }
 
                nextStages.Add( nextStage );
            }
 
            return this.BreakRecursive( nextStages.ToArray(), 1 );
        }
 
        // Private Methods
 
        private string BreakRecursive( Stage[] stages, int step )
        {
            if ( Environment.TickCount - this.startTime > 30 * 60 * 1000 || stages.Length > 800000 )
            {
                return null;
            }
 
            List<Stage> nextStages = new List<Stage>();
            foreach ( Stage stage in stages )
            {
                string[] movables = stage.GetMovables();
                foreach ( string movable in movables )
                {
                    if ( movable != stage.GetRevert() )
                    {
                        Stage nextStage = stage.MakeClone();
                        nextStage.Move( movable );
 
                        if ( !this.snapShots.ContainsKey( nextStage.Data ) )
                        {
                            this.snapShots[ nextStage.Data ] = true;
 
                            if ( nextStage.Check() )
                            {
                                return nextStage.MovedOperations;
                            }
 
                            nextStages.Add( nextStage );
                        }
                    }
                }
            }
 
            string result = this.BreakRecursive( nextStages.ToArray(), step + 1 );
            nextStages = null;
            GC.Collect( GC.MaxGeneration );
 
            return result;
        }
 
        //=========================================================================================
        // Fields
 
        private readonly Stage stage;
        private readonly Dictionary<string, bool> snapShots = new Dictionary<string, bool>();
 
        private readonly int startTime;
    }
}

コメントはまだありません »

コメントはまだありません。

この投稿へのコメントの RSS フィード。 TrackBack URL

コメントする

HTML convert time: 0.923 sec. Powered by WordPress