칸 아카데미 - 하노이의 탑 소스

hanoi.js

// This library exposes 3 functions:
//   hanoi.moveDisk(fromPeg, toPeg);  This moves the top disk from the fromPeg to the toPeg
//   hanoi.getSparePeg(fromPeg, toPeg); This returns the remaining peg that isn't the fromPeg or the toPeg
//   hanoi.isSolved(toPeg); This returns true if all disks are on toPeg and no invalid moves have been used
var hanoi = (function() {
var sprites = function() {
"use strict";

    // A minimalist sprite library for KA visualizations.  
    //   Devin Balkcom, June 2014.

    // Uses prototypical object pattern like that described at 
    // http://davidwalsh.name/javascript-objects-deconstruction
    var extend = function(proto, properties) {
        var obj = Object.create(proto);
        for (var p in properties) {
            if ( properties.hasOwnProperty(p) ) {
                obj[p] = properties[p];
            }
        }
        return obj;
    };

    // global constants used to indicate time periods for timelines
    var FOREVER = -1;
    var NONE = -2;

    // optionally pass in a function to draw background, etc in drawInit
    var Scene = {
        init: function(drawInit) {
            this.sprites = [];
            this.drawInit = drawInit;
            this.draggingSprite = NONE;
            this.lastClickedSprite = null;

            this.mousePressed = null;            

        },
        draw: function() {
            if (this.drawInit) { 
                this.drawInit(); 
            }
            for (var i = 0; i < this.sprites.length; i++) {

                var sprite = this.sprites[i];
                sprite.draw();

                // update mouseOver property for sprites and 
                //  selected sprite for the scene
                sprite.mouseOver = false;
                if (sprite.containsPoint(mouseX, mouseY) ) {
                    sprite.mouseOver = true;
                }
            }
            if (this.draggingSprite !== NONE) {
                this.sprites[this.draggingSprite].draw();
            }
        },

        add:  function(sprite) {
            this.sprites.push(sprite);
        },

        removeAll: function(spriteName) {
            for (var i = this.sprites.length - 1; i >= 0 ; i--) {
                if (this.sprites[i].name === spriteName) {
                    this.sprites.splice(i, 1);
                }
            }
        }
    };

    // definition of a grid that can be used to convert between coordinates of
    //  larger cells and pixel coordinates.  Useful for moving sprites between
    //  locations on a on-screen grid. 

    var Grid = {
        // uses object-creation pattern from 
        //  http://davidwalsh.name/javascript-objects-deconstruction

        init: function(leftX, topY, width, height) {
            this.leftX = leftX;
            this.topY = topY;
            this.width = width;
            this.height = height;
        },
        pixelX: function(gridX) {
            return this.leftX + gridX * (this.width);
        },
        pixelY: function(gridY) {
            return this.topY+ gridY * (this.height);
        }
    };

    // Definition of sprite object
    /////////////////////////////

    // name is a string describing the sprite name.  Used to find sprites in the scene
    //  (for example, to remove them).

    // optionally pass in parameters for initial location and height.
    //  However, getX(), getH(), getW(), and getH() are the proper way to get location, width
    //  and height of a sprite.  Typically, these functions are bound to a model
    //  in a model-view design.

    var Sprite = {

        init:  function(name, x, y, w, h) {

            this.name = name;

            this.x = x;
            this.y = y;
            this.w = w;
            this.h = h;

            this.mouseOver = false;
            this.mousePressed = false;

            this.draggable = false;

            this.visible = true;
            this.selected = false;
            this.release = undefined;
        },

        // set up initial functions to return location of the sprite.  For a sprite
        //  that is not bound to a model, these are fine default functions to return location
        getX: function() {
            return this.x;
        },
        getY: function() {
            return this.y;
        },

        getW: function() {
            return this.w;
        },

        getH: function() {
            return this.h;
        },

        show: function() {
            this.visible = true;
        },

        hide: function() {
            this.visible = false;
        },
        select: function() {
            this.selected = true;
        },
        unselect:function() {
            this.selected = false; 
        },

        draw: function() {},

        translate: function(tx, ty) {
            this.x += tx;
            this.y += ty;
        },

        // animate the motion of a sprite from one location to another on a grid.        
        gridMove: function(timeline, workingFrame, grid, fromGridX, fromGridY, toGridX, toGridY) {


            var dx = ( grid.pixelX(toGridX) - grid.pixelX(fromGridX) );
            var dy = ( grid.pixelY(toGridY) - grid.pixelY(fromGridY) );

            // normalize speed
            var length = sqrt(dx * dx + dy * dy);

            var duration = length;

            dx /= length;
            dy /= length;

            timeline.addEvent(workingFrame, duration, this.translate.bind(this, dx, dy) );

            return duration;

        },


        containsPoint: function(x, y) {
            return x >= this.getX() && y >= this.getY()  &&
                x < (this.getX() + this.getW()) && y < (this.getY() + this.getH());
        }
    };

    var TextSprite = Object.create(Sprite);

    TextSprite.init = function(string, x, y, alignment, label) {
        sprites.Sprite.init.call(this, label, x, y, 0, 0);
        this.string = string;
        this.alignment = alignment;
    };

    TextSprite.draw = function() {
        textAlign(this.alignment);
        fill(0, 0, 0);
        text(this.string, this.x, this.y);
        textAlign(LEFT);

    };

    TextSprite.changeText = function(timeline, workingFrame, string) {
        var textSprite = this;
        timeline.addEvent(workingFrame, 1, function() {
            textSprite.string = string;
         } );
    };

    var Timeline = {

        // a simple hashtable with keys that are times (a frame number) 
        //  and values that are functions to run at those times:

        events: [],
        currentFrame: 0, // an int keeping track of current frame to draw
        speed: 1,
        time: 0,  // a float value keeping track of current time on the timeline
        paused: true,

        lastFrame: 0,

        // a list of times that can be advanced to with "step"
        bookmarks: [],
        nextPause: NONE,

        init: function() {
        },

        setSpeed: function(speed) {
            this.speed = speed;
        },

        // add an event function to the list of events.  Optional parameter
        //   fnAtEnd gives a second function to execute after repeats are 
        //   completed 
        addEvent: function(start, repeats, fn, fnAtEnd) {
            var eventObject = {start: start, repeats: repeats, fn: fn};
            this.events.push(eventObject);

            if(fnAtEnd) {
                this.events.push({start: start + repeats - 1, repeats: 1, fn: fnAtEnd});
            }
            this.lastFrame = start + repeats - 1;
        },

        bookmark: function(t) {
            this.bookmarks.push(t);
        },

        update: function() {
            // catch the drawing up to the time by incrementing currentFrame until it
            //  reaches the floor of the time value.
            while(this.currentFrame < floor(this.time) ) {
                for (var i = 0; i < this.events.length; i++) {
                    var event = this.events[i];
                    if(this.currentFrame >= event.start) {
                        if(event.repeats === FOREVER ||
                            this.currentFrame < (event.start + event.repeats)) {
                                event.fn();
                        }
                    }
                }
            
                this.currentFrame++;
            }

            if (this.nextPause !== NONE && this.time >= this.nextPause) {
                this.pause();
            }

            if (!this.paused) {
                this.time += this.speed;
            }

        },

        step: function() {
            // find the least bookmark greater than the current time, and 
            //  enable playing until that time is reached
            for (var i = 0; i < this.bookmarks.length; i++ ) {
                if (this.bookmarks[i] > this.time) {
                    //this.time = this.bookmarks[i];
                    this.nextPause = this.bookmarks[i];
                    this.play();
                    break;
                }
            }
        },

        play: function() {
            this.paused = false;
        },

        pause: function() {
            this.paused = true;
        }
        
    };

    var startAnimation = function(scene, timeline) {

        draw = function() {
            if(typeof timeline !== 'undefined'){
                timeline.update();
            }
            if(typeof scene !== 'undefined'){
                scene.draw();
            }
        };

        mousePressed = function() {

            if(scene.mousePressed) {
                scene.mousePressed();
            }

            for (var i = 0; i < scene.sprites.length; i++) {
                var sprite = scene.sprites[i];
                if(sprite.mouseOver) {
                    sprite.mousePressed = true;
                    scene.lastClickedSprite = sprite;

                    if (sprite.onAction) {
                        sprite.onAction();
                    }

                    if(sprite.draggable) {
                        scene.draggingSprite = i;
                        sprite.lastDragX = mouseX;
                        sprite.lastDragY = mouseY;
                    }
                }
            }

        };

        mouseReleased = function() {
            
            if ((scene.draggingSprite !== NONE) &&
                (scene.sprites[scene.draggingSprite].release !== undefined)) {
                scene.sprites[scene.draggingSprite].release();
            }
            scene.draggingSprite = NONE;

            // clear all mouseDown variables for sprites
            for (var i = 0; i < scene.sprites.length; i++) {
                var sprite = scene.sprites[i];
                sprite.mousePressed = false;
            }
            
        };

        mouseDragged = function() {
            if(scene.draggingSprite !== NONE) {
                var sprite = scene.sprites[scene.draggingSprite];

                if (sprite.draggable) {
                    sprite.translate(mouseX - sprite.lastDragX,
                            mouseY - sprite.lastDragY);
                    sprite.lastDragX = mouseX;
                    sprite.lastDragY = mouseY;
                }
            }
        };

        scene.draw();
    };

    return {extend: extend,
            Scene: Scene,
            Grid: Grid,
            Sprite: Sprite,
            TextSprite: TextSprite,
            Timeline: Timeline,
            startAnimation: startAnimation,
            FOREVER: FOREVER,
            NONE: NONE
        };
}();

var frame = 1;
var WINDOW_SIZE = width || 400;
var objects = (function() {
    var PEG_WIDTH = 20;
    var DISK_HEIGHT = 20;
    var solving = false;
    var draggingEnabled = true;

    // Uses inheritance pattern from 
    //   https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Object/create
    // ==============================================================================================

    // The disk sprite.
    var Disk = sprites.extend(sprites.Sprite, {
        init: function(diskObject) {
            var w = diskObject.w;
            var h = diskObject.h;
            var number = diskObject.number;
            var peg = diskObject.peg;
            var color = diskObject.color;

            var x = peg.x - w / 2 + peg.w / 2;
            var disksUnder = peg.disks.length;
            var y = peg.y + peg.h- (h+0.1) * (disksUnder + 1);
            
            sprites.Sprite.init.call(this, "Disk " + str(number), x, y, w, h); // calls superclass constructor
            
            this.x=x;
            this.y=y;
            
            this.number = number;
            this.color = color;

            this.draggable = false;
        
            this.release = function() {
                this.dragging = false;
                if (draggingEnabled){
                    //make sure the moved disk came from the top of it's stack
                    if(this.peg.getTopDisk() === this){
                        for (var i = 0; i < pegs.length; i++) {
                            var peg = pegs[i];
                            if (posIsInRect(mouseX, mouseY, peg.x - WINDOW_SIZE / 8, peg.y, WINDOW_SIZE / 4, peg.h)){
                                //check that the destination peg is empty or
                                //that this disk is smaller than the top disk on the destination peg 
                                if ( (peg.countDisks() ===0) ||(this.number < peg.getTopDisk().number ) ) {
                                    this.moveToPeg(peg);
                                }
                                break;
                            }
                        }
                    }
                    //snaps disk back to position when released
                    timeline.addEvent(frame - 3, 1, this.moveToPegPosition.bind(this));
                }
            };

            this.peg = peg;
            this.peg.addDisk(this);
            scene.add(this);
            
        },

        moveToPeg: function(destPeg) {
            // Moves the disk around in the data structures to seemingly move it from one disk to another
            this.peg.removeDisk();
            this.peg = destPeg;
            this.peg.addDisk(this);
            this.dragging = false;
        },
        
        moveToPegPosition: function(){
            //move the position of the disk
            this.x = this.peg.x + this.peg.w / 2 - this.w / 2;
            var disksUnder = this.peg.getNumberOfDisksUnder(this);
            this.y = this.peg.y + this.peg.h - (this.h+0.1) * (disksUnder + 1);
        },

        draw: function() {
            
            textAlign(CENTER, CENTER);
            stroke(lerpColor(0, 0, 0));
 
            fill(this.color[0], this.color[1], this.color[2]);
            rect(this.x, this.y, this.w, this.h, 3);

            // draw disk number
            fill(0, 0, 0);
            text(this.number, this.x + this.w / 2, this.y + this.h / 2);
        },

        onAction: function() {
            this.dragging = draggingEnabled;
            this.draggable = (this === this.peg.getTopDisk());
        }
    });

    var Peg = sprites.extend(sprites.Sprite, {
        init: function(pegObject) {
            var x = pegObject.x;
            var y = pegObject.y;
            var w = pegObject.w;
            var h = pegObject.h;
            var letter = pegObject.letter;
            var number = pegObject.number;

            sprites.Sprite.init.call(this, "Peg " + letter, x, y, w, h);
            this.letter = letter;
            this.number = number;
            this.disks = [];
            scene.add(this);
        },

        removeDisk: function() {
            if(this.disks.length === 0){ return;}
            this.disks.pop();
        },

        addDisk: function(disk) {
            this.disks.push(disk);
        },

        countDisks: function() {
            return this.disks.length;
        },

        getTopDisk: function() {
            return this.disks[this.disks.length-1];
        },

        getNumberOfDisksUnder: function(disk) {
            return this.disks.indexOf(disk);
        },

        draw: function() {
            textAlign(CENTER, CENTER);
            stroke(lerpColor(0, 0, 0));
            fill(149, 149, 149);    // dark gray, peg color from Tom Cormen's images
            rect(this.x, this.y, this.w, this.h, 3);

            // draw peg letter
            fill(0, 0, 0);
            text(this.letter, this.x + this.w / 2, this.y + 15);
        }
    });

    var Table = sprites.extend(sprites.Sprite, {
        init: function(tableObject){
            var x = tableObject.x;
            var y = tableObject.y;
            var w = tableObject.w;
            var h = tableObject.h;

            sprites.Sprite.init.call(this, "Table", x, y, w, h);
            scene.add(this);
        },

        draw: function() {
            textAlign(CENTER, CENTER);
            stroke(lerpColor(0, 0, 0));
            fill(139, 59, 4);
            rect(this.x, this.y, this.w, this.h, 3);
            frame++;
        }
    });

    // End classes
    // ===============================================================================================
    // Start functions

    // From devin's code:
    var posIsInRect = function(x, y, rectX, rectY, width, height) {
        // Returns a boolean for whether the given position is 
        //  within the specified rectangle

        return (x >= rectX && x < rectX + width && y >= rectY && y < rectY + height);
    };

    var workingFrame = 0;

    var updateWorkingFrame = function(value) {
        workingFrame = value;
    };

    var getWorkingFrame = function() {
        return workingFrame;
    };

    // End functions
    //=================================================================================================

    var scene = Object.create(sprites.Scene);
    scene.init(function() {
        background(255, 255, 255);
        textAlign(CENTER, CENTER);
    });
    var timeline = Object.create(sprites.Timeline);

    var pegs = [];
    var disks = [];

    var numberOfDisks = 5;

    var calcDiskHight = DISK_HEIGHT;

    if ((numberOfDisks + 1) * DISK_HEIGHT > (WINDOW_SIZE / 6) * 3 - DISK_HEIGHT  * 1.3) {
        calcDiskHight = ((WINDOW_SIZE / 6) * 3 - DISK_HEIGHT  * 1.3) / numberOfDisks;
    }

    var diskColors = [[252, 51, 61], [252, 106, 7], [255, 255, 11],
            [69, 255, 60], [64, 146, 255]];

    // Create pegs and add them to the list
    var peg = Object.create(Peg);
    peg.init({x: (WINDOW_SIZE / 4) * 1 - PEG_WIDTH / 2,
        y: WINDOW_SIZE / 5,
        w: PEG_WIDTH,
        h: (WINDOW_SIZE / 6) * 3,
        letter: "A",
        number: 1,
        disks: []
    });

    pegs.push(peg);

    peg = Object.create(Peg);
    peg.init({x: (WINDOW_SIZE / 4) * 2 - PEG_WIDTH / 2,
        y: WINDOW_SIZE / 5,
        w: PEG_WIDTH,
        h: (WINDOW_SIZE / 6) * 3,
        letter: "B",
        number: 2,
        disks: []
    });

    pegs.push(peg);

    peg = Object.create(Peg);
    peg.init({x: (WINDOW_SIZE / 4) * 3 - PEG_WIDTH / 2,
        y: WINDOW_SIZE / 5,
        w: PEG_WIDTH,
        h: (WINDOW_SIZE / 6) * 3,
        letter: "C",
        number: 3,
        disks: []
    });

    pegs.push(peg);

    // Create disks and add them to the full list
    // disk1-0
    for (var i = numberOfDisks - 1; i >= 0; i--) {
        var disk = Object.create(Disk);
        var diskNum = i + 1;

        // Optionally allow the peg locations to be configured via settings,
        // like {disk1:0, disk2:1}, where pegs are 0-indexed but disks aren't
        var pegNum = parseInt((Program.settings()["disk" + diskNum] || 0), 10);
        
        disk.init({
            w: (((WINDOW_SIZE * 2 / 4 - WINDOW_SIZE / 4) - PEG_WIDTH * 1.3) / (1.3 * numberOfDisks) * (i + 1) + PEG_WIDTH * 1.3),
            h: calcDiskHight,
            number: diskNum,
            peg: pegs[pegNum],
            color: diskColors[i%(diskColors.length)]
        });
        //disks add themselves automatically to their peg in the init function

        disks.push(disk);
    }

    // Create table
    var table = Object.create(Table);
    table.init({x: 40,
        y: WINDOW_SIZE * 7 / 10,
        w: WINDOW_SIZE - 80,
        h: DISK_HEIGHT
    });
    
    sprites.startAnimation(scene, timeline);
    timeline.play();
    
    return {pegs: pegs, disks: disks, timeline: timeline, scene: scene, workingFrame: workingFrame, updateWorkingFrame: updateWorkingFrame, getWorkingFrame: getWorkingFrame};
})();

var convertLetterToPeg = function(pegLetter) {
    if(pegLetter === "A" || pegLetter === "B" || pegLetter === "C"){
        return objects.pegs[pegLetter.charCodeAt(0)-65];
    }
    return null;   
};

var badmove=false;

var moveDisk = function(fromPeg, toPeg) {
    //no moves allowed after a bad move
    if(badmove){
        return;
    }
    
    var triedFromPeg = fromPeg;
    var triedToPeg = toPeg;
    fromPeg = convertLetterToPeg(fromPeg);
    toPeg = convertLetterToPeg(toPeg);
    
    var validmove=true;
    var badMoveMessage="";
    if(fromPeg === null){
        validmove=false;
        badMoveMessage = "'"+triedFromPeg+"' is not a valid peg";    
        badMoveMessage += "\nvalid peg names are 'A','B' or 'C'";
        badmove=true;
    }
    else if(toPeg === null){
        validmove=false;
        badMoveMessage = "'"+triedToPeg+"' is not a valid peg";
        badMoveMessage += "\nvalid peg names are 'A','B' or 'C'";
        badmove=true;    
    }
    else if(fromPeg.countDisks() === 0){ 
        validmove=false;
        badMoveMessage = "You attempted to move a disk from peg "+ fromPeg.letter;
        badMoveMessage += " but that peg\nwas empty";
        badmove=true;
    }
    else if(toPeg.countDisks() > 0 && fromPeg.getTopDisk().number > toPeg.getTopDisk().number ){
        validmove=false;
        badMoveMessage = "You attempted to move disk "+fromPeg.getTopDisk().number +" from peg ";
        badMoveMessage += fromPeg.letter + " onto disk " + toPeg.getTopDisk().number + " on peg "; 
        badMoveMessage += toPeg.letter +"\nIt is against the rules to move larger disks onto smaller disks";
        badmove=true;
    }
    if(!validmove){
        badMoveMessage += "\nFurther calls to the moveDisk function will be blocked.";
        badMoveMessage += "\nPress 'Restart' to be able to call the function again.";
    }
    
    var nowFrame = objects.getWorkingFrame();
    var duration = WINDOW_SIZE * 3 / (16 * 4);
    
    var workingDisk= null;
    if(fromPeg !== null){ workingDisk = fromPeg.getTopDisk();}
    var numOnToPeg= null;
    if(toPeg !== null){ numOnToPeg = toPeg.disks.length; }

    objects.timeline.addEvent(nowFrame, duration, function() {
        
        //reject invalid moves
        if(!validmove){
            return;
        }
        
        objects.scene.draggingSprite = objects.scene.sprites.indexOf(workingDisk);
        
        var destY = toPeg.y + toPeg.h - (workingDisk.h+0.1) * (numOnToPeg + 1);
        var changeInY = destY - workingDisk.y;
        var yIncrament = changeInY / (duration - (frame - nowFrame - 4));

        var destX = toPeg.x + toPeg.w / 2 - workingDisk.w / 2;
        var changeInX = destX - workingDisk.x;
        var xIncrament = changeInX / (duration - (frame - nowFrame - 4));

        workingDisk.translate(xIncrament, yIncrament);
        
    }, function() {
        
        //reject invalid moves, and announce them
        if(!validmove){
            println(badMoveMessage);
            return;
        }
        
        println(fromPeg.letter + " -> "+toPeg.letter);
        
        //move disk to final position
        workingDisk.x = toPeg.x + toPeg.w / 2 - workingDisk.w / 2;
        var disksUnder = numOnToPeg;
        workingDisk.y = toPeg.y + toPeg.h - (workingDisk.h+0.1) * (disksUnder + 1);
        
    });
    objects.workingFrame = nowFrame + duration + 1;
    objects.updateWorkingFrame(objects.workingFrame);
    
    if(validmove){
        var workingDisk = fromPeg.getTopDisk();
        workingDisk.moveToPeg(toPeg);
    }
    
};

var getSparePeg = function(peg1, peg2) {
    peg1 = convertLetterToPeg(peg1);
    peg2 = convertLetterToPeg(peg2);
    if(peg1 === null || peg2 === null){ return null; }
    var sparePegIndex = 3 - (peg1.number - 1) - (peg2.number - 1);
    return objects.pegs[sparePegIndex].letter;
};

var isSolved=function(toPeg){
    if(badmove){ return false; }
    var pegA= convertLetterToPeg("A");
    var pegB= convertLetterToPeg("B");
    var pegC= convertLetterToPeg("C");
    var goalPeg = convertLetterToPeg(toPeg);
    if(goalPeg === null){ return false; }
    if(goalPeg.disks.length !== 5 ){return false;}
    if(goalPeg === pegA){ return pegB.disks.length ===0 &&  pegC.disks.length ===0;   }
    if(goalPeg === pegB){ return pegA.disks.length ===0 &&  pegC.disks.length ===0;   }
    if(goalPeg === pegC){ return pegA.disks.length ===0 &&  pegB.disks.length ===0;   }
};

return {
    getSparePeg: getSparePeg,
    moveDisk: moveDisk,
    isSolved: isSolved
};
})();


///////////////////*******////////////////////////
var solveHanoi = function(numDisks, fromPeg, toPeg) {
    // base case:  no disks to move
    if(numDisks===0){
        return false;
    }
    // recursive case:
    var sparePeg = hanoi.getSparePeg(fromPeg, toPeg);
    solveHanoi(numDisks-1, fromPeg, sparePeg);
    hanoi.moveDisk(fromPeg,toPeg);
    solveHanoi(numDisks-1, sparePeg, toPeg);
};

solveHanoi(5, "A", "B");
Program.assertEqual(hanoi.isSolved("B"),true);

This source is for towers-of-hanoi challenge, Khan Academy's algorithm lecture.
Except soleveHanoi function, other sources are based on Khan Academy provided.
(Licensed by Khan Academy)