Python 2, 154 bytes
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
A straightforward DP approach. A fair chunk of the program is just reading input.
We calculate a 2D dynamic programming table where each row corresponds to the first
n parking spots, and each column corresponds to the number of trucks (or parts of a truck) placed so far. In particular, column
k means that we've placed
k//L full trucks so far, and we're
k%L along the way for a new truck. Each cell is then the minimal number of cars to clear to reach the state
(n,k), and our target state is
The idea behind the DP recurrence is the following:
- If we're
k%L > 0 spaces along for a new truck, then our only option is to have come from being
k%L-1 spaces along for a new truck
- Otherwise if
k%L == 0 then we have either just finished a new truck, or we'd already finished the last truck and have since skipped a few parking spots. We take the minimum of the two options.
k > n, i.e. we've placed more truck squares than there are parking spots, then we put
∞ for state
(n,k). But for the purposes of golfing, we put
k since this is the worst case of removing every car, and also serves as an upper bound.
This was quite a mouthful, so let's have an example, say:
5 1 3
The last two rows of the table are
[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]
The entry at index 2 of the second last row is 2, because to reach a state of
2//3 = 0 full trucks placed and being
2%3 = 2 spaces along for a new truck, this is the only option:
But the entry at index 3 of the second last row is 1, because to reach a state of
3//3 = 1 full trucks placed and being
3%3 = 0 spaces along for a new truck, the optimal is
The entry at index 3 of the last row looks at the above two cells as options — do we take the case where we are 2 spaces along for a new truck and finish it off, or do we take the case where we have a full truck already finished?
..XX. vs ..X#.
Clearly the latter is better, so we put down a 1.
Pyth, 70 bytes
Basically a port of the above code. Not very well golfed yet. Try it online
Jmvdczd J = map(eval, input().split(" "))
Kw K = input()
=GUhhJ G = range(J+1)
VhJ for N in range(J):
=HG H = G[:]
FTUhN for T in range(N+1):
XHhT H[T+1] =
hS sorted( )
> [ :]
, ( , )
)=GH G = H[:]
Now, if only Pyth had multiple assignment to >2 variables...