- Notifications
You must be signed in to change notification settings - Fork180
Add TowerOfHanoi algorithm solution / visualization in JavaScript#39
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Open
quanxtruong wants to merge7 commits intoalgorithm-visualizer:masterChoose a base branch
base:master
Could not load branches
Branch not found:{{ refName }}
Loading
Could not load tags
Nothing to show
Loading
Are you sure you want to change the base?
Some commits from the old base branch may be removed from the timeline, and old review comments may become outdated.
Uh oh!
There was an error while loading.Please reload this page.
Open
Changes fromall commits
Commits
Show all changes
7 commits Select commitHold shift + click to select a range
b1d070a Create code.js
quanxtruong9c6633c towerOfHanoi working--may add comments
quanxtruong0bf36a5 changed the title for more accuracy
quanxtruonge8e4e02 changed the title, starting adding README
quanxtruong27d5f2e half of readme done, need to complete algorithm explanations
quanxtruongc844b87 TOH algorithm and README finished
quanxtruong309ffb4 TOH final touchups
quanxtruongFile filter
Filter by extension
Conversations
Failed to load comments.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Jump to
Jump to file
Failed to load files.
Loading
Uh oh!
There was an error while loading.Please reload this page.
Diff view
Diff view
There are no files selected for viewing
117 changes: 117 additions & 0 deletionsSimple Recursive/Tower Of Hanoi/README.md
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,117 @@ | ||
| # Tower Of Hanoi | ||
| The **Tower of Hanoi** is a mathematical game or puzzle consisting of `3` rods and | ||
| a `N` number of disks of various diameters, which can slide onto any rod. | ||
| The puzzle begins with the disks stacked on one rod in order of decreasing size, | ||
| the smallest at the top. In this case, each *rod* is represented by a *column of the 2D Array or Matrix*, | ||
| with the original peg being the column indexed as `0` and the destination peg being column indexed as `2`. | ||
| The objective of the puzzle is to move the entire stack to one of the other rods, obeying the following rules: | ||
| - Only one disk may be moved at a time. | ||
| - Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. | ||
| - No disk may be placed on top of a disk that is smaller than it. | ||
| For example, the following is the steps of a solution for The Tower of Hanoi with `4` disks: | ||
|  | ||
| The expected output is a matrix that has all of the disks in column `2` | ||
| in increasing order, that being the smallest valued disk and the top and the highest | ||
| valued disk at the bottom. | ||
| For example, the following is the input and output matrix for a 4 disk Tower of Hanoi soluion. | ||
| ``` | ||
| Input Output | ||
| { 1, 0, 0, 0} { 0, 0, 0, 1} | ||
| { 2, 0, 0, 0} ----------> { 0, 0, 0, 2} | ||
| { 3, 0, 0, 0} ----------> { 0, 0, 0. 3} | ||
| { 4, 0, 0, 0} { 0, 0, 0, 4} | ||
| ``` | ||
| The visualizer provides assistance in visualizing the moves while simultaneously confirming all rules are abided by in each step. | ||
| --- | ||
| ## Iterative Solution | ||
| The iterative solution is equivalent to the execution of the following sequence of steps repeatedly until the Tower of Hanoi is solved: | ||
| `1) `Move one disk from peg A to peg B or vice versa, whichever move is legal. | ||
| `2) `Move one disk from peg A to peg C or vice versa, whichever move is legal. | ||
| `3) `Move one disk from peg B to peg C or vice versa, whichever move is legal. | ||
| Following this approach, the stack will end up on peg B if the number of disks is odd and peg C if it is even. | ||
| Below is a visualization of the iterative solution with 6 disks: | ||
|  | ||
| --- | ||
| ## Recursive Solution | ||
| This is the solution used for this current iteration of the Tower of Hanoi algorithm visualizer. | ||
| The Tower of Hanoi is a puzzle that boils down to a collection of smaller sub-problems. | ||
| For the Towers of Hanoi: | ||
| - Label the pegs A, B, C. | ||
| - Let n be the total number of disks. | ||
| - Number the disks from 1 (smallest, topmost) to n (largest, bottom-most). | ||
| Assuming all n disks are distributed in valid arrangements among the pegs; assuming there are m top disks on a source peg, and all the rest of the disks are larger than m, so they can be safely ignored; to move m disks from a source peg to a target peg using a spare peg, without violating the rules: | ||
| `1)` Move m − 1 disks from the source to the spare peg, by the *same general solving procedure*. Rules are not violated, by assumption. This leaves the disk m as a top disk on the source peg. | ||
| `2)` Move the disk m from the source to the target peg, which is guaranteed to be a valid move, by the assumptions — a simple step. | ||
| `3)` Move the m − 1 disk that we have just placed on the spare, from the spare to the target peg by the same general solving procedure, so they are placed on top of the disk m without violating the rules. | ||
| The base case is to move 0 disks (in steps 1 and 3), that is, do nothing that does not violate the rules (which in this case is just a simple return statement). | ||
| The full Tower of Hanoi solution then moves n disks from the source peg A to the target peg C, using B as the spare peg. | ||
| Below is a general psuedo-code used to implement the recursive solution: | ||
| ``` | ||
| RecursiveHanoi(n, s, a, d) { | ||
| // INPUT | ||
| // n = the number of disks | ||
| // s = the source rod | ||
| // a = the auxiliary rod | ||
| // d = the destination rod | ||
| // Base Case | ||
| if (n == 0) { | ||
| return | ||
| } | ||
| // 1) | ||
| RecursiveHanoi(n - 1, s, d, a) | ||
| // 2) | ||
| move from s peg to d peg | ||
| // 3) | ||
| RecursiveHanoi(n - 1, a, s, d) | ||
| } | ||
| ``` | ||
| --- | ||
| ## Time and Space Complexity | ||
| - **Time**: ) | ||
| - **Space**: ) | ||
| where `N = number of disks` | ||
| ## References | ||
| - [IIT Kanpur](https://www.iitk.ac.in/esc101/08Jan/lecnotes/lecture32.pdf) | ||
| - [GeeksForGeeks](https://www.geeksforgeeks.org/c-program-for-tower-of-hanoi/) | ||
| - [Wikipedia](https://en.wikipedia.org/wiki/Tower_of_Hanoi) | ||
97 changes: 97 additions & 0 deletionsSimple Recursive/Tower Of Hanoi/code.js
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.Learn more about bidirectional Unicode characters
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,97 @@ | ||
| // import visualization libraries { | ||
| const { Tracer, Array2DTracer, LogTracer, Layout, VerticalLayout } = require('algorithm-visualizer'); | ||
| // } | ||
| // define tracer variables { | ||
| const towerTracer = new Array2DTracer('Towers Of Hanoi'); | ||
| const logTracer = new LogTracer('Progress'); | ||
| // } | ||
| let disks = 5; // just change the value of disks, build, and then the visuals will reflect how many disks are stacked! | ||
| const towers = (function createTowers(N) { | ||
| const startState = Array(N).fill().map(() => Array(3).fill(0)); | ||
| for (let k = 1, i = 0; k <= disks; k++, i++) { | ||
| startState[i][0] = k; | ||
| } | ||
| return startState; | ||
| }(disks)); | ||
| // Logger { | ||
| logTracer.println("Tower of Hanoi Puzzle: Each column represents one of the three rods"); | ||
| logTracer.println(" Smaller valued \"disks\" cannot stack on bigger valued \"disks\""); | ||
| logTracer.println("-------------------------------------------------------------------"); | ||
| logTracer.println("Solution with " + disks + " disks:"); | ||
| // } | ||
| function solveHanoi(n, from_rod, to_rod, aux_rod) { | ||
| // Base Case | ||
| if (n === 0) { | ||
| return; | ||
| } | ||
| solveHanoi(n - 1, from_rod, aux_rod, to_rod); | ||
| // Logger { | ||
| logTracer.println(`Moving disk ${n} from rod ${from_rod} to rod ${to_rod}<br/>`); | ||
| // } | ||
| const fromIndex = parseInt(from_rod, 10) - 1; | ||
| const toIndex = parseInt(to_rod, 10) - 1; | ||
| // Find topmost disk: from_rod -> to_rod | ||
| let disk = 0; | ||
| for (let i = 0; i < disks; i++) { | ||
| if (towers[i][fromIndex] !== 0) { | ||
| disk = towers[i][fromIndex]; | ||
| towers[i][fromIndex] = 0; | ||
| // visualize the moves { | ||
| towerTracer.select(i,fromIndex); | ||
| Tracer.delay() | ||
| towerTracer.patch(i, fromIndex, 0); | ||
| towerTracer.depatch(i, fromIndex) | ||
| towerTracer.deselect(i,fromIndex); | ||
| // } | ||
| break; | ||
| } | ||
| } | ||
| for (let i = disks - 1; i >= 0; i--) { | ||
| if (towers[i][toIndex] === 0) { | ||
| towers[i][toIndex] = disk; | ||
| // visualize the moves { | ||
| towerTracer.select(i,toIndex); | ||
| Tracer.delay(); | ||
| towerTracer.patch(i, toIndex, disk); | ||
| Tracer.delay(); | ||
| towerTracer.depatch(i, toIndex); | ||
| Tracer.delay() | ||
| towerTracer.deselect(i,toIndex); | ||
| // } | ||
| break; | ||
| } | ||
| } | ||
| solveHanoi(n - 1, aux_rod, to_rod, from_rod); | ||
| } | ||
| (function main() { | ||
| // visualize { | ||
| Layout.setRoot(new VerticalLayout([towerTracer, logTracer])); | ||
| towerTracer.set(towers); | ||
| Tracer.delay(); | ||
| logTracer.println("Starting execution"); | ||
| logTracer.println("------------------"); | ||
| // } | ||
| solveHanoi(disks, '1', '3', '2'); | ||
| // logger { | ||
| logTracer.println("Execution Finished: all pegs moved from source peg to destination peg (rod 1 --> rod 3)"); | ||
| // } | ||
| })(); | ||
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.