river crossing problem

gistfile1.js

(function () {


    window.CodeIq = {
    };

    var c = CodeIq;

    c.Stack = function Stack() {
        this.__a = new Array();
    }
    c.Stack.prototype.push = function (o) {
        this.__a.push(o);
    };
    c.Stack.prototype.pop = function () {
        if (this.__a.length > 0) {
            return this.__a.pop();
        }
        return null;
    };
    c.Stack.prototype.size = function () {
        return this.__a.length;
    };
    c.Stack.prototype.toString = function () {
        return '[' + this.__a.join(',') + ']';
    };

    c.State = function State() { };
    c.State.prototype = {
        //ノードの状態を表す
        stateString: "SSSTTT/",
        //両岸の人員を記録する
        numLeftPeople: 3,
        numRightPeople: 0,
        numLeftTitans: 3,
        numRightTitans: 0,
        parentState: this,
        //船がどちらにあるのか記録する
        kanoeState: "left",
        peopleInKanoe: 0,
        titansInKanoe: 0,
        //船に乗る人と巨人の組み合わせ １人か２人乗る
        dataArray: [[1, 1], [2, 0], [0, 2], [1, 0], [0, 1]],
        //dataArrayを参照するためのカウンター　親のノードから５つの組み合わせで次のノードを作り試していく
        count: 0,
        depth: 0,
        //結果記録用の配列
        log: ["SSSTTT/"],
        //左右の状態を別々でログに記録しておく。同じ側で同じ状態だと探索失敗とする
        logLeft: [],
        logRight: [],
        isRootNode: false,
        error: "",
        //子ノードを作成する
        createNewCondition: function () {
            var pState = new CodeIq.State();
            pState.copy(this);
            return pState;
        },
        isConsumed: function () {

            //すべての子ノードを作ったらこの親ノードからの探索は終了
            if (this.count > 4) {
                if (!this.isRootNode) {
                    this.parentState.count++;
                }
                return true;
            }
        },
        //子ノードを親から作る。状態が不正であればfalseを返す
        search: function () {

            var condition = this.dataArray[this.parentState.count];
            //子ノードが親ノードと同じ舟に乗る組み合わせの状態を作らないようにする
            //かぶったらこのノードはなかったことに
            if (this.parentState.peopleInKanoe == condition[0] &&
                this.parentState.titansInKanoe == condition[1]) {
                //ダメなら次の乗り合わせの選択肢に移す
                this.parentState.count++;
                //console.log("sippai");
                this.log.push(this.stateString);
                //this.log.forEach(function (element) {
                //    console.log(element);
                //});
                //console.log("same order");
                //console.log(this.parentState.count);
                return false;
            }

            //引数の組み合わせで船に乗って渡らせ、正しい状態かチェックする
            var isValid = this.ride(condition[0], condition[1]);
            if (!isValid) {
                //ダメなら次の乗り合わせの選択肢に移す
                this.parentState.count++;
                //console.log("sippai");
                this.log.push(this.stateString);
                //this.log.forEach(function (element) {
                //    console.log(element);
                //});
                //console.log(this.error);
                //console.log(this.parentState.count);
                return false;
            }
            return true;

        },
        //船にのってわたらせるシミュレーション 引数は船に乗る人の数
        ride: function (people, titan) {
            if (this.kanoeState == "left") {
                //岸にいる人の数がマイナスにならないようにする
                if (this.numLeftPeople - people >= 0 && this.numLeftTitans - titan >= 0) {
                    this.move(people, titan);
                    if (!this.checkCurrentState()) {
                        this.error = "after moved, invalid minus";
                        return false;
                    }
                    this.peopleInKanoe = people;
                    this.titansInKanoe = titan;
                    //状態をプリントして記録する
                    this.stateString = this.print(this.numLeftPeople, this.numLeftTitans, this.numRightPeople, this.numRightTitans);
                    //左右の岸で別々にログを取る
                    if (this.logLeft.indexOf(this.stateString) >= 0) {
                        this.error = "duplicated";
                        return false;
                    }
                    this.log.push(this.stateString);
                    this.logLeft.push(this.stateString);

                    return true;
                } else {
                    this.move(people, titan);
                    this.error = " before move minus  ";
                    return false;
                }
            } else {
                if (this.numRightPeople - people >= 0 && this.numRightTitans - titan >= 0) {
                    this.move(people, titan);
                    if (!this.checkCurrentState()) {
                        this.error = "after moved, invalid minus";
                        return false;
                    }
                    this.peopleInKanoe = people;
                    this.titansInKanoe = titan;
                    this.stateString = this.print(this.numLeftPeople, this.numLeftTitans, this.numRightPeople, this.numRightTitans);
                    if (this.logRight.indexOf(this.stateString) >= 0) {
                        this.error = "duplicated";
                        return false;
                    }
                    this.log.push(this.stateString);
                    this.logRight.push(this.stateString);
                    return true;
                } else {
                    this.move(people, titan);
                    this.error = " before move minus  ";
                    return false;
                }
            }

        },
        //人が巨人より少ない場合は不正としfalseを返す
        checkCurrentState: function () {
            if ((this.numLeftPeople > 0 && this.numLeftPeople < this.numLeftTitans) ||
                (this.numRightPeople > 0 && this.numRightPeople < this.numRightTitans)) {
                return false;
            }
            return true;
        },
        //無事に全員渡れたかチェック
        isFinish: function () {
            if (this.numRightPeople + this.numRightTitans == 6) {
                this.parentState.count++;
                return true;
            }
            //console.log(this);
            return false;
        },
        copy: function (oldState) {
            this.stateString = oldState.stateString;
            this.numLeftPeople = oldState.numLeftPeople;
            this.numRightPeople = oldState.numRightPeople;
            this.numLeftTitans = oldState.numLeftTitans;
            this.numRightTitans = oldState.numRightTitans;
            this.kanoeState = oldState.kanoeState;
            this.parentState = oldState;
            this.log = oldState.log.slice(0);
            this.logLeft = oldState.logLeft.slice(0);
            this.logRight = oldState.logRight.slice(0);
            this.depth += 1 + oldState.depth;
        },
        //移動後の岸の状態を更新
        move: function (numPerson, numTitan) {
            if (this.kanoeState == "left") {
                this.numLeftPeople -= numPerson;
                this.numRightPeople += numPerson;
                this.numLeftTitans -= numTitan;
                this.numRightTitans += numTitan;
                this.kanoeState = "right";

            } else {
                this.numLeftPeople += numPerson;
                this.numRightPeople -= numPerson;
                this.numLeftTitans += numTitan;
                this.numRightTitans -= numTitan;
                this.kanoeState = "left";
            }
        },
        print: function (numLeftS, numLeftT, numRightS, numRightT) {
            var strLeftS = this.makeString(numLeftS, "S");
            var strLeftT = this.makeString(numLeftT, "T");
            var strRightS = this.makeString(numRightS, "S");
            var strRightT = this.makeString(numRightT, "T");
            return strLeftS + strLeftT + "/" + strRightS + strRightT;

        },
        makeString: function (num, str) {
            var result = "";
            for (var i = 0; i < num; i++) {
                result += str;
            }
            return result;
        }
    };

    c.Main = function Main() { };
    c.Main.prototype = {
        answers: 1,
        solve: function (initialState) {
            //スタッククラス
            var stack = new CodeIq.Stack();
            stack.push(initialState);
            initialState.isRootNode = true;

            while (stack.size() > 0) {
                var state = stack.pop();

                if (state.isConsumed()) {
                    continue;
                } else {
                    stack.push(state);
                }

                //console.log("depth:" + state.depth);

                if (state.isFinish()) {
                    //console.log("found");
                    console.log("解答" + this.answers++);
                    state.log.forEach(function (element) {
                        console.log(element);
                    });
                    stack.pop();
                    continue;
                } else {
                    //console.log("failed : " + state.numLeftPeople + "," + state.numLeftTitans + ", " + state.numRightPeople +  ","  + state.numRightTitans);
                }
                var newState;
                newState = state.createNewCondition();
                var isValid = newState.search();
                if (isValid) {
                    stack.push(newState);
                }
            }
            //this.answers.forEach(function (element) {
            //    console.log(element);
            //});
        }
    };

    var initialState = new CodeIq.State();
    var main = new CodeIq.Main();
    main.solve(initialState);

})();