CoinGame.java

/*
 * Coin game.
 */

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class CoinGame {
    static class MoveInfo {
        enum Position { BEGIN, END }

        public Position move;
        public int value;

        public MoveInfo(Position m, int v) {
            move = m;
            value = v;
        }

        public String toString() {
            return String.format("MoveInfo(move=" + move.toString() + ", value=%d)", value);
        }
    }

    private Map<Deque<Integer>, MoveInfo> transpositionTable;
    {
        transpositionTable = new HashMap<Deque<Integer>, MoveInfo>();
    }

    private static Deque<Integer> singletonDeque(int coin) {
        Deque<Integer> deque = new LinkedList<Integer>();
        deque.add(coin);
        return deque;
    }

    private MoveInfo saveMove(Deque<Integer> coins, MoveInfo move) {
        transpositionTable.put(coins, move);
        return move;
    }

    /*
     * Driver for coinGame()
     */
    MoveInfo play(Deque<Integer> coins) {
        for (int coin : coins) {
            transpositionTable.put(singletonDeque(coin),
                                   new MoveInfo(MoveInfo.Position.BEGIN, coin));
        }
        return coinGame(coins, Integer.MAX_VALUE);
    }

    private MoveInfo coinGame(Deque<Integer> coins, int beta) {
        //System.out.println(coins.toString());
        if (transpositionTable.containsKey(coins)) {
            if (coins.size() > 1) {
                System.out.format("Remembered value of %s from before: %d.", coins,
                                  transpositionTable.get(coins).value);
            }
            return transpositionTable.get(coins);
        }

        int coin, value, best_value;
        MoveInfo.Position move;

        // Test first
        move = MoveInfo.Position.BEGIN;
        System.out.format("Coin list %s. ", coins);
        coin = coins.removeFirst();
        System.out.format("Try coin %d: (%n", coin);
        //System.out.format("First: %d%n", coin);
        value = coinGame(coins, Integer.MAX_VALUE).value;

        best_value = coin - value;

        coins.addFirst(coin);
        System.out.format(") value so far at %s is >= %d. ", coins, best_value);

        // "beta" pruning
        if (best_value >= beta) {
            System.out.format("Which is not better than %d%n", beta);
            return saveMove(coins, new MoveInfo(move, best_value));
        }

        // Test last
        coin = coins.removeLast();
        System.out.format("Now try coin %d: (", coin);
        value = coinGame(coins, coin - best_value).value;

        coins.addLast(coin);

        if (coin - value > best_value) {
            best_value = coin - value;
            move = MoveInfo.Position.END;
        }
        System.out.format(") Value of %s is %d.", coins, best_value);

        return saveMove(coins, new MoveInfo(move, best_value));
    }

    public static void main(String[] args) {
        System.out.println("Coin game");
        CoinGame c = new CoinGame();
        MoveInfo m = c.play(new LinkedList<Integer>(Arrays.asList(4, 3, 2, 1)));
        System.out.format("%n%s%n", m);
    }
}