# Algorithm Problem: Houses

This is an interesting maximization problem that can be solved efficiently, in O(n) time, using dynamic programming.

You’re given a list of houses, each with a money value assigned to it. The problem is to choose houses from the list so as to maximize the total money from them, but no two houses chosen can be adjacent.

I originally created a binary tree from the input data and recursively searched every possible combination of houses, but for a large number of houses the number of combinations exploded and my program never returned.

```  1 import java.util.ArrayList;
2 import java.util.Arrays;
3 import java.util.List;
4 import java.util.Random;
5
6 /**
7  * The problem: given a list of houses, each house with a certain money value associated with it, write an algorithm
8  * that computes the maximum money that can be obtained by picking houses such that no two chosen houses are adjacent
9  * to one another.
10  * <p/>
11  * Example input: {(H1, 2), (H2, 1), (H3, 2), (H4, 3), (H5, 2)}
12  * <p/>
13  * Expected output: {6, (H1, H3, H5)}
14  * <p/>
15  * The solution: use dynamic programming.  Realize that the solution can be expressed by the following relationship:
16  * <p/>
17  * Solution for 1 house = S(1) = money value of house 1 = H1
18  * Solution for 2 houses = S(2) = max(H2, S(1))
19  * S(3) = max(H3 + S(1), S(2))
20  * ...
21  * S(n) = max(Hn + S(n - 2), S(n - 1))
22  *
23  * @author Chip Killmar
24  */
25 public class Houses {
26     public static void main(String[] args) throws Exception {
27         // Create some houses with random money values.
28         Random random = new Random();
29         House[] houses = new House;
30         for (int i = 0; i < houses.length; ++i) {
31             House house = new House(String.valueOf(i), random.nextInt(4));
32             houses[i] = house;
33         }
34         System.out.println("Input=" + Arrays.toString(houses));
35
36         System.out.println("Output=" + chooseHouses(Arrays.asList(houses)));
37     }
38
39     /**
40      * An O(n) algorithm that chooses the houses such that the total money value of the houses is maximized, with the
41      * constraint that no two houses chosen can be adjacent to each other.
42      *
43      * @param houses An array of input houses.
44      * @return The result as a 2-tuple of {Total Money, List of Houses}.
45      */
46     private static Tuple2<Integer, List<House>> chooseHouses(List<House> houses) {
47         List<Tuple2<Integer, List<House>>> results = new ArrayList<Tuple2<Integer, List<House>>>(houses.size());
48
49         for (int i = 0; i < houses.size(); ++i) {
50             if (i == 0) {
51                 int money = houses.get(0).getMoney();
52
53                 List<House> housesResult = new ArrayList<House>();
55
56                 Tuple2<Integer, List<House>> result = new Tuple2<Integer, List<House>>(money, housesResult);
58             } else if (i == 1) {
59                 int money = houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1).getMoney() : houses.get(0).getMoney();
60
61                 List<House> housesResult = new ArrayList<House>();
62                 housesResult.add(houses.get(1).getMoney() > houses.get(0).getMoney() ? houses.get(1) : houses.get(0));
63
64                 Tuple2<Integer, List<House>> result = new Tuple2<Integer, List<House>>(money, housesResult);
66             } else {
67                 Tuple2<Integer, List<House>> previousPreviousResult = results.get(i - 2);
68                 Tuple2<Integer, List<House>> previousResult = results.get(i - 1);
69
70                 int previousMoney = previousResult.getFirst();
71                 int currentMoney = previousPreviousResult.getFirst() + houses.get(i).getMoney();
72
73                 Tuple2<Integer, List<House>> result;
74                 if (currentMoney > previousMoney) {
75                     List<House> housesResult = new ArrayList<House>(previousPreviousResult.getSecond());
77                     result = new Tuple2<Integer, List<House>>(currentMoney, housesResult);
78                 } else {
79                     result = new Tuple2<Integer, List<House>>(previousMoney, previousResult.getSecond());
80                 }
82             }
83         }
84
85         return results.get(results.size() - 1);
86     }
87
88     private static class House {
89         private String name;
90         private int money;
91
92         public House(String name, int money) {
93             this.name = name;
94             this.money = money;
95         }
96
97         public String getName() {
98             return name;
99         }
100
101         public int getMoney() {
102             return money;
103         }
104
105         @Override
106         public String toString() {
107             final StringBuilder sb = new StringBuilder();
108             sb.append("House");
109             sb.append("{name='").append(name).append('\'');
110             sb.append(", value=").append(money);
111             sb.append('}');
112             return sb.toString();
113         }
114     }
115
116     private static class Tuple2<T, U> {
117         private T first;
118         private U second;
119
120         public Tuple2(T first, U second) {
121             if (first == null) {
122                 throw new NullPointerException("first");
123             }
124             if (second == null) {
125                 throw new NullPointerException("second");
126             }
127
128             this.first = first;
129             this.second = second;
130         }
131
132         public T getFirst() {
133             return first;
134         }
135
136         public U getSecond() {
137             return second;
138         }
139
140         @Override
141         public String toString() {
142             final StringBuilder sb = new StringBuilder();
143             sb.append("Tuple2");
144             sb.append("{first=").append(first);
145             sb.append(", second=").append(second);
146             sb.append('}');
147             return sb.toString();
148         }
149     }
150 }```