All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Parking Cars (Posted on 2004-07-01)
There is an east-west street of length L units. And we park cars of unit length along the north side until we can't place any more cars. Each car is placed randomly (uniformly).

What is the expected number of cars that can be parked (as a function of L)?
__________________________

I'll start you off...

For 0 <= L < 1, F(L) = 0
For 1 <= L < 2, F(L) = 1

Okay... now the easy ones are out of the way, can you describe the function for L>=2?

 No Solution Yet Submitted by SilverKnight Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 simulation | Comment 7 of 14 |

The following program simulates 2000 trials of each of various lengths of curb, and displays the average number of cars fitted at that length.

The program maintains an array of available stretches of points at which the front of a newly arriving car can be placed.  Initially there is just one stretch of L - 1 units at which the front of a car may be placed. (I've used the variable n rather than L.)  When a car takes a spot it divides one stretch into two.  In the normal circumstance the total available length decreases by 2: one unit in the portion between the front of the car and the beginning of the stretch, as no car front can any longer be in that portion even though the new car is not there, as the back would extend into the car.  And the other unit is taken from the new stretch between the front of the arriving car and the end of the original stretch--this is occupied by the car itself.

The sequence of the stretches available at a given time does not matter, so an array is used rather than a linked list, so that when a segment disappears (such as a 2-unit stretch in which the front of a car is at .7) the last other segment can be brought back into the emptied slot, and contiguousness is maintained.

RANDOMIZE TIMER
DEFDBL A-Z
FOR n = 5 TO 100 STEP 5
trials = 0
numCars = 0
FOR tr = 1 TO 2000
REDIM spaceLoc(200), spaceAmt(200)

numSpaces = 1: totSpace = n - 1
spaceLoc(1) = 0: spaceAmt(1) = n - 1
'spaceLoc is the loc avalable for the Front of the car

DO
newCar = RND(1) * totSpace
covered = 0
done = 0
FOR sb = 1 TO numSpaces
IF covered + spaceAmt(sb) >= newCar THEN
done = 1
newSpace1 = newCar - covered - 1 ' this 1 is for the new buffer zone
newSpace2 = covered + spaceAmt(sb) - newCar - 1 'this 1 is for the car itself
IF newSpace1 > 0 THEN
savSpace = spaceAmt(sb)
spaceAmt(sb) = newSpace1
IF newSpace2 > 0 THEN
numSpaces = numSpaces + 1
spaceAmt(numSpaces) = newSpace2
spaceLoc(numSpaces) = newCar + 1
totSpace = totSpace - 2
ELSE
totSpace = totSpace - 1 - (savSpace + covered - newCar)
END IF
ELSE
IF newSpace2 >= 0 THEN
spaceAmt(sb) = newSpace2
spaceLoc(sb) = newCar + 1
totSpace = totSpace - (newCar - covered) - 1
ELSE
totSpace = totSpace - spaceAmt(sb)
IF numSpaces > sb THEN
spaceAmt(sb) = spaceAmt(numSpaces)
spaceLoc(sb) = spaceLoc(numSpaces)
ELSE
spaceAmt(sb) = 0
END IF
numSpaces = numSpaces - 1
END IF
END IF
EXIT FOR
END IF
covered = covered + spaceAmt(sb)
sb = sb + 1
NEXT sb
IF done THEN numCars = numCars + 1
LOOP UNTIL totSpace <= 0 OR numSpaces = 0
trials = trials + 1
NEXT tr
PRINT n, numCars / trials
NEXT n

The results for various lengths are the following average number of cars fitting:

5             3.4925
10            7.251
15            10.9605
20            14.7155
25            18.4145
30            22.14
35            25.9195
40            29.7045
45            33.3655
50            37.1205
55            40.818
60            44.6445
65            48.317
70            52.0545
75            55.8365
80            59.6075
85            63.3095
90            67.069
95            70.85599999999999
100           74.54949999999999

Toward the end of this series, 10 extra units seems to allow 7.5 additional cars, so possibly the average number of cars approaches 75% of the length of the curb as that length increases without limit.  Small lengths are heavily affected by border problems:

1.75          1
2             1
2.25          1.3968
2.5           1.6682
2.75          1.85695
3             2
3.25          2.1572
3.5           2.348
3.75          2.55295
4             2.7395
4.25          2.92565
4.5           3.10855
4.75          3.2963
5             3.4826
5.25          3.67105
5.5           3.86305
5.75          4.04105
6             4.2331
6.25          4.42145
6.5           4.6023
6.75          4.8001
7             4.97775
7.25          5.1708
7.5           5.35325
7.75          5.5425
8             5.7282
8.25          5.9148
8.5           6.10445
8.75          6.28905
9             6.4756
9.25          6.65775
9.5           6.85385
9.75          7.0278
10            7.22715
10.25         7.41315

I would suggest the accuracy is good only to two positions after the decimal, rather than what might be implied by the precision shown.

In this run, each length shows the average of 20,000 trials, rather than 2,000.

 Posted by Charlie on 2004-07-02 00:16:28

 Search: Search body:
Forums (0)