Meepo Challenge

MeepoChallenge.java:

import java.math.BigInteger;
import java.util.HashMap;

public class MeepoChallenge {

    public static void main(String[] args) {

        HashMap<State, BigInteger> states = new HashMap<State, BigInteger>();
        // Antalet personer
        int n = 1;
        states.put(new State(), BigInteger.ONE);

        while (true) {
            // Antalet olika sätt man kan placera n personer på enligt villkoren i
            // uppgiften, alltså t(n).
            BigInteger permutations = BigInteger.ZERO;
            for (BigInteger amounts : states.values()) {
                permutations = permutations.add(amounts);
            }
            System.out.println("n: " + n + ", t(n): " + permutations);

            HashMap<State, BigInteger> nextStates = new HashMap<State, BigInteger>();
            for (State state : states.keySet()) {
                BigInteger amount = states.get(state);
                for (State newState : state.getNextStates()) {
                    nextStates.putIfAbsent(newState, BigInteger.ZERO);
                    nextStates.put(newState, nextStates.get(newState).add(amount));
                }
            }

            states = nextStates;
            n++;
        }
    }

}

State.java:

import java.util.ArrayList;
import java.util.Arrays;

public class State {

    // cols[i] anger hur många personer som står i kolumn i.
    int[] cols;

    /**
     * Skapar ett tillstånd med endast en person som står i hörnet.
     */
    public State() {
        cols = new int[] { 1 };
    }

    /**
     * Skapar ett tillstånd som är en kopia av parent, antalet kolumner som
     * initialiseras ges av numCols.
     */
    private State(State parent, int numCols) {
        cols = new int[numCols];
        for (int i = 0; i < parent.cols.length; i++) {
            this.cols[i] = parent.cols[i];
        }
    }

    /**
     * Lägger till en person i den givna kolumnen. Returnerar det här objektet.
     */
    private State incrementCol(int col) {
        cols[col]++;
        return this;
    }

    /**
     * Returnerar en ArrayList av alla godkända tillstånd som kan skapas genom att
     * lägga till en person någonstans i det här tillståndet.
     */
    public ArrayList<State> getNextStates() {
        ArrayList<State> nextStates = new ArrayList<State>();
        nextStates.add(new State(this, this.cols.length).incrementCol(0));
        for (int i = 1; i < cols.length; i++) {
            if (cols[i] < cols[i - 1]) {
                nextStates.add(new State(this, this.cols.length).incrementCol(i));
            }
        }
        nextStates.add(new State(this, this.cols.length + 1).incrementCol(this.cols.length));
        return nextStates;
    }

    @Override
    public int hashCode() {
        int hash = 0;
        for (int i = 0; i < cols.length; i++) {
            hash += i * 35731 * cols[i];
        }
        return hash;
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof State) {
            return Arrays.equals(((State) obj).cols, this.cols);
        }
        return false;
    }

}