migration C#, Java, C++ (day 9), Recursion

logo
The Tower of Hanoi is one of the most classical examples. I would say that the it is a kind of medieval version of the Rubik’s Cube. I remember that we had to solve the Tower of Hanoi problem in Pascal at school around 1992. Yeah, the good old times. Basically we are talking about code that could be written with less than 15 lines. Anyway, this version here is far more verbose. It tells you the position of each disk for each move.

I was thinking about doing some more coding today. Maybe JSON or calling C# code from inside C++. The problem is that you always have to install something else in C++ to get things running. I only have a few hours per day to write the source code for this blog. I could post more complex ideas every once in a while, but this would contradict my precondition of 15 days. Today is day 9. I can tell you already that it is not enough to just learn these examples here. You have to look a bit on the left and right side as well to be as fit as a fiddle in C++ after just 15 days.

Tower of Hanoi

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DemoApp {
   class TowerOfHanoi {

      private class Stack {
         private Stack<int> _Stack = new Stack<int>();
         public readonly int StackId;

         public Stack(int xStackId) { StackId = xStackId; }
         public void push(int xDisk) { _Stack.Push(xDisk); }
         public int pop() { return _Stack.Pop(); }

         public void print() {
            Console.Write("stack" + StackId + ":  ");
            foreach (int lDisk in _Stack) Console.Write(lDisk + " ");
            Console.WriteLine();
         } //
      }; // class

      private Stack _Stack0 = new Stack(0);
      private Stack _Stack1 = new Stack(1);
      private Stack _Stack2 = new Stack(2);

      void SolveTowerOfHanoi(int xDisk, Stack xSource, Stack xTemp, Stack xDestination) {
         int lDisk;

         if (xDisk == 1) {
            lDisk = xSource.pop();
            xDestination.push(lDisk);
            Console.WriteLine("moving disk " + lDisk + " from " + xSource.StackId + " to " + xDestination.StackId);
            _Stack0.print();
            _Stack1.print();
            _Stack2.print();
            Console.WriteLine();
            return;
         } 

         SolveTowerOfHanoi(xDisk - 1, xSource, xDestination, xTemp);
         lDisk = xSource.pop();
         xDestination.push(lDisk);
         Console.WriteLine("moving disk " + lDisk + " from " + xSource.StackId + " to " + xDestination.StackId);
         _Stack0.print();
         _Stack1.print();
         _Stack2.print();
         Console.WriteLine();
         SolveTowerOfHanoi(xDisk - 1, xTemp, xSource, xDestination);
      } //

      public void test() {
         int lDiskCount;
         string s;
         
         do {
            Console.Write("number of disks: ");
            s = Console.ReadLine();
         }
         while (!int.TryParse(s, out lDiskCount));         
         
         Console.WriteLine();
         for (int i = lDiskCount; i > 0; --i) _Stack0.push(i);
         SolveTowerOfHanoi(lDiskCount, _Stack0, _Stack1, _Stack2);

         Console.ReadKey();
      } //

   } // class
} // namespace
package Demos;

import java.io.IOException;
import java.util.*;

public class TowerOfHanoi {

  private static class Stack {

    private final java.util.Stack<Integer> _Stack = new java.util.Stack<>();
    public int StackId;

    public Stack(int xStackId) {
      StackId = xStackId;
    }

    public final void push(int xDisk) {
      _Stack.push(xDisk);
    }

    public final int pop() {
      return _Stack.pop();
    }

    public final void print() {
      System.out.print("stack" + StackId + ":  ");
      for (int lDisk : _Stack) System.out.print(lDisk + " ");
      System.out.println();
    }
  } // class

  private final Stack _Stack0 = new Stack(0);
  private final Stack _Stack1 = new Stack(1);
  private final Stack _Stack2 = new Stack(2);

  private void SolveTowerOfHanoi(int xDisk, Stack xSource, Stack xTemp, Stack xDestination) {
    int lDisk;

    if (xDisk == 1) {
      lDisk = xSource.pop();
      xDestination.push(lDisk);
      System.out.println("moving disk " + lDisk + " from " + xSource.StackId + " to " + xDestination.StackId);
      _Stack0.print();
      _Stack1.print();
      _Stack2.print();
      System.out.println();
      return;
    }

    SolveTowerOfHanoi(xDisk - 1, xSource, xDestination, xTemp);
    lDisk = xSource.pop();
    xDestination.push(lDisk);
    System.out.println("moving disk " + lDisk + " from " + xSource.StackId + " to " + xDestination.StackId);
    _Stack0.print();
    _Stack1.print();
    _Stack2.print();
    System.out.println();
    SolveTowerOfHanoi(xDisk - 1, xTemp, xSource, xDestination);
  } //

  boolean tryParseInt(String xValue) {
    try {
      Integer.parseInt(xValue);
      return true;
    } catch (NumberFormatException ex) {
      System.out.println("NumberFormatException: " + ex.getMessage());
      return false;
    }
  } //

  public final void test() {
    String s = null;
    do {
      System.out.print("number of disks: ");
      s = new Scanner(System.in).nextLine();
    } while (!tryParseInt(s));
    int lDiskCount = Integer.parseInt(s);

    System.out.println();
    for (int i = lDiskCount; i > 0; --i) _Stack0.push(i);
    SolveTowerOfHanoi(lDiskCount, _Stack0, _Stack1, _Stack2);

    try {
      System.in.read();
    } catch (IOException ex) {
      System.out.println("IOException: " + ex.getMessage());
    }
  } //
} // class
#include<iostream>
#include<vector>

