// CS100M  Spring 2001   Sample Solutions to P7

// instances of the FreeCell game
// note: multiple instances are allowed
public class FreeCell {
    // game has three "arenas": free cells, home cells, columns, in that order.
        final static int FREE = 0;
        final static int HOME = 1;
        final static int COL = 2;
    // name of each arena and one-letter abbrevation of each arena
        final static String[] NAMES = { "Free cell", "Home cell", "Column"};
        final static String[] ABBREV = { "f", "h", "c" } ;
    // create the arenas and collect together into one array
        Pile[] free = new Pile[4];
        Pile[] home = new Pile[4];
        Pile[] column = new Pile[8];
        Pile[][] pile = new Pile[][] { free, home, column };

    // return 2-character bottom card for non-empty pile $p$ \ plus
    // return $"[]"$ for empty pile $p$                      / padding space
    private String displayCells(Pile[] p) {
        String s = "";
        for (int i = 0; i<p.length; i++)
            s += p[i].count() == 0 ? "[]  " : p[i].bot(0).toString() + "  ";
        return s;
    }

    // return $s$ with enough trailing spaces to be at least as long as $len$
    private String pad(String s, String len) {
       while (s.length() < len.length()) s += " ";
       return s;
    }

    // display game state: all the arenas
    public void display() {
        String sep = "    ";
        String s = NAMES[FREE] + "s";
        String t = pad(displayCells(free), s);
        System.out.println(pad(s,t) + sep + NAMES[HOME] + "s");
        System.out.println(t + sep + displayCells(home));
        System.out.println();
        System.out.println(NAMES[COL] + "s");
        int depth = 0;
        for (boolean go = true; go; depth++) {
            go = false;
            String u = "  ";
            for (int i = 0; i<column.length; i++)
                if (column[i].count() > depth) {
                    u += column[i].top(depth) + "  ";
                    go = true;
                } else
                    u += depth == 0 ? "[]  " : "    ";
            System.out.println(u);
        }
    }

    // search for empty pile $s$ or for card $s$ at the bottom of a pile.
    // return ${ j, i }$ if $i$-th pile in arena $j$ is a match;
    // return $null$ otherwise
    public int[] find(String s) {
        for (int j = 0; j<pile.length; j++)
            for (int i = 0; i<pile[j].length; i++) 
                if (pile[j][i].count() == 0) {
                    if (s.equals(ABBREV[j])) return new int[] { j, i };
                } else if (pile[j][i].bot(0).toString().equalsIgnoreCase(s))
                    return new int[] { j, i };
        return null;
    }

    // try to perform the move $src dst$; return an error message
    // if the move is not legal, $""$ if the move is legal.
    // rules:
    // free cells can hold at most 1 card each.
    // home cells must build the same suit up in value from ace.
    // a new card atop an old card on a column must have a different
    // color and value one less.
    public String move(String src, String dst) {
        String err = "";
        int[] source = find(src);
        Pile from = null;
        if (source == null) 
            err += "  cannot find/reach card or empty location " + src + "\n";
        else if (source[0] == HOME) 
            err += "  cannot remove cards from home cell\n";
        else {
            from = pile[source[0]][source[1]];
            if (from.count() == 0) 
                err += "  cannot remove cards from an empty " 
                       + NAMES[source[0]] + "\n";
        }
        int[] destination = find(dst);
        Pile to = null;
        if (destination == null)
            err += "  cannot find/reach card or empty location " + dst + "\n";
        else if (from != null && from.count() > 0) {
            to = pile[destination[0]][destination[1]];
            if (to.count() == 0) {
                if (destination[0] == HOME && from.bot(0).value() != Card.ACE)
                    err += "  first card on home cell must be an Ace\n";
            } else if (destination[0] == HOME) {
                if (from.bot(0).suit() != to.bot(0).suit())
                    err += "  suit does not match home cell suit\n";
                if (from.bot(0).value() != 1+to.bot(0).value())
                    err += "  value is not one more than card in home cell\n";
            } else if (destination[0] == COL) {
                if (from.bot(0).isred() == to.bot(0).isred())
                    err += "  colors are not different\n";
                if (1+from.bot(0).value() != to.bot(0).value())
                    err += "  value is not one less than card in column\n";
            } else // destination is non-empty free cell
                    err += "  free cells can hold at most 1 card each\n";
        }
        if (err.length() > 0) 
            return "illegal move:\n" + err;
        from.deal(to);
        return "OK";
    }

    // return "has the game been won?" (home cells hold all 52 cards?)
    public boolean win() {
        int count = 0;
        for (int i = 0; i<home.length; i++) count += home[i].count();
        return count == 52;
    }
    
    // create a new instance of the game
    public FreeCell() {
        // instantiate each pile
            for (int j = 0; j<pile.length; j++)
                for (int i = 0; i<pile[j].length; i++)
                    pile[j][i] = new Pile(false);
        // get a shuffled deck of cards
            Pile deck = new Pile(true);
        // deal cards to columns, round-robin
            for (int i = 0; deck.count()>0; i++)
                deck.deal(column[i % column.length]);
    }

    // play the game until the user wins or quits;
    // read moves from $in$
    public void play(TokenReader in) {
        for (boolean go = true; go && !win(); ) {
            display();
            System.out.print("What is your move? ");
            String src = in.readString().toLowerCase();
            if (src.equals("quit") || src.equals("stop"))
                go = false;
            else if (src.equals("?") || src.equals("help")) {
                System.out.println ( "to quit: $quit$\n"
                                   + "to get help: $help$ or $?$\n"
                                   + "to move card $a$ atop card $b$: $a b$");
                for (int i = 0; i<pile.length; i++)
                    System.out.println("    to specify any empty " 
                                       + NAMES[i] + ": $" + ABBREV[i] + "$");
            } else {
                String dst = in.readString().toLowerCase();
                System.out.println(move(src,dst));
            }
            System.out.println("\n");
        }
        System.out.println(win() ? "Congratulations, you've won!"
                                 : "Sorry, you did not win.");
    }

