Graal Forums - Programming Exercise #8: Parking

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)

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.

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

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.

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.

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

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.

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

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

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?

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! :)

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.

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.

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

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

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