import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class PegGame {

  private boolean[][] pegs = new boolean[5][5];
  private int[] children = new int[15];
  int childCount = -1;
  int pegCount=0;
  int redundancy = 1;
  String info;
  
  // these should be set back to -1 if data changes...
  private long wins=-1, leaves=-1;
  private long[] pegsLeft = { 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };
  
  
  static PegGame[] allBoardsEver = new PegGame[2<<15];
  
  
  public static void main(String[] args) {
    PegGame root = getRoot();
    root.createAllChildren();
    int tot=0;
    for(int i=0; i<allBoardsEver.length; i++) {
      if (allBoardsEver[i]!=null) tot++;
    }
    System.out.println("  boards "+tot);
    for(int i=15; i>1; i--) System.out.println("  "+i+" left "+root.remainingPegCount(i));
    System.out.println("    wins "+root.winCount());
    System.out.println("   total "+root.leafCount());
  }

  public PegGame(int hash) {
    for(int i=0; i<5; i++) {
      for(int j=0; j<=i; j++) {
        if ((hash & 1) == 1) {
          pegs[i][j] = true;
          pegCount++;
        }
        hash >>=1;
      }
    }
  }
  
  public PegGame(PegGame p) {
    pegs[0][0] = p.pegs[0][0];
    pegs[1][0] = p.pegs[1][0];
    pegs[1][1] = p.pegs[1][1];
    pegs[2][0] = p.pegs[2][0];
    pegs[2][1] = p.pegs[2][1];
    pegs[2][2] = p.pegs[2][2];
    pegs[3][0] = p.pegs[3][0];
    pegs[3][1] = p.pegs[3][1];
    pegs[3][2] = p.pegs[3][2];
    pegs[3][3] = p.pegs[3][3];
    pegs[4][0] = p.pegs[4][0];
    pegs[4][1] = p.pegs[4][1];
    pegs[4][2] = p.pegs[4][2];
    pegs[4][3] = p.pegs[4][3];
    pegs[4][4] = p.pegs[4][4];
    pegCount = p.pegCount;
    info = p.info + " " + (int)(255*Math.random());
  }
  
  public static PegGame getRoot() {
    PegGame root = new PegGame(0xFFFF);
    root.pegCount = 15;
    root.children = new int[15];
    root.childCount = 0;
    root.info = "root";
    PegGame tmp;
    int hash;
    for(int i=0; i<5; i++) {
      for(int j=0; j<=i; j++) {
        tmp = new PegGame(root);
        tmp.pegs[i][j]=false;
        tmp.pegCount=14;
        tmp.info = "start "+i;
        hash = tmp.hashCode();
        if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
        else allBoardsEver[hash].redundancy++;
        root.children[root.childCount++] = hash;
      }
    }
    return root;
  }
  
  public void createAllChildren() {
    if (childCount == -1) createChildren();
    for(int i=0; i<childCount; i++) {
      if (pegCount>13) System.out.println("Making tree..."+"                              ".substring(pegCount*2)+i);
      allBoardsEver[children[i]].createAllChildren();
    }
  }
  
  public void createChildren() {
    PegGame tmp;
    int hash;
    childCount = 0;
    for(int i=0; i<5; i++) {
      for(int j=0; j<=i; j++) {
        if (pegs[i][j]) {
        
          if (i>j+1 && pegs[i-1][j] && !pegs[i-2][j]) {
            tmp = new PegGame(this);
            tmp.pegs[i  ][j]=false;
            tmp.pegs[i-1][j]=false;
            tmp.pegs[i-2][j]=true;
            tmp.pegCount--;
            hash = tmp.hashCode();
            if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
            else allBoardsEver[hash].redundancy++;
            children[childCount++] = hash;
          }
          if (i<3 && pegs[i+1][j] && !pegs[i+2][j]) {
            tmp = new PegGame(this);
            tmp.pegs[i  ][j]=false;
            tmp.pegs[i+1][j]=false;
            tmp.pegs[i+2][j]=true;
            tmp.pegCount--;
            hash = tmp.hashCode();
            if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
            else allBoardsEver[hash].redundancy++;
            children[childCount++] = hash;
          }
          
          if (j>1 && pegs[i][j-1] && !pegs[i][j-2]) {
            tmp = new PegGame(this);
            tmp.pegs[i][j  ]=false;
            tmp.pegs[i][j-1]=false;
            tmp.pegs[i][j-2]=true;
            tmp.pegCount--;
            hash = tmp.hashCode();
            if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
            else allBoardsEver[hash].redundancy++;
            children[childCount++] = hash;
          }
          if (j<3 && pegs[i][j+1] && !pegs[i][j+2] && i>j+1) {
            tmp = new PegGame(this);
            tmp.pegs[i][j  ]=false;
            tmp.pegs[i][j+1]=false;
            tmp.pegs[i][j+2]=true;
            tmp.pegCount--;
            hash = tmp.hashCode();
            if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
            else allBoardsEver[hash].redundancy++;
            children[childCount++] = hash;
          }
          
          if (i>1 && j>1 && pegs[i-1][j-1] && !pegs[i-2][j-2]) {
            tmp = new PegGame(this);
            tmp.pegs[i  ][j  ]=false;
            tmp.pegs[i-1][j-1]=false;
            tmp.pegs[i-2][j-2]=true;
            tmp.pegCount--;
            hash = tmp.hashCode();
            if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
            else allBoardsEver[hash].redundancy++;
            children[childCount++] = hash;
          }
          if (i<3 && pegs[i+1][j+1] && !pegs[i+2][j+2]) {
            tmp = new PegGame(this);
            tmp.pegs[i  ][j  ]=false;
            tmp.pegs[i+1][j+1]=false;
            tmp.pegs[i+2][j+2]=true;
            tmp.pegCount--;
            hash = tmp.hashCode();
            if (allBoardsEver[hash]==null) allBoardsEver[hash] = tmp;
            else allBoardsEver[hash].redundancy++;
            children[childCount++] = hash;
          }
          
        }
        
      }
    }
    
  }
  
  public PegGame getChild(int i) {
    return allBoardsEver[children[i]];
  }
  
  public long winCount() {
    if (wins != -1) return wins;
    if (childCount == 0) {
      if (pegCount == 1) wins = 1;
      else wins = 0;
    }
    else {
      wins = 0;
      for(int i=0; i<childCount; i++) wins += allBoardsEver[children[i]].winCount();
    }
    return wins;
  }
  
  public long remainingPegCount(int pi) {
    if (pegsLeft[pi] != -1) return (pegsLeft[pi]);
    long left;
    if (childCount == 0) {
      if (pegCount == pi) left = 1;
      else left = 0;
    }
    else {
      left = 0;
      for(int i=0; i<childCount; i++) left += allBoardsEver[children[i]].remainingPegCount(pi);
    }
    pegsLeft[pi] = left;
    return left;
  }
  
  public long leafCount() {
    if (leaves != -1) return leaves;
    if (childCount == 0) leaves = 1;
    else {
      leaves = 0;
      for(int i=0; i<childCount; i++) leaves += allBoardsEver[children[i]].leafCount();
    }
    return leaves;
  }
  
  public long leafCount(int depth) {
    if (childCount == 0 || depth == 0) return 1;
    else if (depth == 1) return childCount;
    else {
      long leaves = 0;
      for(int i=0; i<childCount; i++) leaves += allBoardsEver[children[i]].leafCount(depth-1);
      return leaves;
    }
  }
  
  public boolean equals(PegGame pg) {
    return pg instanceof PegGame && hashCode() == pg.hashCode();
  }
  
  public int hashCode() {
    // 0 <= hashCode() < 2^15
    int hash = 0;
    for(int i=0; i<5; i++) {
      for(int j=0; j<=i; j++) {
        if (pegs[i][j]) hash++;
        hash <<= 1;
      }
    }
    return hash;
  }
  
  Vector pathTo(PegGame descendent, int maxDepth) {
    Vector v=null;
    if (equals(descendent)) v = new Vector();
    else if (maxDepth <= 0) return null;
    else {
      for(int i=0; v==null && i<childCount; i++) {
        v = getChild(i).pathTo(descendent, maxDepth-1);
      }
    }
    if (v==null) return null;
    else v.addElement(this);
    return v;
  }
  
  public String toString() {
    return "P["+info+"]";
  }
  
  public void print() {
    for(int i=0; i<5; i++) {
      System.out.print("     ".substring(i));
      for(int j=0; j<=i; j++) {
        System.out.print(" "+(pegs[i][j] ? "o" : "." ));
      }
      if (i==0) System.out.println("         "+info);
      else System.out.println();
    }
  }
  
  boolean drawLines = true;
  Color pegColor = new Color(255, 0, 0);
  
  // would be nice to add customization in colors, size, etc
  public void draw(Graphics g, int w, int h) {
    int xoff = 0, yoff = 0, x=w/2, y=h/2, s=3;
    int[] xs = { x    , x+8*s, x-8*s, x     };
    int[] ys = { y-8*s, y+6*s, y+6*s, y-8*s };
    
    g.setColor(Color.yellow);
    g.fillPolygon(xs, ys, 4);
    g.setColor(Color.black);
    g.drawPolygon(xs, ys, 4);
    
    FontMetrics fm = g.getFontMetrics();
    
    String info = ""+winCount()+" wins";
    if (info.startsWith("1 ")) info = info.substring(0, info.length()-1);
    if (childCount == 0) {
      if (info.charAt(0)=='1') info = "win";
      else info = "lose";
    }
    g.setColor(Color.white);
    g.fillRect(w/2-fm.stringWidth(info)/2, y+7*s, fm.stringWidth(info), fm.getHeight());
    g.setColor(Color.blue);
    g.drawString(info, w/2-fm.stringWidth(info)/2, y+7*s + fm.getHeight()-2);
    
    info = ""+leafCount()+" paths";
    if (childCount == 0) {
      info = "end";
    }
    if (info.startsWith("1 ")) info = info.substring(0, info.length()-1);
    g.setColor(Color.white);
    g.fillRect(w/2-fm.stringWidth(info)/2, y+7*s + fm.getHeight(), fm.stringWidth(info), fm.getHeight());
    g.setColor(Color.red);
    g.drawString(info, w/2-fm.stringWidth(info)/2, y+7*s + 2*fm.getHeight()-2);
    
    g.setColor(pegColor);
    for(int i=0; i<5; i++) {
      for(int j=0; j<=i; j++) {
        x = w/2 - 2*s*j + s*i;
        y = h/2 + 2*s*i - 4*s;
        if (pegs[i][j]) {
          g.fillOval(x-2, y-2, 4, 4);
        }
        else {
          g.drawOval(x-2, y-2, 4, 4);
        }
      }
    }
    
  }
  
  public void draw(Graphics g, int w, int h, int depth) {
    if (depth == 1) draw(g, w, h);
    else {
      int leaves = (int)leafCount(depth);
      int t=0, l;
      for(int i=0; i<childCount; i++) {
        l = (int)getChild(i).leafCount(depth-1);
        if (drawLines) {
          g.setColor(Color.black);
          g.drawLine(w/2, h/depth/2, t*w/leaves + l*w/leaves/2, 3*h/depth/2);
        }
        //getChild(i).draw(g.create(t*w/leaves, h/depth, l*w/leaves, (depth-1)*h/depth),
        //
        g.translate(t*w/leaves, h/depth);
        getChild(i).draw(g, l*w/leaves, (depth-1)*h/depth, depth-1);
        g.translate(-t*w/leaves, -h/depth);
        t+=l;
      }
      draw(g, w, h/depth);
    }
  }
  
  public PegGame getPegGameAt(Point p, int w, int h, int depth) { return getPegGameAt(p.x, p.y, w, h, depth); }
  public PegGame getPegGameAt(int x, int y, int w, int h, int depth) {
    if (depth==1) return this;
    else {
      if (y < h/depth) return this;
      int leaves = (int)leafCount(depth);
      int t=0, l;
      for(int i=0; i<childCount; i++) {
        l = (int)getChild(i).leafCount(depth-1);
        if (x < (t+l)*w/leaves) return getChild(i).getPegGameAt(x - t*w/leaves, y - h/depth, l*w/leaves, (depth-1)*h/depth, depth-1);
        t+=l;
      }
    }
    return null;
  }
  

}