#include <iostream>
#include <vector>

using namespace std;
typedef unsigned int uint32;
typedef int int32;

typedef uint32 Stack;
typedef uint32 Disc;

Stack next_stack( Stack curr_stack )
{
  return ( curr_stack + 1 ) % 3;
}

int32 main( void )
{
  cout << "Calculating tower of hanoi moves" << endl;
  cout << "Enter the number of discs: ";
  uint32 num_discs = 0; cin >> num_discs;

  /**
   * Set up the stacks, with discs loaded onto the first one.
   */
  vector< vector<Disc> > stacks;
  for ( Stack stack_id = 0; stack_id < 3; stack_id++ ) {
    stacks.push_back(
      vector<Disc>( 1, num_discs+1 ) // sentinel to avoid empty-stack logic
    );
  }
  Stack curr_stack = 0;
  for ( Disc disc = num_discs; disc > 0; disc-- ) {
    stacks[curr_stack].push_back( disc );
  }

  uint32 num_moves = 0;
  while ( true ) {

    /**
     * Smallest disc always moved one over.
     */
    Disc disc1 = stacks[curr_stack].back();
    stacks[curr_stack].pop_back();
    curr_stack = next_stack( curr_stack );
    stacks[curr_stack].push_back( disc1 );
    num_moves++;

    /**
     * Remaining move is forced.
     */
    Stack from_stack = next_stack( curr_stack );
    Stack to_stack = next_stack( from_stack );
    if ( stacks[from_stack].back() > stacks[to_stack].back() ) {
      Stack temp_stack = from_stack;
      from_stack = to_stack;
      to_stack = temp_stack;
    }
    Disc disc2 = stacks[from_stack].back();
    stacks[from_stack].pop_back();
    if ( stacks[from_stack].empty() ) { // we're done
      break;
    }
    stacks[to_stack].push_back( disc2 );
    num_moves++;
  }

  cout << "Total moves:" << num_moves << endl;

  return 0;
}