Freebie!! Here you go!
This problem was asked by Facebook.
A builder is looking to build a row of N houses that can be of K different colors. He has a goal of minimizing cost while ensuring that no two neighboring houses are of the same color.
Given an N by K matrix where the nth row and kth column represents the cost to build the nth house with kth color, return the minimum cost which achieves this goal.
Octave solution
Can you provide some test cases? I tried to avoid brute-forcing it but I'm not 100% confident of my algorithm's correctness as the solution being optimal.
function cheapest = paint_optimise(cost_matrix, safe = true)
if size(cost_matrix, 2) == 1
[~, cheapest] = min(cost_matrix);
if ~safe
cheapest = [cheapest; zeros(3, 1)];
cost_matrix(cheapest(1)) = Inf;
[~, cheapest(2)] = min(cost_matrix);
cheapest(3) = cheapest(2);
cost_matrix(cheapest(2)) = Inf;
[~, cheapest(4)] = min(cost_matrix); end;
else
pivot = floor(size(cost_matrix, 2) / 2);
left = paint_optimise(cost_matrix(:, 1:pivot), false);
left_cost = price(left, cost_matrix(:, 1:pivot));
right = paint_optimise(cost_matrix(:, (pivot + 1):end), false);
right_cost = price(right, cost_matrix(:, (pivot + 1):end));
combination = zeros(4);
for left_index = 1:4
for right_index = 1:4
if(left(left_index, end) == right(right_index, 1))
combinations(left_index, right_index) = Inf;
else
combinations(left_index, right_index) = left_cost(left_index) + right_cost(right_index); end; end; end;
[left_index, right_index] = min2d(combinations);
cheapest = [left(left_index, :) right(right_index, :)];
if ~safe
cheapest = [cheapest; zeros(3, size(cost_matrix, 2))];
left_mask = double(left(:, end) == left(left_index, end));
right_mask = double(right(:, 1) == right(right_index, 1));
[right_mask, left_mask] = meshgrid(right_mask, left_mask);
left_mask(logical(left_mask)) = Inf;
right_mask(logical(right_mask)) = Inf;
[left_index, right_index] = min2d(combinations + left_mask);
cheapest(2, :) = [left(left_index, :) right(right_index, :)];
[left_index, right_index] = min2d(combinations + right_mask);
cheapest(3, :) = [left(left_index, :) right(right_index, :)];
[left_index, right_index] = min2d(combinations + left_mask + right_mask);
cheapest(4, :) = [left(left_index, :) right(right_index, :)]; end; end;
function total_cost = price(selections, costs)
total_cost = zeros(size(selections, 1), 1);
for index = 1:size(selections, 1)
for house = 1:size(selections, 2)
total_cost(index) += costs(selections(index, house), house); end; end; end;
function [row_index column_index] = min2d(matrix)
[row_index column_index] = find(matrix == min(min(matrix)), 1); end; end;
