Programming Exercise #8: Parking

[Tolnaftate2004]

It has been more than a year since the last programming exercise! So, I thought I'd give it another go. Today's puzzle is about a circular parking lot.

Now, let's suppose that cars are two units long and that our parking lot is N units long, arranged along the circumference of a circle. Cars come and park randomly in the parking lot in any space that can accommodate them (that is, any space that is at least 2 units long).

We wait until there are no spaces left. How many cars do we expect to find in our parking lot? In other words, if we counted the cars in our parking lot every day til the end of time, what would the average be?

This thread is about discussing methods of solving this problem. If you've seen this problem before, you can aid in the discussion, but let's wait some time before ruining the fun for everyone. Otherwise, when you have an answer, post the code and the output for when N = 100.

[Tricxta]

You're asking how many times 2 goes into 100? lol
Anyhow if it's not and I mis-interpreted the question and the length of a car is 2 units as well as the width... then I'd:
1)Find the original radius:
100=2*pi*r
100/2/pi=r
r=15.9(rounded)

2)then subtract 2 units(length of the car) from that
r=13.9

3)Find the new circumfrence
circ=2*pi*13.9
circ=87.3(rounded)

The amount of cars able to fit in the parking lot is now:
=86/2
=43

[Tolnaftate2004]

Originally Posted by Tricxta

You're asking how many times 2 goes into 100? lol

Well if 50's your answer, then you're wrong.

Let's consider a linear lot and the case on N=4:
1/2 of the time, you will have two cars in the lot:

PHP Code:

[][][][] t = t0
car [][] t = t1
car car  t = t2 


But sometimes it's just 1:

PHP Code:

[][][][] t = t0
[]car [] t = t1 


So the answer in this case is 1.5.

[ffcmike]

Originally Posted by Tricxta

You're asking how many times 2 goes into 100? lol

Except the 100 is circular rather than a square, so it's not an exact fit.

Also I swear had I paid attention on this specific maths in school, this would have been the first time it would have been any use to me some 7 years later.

[Tricxta]

I'm a bit confused with this challenge, don't we also need the width of the car? assuming its the length that's already been given

[Tolnaftate2004]

Originally Posted by Tricxta

Anyhow if it's not and I mis-interpreted the question and the length of a car is 2 units as well as the width... then I'd:
1)Find the original radius:
100=2*pi*r
100/2/pi=r
r=15.9(rounded)

2)then subtract 2 units(length of the car) from that
r=13.9

3)Find the new circumfrence
circ=2*pi*13.9
circ=87.3(rounded)

The amount of cars able to fit in the parking lot is now:
=86/2
=43

1. The width of a car has nothing to do with the problem.
2. The cars are parallel parking AROUND a circle.
3. Nope.

[Tricxta]

So let me get this right then I'll leave this thread alone :P
The question basically is how many cars of the length 2 units can you fit into a car park with the outer radius of 100 units whilst having the cars parked as shown?

[Tolnaftate2004]

Originally Posted by Tricxta

So let me get this right then I'll leave this thread alone :P
The question basically is how many cars of the length 2 units can you fit into a car park with the outer radius of 100 units whilst having the cars parked as shown?

This would be a perfect packing of the cars, yes. In this case, 50 cars could fit in a lot of 100 units. However, they are parking randomly, so the cars are unlikely to park perfectly packed (say that 5x fast).

[Tricxta]

If the cars are parking randomly and leaving gaps too small for other cars to fit we can only come up with an algorithm to determine the average over a given time but no actual answer. Right?

[Tolnaftate2004]

Originally Posted by Tricxta

If the cars are parking randomly and leaving gaps too small for other cars to fit we can only come up with an algorithm to determine the average over a given time but no actual answer. Right?

Which is the problem, isn't it!

[xAndrewx]

Originally Posted by Tolnaftate2004

Which is the problem, isn't it!

What you mean to say is yes.

To be totally honest with you, would you ever need to design this system on Graal?

Make the challenges based on Graal stuff which can help new developers, you could have done something Halloween based or thanks giving, not a car park.

[Crow]

Originally Posted by xAndrewx

To be totally honest with you, would you ever need to design this system on Graal?

No. Programming exercises are not about things you may or may not need, though. They present problems for you to reflect on. Complicated problems that, when solved, can give you an idea on how to tackle similar ones in the future.

[iBeatz]

