2
$\begingroup$

I just came up across this question in the mathematics stack exchange site and found it quite interesting:

100 autonomous robotic vehicles enter a warehouse in random order to park. Inside the warehouse, there are 100 sequential parking spaces enumerated from 1 to 100. Each vehicle has an assigned number where it will attempt to park. However, there is an error in the programming such that if a vehicle finds its path to the assigned parking spot blocked by an already-parked robot, the robot will immediately park in the spot before it. For example, if vehicle 50 parks in spot 50 but vehicle 75 is immediately behind it, vehicle 75 will park in spot 49. Also, if vehicle 1 parks in spot 1, every robot behind it will be blocked from entering the warehouse at all. The vehicles do not have the ability to maneuver around already-parked vehicles.

What is the most likely number of robots that will be parked in the warehouse at the end of the routine?

$\endgroup$
  • $\begingroup$ Arbitrary order, or random order? $\endgroup$ – Ry- Oct 9 '14 at 19:33
  • 1
    $\begingroup$ Random! At first any car has a 1/100 probability of being the first. Once it has entered the remaining cars have a 1/99 probability... $\endgroup$ – Ioannes Oct 9 '14 at 19:39
  • $\begingroup$ Can you provide a link to the question on math.stackexchange? $\endgroup$ – Julian Rosen Oct 9 '14 at 20:41
  • $\begingroup$ The math question is here $\endgroup$ – Ross Millikan Oct 10 '14 at 2:40
2
$\begingroup$

I decided to brute force the problem by writing a quick program.

using System;
using System.Collections.Generic;
using System.Linq;

public class Test
{
    static readonly int NUMROBOTS = 100;
    static readonly int ITERATIONS = 1000000;
    static Random rng = new Random();

    int FindParking()
    {
        int free = NUMROBOTS; // # of largest free spot
        int count = 0; // Number of robots parked

        var robots = Enumerable.Range(1, NUMROBOTS).ToList();
        // Shuffle list
        int n = robots.Count;
        while (n > 1)
        {  
            n--;  
            int k = rng.Next(n + 1);  
            int value = robots[k];  
            robots[k] = robots[n];  
            robots[n] = value;  
        }

        while (free > 1)
        {
            if (free > robots[count])
                free = robots[count]; // Robot found its spot
            else
                free--;               // Spot is filled
            count++;
        }
        return count;
    }


    public static void Main()
    {
        var p = new Test();
        int total = 0;
        for (int i = 0; i < ITERATIONS; i++)
        {
            total += p.FindParking();
        }
        Console.WriteLine("Average robots parked: {0} ({1} iterations)", (decimal)total / ITERATIONS, ITERATIONS);
    }
}

Average robots parked: 11.920253 (1000000 iterations)

I'd like to see the math for this, though.

$\endgroup$
  • $\begingroup$ This was the same approach I was going to take. I have no idea how the math would be set up though. $\endgroup$ – DiscOH Oct 9 '14 at 20:31
  • 1
    $\begingroup$ @DiscOH I've just added the link to the math.stackexchange site. There are some math answers there. $\endgroup$ – Ioannes Oct 9 '14 at 20:52
  • $\begingroup$ Your simulation seems to disagree greatly with my calculation. I think the difference is that I was calculating the average number, not the most probable number. Can you modify the program to check? I suspect the distribution is skewed enough that the average is much lower than the mode. $\endgroup$ – Ross Millikan Oct 10 '14 at 2:44
  • $\begingroup$ @Ross Millikan For getting the average from individual probabilities could one multiply the number X of parked cars by its probability and then add the results to get the average? $\endgroup$ – Ioannes Oct 10 '14 at 13:38
  • $\begingroup$ @Ross Millikan The program calculates the mean, not the mode. There could be a problem with the algorithm, but I don't see it. $\endgroup$ – Otaia Oct 10 '14 at 13:41
1
$\begingroup$

I would guess around 18 cars. If we assume that average placement of a car in the empty lot is 1/2 way up, then we can make some assumptions as to where the cars are placed and how many are placed ahead of it.

  • First car is at 50. (1)
  • Next car is at 25, but before that car parks, there is a 50% chance (repeating) that a car is at 50+ and so is placed right after the 50. That averages out to 1 extra car. (3)
  • The next car is at 12, but before it parks this time there's a 75% chance of a car at 25+. That averages out to 3 extra cars. (7)
  • Here's where it gets a little tricky. You have ~7/8 chance of the next car being above 12, but there are only 12 places left. You could do the math to get an average of 8 cars in this scenario, which puts you down to spot 4 (15)
  • At that point, you have 3 spots left, but a really high chance of picking a car ahead of 3. So, we can just say they're fully filled (18)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.