Graal Forums  

Go Back   Graal Forums > Development Forums > NPC Scripting
FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
Thread Tools Search this Thread Display Modes
  #1  
Old 11-08-2011, 09:11 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
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.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #2  
Old 11-08-2011, 10:46 PM
Tricxta Tricxta is offline
The Muffin Man
Tricxta's Avatar
Join Date: Oct 2010
Location: Australia
Posts: 563
Tricxta is a jewel in the roughTricxta is a jewel in the rough
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

Last edited by Tricxta; 11-08-2011 at 10:56 PM..
Reply With Quote
  #3  
Old 11-08-2011, 10:50 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Tricxta View Post
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:
[][][][] t0
car 
[][] t1
car car  t 
t2 
But sometimes it's just 1:
PHP Code:
[][][][] t0
[]car [] t1 
So the answer in this case is 1.5.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #4  
Old 11-08-2011, 10:50 PM
ffcmike ffcmike is offline
Banned
Join Date: Jul 2004
Location: London
Posts: 2,029
ffcmike has a reputation beyond reputeffcmike has a reputation beyond reputeffcmike has a reputation beyond reputeffcmike has a reputation beyond reputeffcmike has a reputation beyond reputeffcmike has a reputation beyond reputeffcmike has a reputation beyond reputeffcmike has a reputation beyond repute
Send a message via AIM to ffcmike Send a message via MSN to ffcmike
Quote:
Originally Posted by Tricxta View Post
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.
Reply With Quote
  #5  
Old 11-08-2011, 11:00 PM
Tricxta Tricxta is offline
The Muffin Man
Tricxta's Avatar
Join Date: Oct 2010
Location: Australia
Posts: 563
Tricxta is a jewel in the roughTricxta is a jewel in the rough
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
Reply With Quote
  #6  
Old 11-08-2011, 11:02 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Tricxta View Post
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.
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #7  
Old 11-08-2011, 11:14 PM
Tricxta Tricxta is offline
The Muffin Man
Tricxta's Avatar
Join Date: Oct 2010
Location: Australia
Posts: 563
Tricxta is a jewel in the roughTricxta is a jewel in the rough
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?
Reply With Quote
  #8  
Old 11-08-2011, 11:16 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Tricxta View Post
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).
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #9  
Old 11-08-2011, 11:22 PM
Tricxta Tricxta is offline
The Muffin Man
Tricxta's Avatar
Join Date: Oct 2010
Location: Australia
Posts: 563
Tricxta is a jewel in the roughTricxta is a jewel in the rough
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?
Reply With Quote
  #10  
Old 11-08-2011, 11:26 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to Tolnaftate2004
Quote:
Originally Posted by Tricxta View Post
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!
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/
Reply With Quote
  #11  
Old 11-09-2011, 09:10 AM
xAndrewx xAndrewx is offline
Registered User
xAndrewx's Avatar
Join Date: Sep 2004
Posts: 5,260
xAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud ofxAndrewx has much to be proud of
Quote:
Originally Posted by Tolnaftate2004 View Post
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.
__________________
Reply With Quote
  #12  
Old 11-09-2011, 12:08 PM
Crow Crow is offline
ǝɔɐɹq ʎןɹnɔ
Crow's Avatar
Join Date: Dec 2006
Location: Germany
Posts: 5,153
Crow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond reputeCrow has a reputation beyond repute
Quote:
Originally Posted by xAndrewx View Post
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.
__________________
Reply With Quote
  #13  
Old 11-09-2011, 06:37 PM
iBeatz iBeatz is offline
Kavan
iBeatz's Avatar
Join Date: Dec 2010
Location: Northern Ireland, UK
Posts: 154
iBeatz will become famous soon enough
Send a message via Yahoo to 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.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)^+ (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 = (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 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.
__________________

Intelligence without ambition is like a bird without wings.


Last edited by iBeatz; 11-09-2011 at 07:01 PM..
Reply With Quote
  #14  
Old 11-09-2011, 07:17 PM
Tolnaftate2004 Tolnaftate2004 is offline
penguin.
Join Date: Jul 2004
Location: Berkeley, CA
Posts: 534
Tolnaftate2004 is a jewel in the roughTolnaftate2004 is a jewel in the rough
Send a message via AIM to 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).
Attached Images
 
__________________
◕‿‿◕ · pfa · check yer syntax! · src

Killa Be: when i got that locker in 6th grade the only thing in it was a picture of a midget useing a firehose :/

Last edited by Tolnaftate2004; 11-09-2011 at 07:36 PM..
Reply With Quote
  #15  
Old 11-09-2011, 07:23 PM
iBeatz iBeatz is offline
Kavan
iBeatz's Avatar
Join Date: Dec 2010
Location: Northern Ireland, UK
Posts: 154
iBeatz will become famous soon enough
Send a message via Yahoo to iBeatz
Quote:
Originally Posted by Tolnaftate2004 View Post
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
__________________

Intelligence without ambition is like a bird without wings.

Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 10:59 PM.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2024, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.