//
// The Towers Of Hanoi
// C++
// Copyright (C) 1998 Amit Singh. All Rights Reserved.
// http://hanoi.kernelthread.com
//
// Tested under GNU C++ 2.8.1
//

#include <iostream.h>
#include <stdlib.h>
#include <limits.h>

#define STYPE	int

#define	EMPTY		-2
#define	FULL		-1
#define	PUSH_OK		1
#define	CAPACITY	32767

class Stack {
  int top;
  STYPE element [CAPACITY];
public:
  Stack ();
  ~Stack ();
  int num (void);
  int push (STYPE new_elem);
  STYPE pop (void);
  STYPE snoop (void);
};

Stack::Stack (void)
{
  top = -1;
  for (int i=0; i<CAPACITY; i++)
    element[i] = 0;
}

Stack::~Stack (void)
{
  // nothing
}

int Stack::num(void)
{
  return (top + 1);
}

STYPE Stack::pop (void)
{
  STYPE x;
  if (top >= 0) {
    x = element[top];
    element[top] = 0;
    top--;
    return x;
  } else
    return EMPTY;
}

STYPE Stack::snoop(void)
{
  if (top >= 0)
    return element[top];
  else
    return EMPTY;
}

int Stack::push(STYPE new_elem)
{
  if (top < CAPACITY - 1) {
    top++;
    element[top] = new_elem;
    return PUSH_OK;
  } else
    return FULL;
}

int
main(int argc, char **argv)
{
  STYPE N, _N, _P, _T, _F, _R;

  if (argc != 2) {
    cerr << "usage: " << argv[0] << " N\n";
    exit(1);
  }

  N = (STYPE)strtol(argv[1], (char **)NULL, 10);

  /* a bit of error checking, LONG_XXX should be there in limits.h */
  if (N == LONG_MIN || N == LONG_MAX || N <= 0) {
    cerr << "illegal value for number of disks\n";
    exit(2);
  }

  Stack s;
  s.push(N);
  s.push(1);
  s.push(3);
  s.push(0);

  while (s.num() != 0) {
    _P = s.pop();
    _T = s.pop();
    _F = s.pop();
    _N = s.pop();
    _R = 6 - _F - _T;
    if (_P == 0) {
      if (_N == 1)
        cout << "move " << _F << " --> " << _T << "\n";
      else {
        s.push(_N);
        s.push(_F);
        s.push(_T);
        s.push(1);
        s.push(_N-1);
        s.push(_F);
        s.push(_R);
        s.push(0);
      } 
    } else {
      cout << "move " << _F << " --> " << _T << "\n";
      s.push(_N-1);
      s.push(_R);
      s.push(_T);
      s.push(0);
    }
  }
}