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

Implement the Hanoi class in two stages.

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!

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$

$13$

$12$

$32$

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:

$13$

$12$

$32$