using namespace std;

class Stack{
private:
    vector<int> _Stack;
    int _StackId;

public:
    Stack (int xStackId) : _StackId(xStackId) { }
    int getStackId() { return _StackId; }

    void push(int xDisk){_Stack.push_back(xDisk);}
    int pop() {
        int lDisk = _Stack.back();
        _Stack.pop_back();
        return lDisk;
    } //

    void print() {
        cout << "stack" << _StackId << ":  ";
        for (int lDisk : _Stack) cout << lDisk << " ";
        cout << endl;
    } //
}; // class

Stack _Stack0(0);
Stack _Stack1(1);
Stack _Stack2(2);

void SolveTowerOfHanoi(int xDisk, Stack *xSource, Stack *xTemp, Stack *xDestination) {
    int lDisk;

    if (xDisk==1) {
      lDisk = xSource->pop();
      xDestination->push(lDisk);
      cout << "moving disk " << lDisk << " from " << xSource->getStackId() << " to " << xDestination->getStackId() << endl;
      _Stack0.print();
      _Stack1.print();
      _Stack2.print();
      cout << endl;
      return;
    }

    SolveTowerOfHanoi(xDisk-1, xSource, xDestination, xTemp);
    lDisk = xSource->pop();
    xDestination->push(lDisk);
    cout << "moving disk " << lDisk << " from " << xSource->getStackId() << " to " << xDestination->getStackId() << endl;
    _Stack0.print();
    _Stack1.print();
    _Stack2.print();
    cout << endl;
    SolveTowerOfHanoi(xDisk-1, xTemp, xSource, xDestination);
} //

int main() {
    int lDiskCount;
    cout << "number of disks: ";
    cin >> lDiskCount;
    cout << endl;
    if (cin.fail()) return -1; // error code

    for(int i=lDiskCount; i>0; --i) _Stack0.push(i);

    SolveTowerOfHanoi(lDiskCount, &_Stack0, &_Stack1, &_Stack2);

    cin.get();
    return 0;
} //

example output:
number of disks: 5

moving disk 1 from 0 to 2
stack0: 5 4 3 2
stack1:
stack2: 1

moving disk 2 from 0 to 1
stack0: 5 4 3
stack1: 2
stack2: 1

moving disk 1 from 2 to 1
stack0: 5 4 3
stack1: 2 1
stack2:

moving disk 3 from 0 to 2
stack0: 5 4
stack1: 2 1
stack2: 3

moving disk 1 from 1 to 0
stack0: 5 4 1
stack1: 2
stack2: 3

moving disk 2 from 1 to 2
stack0: 5 4 1
stack1:
stack2: 3 2

moving disk 1 from 0 to 2
stack0: 5 4
stack1:
stack2: 3 2 1

moving disk 4 from 0 to 1
stack0: 5
stack1: 4
stack2: 3 2 1

moving disk 1 from 2 to 1
stack0: 5
stack1: 4 1
stack2: 3 2

moving disk 2 from 2 to 0
stack0: 5 2
stack1: 4 1
stack2: 3

moving disk 1 from 1 to 0
stack0: 5 2 1
stack1: 4
stack2: 3

moving disk 3 from 2 to 1
stack0: 5 2 1
stack1: 4 3
stack2:

moving disk 1 from 0 to 2
stack0: 5 2
stack1: 4 3
stack2: 1

moving disk 2 from 0 to 1
stack0: 5
stack1: 4 3 2
stack2: 1

moving disk 1 from 2 to 1
stack0: 5
stack1: 4 3 2 1
stack2:

moving disk 5 from 0 to 2
stack0:
stack1: 4 3 2 1
stack2: 5

moving disk 1 from 1 to 0
stack0: 1
stack1: 4 3 2
stack2: 5

moving disk 2 from 1 to 2
stack0: 1
stack1: 4 3
stack2: 5 2

moving disk 1 from 0 to 2
stack0:
stack1: 4 3
stack2: 5 2 1

moving disk 3 from 1 to 0
stack0: 3
stack1: 4
stack2: 5 2 1

moving disk 1 from 2 to 1
stack0: 3
stack1: 4 1
stack2: 5 2

moving disk 2 from 2 to 0
stack0: 3 2
stack1: 4 1
stack2: 5

moving disk 1 from 1 to 0
stack0: 3 2 1
stack1: 4
stack2: 5

moving disk 4 from 1 to 2
stack0: 3 2 1
stack1:
stack2: 5 4

moving disk 1 from 0 to 2
stack0: 3 2
stack1:
stack2: 5 4 1

moving disk 2 from 0 to 1
stack0: 3
stack1: 2
stack2: 5 4 1

moving disk 1 from 2 to 1
stack0: 3
stack1: 2 1
stack2: 5 4

moving disk 3 from 0 to 2
stack0:
stack1: 2 1
stack2: 5 4 3

moving disk 1 from 1 to 0
stack0: 1
stack1: 2
stack2: 5 4 3

moving disk 2 from 1 to 2
stack0: 1
stack1:
stack2: 5 4 3 2

moving disk 1 from 0 to 2
stack0:
stack1:
stack2: 5 4 3 2 1

Advertisements

About Bastian M.K. Ohta

Happiness only real when shared.

Posted on March 12, 2014, in C#, C++, Java and tagged , , , , , , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: