Follow
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
@khird I haven't attacked this one yet. But from what I can see it is essentially the same problem as the non-adjacent sums problem. When I look at it, I will come up with some test cases
Octave solution
@Absinthe
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;