# 1+ lines Ruby, Python

• First two solutions could easily be generalized to arbitrary number of colors.

Solution 1 ... Ruby

``````def min_cost(costs)
costs.reduce([0]*3) { |prev, now| now.map { |n| n + prev.rotate![0,2].min } }.min
end
``````

Solution 2 ... Python

``````def minCost(self, costs):
prev = [0] * 3
for now in costs:
prev = [now[i] + min(prev[:i] + prev[i+1:]) for i in range(3)]
return min(prev)
``````

Solution 3 ... Python

``````def minCost(self, costs):
return min(reduce(lambda (A,B,C), (a,b,c): (a+min(B,C), b+min(A,C), c+min(A,B)),
costs, [0]*3))``````

• I like the second one --- `now` and `prev` are very readable :-)

• What about the first one? It's shorter and it also uses those names :-)

• Hi, Stefan. Yeah, it is similar or even better :-) It is just that Ruby grammar is still not accesible to me...

• well it's still O(n*k^2) time complexity. As pre[0:i] + pre[i+1:] need O(k)

• What is k? Number of colors? That's constant here, so it's O(n).

It would be O(n*k^2) if generalized naively, but can be made O(nk) in a nice way, which is why I suggested that extension :-)

• yes, I have seen your elegant python code. So strong you are!

• Similar solution in Java:
Here is the java implementation with lambda:

``````if (costs.length == 0 || costs[0].length == 0) {
return 0;
}
return Arrays.stream(Arrays.stream(costs).reduce((a, b) -> {
final int len = costs[0].length;
int[] now = new int[len];
for (int i = 0; i < len; i++) {
int tmp = a[i];
a[i] = Integer.MAX_VALUE;
now[i] = Arrays.stream(a).min().getAsInt() + b[i];
a[i] = tmp;
}
return now;
}).get()).min().getAsInt();
``````

Or with AbacusUtil (A tool developed by me :-))

``````return N.min(N.reduce(costs, (a, b) -> {
final int len = costs[0].length;
int[] now = new int[len];
for (int i = 0; i < len; i++) {
int tmp = a[i];
a[i] = Integer.MAX_VALUE;
now[i] = N.min(a) + b[i];
a[i] = tmp;
}
return now;
}));
``````

• @StefanPochmann thx. I like your python solution

But sometimes you are being too pythonic...

• you can do

``````min(prev[(i+1)%3],prev[(i+2)%3])
``````

``````min(prev[:i] + prev[i+1:])
``````

which slice the list and create new lists.

• @hzc930916 Yes, but with three colors both ways are O(1) and with an arbitrary number of colors, I think yours doesn't work, does it? I didn't think it through now... Anyway, I like mine for the simplicity and the generality.

But yours is also good, yes. I think I'd prefer `min(prev[(i+1)%3], prev[(i-1)%3])`, though. I somehow find that nicer, and it supports the two-colors case as well (although that one is trivial).

• Haha, we have similar solution again and I have a feeling before I came to the discussion if you have posted the solution, this solution must be one of them, but yours definitely better than mine:

``````return costs and min(reduce(lambda x, y: (y[0] + min(x[1], x[2]), y[1] + min(x[0], x[2]), y[2] + min(x[0], x[1])), costs)) or 0
``````

I just know today the third parameter of reduce function is initializer

• Why I have this error?

``````In [68]: f = lambda (A,B,C),(a,b,c): (a + min(B, C), b + min(A, C), c + min(A, B))