# Solve Hanoi recursively

```javascript
// 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;
    }
    // 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);
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://stephanosterburg.gitbook.io/scrapbook/math/algorithm-khan-academy/solve-hanoi-recursively.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.