import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

/**
 * The problem: given a list of houses, each house with a certain money value associated with it, write an algorithm
 * that computes the maximum money that can be obtained by picking houses such that no two chosen houses are adjacent
 * to one another.
 * <p/>
 * Example input: {(H1, 2), (H2, 1), (H3, 2), (H4, 3), (H5, 2)}
 * <p/>
 * Expected output: {6, (H1, H3, H5)}
 * <p/>
 * The solution: use dynamic programming.  Realize that the solution can be expressed by the following relationship:
 * <p/>
 * Solution for 1 house = S(1) = money value of house 1 = H1
 * Solution for 2 houses = S(2) = max(H2, S(1))
 * S(3) = max(H3 + S(1), S(2))
 * ...
 * S(n) = max(Hn + S(n - 2), S(n - 1))
 *
 * @author Chip Killmar
 */
public class Houses {
    public static void main(String[] args) throws Exception {
        // Create some houses with random money values.
        Random random = new Random();
        House[] houses = new House[5];
        for (int i = 0; i < houses.length; ++i) {
            House house = new House(String.valueOf(i), random.nextInt(4));
            houses[i] = house;
        }
        System.out.println("Input=" + Arrays.toString(houses));

        System.out.println("Output=" + chooseHouses(Arrays.asList(houses)));
    }

    /**
     * An O(n) algorithm that chooses the houses such that the total money value of the houses is maximized, with the
     * constraint that no two houses chosen can be adjacent to each other.
     *
     * @param houses An array of input houses.
     * @return The result as a 2-tuple of {Total Money, List of Houses}.
     */
    private static Tuple2<Integer, List<House>> chooseHouses(List<House> houses) {
        List<Tuple2<Integer, List<House>>> results = new ArrayList<Tuple2<Integer, List<House>>>(houses.size());

        for (int i = 0; i < houses.size(); ++i) {
            if (i == 0) {
                int money = houses.get(0).getMoney();

                List<House> housesResult = new ArrayList<House>();
                housesResult.add(houses.get(0));

                Tuple2<Integer, List<House>> result = new Tuple2<Integer, List<House>>(money, housesResult);
                results.add(result);
            } else if (i == 1) {
                int money = houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1).getMoney() : houses.get(0).getMoney();

                List<House> housesResult = new ArrayList<House>();
                housesResult.add(houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1) : houses.get(0));

                Tuple2<Integer, List<House>> result = new Tuple2<Integer, List<House>>(money, housesResult);
                results.add(result);
            } else {
                Tuple2<Integer, List<House>> previousPreviousResult = results.get(i - 2);
                Tuple2<Integer, List<House>> previousResult = results.get(i - 1);

                int previousMoney = previousResult.getFirst();
                int currentMoney = previousPreviousResult.getFirst() + houses.get(i).getMoney();

                Tuple2<Integer, List<House>> result;
                if (currentMoney > previousMoney) {
                    List<House> housesResult = new ArrayList<House>(previousPreviousResult.getSecond());
                    housesResult.add(houses.get(i));
                    result = new Tuple2<Integer, List<House>>(currentMoney, housesResult);
                } else {
                    result = new Tuple2<Integer, List<House>>(previousMoney, previousResult.getSecond());
                }
                results.add(result);
            }
        }

        return results.get(results.size() - 1);
    }

    private static class House {
        private String name;
        private int money;

        public House(String name, int money) {
            this.name = name;
            this.money = money;
        }

        public String getName() {
            return name;
        }

        public int getMoney() {
            return money;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("House");
            sb.append("{name='").append(name).append('\'');
            sb.append(", value=").append(money);
            sb.append('}');
            return sb.toString();
        }
    }

    private static class Tuple2<T, U> {
        private T first;
        private U second;

        public Tuple2(T first, U second) {
            if (first == null) {
                throw new NullPointerException("first");
            }
            if (second == null) {
                throw new NullPointerException("second");
            }

            this.first = first;
            this.second = second;
        }

        public T getFirst() {
            return first;
        }

        public U getSecond() {
            return second;
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder();
            sb.append("Tuple2");
            sb.append("{first=").append(first);
            sb.append(", second=").append(second);
            sb.append('}');
            return sb.toString();
        }
    }
}