$*$PLEASE READ INSTRUCTIONS CAREFULLY, DO NOT CREATE ANY FUNCTIONS NOT GIVEN IN INSTRUCTIONS$*$ In this project, we will implement a class that can solve a three$-$pole Tower of Hanoi puzzle for any number of discs starting from any source pole and going to any other destination pole. First, our class will do so recursively, and then it will do so recursively and efficiently.

TODO

Stage $1$:

Implement the recursive solution.

Commit and push your work as you do so$,$ committing at a minimum after each function definition.

Test drive your recursive implementation from src$/$main$.$cpp confirming correct solutions.

Commit and push your work.

Iterate as necessary, and commit and push your work throughout.

Commit and push successful program run$($s$)$ for stage $1.$

Stage $2$:

Memoize and optimize your solution.

Commit and push your work.

Test drive your memoized implementation from src$/$main$.$cpp$.$

Commit and push your work.

Run unit tests.

Iterate as necessary, and commit and push your work throughout.

Commit and push successful program run$($s$)$ for stage $2.$ Solution output will of course be identical to stage $1.$

Add a "Project $02$ Complete" comment to your Feedback pull request.

Give yourself yet another high five!

make terminal commands

make

builds bin$/$main executable

builds tests$/$bin$/*.$test executables

make main

builds bin$/$main executable

make run$\_$main

builds and runs bin$/$main executable

make memcheck$\_$main

runs bin$/$main executable with Valgrind:

valgrind $--$leak$-$check$=$yes $./$bin$/$main

make tests

builds tests$/$bin$/*.$test executables

make run$\_$tests

builds and iteratively runs all tests$/$bin$/*.$test executables

Note: VSCode test explorer can be used as an alternative to run tests after they're built

make run$\_$tests$\_$verbose

builds and iteratively runs all tests$/$bin$/*.$test executables with verbose output

Note: VSCode test explorer can be used as an alternative to run tests after they're built

make memcheck$\_$tests

builds and iteratively runs all tests$/$bin$/*.$test executables with Valgrind:

valgrind $--$leak$-$check$=$yes $./$tests$/$bin$/[$test$\_$name$].$test

make clean

removes all build artifacts

Implementation Notes & Details

Stage $1$

std::string Hanoi::solve$($int num$\_$discs, int src$,$ int dst$,$ int tmp$)$

This is the one and only public member function of the Hanoi class. It represents the user interface.

The user will call solve$()$ and provide the number of discs $($num$\_$discs $)$ they would like to move from the source pole $($src$)$ to the destination pole $($dst$)$ using the third pole as a temporary pole $($tmp$).$

solve$()$ returns a string representation of the necessary moves preceded by the following line:

# Below, $\text{'}$A$->$B$\text{'}$ means 'move the top disc on pole A to pole B

solve$()$ will supply this line and then add to it the string solution provided by calling get$\_$moves$().$

For example, calling solve$(2,1,2,3)$ would ultimately return the string:

# Below, $\text{'}$A$->$B$\text{'}$ means 'move the top disc on pole A to pole B

$1->3$

$1->2$

$3->2$

std::string Hanoi::get$\_$moves$($int num$\_$discs, int src$,$ int dst$,$ int tmp$)$

get$\_$moves$()$ returns the string representation of the required moves to move num$\_$discs discs from the src pole to the dst pole using the tmp pole as a temporary pole.

Each move will be on its own line.

For example, get$\_$moves$(2,1,2,3)$ would return the string:

$1->3$

$1->2$

$3->2$

Stage $2$

Hanoi::$\_$cache

$\_$cache is a private data member of the Hanoi class.

You must declare this data structure in hanoi.h$.$

$\_$cache is a $3-$dimensional vector that ultimately holds string representations for the sequence of moves that represent a solution for moving num$\_$discs $($the first dimension of $\_$cache$)$ from pole src $($the second dimension of $\_$cache$)$ to pole dst $($the third dimension of $\_$cache$).$

That makes $\_$cache a vector of vector of vector of strings.

For example, accessing the cache like so: $\_$cache$[4][1][3]$ would give you the string representation for the sequence of moves necessary to move $4$ discs from pole $1$ to pole $3$ using pole $2$ as a temporary pole $--$ if that solution was available in the cache.

std::string Hanoi::lookup$\_$moves$($int num$\_$discs, int src$,$ int dst$)$ const

lookup$\_$moves$()$ is responsible for accessing $\_$cache.

If the requested string solution is found, return it$.$

Otherwise return an empty string.

Memoization

$\_$cache

Declare the $\_$cache data structure in hanoi.h

Implement lookup$\_$moves$()$

Update get$\_$moves$()$ to use $\_$cache.

When invoked, first check the cache for the solution.

If the cache entry exists, return it$.$

Otherwise, calculate the sequence of moves as before, but store it in the cache before returning.

Only create $\_$cache entries lazily. That is$,$ don't create $\_$cache$[$i$]$ or $\_$cache$[$i$][$j$]$ or $\_$cache$[$i$][$j$][$k$]$ until you actually have a use for it$.$ In other words, you will only be expanding your cache dimensions as necessary and on demand so as to keep the memory footprint as light as possible.

Use pole labels $1,2$ and $3($not $0,1$ and $2$ or any other$).$ This means that $\_$cache$[$i$][0]$ and $\_$cache$[$i$][$j$][0]$ are dead locations you won't use in your program. But the savings you get in reduced cognitive load.$|$