/**
 * Top-down and bottom-up solutions to the world series puzzle.
 *   @author Dave Reed
 *   @version 4/1/14
 */
public class SeriesPuzzle {
    public final static double FINAL_WORTH = 1000.0;
    public final static int SERIES_LENGTH = 7;
    public final static int GAMES_TO_WIN = (SERIES_LENGTH+1)/2;
    
    /**
     * Solves the WorldSeries puzzle (using top-down recursion).
     * @param numWins the number of wins for the player's team
     * @param numLosses the number of losses for the player's team
     * @return the winnings the player must have at this point
     */
    public static double winningsTopDown(int numWins, int numLosses) {
        if (numWins == GAMES_TO_WIN) {
            return FINAL_WORTH;
        }
        else if (numLosses == GAMES_TO_WIN) {
            return -FINAL_WORTH;
        }
        else {
            return (winningsTopDown(numWins+1, numLosses) +
                    winningsTopDown(numWins, numLosses+1))/2;
        }
    }
    
    /**
     * Solves the WorldSeries puzzle (using bottom-up dynamic programming).
     * @param numWins the number of wins for the player's team
     * @param numLosses the number of losses for the player's team
     * @return the winnings the player must have at this point
     */
    public static double winningsBottomUp(int numWins, int numLosses) {
        double winGrid[][] = new double[GAMES_TO_WIN+1][GAMES_TO_WIN+1];
        for (int w = GAMES_TO_WIN; w >= numWins; w--) {
            for (int l = GAMES_TO_WIN; l >= numLosses; l--) {
                if (w == GAMES_TO_WIN) {
                    winGrid[w][l] = FINAL_WORTH;
                }
                else if (l == GAMES_TO_WIN) {
                    winGrid[w][l] = -FINAL_WORTH;
                }
                else {
                    winGrid[w][l] = (winGrid[w+1][l]+winGrid[w][l+1])/2;
                }
            }
        }
        return winGrid[numWins][numLosses];
    }
     
    public static void main(String[] args) {
        System.out.println(SeriesPuzzle.winningsTopDown(1, 0));
        System.out.println(SeriesPuzzle.winningsBottomUp(1, 0));
    }
}