    // create and play an instance of the game
    public static void main(String args[]) {
        new FreeCell().play(new TokenReader(System.in));
    }
}

// standard Poker cards -- no jokers.  each card is displayed as a 2-character
// string, value followed by suit-and-color:
// value: A=Ace, 2, 3, 4, 5, 6, 7, 8, 9, T=10, J=Jack, Q=Queen, K=King
// suit, color: C=black clubs, d=red diamonds, h=red hearts, S=black spades
// cards are tamper-resistant: the color, value, and suits cannot be changed.
class Card {
    public final static int CLUBS   = 0;
    public final static int DIAMONDS= 1;
    public final static int HEARTS  = 2;
    public final static int SPADES  = 3;
    public final static String suitnames = "CdhS";

    public final static int ACE    = 1;
    public final static int JACK   = 11;
    public final static int QUEEN  = 12;
    public final static int KING   = 13;
    // need $?$ below since values start at 1, but Java indices start at 0
        public final static String valuenames = "?A23456789TJQK"; 

    private int mysuit;   // suit: CLUBS, DIAMONDS, HEARTS, or SPADES
    private int myvalue;  // value: ACE..KING

    public int suit() { return mysuit; }    
    public int value() { return myvalue; }    
    public boolean isred() { return mysuit == DIAMONDS || mysuit == HEARTS; }
    public boolean isblack() { return !isred(); }

    // constructor
    public Card(int suit, int value) {
        mysuit = suit;
        myvalue = value;
    }

    // 2-letter representation
    public String toString() {
        return valuenames.charAt(myvalue) + "" + suitnames.charAt(mysuit);
    }
}

// a pile of 0..52 cards, where only the bottom-most card can be moved,
// but all the cards are accessible.  except for creating a new deck of cards,
// piles conserve cards: it is impossible to destroy or duplicate cards
// within a pile.
class Pile {                             // $cards[0..size-1]$ holds cards:
    private int size = 0;                // position $0$ is the top
    private Card[] cards = new Card[52]; // position $size-1$ is the bottom

    // constructor: return full, scrambled, 52-card deck or empty pile
    // *** modified to make better use of constants in class $CARD$ ***
    public Pile(boolean fulldeck) {
        if (fulldeck)
            for (int value = Card.ACE; value <= Card.KING; value++)
                for (int suit = Card.CLUB; suit <= Card.SPADE; suit++) {
                    cards[size] = new Card(suit, value); size++;
                }
        scramble(); // <-- added because $scramble$ is now private
    }

    // number of cards
    public int count() {
        return size;
    }


    // return $i$-th card from the top of non-empty Pile \ <-- new method, for
    // (0=top; client must check bounds)				 /     FreeCell.display
    public Card top(int i) {
        return cards[i];
    }

    // return $i$-th card from the bottom of non-empty Pile
    // (0=bottom; client must check bounds)
    public Card bot(int i) {
        return cards[size-1-i];
    }

    // scramble order of cards by swapping each cards[i] with a random cards[j]
    private void scramble() {
        for (int i=size-1; i>0; i--) {
            int j = (int) (Math.random() * (i+1));
            // swap cards at positions i, j
                Card c = cards[i]; 
                cards[i] = cards[j]; 
                cards[j] = c;
        }
    }

    // deal 1 card from bottom of self onto bottom of $destination$
    public void deal(Pile destination) {
        size--;
        destination.cards[destination.size] = cards[size];
        destination.size++;
    }
}
/*
notes on class $Pile$ above:
+ $size$ is maintained by all the methods: constructor $Pile$ and
  method $move$ adjust size appropriately to reflect the number of
  cards in each pile ($size++;$, $size--;$, $destination.size++;$).
+ $scramble$ has been made private: if it were public, then it would
  be possible to (eventually) access any card in the pile: simply
  repeatedly scramble until the desired card appears on the bottom.
  probability theory says it will eventually happen.
+ since only method $deal$ can modify a pile, 
  + to move a card from or to a pile, 
    it must be moved from or to another pile,
    so all the "arenas" in free cell must be $Pile$s.
  + furthermore, this prevents others from:
    + re-arranging cards within a pile
    + putting the same card into multiple piles
    + losing a card (e.g. drop behind the couch)
    
notes on how to prevent even more "cheating":
+ the code above allows others to create any number of decks of
  cards, so it is still possible for class $FreeCell$ to cheat
  by using cards from extra decks.
+ we could eliminate that problem if class $Pile$ were to supply
  only one deck of cards and not allow any others to be created:
  + include a static variable for the unique deck:
       $final static Pile DECK = new Pile(true);$
  + make the old constructor $private$, so no one else can make a full deck.
  + include a nullary public constructor that calls the private constructor: 
       $public Pile() { this(false); }$
    here, $this$ is treated as a method (like how $super$ is used), 
    which java understands to mean "a constructor for the current class"
    (as opposed to "a constructor for the super-class").
    
    this is good style: if we modify the body of the private 
    constructor, we can probably leave the public constructor unchanged.
+ note that this means only one card game can be run, since multiple instances
  of the game would have to share the same deck of cards.
*/