fsteeg.com | notes | tags

∞ /notes/complexity | 2006-11-10 | algorithms

Complexity

After having failed on it in the actual match miserably, here are three solutions, each with improved runtime behaviour: (Problem: http://www.topcoder.com/stat?c=problem_statement&pm=6680&rd=10005&rm=250175&cr=10496944).
// simple recursive solution
public class RGBStreet {
private String[] houses;
public int estimateCost(String[] houses) {
this.houses = houses;
int rec = rec(0, -1);
return rec;
}
int rec(int index, int last) {
if (index == houses.length) {
return 0;
}
int min = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
if (last != i) {
min = Math.min(min, rec(index + 1, i) + cost(index, i));
}
}
return min;
}
private int cost(int index, int i) {
return Integer.parseInt(houses[index].split(" ")[i]);
}
}
// memoized recursive solution
public class RGBStreet {
private String[] houses;
// memoization table
int[][] best;
public int estimateCost(String[] houses) {
this.houses = houses;
// initialize the memoization table
best = new int[3][houses.length];
for (int i = 0; i < best.length; i++) {
Arrays.fill(best[i], Integer.MAX_VALUE);
}
int rec = rec(0, -1);
return rec;
}
int rec(int index, int last) {
// we are done:
if (index == houses.length) {
return 0;
}
// we found an optimal solution for painting the current house, given
// the previous color before:
if (last != -1 && best[last][index] < Integer.MAX_VALUE)
return best[last][index];
// search the best solution for every allowed color for the rest:
int min = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
if (last != i) {
min = Math.min(min, rec(index + 1, i) + cost(index, i));
}
}
// memoize the solution found:
if (last != -1)
best[last][index] = min;
return min;
}
private int cost(int index, int i) {
return Integer.parseInt(houses[index].split(" ")[i]);
}
}
// dynamic programming solution
public class RGBStreet {
public int estimateCost(String[] houses) {
int[][] matrix = new int[3][houses.length];
for (int i = 0; i < matrix.length; i++) {
Arrays.fill(matrix[i], Integer.MAX_VALUE);
matrix[i][0] = Integer.parseInt(houses[0].split(" ")[i]);
}
for (int i = 1; i < houses.length; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (k != j) {
int cost = Integer.parseInt(houses[i].split(" ")[k]);
int recentValue = matrix[k][i];
int newValue = matrix[j][i - 1] + cost;
matrix[k][i] = Math.min(recentValue, newValue);
}
}
}
}
return Math.min(Math.min(matrix[0][houses.length - 1],
matrix[1][houses.length - 1]), matrix[2][houses.length - 1]);
}
}