| Bytes | Lang | Time | Link |
|---|---|---|---|
| nan | Scala 3 | 240716T122025Z | 138 Aspe |
| 070 | JavaScript Node.js | 240718T065742Z | l4m2 |
| 130 | Python 3 | 240716T082401Z | Jitse |
| 229 | Python3 | 240715T223722Z | Ajax1234 |
| 154 | Python 2 | 150126T063449Z | Sp3000 |
| 196 | Haskell | 150126T045305Z | MtnViewM |
Scala 3, 217 200 bytes
A port of @Etaoin Shrdlu's Python code in Scala.
Saved 17 bytes thanks to @corvus_192
Golfed version. Attempt This Online!
(p,k,l,q)=>{var(a,b)=(q,Array.fill(k)((l,0)));0 to k-1map{i=>0 to a.size-l map{j=>if(a.slice(j,j+l).count('#'==)<b(i)._1)b(i)=(a.slice(j,j+l).count('#'==),j)};a=a.patch(b(i)._2,Nil,l)};b.map(_._1)sum}
Ungolfed version. Attempt This Online!
object Main extends App {
def calculate(P: Int, K: Int, L: Int, Q: String): Int = {
var QList = Q.toList
var l = Array.fill(K)((L, 0))
for (i <- 0 until K) {
for (j <- 0 until (QList.length - L + 1)) {
if (QList.slice(j, j + L).count(_ == '#') < l(i)._1) {
l(i) = (QList.slice(j, j + L).count(_ == '#'), j)
}
}
QList = QList.patch(l(i)._2, Nil, L)
}
l.map(_._1).sum
}
// Test cases
println(calculate(6, 1, 3, "#.#.##")) // 1
println(calculate(9, 2, 3, ".##..#..#")) // 2
println(calculate(15, 2, 5, ".#.....#.#####.")) // 3
}
JavaScript (Node.js), 70 bytes
L=>g=([c,...A],T,n=L)=>T?1/c?Math.min(g(A,T),c+g(A,T-!--n,n||L)):1/0:0
Output Infinity if no solution. Slower than brute force but reasonable for test cases
Python 3, 130 bytes
p,t,l=map(int,input().split())
q=[(input(),0)]
for s,n in q:q+=[(s[s.count('.'*l)>=t>exit(n):x]+'.'+s[x+1:],n+1)for x in range(p)]
Full program, outputs via exit code
Python 3, 89 bytes
lambda p,t,l,q:min(bin(x).count('1')for x in range(q+1)if f'{x^q:0{p}b}'.count('0'*l)>=t)
Uses more lenient input restrictions: here, q is a bitmap representing the occupied parking spots, so 8382 represents 10000010111110.
Python3, 229 bytes
from itertools import*
def f(b,t,l):
q,s=[(b,0)],[]
for b,c in q:
for i,a in enumerate(b):
if a and(B:=b[:i]+[0]+b[i+1:])not in s:
if sum(len([*k])//l for j,k in groupby(B)if 0==j)>=t:return c+1
q+=[(B,c+1)];s+=[B]
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 > 0spaces along for a new truck, then our only option is to have come from beingk%L-1spaces along for a new truck - Otherwise if
k%L == 0then 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...
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.