The nth disc is moved again to its adjacent tower and has reached its destination tower. Then we move n-1 discs to its adjacent tower. Then the nth disc moves to the adjacent tower. So we make space the first time by transferring the top n-1 discs to the post-adjacent tower. In essence, we’ll have to make space twice to allow the nth disc to move to its final position. To move an n-tower of discs to the post-adjacent tower, we must do a little bit more. But we have to specialize the remaining function before we make the actual call: The answer is that we’ve only defined the templates, but we haven’t used them yet – we haven’t yet referred to a class where we’ve nailed down all of the template parameters, so they still only exist “in the ether”. Now you may wonder why we can call the indirect transfer for n > 1 discs before we specialize it. Now the destination tower is the post-adjacent tower to where our n-1 discs are temporarily stacked, so we’ll do another indirect transfer as before. Then we move the nth disc to the adjacent tower. So first, we’ll need to move n-1 discs from the source tower to the tower after next. To move an n-tower of discs to an adjacent tower, if we remember our invariant, we first have to make room so that we can move the nth disc into the final position. Then we’ll need to generalize these two functions for cases with more than one disc. There is also another opportunity for optimization by keeping track of the top disc for each tower so that we can avoid the search. These two specializations are the base cases and as you can see they will never fall down further to the undefined structure definition above. We can cheat a bit here where we can simulate two transfers by calling the direct specialization with the Src and Dst towers, as long as any metadata function (such as move counts, or move listing) is also simulated in the output. This is the only case where moving to a post-adjacent tower is equal to moving to the adjacent tower twice. Next we’ll need to specialize for moving one disc to a post-adjacent tower – the indirect specialization: I use std::iter_swap to do the actual transfer of the disc from one tower to the next since, by definition, it will always swap with a 0-disc, so it will look like we actually moved something. I use a reverse linear search (std::find with reverse iterators) because the array is small and the first non-zero disc will regularly be closer to the bottom than the top (beginning of the array), but using binary search (std::upper_bound) will work equally well. The top of the destination tower which we place our disc is the element before the first non-zero element in the destination tower array. The top disc of the first tower is the first non-zero element in our source tower array. To move a disc from one tower to another, we find the top disc of the source tower, remove it, and place it on top of the destination tower. This shows how the power of the strong static typing in C++ allows us to check algorithm validity without having to run it. This means that in the specialization, the compiler will calculate it for us and we would not need to specify whether it is direct or not. The direct boolean is a default parameter calculated from the source and destination tower arguments. Leaving it undefined like this means that if we made a mistake in our implementation, the compiler will tell us with a compiler error saying that there is no definition. This is okay as we should expect that we will cover all cases. The templated structure definition does not actually define a complete structure. Return std::find(riter(_last), riter(_first), 0).base() Īuto top_src = rfind_zero(tower, tower + DISCS) Īuto top_dst = rfind_zero(tower, tower + DISCS) - 1 The towers are printed horizontally to avoid having to align columns. Std::string padding(disc_width + 1, '-') The Tower of Hanoi problem consists of moving a size-ordered stack of n discs from one tower to another tower, out of three towers Ĭonstexpr int DISCS = std::extent::value Ĭonst auto disc_width = std::to_string(DISCS).length()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |