Programming Exercise #8: Parking

[WanDaMan]

Originally Posted by Tolnaftate2004

We wait until there are no spaces left.

Then :

Originally Posted by Tolnaftate2004

N = 100.

[Tolnaftate2004]

Originally Posted by Mark Sir Link

The length of the array is increased to units + 1 to reconcile the idea of each element of the array scaling from the beginning of that index that index to the beginning of the next, IE, 0-1, 1-2, ..., 100-0

snip

As best as I can tell, this is just an expensive way to compute (min+max)/2, which isn't right.

My hint would be to first consider the lot when it is empty; the first car comes along and parks anywhere at all. After this event, we have 1 car in the lot and the lot is now linear (the endpoints being the front and end of our first car). On top of that, the size of the lot has shrunken to N-2. Then you just have to consider every possible arrangement of cars in a linear lot of length N-2.

What do you have after the next car arrives?

[fowlplay4]

I ended up with something like this:

PHP Code:

function onCreated() {

  temp.n = 4; // Amount of Slots in Units
  temp.l = 2; // Length of Cars in Units
  
  temp.parking_available = new[temp.n];

  this.tick = 0;
  this.cars_sum = 0;
  this.cars_min = 0;
  this.cars_max = 0;
  this.cars_sample = 0;
  this.tracking = {};
  
  findParking(temp.parking_available, 1, temp.l);

  temp.avg = this.cars_sum / this.cars_sample;
  echo("Sample Size: " @ this.cars_sample);
  echo("Min: " @ this.cars_min);
  echo("Max: " @ this.cars_max);
  echo("Sum: " @ this.cars_sum);
  echo("Average: " @ temp.avg);
}

function findParking(temp.slots, temp.car, temp.car_length) {
  // Find Possible Spots
  temp.spots = findPossibleSpots(temp.car - 1, temp.slots.link(), temp.car_length);
  temp.spots_count = temp.spots.size();
  if (temp.spots_count > 1) {
    // Avoid Crashing Server
    this.tick++;
    if (this.tick == 1000) {
      //echo("Calculating..." SPC timevar2);
      this.tick = 0;
      sleep(0.05);
    }
    for (temp.spot: temp.spots) {
      temp.updated_slots = parkInSpot(temp.slots, temp.spot, temp.car, temp.car_length);
      findParking(temp.updated_slots, temp.car + 1, temp.car_length);
    }
  } else {
    // No Parking Available for Car
    // Add Amount of Cars that did Find Parking
    // Increment Sample Size
    temp.cars = (temp.spots_count == 1 ? temp.car : temp.car - 1);
    this.cars_sum += temp.cars;
    this.cars_sample++;
    this.cars_min = (this.cars_min == 0) ? temp.cars : min(this.cars_min, temp.cars);
    this.cars_max = (this.cars_max == 0) ? temp.cars : max(this.cars_max, temp.cars);
    this.tracking.add(temp.slots);
  }
}

function parkInSpot(temp.slots, temp.spot, temp.car, temp.car_length) {
  temp.car_slots = {};
  temp.car_slots.addarray(temp.slots);
  for (temp.i = 0; temp.i < temp.car_length; temp.i++) {
    temp.car_slots[temp.spot + temp.i] = true;
  }
  return temp.car_slots;
}

function findPossibleSpots(temp.last_car, temp.slots, temp.car_length) {
  temp.found = {};
  temp.max   = temp.slots.size();
  for (temp.i: temp.slots.indices(0)) {
    temp.canpark = true;
    for (temp.j = 0; temp.j < temp.car_length && temp.canpark; temp.j++) {
      temp.k = temp.i + temp.j;
      if (temp.slots[temp.k] > 0 || temp.k == temp.max) {
        temp.canpark = false;
      }
    }
    if (temp.canpark) {
      temp.found.add(temp.i);
    }
  }
  return temp.found;
} 


Which recursively generates every possible combination that the parking lot can accept. When the parking lot is full then it records the amount of cars the combination could take add it's to the sum and increases the sample size.

I don't think that's the 'linear' way though since when N=4 I get 1.666_. If I track the patterns and ignore ones that have already been generated I get the right answer for N=4.

I'm guessing there's a much better way of going about this than brute force since I can't even calculate an answer where N=100 with the (npcserver).

[Tolnaftate2004]

Originally Posted by fowlplay4

I ended up with something like this:

snip

I don't think that's the 'linear' way though since when N=4 I get 1.666_. If I track the patterns and ignore ones that have already been generated I get the right answer for N=4.

I think you're close. 1.666 may be due to treating the circular lot as if it were linear? I can't really tell...

[fowlplay4]

Originally Posted by Tolnaftate2004

I think you're close. 1.666 may be due to treating the circular lot as if it were linear? I can't really tell...

These would be the full combinations (N=4):

1122
0110
2211

(2 + 1 + 2) / 3 = 1.666_

If we don't care about the order:

1111
0110

(2 + 1) / 2 = 1.5

Like in your example. The code I have edited in there ignores the order so I do get 1.5 with it, problem is that it has to go through all the permutations first so it scales horribly.

[Crono]

none because crono crushed them all in his monster truck!

[Gunderak]

Oh how I wish Stefan would implement the equivalent of a like button.
*Likes Crono's post 1000 times*

[oo_jazz_oo]

Originally Posted by Gunderak

Oh how I wish Stefan would implement the equivalent of a like button.
*Likes Crono's post 1000 times*

Like

Close enough.

[Tricxta]

Too bad you can only like a post once a day

[Tolnaftate2004]

Originally Posted by fowlplay4

These would be the full combinations (N=4):

1122
0110
2211

(2 + 1 + 2) / 3 = 1.666_

If we don't care about the order:

1111
0110

(2 + 1) / 2 = 1.5

The example I gave was wrong, unfortunately. I can't edit that post. it should be 1.666...
The number of cars that can fit in a lot of size 4 is 2. No matter where the first car parks, there is always room for the second car.

[xAndrewx]

Originally Posted by Tolnaftate2004

The example I gave was wrong, unfortunately. I can't edit that post. it should be 1.666...
The number of cars that can fit in a lot of size 4 is 2. No matter where the first car parks, there is always room for the second car.

kewl

[Tolnaftate2004]

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.

[Tricxta]

Looks more like a maths lesson rather then a programming solution. Pretty cool though since I see what you did there, I'll rep you for that.

[xAndrewx]

gj on the four people that entered.

[oo_jazz_oo]

I'm bad at conceptualizing maths.

Can't we have a programming excercise thats like....useful. :3