Graal Forums - Programming Exercise #8: Parking

Page 1 of 2

Show 40 post(s) from this thread on one page

Graal Forums (https://forums.graalonline.com/forums/index.php)

- NPC Scripting (https://forums.graalonline.com/forums/forumdisplay.php?f=8)

- - Programming Exercise #8: Parking (https://forums.graalonline.com/forums/showthread.php?t=134265002)

Tolnaftate2004

11-08-2011 09:11 PM

Programming Exercise #8: Parking

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

11-08-2011 10:46 PM

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

11-08-2011 10:50 PM

Quote:

Originally Posted by Tricxta (Post 1673586)

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

11-08-2011 10:50 PM

Quote:

Originally Posted by Tricxta (Post 1673586)

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

11-08-2011 11:00 PM

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

11-08-2011 11:02 PM

Quote:

Originally Posted by Tricxta (Post 1673586)

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

11-08-2011 11:14 PM

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?
http://i.imgur.com/Cf4ZK.png

Tolnaftate2004

11-08-2011 11:16 PM

Quote:

Originally Posted by Tricxta (Post 1673592)

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

11-08-2011 11:22 PM

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

11-08-2011 11:26 PM

Quote:

Originally Posted by Tricxta (Post 1673594)

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

11-09-2011 09:10 AM

Quote:

Originally Posted by Tolnaftate2004 (Post 1673596)

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	11-09-2011 12:08 PM

Quote:

Originally Posted by xAndrewx (Post 1673640)

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

11-09-2011 06:37 PM

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

11-09-2011 07:17 PM

1 Attachment(s)

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

11-09-2011 07:23 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1673669)

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

11-09-2011 07:38 PM

Quote:

Originally Posted by iBeatz (Post 1673672)

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

11-09-2011 09:16 PM

Quote:

Originally Posted by Crow (Post 1673644)

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

Crow	11-09-2011 09:22 PM

Quote:

Originally Posted by xAndrewx (Post 1673687)

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

I can't see this being over yet.

fowlplay4

11-10-2011 12:22 AM

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

11-10-2011 12:29 AM

How many floors does this parking lot contain?

Tolnaftate2004

11-10-2011 10:35 PM

Quote:

Originally Posted by fowlplay4 (Post 1673710)

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.

Quote:

Originally Posted by ffcmike (Post 1673711)

How many floors does this parking lot contain?

Just 1.

Gunderak

11-10-2011 11:27 PM

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

Tricxta

11-11-2011 02:57 AM

Quote:

Originally Posted by Gunderak (Post 1673826)

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

11-11-2011 03:45 AM

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:

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

11-11-2011 08:01 AM

Quote:

Originally Posted by Mark Sir Link (Post 1673844)

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

11-11-2011 11:25 AM

Quote:

Originally Posted by Tolnaftate2004 (Post 1673850)

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

11-11-2011 11:59 AM

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:

Gunderak

11-11-2011 12:24 PM

1 Attachment(s)

Quote:

Originally Posted by Tricxta (Post 1673840)

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

http://i886.photobucket.com/albums/a.../TrollFace.png

Fulg0reSama

11-11-2011 06:12 PM

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

http://i1206.photobucket.com/albums/.../burnmoney.jpg
and time

Gunderak

11-11-2011 06:17 PM

lmao.

WanDaMan

11-11-2011 06:18 PM

Quote:

Originally Posted by Tolnaftate2004 (Post 1673568)

We wait until there are no spaces left.

Then :

Quote:

Originally Posted by Tolnaftate2004 (Post 1673568)

N = 100.

Tolnaftate2004

11-12-2011 01:29 AM

Quote:

Originally Posted by Mark Sir Link (Post 1673855)

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

11-12-2011 01:57 AM

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

11-12-2011 02:58 AM

Quote:

Originally Posted by fowlplay4 (Post 1673925)

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

11-12-2011 03:30 AM

Quote:

Originally Posted by Tolnaftate2004 (Post 1673934)

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

11-12-2011 03:57 AM

none because crono crushed them all in his monster truck!

Gunderak

11-12-2011 06:12 AM

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

oo_jazz_oo

11-12-2011 06:58 AM

Quote:

Originally Posted by Gunderak (Post 1673953)

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

http://forums.graalonline.com/forums...reputation.gif Like

Close enough.

Tricxta

11-12-2011 07:21 AM

Too bad you can only like a post once a day x_x

Tolnaftate2004

11-12-2011 08:15 AM

Quote:

Originally Posted by fowlplay4 (Post 1673940)

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.

All times are GMT +2. The time now is 03:26 PM.

Page 1 of 2

Show 40 post(s) from this thread on one page