11
\$\begingroup\$

There are P parking spaces in a parking lot, though some spaces are occupied by cars represented by octothorpes # while the free spaces are dots .. Soon there arrive T trucks, each of which will take up exactly L consecutive spaces. The trucks don't have to be parked next to each other.

Your task is to create a program that will find the smallest number of cars that need to be removed in order to park all of the trucks. There will always be enough spaces to fit all of the trucks, meaning T*L<P

Input

In the first row there will be three integers, P, T and L separated by spaces. In the second row there will be a string of P characters representing the parking lot in its initial state.

Output

In the first and only line your program should print out the smallest number of cars that need to be removed in order to park all of the trucks.

Test cases

Input:
6 1 3
#.#.##

Output: 1

Input:
9 2 3
.##..#..#

Output: 2

Input:
15 2 5
.#.....#.#####.

Output: 3

Shortest code wins. (Note: I'm particularly interested in a pyth implementation, if one is possible)

\$\endgroup\$
4
\$\begingroup\$

Python 2, 154 bytes

I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
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)]
print D[T*L]

A straightforward DP approach. A fair chunk of the program is just reading input.

Explanation

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 (P, L*T).

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.

If 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:

  TT
..XX

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

TTT
..X#

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?

  TTT            TTT
..XX.     vs     ..X#.

Clearly the latter is better, so we put down a 1.

Pyth, 70 bytes

JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ

Basically a port of the above code. Not very well golfed yet. Try it online

Expanded

Jmvdczd              J = map(eval, input().split(" "))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
>                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]=="#")
>%hT@J2Z                                                           (T+1)%J[2]>0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Now, if only Pyth had multiple assignment to >2 variables...

\$\endgroup\$
5
  • \$\begingroup\$ I was doing something completely different, I think.. but if you have the time, you can tell me where I can cut down on the code (honestly I'd love a one line solution with just a print statement.. dreams dreams...) P,K,L=map(int,input().split()) Q=list(input()) l=[(L,0)]*K for j in range(len(Q)-L): if Q[j:j+L].count('#')<l[i][0]: l[i]=Q[j:j+L].count('#'),j del Q[l[i][1]:l[i][1]+L] print(sum([x[0]for x in l])) \$\endgroup\$ – Etaoin Shrdlu Jan 26 '15 at 20:02
  • \$\begingroup\$ @EtaoinShrdlu Might be easier if you put the code up somewhere like Pastebin so the indentation's correct. From what I can see though that looks like Python 3, and an immediate saving is Q=list(input()) -> *Q,=input() \$\endgroup\$ – Sp3000 Jan 27 '15 at 0:23
  • \$\begingroup\$ yeah, I tried to make this cooperate, but it just didn't want to. didn't really think of pastebin though heh \$\endgroup\$ – Etaoin Shrdlu Jan 27 '15 at 3:15
  • \$\begingroup\$ here it is pastebin.com/ugv4zujB \$\endgroup\$ – Etaoin Shrdlu Jan 27 '15 at 3:23
  • \$\begingroup\$ @EtaoinShrdlu I'm not sure how your logic works, but some other things you can do are 1) Store Q[j:j+L].count('#') as a variable, 2) x=l[i][1];del Q[x:x+L], \$\endgroup\$ – Sp3000 Jan 27 '15 at 4:11
3
\$\begingroup\$

Haskell, 196 characters

import Data.List
f=filter
m=map
q[_,t,l]=f((>=t).sum.m((`div`l).length).f(>"-").group).sequence.m(:".")
k[a,p]=minimum.m(sum.m fromEnum.zipWith(/=)p)$q(m read$words a)p
main=interact$show.k.lines

Runs all examples

& (echo 6 1 3 ; echo "#.#.##" )  | runhaskell 44946-Trucks.hs 
1

& (echo 9 2 3 ; echo ".##..#..#" )  | runhaskell 44946-Trucks.hs 
2

& (echo 15 2 5 ; echo ".#.....#.#####." )  | runhaskell 44946-Trucks.hs 
3

Somewhat slow: O(2^P) were P is the size of the lot.

Probably plenty left to golf here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.