Frame-Stewart.

So here is something that always shocks me about university assignments:

Why is it that nobody knows how to use Google?

Because if they did, there would be very little issue with the "Tour" part of our latest assignment. The recursive formula we are provided with in the assignment is known as the "Frame-Stewart Algorithm", and in plain english is as follows.

If you have N cheeses:

1. Move n-i cheeses to some peg that isn't the final peg.
2. Using a 3 tower algorithm, move i cheeses to the final peg
3. Using the same procedure as before, move the cheeses from part 1 to the final peg.

That is all there is to it, and there are even extensive papers on the subject complete with various implementations of the program as well as charts showing that it is optimal at least up to 20 cheeses (regardless of the fact that it is an "unproven" conjecture).

So how did I decide to implement it? Well, I wrote two functions, one to solve recursively for 3 stools based on listed indices (mainly so that they could change depending on what the 4 stools one required), then I wrote a program for 4 stools that uses inputted indices and works recursively the same way.

After it spit out a list of tuples, which directly correspond to moves, I then use that list to apply the moves to a model. I considered just applying the moves directly to the model but I felt like it was easier to animate if the list of moves existed BEFORE we applied them, since all we would then need to do is apply, print, apply, print, apply, print etc.

Perhaps for fun I will try to implement it for n-stools.