Ad
Konomiravs.wtvamp

Sarai vs. Uly vs. Makayla - Tower of Hanoi

Iterative solution to the Tower of Hanoi puzzle, using the "Simpler statement of iterative solution" from Wikipedia https://en.wikipedia.org/wiki/Tower_of_Hanoi#Simpler_statement_of_iterative_solution

While not expressed in tests, once Solve() is called, the stacks a,b will be empty, and c will contain a list of integers in increasing order to numOfDisks

TODO: Add output to display the stacks each move

   +       |       |  
  -+-      |       |  
 --+--     |       |  
---+---    |       |  
####### ####### #######

Perhaps? 🤔🤔

Code
Diff
  • using System;
using System.Collections.Generic;

public class TowerOfHanoi
{
    public static Stack<int> a, b, c;
  
    public static int Tower(int numOfDisks)
    {
      // Generates new puzzle
      a = new Stack<int>();
      for(int i = numOfDisks; i > 0; i--)
        a.Push(i);
      
      b = new Stack<int>();
      b.Push(0);
      c = new Stack<int>();
      c.Push(0);
      
      var minIterations = (int)Math.Pow(2,numOfDisks) - 1;
      Solve(numOfDisks % 2 == 0, minIterations);
      
      return minIterations;
    }
  
    // Iterative (non-recursive) solution
    private static void Solve(bool even, int minIterations)
    {     
      void SwapHighest(Stack<int> x, Stack<int> y)
      {
        // Returns false if stack is empty
        if(!x.TryPeek(out var x1))
        {
          x.Push(y.Pop());
          return;
        }
        
        if(!y.TryPeek(out var y1))
        {
          y.Push(x.Pop());
          return;
        }
        
        if(x1 > y1)  
          y.Push(x.Pop());
        else
          x.Push(y.Pop());
      }
      
      if(even)
      {
        for(int i = 0; i <= minIterations; i+=3)
        {
          SwapHighest(a,b);
          SwapHighest(a,c);
          SwapHighest(b,c);
        }
      }
      else
      {
        for(int i = 0; i <= minIterations; i+=3)
        {
          SwapHighest(a,c);
          SwapHighest(a,b);
          SwapHighest(b,c);
        }
      }
    }
}
    • using System;
    • using System.Collections.Generic;
    • using System.Diagnostics;
    • public class TowerOfHanoi
    • {
    • public static Stack<int> a, b, c;
    • public static int Tower(int numOfDisks)
    • {
    • return 0;
    • // Generates new puzzle
    • a = new Stack<int>();
    • for(int i = numOfDisks; i > 0; i--)
    • a.Push(i);
    • b = new Stack<int>();
    • b.Push(0);
    • c = new Stack<int>();
    • c.Push(0);
    • var minIterations = (int)Math.Pow(2,numOfDisks) - 1;
    • Solve(numOfDisks % 2 == 0, minIterations);
    • return minIterations;
    • }
    • private static int Tower(int n, string source, string aux, string dest, Dictionary<int, int> cache)
    • {
    • return 0;
    • // Iterative (non-recursive) solution
    • private static void Solve(bool even, int minIterations)
    • {
    • void SwapHighest(Stack<int> x, Stack<int> y)
    • {
    • // Returns false if stack is empty
    • if(!x.TryPeek(out var x1))
    • {
    • x.Push(y.Pop());
    • return;
    • }
    • if(!y.TryPeek(out var y1))
    • {
    • y.Push(x.Pop());
    • return;
    • }
    • if(x1 > y1)
    • y.Push(x.Pop());
    • else
    • x.Push(y.Pop());
    • }
    • if(even)
    • {
    • for(int i = 0; i <= minIterations; i+=3)
    • {
    • SwapHighest(a,b);
    • SwapHighest(a,c);
    • SwapHighest(b,c);
    • }
    • }
    • else
    • {
    • for(int i = 0; i <= minIterations; i+=3)
    • {
    • SwapHighest(a,c);
    • SwapHighest(a,b);
    • SwapHighest(b,c);
    • }
    • }
    • }
    • }