import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stack;

public class Hanoi {
    /*
    Táknar eina ákveðna uppsetningu á Hanoi þrautinni.
    */

    private Stack<Integer> left;
    private Stack<Integer> middle;
    private Stack<Integer> right;
    private int n;
    private int skref = -1; //verður 0 fyrir upphafsprentið sem við teljum ekki með sem skref.

    public Hanoi(int n) {
        /*
        Upphafsstillir þrautina með n skífum.
         */
        this.n = n;
        this.left = new Stack<>();
        this.middle = new Stack<>();
        this.right = new Stack<>();

        for (int i = n; 0 < i; i--) {
            this.left.push(i);
        }
        this.displayState();
    }

    /* samkvæmt Wikipedia er stysta ítrunarleiðin A-C, A-B, B-C. Lausnin mín ætti að vera almenn og virka fyrir
       hvaða n sem er og ætti ekki að skipta máli frá hvaða stack við byrjum */
    public void solve() {
      int i = 1;

      // fyrsta umferð, gerum löglega move-ið frá A-C, A-B, B-C:
      if (this.left.size() > this.right.size()) {this.left.pop(); this.right.push(i);}
      if (this.right.size() > this.left.size()) {this.right.pop(); this.left.push(i);}
      this.displayState();
      // ef vinstri og þriðji eru núll:
      if (this.middle.size() > 0) {this.middle.pop(); this.left.push(i);}
      // ef ekki:
      else {this.left.pop(); this.middle.push(i+1);}
      this.displayState();
      //B-C:
      if (this.right.size() > this.middle.size()) {this.right.push(this.middle.peek()); this.middle.pop();}
      else {this.middle.push(this.right.peek()); this.right.pop();}
      this.displayState();

      // allar aðrar umferðir:
      while (true) {
        // löglega move-ið frá A-C:
        if (this.left.size() > 0 && this.right.size() > 0) { // annars virkar peek ekki
          if (this.left.peek() < this.right.peek()) {this.right.push(this.left.peek()); this.left.pop();}
          else {this.left.push(this.right.peek()); this.right.pop();}
        } else {
          if (this.left.size() == 0 && this.right.size() == 0) break; // ef 0 á tveimur stöðum er þetta búið!
          else if (this.left.size() == 0) {this.left.push(this.right.peek()); this.right.pop();}
          else {this.right.push(this.left.peek()); this.left.pop();}
        }
        this.displayState();

        // löglega move-ið frá A-B:
        if (this.left.size() > 0 && this.middle.size() > 0) { // annars virkar peek ekki
          if (this.left.peek() < this.middle.peek()) {this.middle.push(this.left.peek()); this.left.pop();}
          else {this.left.push(this.middle.peek()); this.middle.pop();}
        } else {
          if (this.left.size() == 0 && this.middle.size() == 0) break; // ef 0 á tveimur stöðum er þetta búið!
          else if (this.left.size() == 0) {this.left.push(this.middle.peek()); this.middle.pop();}
          else {this.middle.push(this.left.peek()); this.left.pop();}
        }
        this.displayState();

        // löglega move-ið frá B-C:
        if (this.middle.size() > 0 && this.right.size() > 0) { // annars virkar peek ekki
          if (this.middle.peek() < this.right.peek()) {
            this.right.push(this.middle.peek()); this.middle.pop();
          } else {
            this.middle.push(this.right.peek()); this.right.pop();
          }
        } else {
          if (this.right.size() == 0 && this.middle.size() == 0) break; // ef 0 á tveimur stöðum er þetta búið!
          else if (this.middle.size() == 0) {this.middle.push(this.right.peek()); this.right.pop();}
          else {this.right.push(this.middle.peek()); this.middle.pop();}
        }
        this.displayState();
      }
    }

    private void displayState() {
        StdOut.println("Vinstri : " +  this.left.toString());
        StdOut.println("Miðja   : " +  this.middle.toString());
        StdOut.println("Hægri   : " + this.right.toString());
        StdOut.println("#####################");
        skref++;
    }

    public static void main(String[] args) {
        Hanoi h = new Hanoi(3);
        h.solve();
        System.out.println("Skrefafjöldi: " + h.skref);
    }

}