Well, I was trying to come up with some sort of algorithm for this which took into account the largest potential area the cars could take up, as well as the least amount of area the cars could take up, and came up with this. The problem is, I can only work it out if the width of the cars are known, as I don't really know how this can be solved without knowing this.

PHP Code:

function onCreated(){
  
  temp.n = 100;
  temp.car_length = 2;
  temp.car_width = 2;    // Because I can't do it with an unknown value

  /* Using Pythagoras' theorm, I found the hypotenuse of the triangle inside 
      the car, which also gave me the radius of the circle around the car,
      which represents the total amount of area it could potentially take up, as
      they are parking randomly.
  */
  temp.car_potential_area = ((car_length / 2)^2 + (car_width / 2)^2)^0.5;
  
  /* I then used the radius of the circle found above so that I could
      calculate the length of the radius between the center of the inner
      circle and the center of the car's "circle"
  */
  temp.car_middle = (n / pi / 2) + car_potential_area;

  /* And then, using the radius from above, calculated how many cars 
      could fit along the circumference of this line, like beads on a string
      if you imagine the circles around the cars.
  */
  temp.parking_places = 2 * pi * car_middle;

  /* From this, I divided the total parking space by the diameter of the
      circle of potential area they could take up, to get a decimal value
      for the number of cars.
  */
  temp.cars = parking_places / (car_potential_size * 2);

  // Echoes a value for the minimum number of cars (38 cars)
  echo(int(temp.cars)); // Integer because you can't have a fraction of a car

  /* A value for the maximum number of cars, parking side by side around the
      circle
  */
  temp.max_cars = parking_places / car_length;

  // Echoes a value for the maximum number of cars if they were lined up side by side (54 cars)
  echo(int(temp.max_cars));
} 


So my answer is that there could be any number between 38 and 54 cars in the parking lot.
This is the best I could come up with, tell me if I'm along the right lines.

[Tolnaftate2004]

I don't know where you guys are getting pi from, the lot is 100 units and a car is 2 units, so the very most you could fit around the circle is 50 cars and if every car left a space behind it, the very least you could have is 34 cars. So the answer is somewhere in there (it's not an integer).

I've attached a picture of a possible outcome for a lot of N=21. Blue are cars, black is left-over spaces that a car cannot fit into (that is, they are 1 unit long).

[iBeatz]

Originally Posted by Tolnaftate2004

I don't know where you guys are getting pi from, the lot is 100 units and a car is 2 units, so the very most you could fit around the circle is 50 cars (but this is not the answer).

How could you not use pi to solve this? o_o

[Tolnaftate2004]

Originally Posted by iBeatz

How could you not use pi to solve this? o_o

Because the lot isn't 100*pi or 4*arctan(1/5)-arctan(1/239) or sqrt(1+sqrt(1+sqrt(1+...))) units, it's 100 units.

[xAndrewx]

Originally Posted by Crow

No. Programming exercises are not about things you may or may not need, though. They present problems for you to reflect on. Complicated problems that, when solved, can give you an idea on how to tackle similar ones in the future.

Maybe more than one person will participate next time. Who knows

[Crow]

Originally Posted by xAndrewx

Maybe more than one person will participate next time. Who knows

I can't see this being over yet.

[fowlplay4]

They could:

1. Paint the lines so there's at least 2.5 units of space for each car.
2. Have offenders towed/exploded for not staying within the lines of their spot.

So the solution to me is N / 2.5

[ffcmike]

How many floors does this parking lot contain?

[Tolnaftate2004]

Originally Posted by fowlplay4

They could:

1. Paint the lines so there's at least 2.5 units of space for each car.
2. Have offenders towed/exploded for not staying within the lines of their spot.

So the solution to me is N / 2.5

Heh, nope.

Originally Posted by ffcmike

How many floors does this parking lot contain?

Just 1.

[Gunderak]

Maybe just make a normal car park and you'd be right.

[Tricxta]

Originally Posted by Gunderak

Maybe just make a normal car park and you'd be right.

Why not test out your theory? Tolnaftate will tell you if you're correct or not

[Mark Sir Link]

Began the equation by assuming the fact that the lot was circular was essentially an extra detail that mattered very little to the eventual outcome since the circumference can basically be regarded as a circle laid out flat. So assuming a 100 unit long straight line, and a gap of 1 unit between the cars as the highest gap (rather than say 1.99999 repeated which would lead to 25 cars instead of whatever limit you said later), came up with this code that would linearly determine how many cars would fit.

