Alright, this thread has been dead for long enough...
Like I said before, the fact that the lot is circular is important. However, let us consider the first car. With probability 1 it parks somewhere in the lot (since it's empty). Then we can henceforth consider the lot to be linear (and 1 car-length shorter) with one end being the front of the first car and the other the end of the first car. And we have 1 car in our lot. So,
f(N; circular) = 1 + f(N-2; linear).
So now we consider the second car and a lot of
N-2. Somewhere in this lot, the car will park and split our lot into 2 even further smaller lots. If we number the units 0 ...
N-3, let us call the smaller unit number that the second car occupies
i. After parking, there are lots of size
i and
N-4-
i. So,
f(N-2; linear | car 2 parks in unit i) = 1 + f(i; linear) + f(N-4-i; linear).
For those of you who know your probability, you'll know that
P(Y) = P(Y | X = x1) * P(X = x1) + ... + P(Y | X = xn) * P(X = xn).
And for those of you who don't,
P is the probability and that | means "given".
So, we apply this rule to the above:
f(N-2; linear) = 1 + (f(0; linear) + f(N-4; linear)) * P(i = 0) + ... + (f(N-4; linear) + f(0; linear)) * P(i = N-3).
Of course,
P(
i =
x) = 1/(
N-3), so we can boil this down to
f(N; linear) = 1 + 2/(N-1)*(f(0) + ... f(N-2)).
When applied,
f(100; circular) = 43.233235838...
However, the recursion grows with N!! (repeat !s as many times as a car-length...
), so to speed up this calculation, we use memoization.
PHP Code:
function f(n) {
if (n < 2) return 0;
temp.r = f.("lot_" @ n);
if (r) return r;
temp.v = 0, temp.i = 0;
for (; i < n - 1;)
v += f(i++);
v = 1 + 2 / (n - 1) * v;
f.("lot_" @ n ) = v;
return v;
}
I've looked at the case where cars can park at non-integer positions within the lot. The answer would be smaller than the discrete case, so I have a sneaking suspicion that Mark Sir Link got it right in that case (but it's a pretty hard problem to solve exactly). Brownie points for you.
11-12-2011, 09:51 AM
does that count?
Linear Mode
