CareerCup

edited: changed recursion as Fernandoz pointed out
Analysis:
--

the cost of a single column depends on which color is on which row.
Which color can be painted on which row depends on the previous
column. No greedy choice is possible if optimal solution is wanted.

Solution (assuming no negative cost)
--
a) brute force, trying all potential combinations which are
roughly 3!^n = 6^n

b) look at all potential combinations per columns as adjacent nodes
from all the reachable combinations of the previous column. Thus build
a graph and find the shortest path. This can be done using Dijkstra's
shortest path algorithm. That's a bit a heavy tool for this problem.

There is a better alternative because in the DAC there are only edges from
Nodes in Column i to Column i + 1.

Every column can have 6 potential house-color combinations RGB, RBG, BGR, ...)
potentially each of those combinations can be reached by various paths, but
we are only interested in the cheapest path to a given combination. So, we
could just calculate the cost to go from each combination in column i to
each allowed combination in column i+1 and if multiple ways are allowed, we
pick the cheapest.

as recursion:

DP(col, comb) = Min(DP(col-1, prev_comb) + cost(comb))
                               for each prev_comb that leads to comb,
                               cost(comb) is the cost for the combination comb
                               if col = 0: DP(col, comb) = 0

    The minimal cost then is: Min(DP(N, last_comb)) for each of the 6 color combinations

complete solution (iterative DP solution), time complexity O(n*8*8*3*6) = O(n), space: O(n)

public class PaintHouses {
    static final String[] COLOR_COMBINATION_STR = new String[]{"RGB", "RBG", "GBR", "GRB", "BGR", "BRG" };

    static public void printMinPaint(int n) {
        int[][] cost = new int[n][COLOR_COMBINATION_STR.length]; // can optimize 1st dimension to 2
        int[][] backTrack = new int[n][COLOR_COMBINATION_STR.length]; // previous combination

        // initialize
        for (int j = 0; j < COLOR_COMBINATION_STR.length; j++) {
            cost[0][j] = getCost(0, j);
        }
        for(int i = 1; i < n; i++) {
            for (int j = 0; j < COLOR_COMBINATION_STR.length; j++) {
                cost[i][j] = Integer.MAX_VALUE;
            }
        }

        // calculate cheapest cost
        int min = 0; // keeps the cheapest last color combination
        for(int i = 1; i < n; i++) {
            int minCost = Integer.MAX_VALUE;
            for(int l = 0; l < COLOR_COMBINATION_STR.length; l++) { // O(n*9)
                for(int r = 0; r < COLOR_COMBINATION_STR.length; r++) { // O(n*9*9)
                    if(cost[i-1][l] < Integer.MAX_VALUE && isValidAdjacent(l, r)) {
                        int rc = cost[i-1][l] + getCost(i, r);
                        if(cost[i][r] > rc) {
                            cost[i][r] = rc;
                            backTrack[i][r] = l;
                            if(rc < minCost) {
                                min = r;
                                minCost = rc;
                            }
                        }
                    }
                }
            }
        }

        // backtrack to print (... print in reverse order, that's the same cost result)
        for(int i = n-1; i >= 0; i--) {
            System.out.println("Column: " + (n - i) + " Colors: " + COLOR_COMBINATION_STR[min]);
            min = backTrack[i][min];
        }
        System.out.println("---");
    }

    // some arbitrary cost function to produce a "random" cost per column for
    // a certain combination of house colors for the three rows
    private static int getCost(int column, int rowColorCombination) {
        return ((rowColorCombination * 17) * (column * 31)) % 11;
    }

    // can next column have this colors per row
    // e.g. if left=0 and right=1:
    // left   right
    // R      R
    // G      B
    // B      G
    // result false, because R   and R in the first row
    static private boolean isValidAdjacent(int left, int right) {
        for(int i = 0; i < 3; i++)
            if(COLOR_COMBINATION_STR[left].charAt(i) == COLOR_COMBINATION_STR[right].charAt(i))
                return false;
        return true;
    }


    static public void main(String[] args) {
        printMinPaint(2);
        printMinPaint(6);
        printMinPaint(12);
    }

}

In general for this kind of problems I prefer to use the tabling method as it solves you all the pain of unrolling the recursion which is specially useful on an interview. You have to check that DP is going to be effective so you have to check that there are multiple repeated calls and the solution is monotonous.
Here is a possible implementation in python

# cost(n, color) is supposed to be the function with the 
# cost for a given row and colors
from itertools import permutations

def compute_houses_cost(n, colors):
	tabling = dict()
	# Initialize the first column. 
        # This saves the base case on the 
        # recursive function
	for p in permutations(colors):
		tabling[(0, p)] = cost(0, p)
	def _aux(n, colors):
		if (n, colors) in tabling:
			return tabling[(n, colors)]
		res = []
		for p in permutations(colors):
			# Don't recurse using the same colors
			if p == colors:
				continue
			res.append(_aux(n-1, p))
		tabling[(n, colors)] = min(res) + cost(n, colors)
		return tabling[(n, colors)]
	return _aux(n, colors)