PHP Code:

function onCreated(){
  temp.val1 = findMin(100, 2);
  temp.val2 = findMax(100, 2);
  echo(val1);
  echo(val2);
  for(temp.i = 0; i < 100; i++){
    temp.val3 += findRand(100, 2);
  }
  echo(val3/100);
}

function findRand(n, i){
  temp.space = 0;
  temp.gap = i - random(1, 2);
  temp.isgap = false;
  temp.cars = 0;
  while(space < n){
    isgap = !isgap;
    if(isgap){
      space += gap;
    }
    else{
      space += i;
      cars++;
    }
  }
  return cars;
}

function findMin(n, i){
  temp.space = 0;
  temp.gap = i - 1;
  temp.isgap = false;
  temp.cars = 0;
  while(space < n){
    isgap = !isgap;
    if(isgap){
      space += gap;
    }
    else{
      space += i;
      cars++;
    }
  }
  return cars;
}

function findMax(n, i){
  return int(n/i);
} 


Output:

PHP Code:

33
50
40.87 


The results if plotted for each random iteration would wind up being a sort of diamond leading around the value of min + max / 2, causing the average to approach that value.

[Tolnaftate2004]

Originally Posted by Mark Sir Link

Began the equation by assuming the fact that the lot was circular was essentially an extra detail that mattered very little to the eventual outcome since the circumference can basically be regarded as a circle laid out flat. So assuming a 100 unit long straight line, and a gap of 1 unit between the cars as the highest gap...

Gaps between cars should be either 0 units or 1 unit. The cars have to line up with the units. Additionally, the lot being circular does have an impact on the answer, but somehow considering it as a linear lot is a step in the right direction.

[Mark Sir Link]

Originally Posted by Tolnaftate2004

Gaps between cars should be either 0 units or 1 unit. The cars have to line up with the units. Additionally, the lot being circular does have an impact on the answer, but somehow considering it as a linear lot is a step in the right direction.

the only significant impact I can see from the lot being circular is the relationship of the car at the theoretical start and ending points, meaning if a car were attempted to be parked at N-1 marker, it should then consider if there is a car at 1 or 2 (0 or 1 as array form).

I'll adjust for that and shift to using an array since the gaps remaining integer makes the question tremendously easier.

Or it'd be getting more complex into relational math where the fact that the car is tangent to whatever point on the circle has some profound effect on how the cars can align and modifying the math to account for that but I don't think that's what you were going for

[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

It doesn't matter if temp.isgap starts as true or false, and it's possible to see a sort of representation of how the cars align by returning lot instead of this.parkedcars.




Code:

PHP Code:

function onCreated(){
  this.gapmax = 1;
  this.gapmin = 0;
  temp.val1 = findMin(100, 2);
  temp.val2 = findMax(100, 2);
  echo(val1);
  echo(val2);
  for(temp.i = 0; i < 100; i++){
    temp.val3 += findRand(100, 2);
  }
  echo(val3/100);
}

function findMin(units, carlength){
  this.parkedcars = 0;
  temp.isgap = false;
  for(temp.i = 0; i < units+1; i++){
    temp.lot.add("E");
  }
  for(temp.i = 0; i < lot.size(); i++){
    temp.isgap = !temp.isgap;
    if(!temp.isgap){
      lot = parkCar(lot, i);
      i++;
    }
  }
  return this.parkedcars; 
}

function findRand(units, carlength){
  temp.i = int(random(0,2));
  if(i == 0){
    return findMin(units, carlength);
  }
  else{
    return findMax(units, carlength);
  }
}

function parkCar(arr, i){
  if(i + 1 == arr.size()){
    temp.val = 0;
  }
  else{
    temp.val = i + 1;
  }
  if(arr[i] == "E" && arr[val] == "E"){
    arr[i] = "C";
    arr[val] = "C";
    this.parkedcars++;
  }
  return arr;
}

function findMax(units, carlength){
  return int((units+1)/carlength); 
} 


Output:

PHP Code:

34
50
42.96 


[Gunderak]

Originally Posted by Tricxta

Why not test out your theory? Tolnaftate will tell you if you're correct or not

[Fulg0reSama]

Not gonna lie, I see this circular parking lot as this.


and time

[Gunderak]

lmao.

[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.