The grand opening of the Collapsible Robot Museum is just 1 week away in the robot nation of Robotia. The museum is unique because shortly after the museum closes, the building collapses into a flat plot of land and un-collapses prior to opening. Needless to say, any robot inside at the time of collapse will be destroyed. Normally, a wireless signal informing robots inside the structure of the closing would allow ample time for all to leave safely. The problem is that some robots may experience interference from all the exhibits and may not get the signal.

Fortunately, museum employee bots can also deliver the signal via direct interface, although this requires close range. The museum director is cheap, and only wants to hire 2 bots for each of the 4 sections (lined up in a row A,B,C,D) and has set up an automatic collapse system (to prevent robber bots from bribing their way in after hours). Wanting to avoid lawsuits, the director wants to know how long to set the timer after closing in order to ensure every robot (including the employees) is out of the building.

The following facts are known about the closing procedure:

  1. There will be at most 100 visitors still in the museum at closing time (everyone else has chronometers and leaves by then)
  2. The visitors are distributed throughout each of the 4 buildings, although each has at least 2 visitors.
  3. Each building has at least 1 visitor who receives the signal, and at least 1 who does not. All employees receive the signal.
  4. Any visitor who receives the signal proceeds immediately to the exit (at the front of A).
  5. Any visitor who does not receive the signal remains in place until an employee delivers it.
  6. It takes any robot 10 seconds to leave a building, regardless of where in the building they are (i.e. it takes 10 seconds to go from D to C, C to B, etc, and 10 seconds to go from A to the exit)
  7. Ten seconds after closing, the workers begin clearing robots within their building, taking a route such that every second, 1 visitor per employee receives the closing message (which takes negligible time).
  8. Once a building is clear of visitors, it takes the workers 10 seconds to verify that everyone is gone.
  9. When D is clear and verified, the workers from D move to C; once C is clear the 4 workers move to B, and so on.
  10. If A, B, or C clear first, 1 robot may go assist any other building; the other must stay behind to direct robots to the exit.
  11. The employees can coordinate to minimize the total time.

How long should the timer be set (to the nearest second) to ensure every robot is out, while minimizing the time the building stands empty?

  • $\begingroup$ I suppose the next relevant question is whether the building must be cleared and verified, or merely apparently 'clear' before workers leave to assist in other buildings. If the former, I'm not sure that the workers from A to C will ever go to D. $\endgroup$ – James Gryphon Jun 19 '18 at 19:00

We need to find the greatest amount of time that can be spent inside the building. The big bottlenecks are travel time and employee cleared-room verification time. So, a worst-case scenario should be generated that stacks it in such a way so as to require as much travel time and waste as much employee time as possible. At 0 seconds, the layout could look something like this:
(Leaving visitors/stationary visitors/employees)
1/1/2 - 1/1/2 - 1/1/2 - 1/93/2
At 0 seconds, 1 visitor in each room gets the closing time message and begins to leave. For the purpose of generating the longest possible time, we will assume that all other visitors didn't get the message. The aware visitors begin leaving the building. 1 visitor leaves building A and so on.
10 seconds after - 1/1/2 - 1/1/2 - 1/1/2 - 0/93/2
Employees begin delivering closing messages. This begins a mass exodus from building D, while buildings A, B and C are less dramatically affected. Employee processing time is wasted in this case due to the uneven allotment of visitors to employees -- in a better-case scenario, time might be saved starting here.
20 seconds - 2/2 - 2/2 - 1/2 - 20/73/2
Some visitors have started to leave, but are not actually gone from their rooms yet, less than ten seconds having elapsed since becoming aware of closing time. These are grouped with newly arrived 'leaving robots' here. With all visitors in A, B and C leaving, spare employee bots can now begin the trek to room D.
30 seconds - 2/1 - 1/2 - 20/2 - 20/53/3
40 seconds - 1/1 - 20/1 - 20/2 - 30/13/4
50 seconds - 20/1 - 20/1 - 30/1 - 13/5
After this point, only leaving visitors and employees remain.
60 seconds - 20/1 - 30/1 - 13/1 - 5v
The five employees in building D begin verifying that it is empty.
70 seconds - 30/1 - 13/1 - 1v - 5l
Having done that, they begin to leave.
80 seconds - 13/1 - 1v - 6l - D
90 seconds - 1v - 7l - C - D
100 seconds - 8l - B - C - D
By 110 seconds, if this thinking is correct, the building should be cleared out.

  • $\begingroup$ The formatting in the spoiler tags as of the time I first posted this is horrible. I mean to try to improve it, but any help I can get would definitely be appreciated. $\endgroup$ – James Gryphon Jun 19 '18 at 10:03
  • $\begingroup$ 2 issues I will clarify. First, the intent behind 7 is that the worker-bots don't do anything until 10 seconds have passed. Second, 10 means that no workers can leave until every visitor is heading towards the exit. 11 is intended to indicate coordination with where the workers go once their building is "clear". Apologies for the confusion. $\endgroup$ – Saladani Jun 19 '18 at 12:33
  • $\begingroup$ Updated it a bit; hopefully this one correctly accounts for the logic in play! $\endgroup$ – James Gryphon Jun 19 '18 at 15:08

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.