If I am right then the cost will be same for fixed 3 row of houses, 3 combinations of paint and variable number of columns(houses) N. The program below shows the answer.
Order of complexity O(n*m).

I'm open to suggestions, improvement and learning. :)

public static List<List<string>> InitRows(int row, int columns)
{
    List<List<string>> rowOfHouses = new List<List<string>>();            
    for (int i = 0; i < row; i++)
        rowOfHouses.Insert(i, InitHouses(i, columns));

    return rowOfHouses;
}

// Create Columns of Houses
public static List<string> InitHouses(int row, int n)
{
    List<string> houses = new List<string>();

    for (int j = 0; j < n; j++)
        houses.Add(("H="+ row + "-" + j).ToString());

    return houses;
}

public static List<List<string>> PaintHouses(int rows, int columns, List<List<string>> rowOfHouses)
{            
    string[] color = { "R", "G", "B" };
    int colorSelector = 0;
    int[] colorCount = new int[color.Length];

    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < columns; j++)
        {
            rowOfHouses[i][j] = (rowOfHouses[i][j] + ":" + color[colorSelector]);

            colorCount[colorSelector] = colorCount[colorSelector]+1;

            if (colorSelector < 2)
                colorSelector++;
            else
                colorSelector = 0;
        }
        colorSelector++;
        if (colorSelector >= color.Length)
            colorSelector = 0;
    }
    Console.WriteLine("-------------------------------------------------------------");
    Console.WriteLine("-------------------------------------------------------------");
    Console.WriteLine("Red: " + colorCount[0]);
    Console.WriteLine("Green: " + colorCount[1]);
    Console.WriteLine("Blue: " + colorCount[2]);
    return rowOfHouses;
}

public static void Print(List<List<string>> list)
{
    Console.WriteLine("H=[Row]-[Column]:[Color]");
    for(int i = 0; i < list.Count; i++)
    {
        for(int j = 0; j < list[i].Count; j++)
            Console.Write(list[i][j] + " ");
        Console.Write("\n");
    }
}

static void Main(string[] args)
{
    // Number of Row of Houses
    int rows = 3;
    // Number of Columns = N
    int columns = 6;
            
    List<List<string>> rowOfHouses = InitRows(rows, columns);
            
    // Print Initial Houses
    Print(rowOfHouses);

    // Paint Houses
    rowOfHouses = PaintHouses(rows, columns, rowOfHouses);

    Console.WriteLine("-------------------------------------------------------------");
    Print(rowOfHouses);
}

Approach:
Dynamic Programming solution:
we can paint the ith house with blue, red or green.
so we have the following equations:
cost[i,r] = min( cost[i-1,b], cost[i-1,g] ) + cost of painting i with r.
cost[i,g] = min( cost[i-1,b], cost[i-1,r] ) + cost of painting i with g.
cost[i,b] = min( cost[i-1,r], cost[i-1,g] ) + cost of painting i with b.


Final Min Cost = min (cost[n,b], cost[n,r], cost[n,g]);

@ChrisK Good answer just one small detail it is weird to see the recursion not starting from the last element as it doesn't make much sense that the first column is more expensive than the last one.

public static void main(String[] args) {

		int row = 3;
		int column = 10;
		String color[] = {"Red","Green","Blue"};
		String newColor[]=new String[3];

		Map<String, Integer> colorCostMap = new HashMap<>();
		colorCostMap.put("Red",5);
		colorCostMap.put("Green", 10);
		colorCostMap.put("Blue", 8);

		Map<String, Integer> rowWiseCostMap = new HashMap<>();

		int val[] = {2,0,1};

		for(int i=0; i<=column; i++){
			if(i==0){
				for(int j=0; j<row; j++){
					System.out.print(color[j]+" - ");
				}
			}else{
				for(int j=0; j<row; j++){
					newColor[j] = color[val[j]];
					System.out.print(newColor[j]+" - ");
					if(rowWiseCostMap.get("Row-"+j)==null){
						rowWiseCostMap.put("Row-"+j, colorCostMap.get(newColor[j]));
					}else{
						rowWiseCostMap.put("Row-"+j, rowWiseCostMap.get("Row-"+j)+colorCostMap.get(newColor[j]));
					}
				}
				for(int k=0; k<color.length; k++){
					color[k] = newColor[k];
				}
			}
			System.out.println();
		}
		for(Map.Entry<String, Integer> mapEntry: rowWiseCostMap.entrySet()){
			System.out.println(mapEntry.getKey() + " cost is : "+mapEntry.getValue());
		}
	}