[Community Puzzle] The helpdesk

Puzzles
#23

There is ALWAYS rounding when floating point is used. For example, 0.1 is a simple value in decimal but cannot be represented precisely in binary. If you repeatedly add 0.1 to itself, you will eventually diverge from hitting an integer every ten iterations. Assuming all platforms will round floating point the same way is bound to cause problems.

To ensure there is no rounding error at all, I used python’s Fraction package and computed all times as rational numbers with no rounding errors. When I do this, I cannot get it to pass both test 5 and test 6. I can get it to pass test 5 by assuming that a break that completes with no more visitors in line is not counted as a break. I can get it to pass test 6 by assuming that a break that completes after all visitors are being served but before all visitors are completely served is still counted as a break. I’m guessing passing the tests is dependent on peculiarities of rounding errors using floating point on a particular platform (single vs double precision perhaps)?

Here is the log output for test 5 when I assume terminal breaks are counted:

     0.000: Counter(0): Starting helping visitor 0, 50 standard minutes (50 minutes with efficiency 1)
     0.000: Counter(1): Starting helping visitor 1, 50 standard minutes (100 minutes with efficiency 1/2)
     0.000: Counter(2): Starting helping visitor 2, 10 standard minutes (13 1/3 minutes with efficiency 3/4)
     0.000: Counter(3): Starting helping visitor 3, 50 standard minutes (40 minutes with efficiency 1 1/4)
     0.000: Counter(4): Starting helping visitor 4, 30 standard minutes (20 minutes with efficiency 1 1/2)
     0.000: Counter(5): Starting helping visitor 5, 20 standard minutes (20 minutes with efficiency 1)
    13.333: Counter(2): Finished helping visitor 2
    13.333: Counter(2): Starting helping visitor 6, 60 standard minutes (80 minutes with efficiency 3/4)
    20.000: Counter(4): Finished helping visitor 4
    20.000: Counter(4): Starting a break for 10 minutes
    20.000: Counter(5): Finished helping visitor 5
    20.000: Counter(5): Starting a break for 10 minutes
    30.000: Counter(4): Finished a break, next break at 50
    30.000: Counter(4): Starting helping visitor 7, 30 standard minutes (20 minutes with efficiency 1 1/2)
    30.000: Counter(5): Finished a break, next break at 50
    30.000: Counter(5): Starting helping visitor 8, 40 standard minutes (40 minutes with efficiency 1)
    40.000: Counter(3): Finished helping visitor 3
    40.000: Counter(3): Starting a break for 10 minutes
    50.000: Counter(0): Finished helping visitor 0
    50.000: Counter(0): Starting a break for 10 minutes
    50.000: Counter(3): Finished a break, next break at 70
    50.000: Counter(3): Starting helping visitor 9, 40 standard minutes (32 minutes with efficiency 1 1/4)
    50.000: Counter(4): Finished helping visitor 7
    50.000: Counter(4): Starting a break for 10 minutes
    60.000: Counter(0): Finished a break, next break at 80
    60.000: Counter(0): Starting helping visitor 10, 60 standard minutes (60 minutes with efficiency 1)
    60.000: Counter(4): Finished a break, next break at 80
    60.000: Counter(4): Starting helping visitor 11, 60 standard minutes (40 minutes with efficiency 1 1/2)
    70.000: Counter(5): Finished helping visitor 8
    70.000: Counter(5): Starting a break for 10 minutes
    80.000: Counter(5): Finished a break, next break at 100
    80.000: Counter(5): Starting helping visitor 12, 50 standard minutes (50 minutes with efficiency 1)
    82.000: Counter(3): Finished helping visitor 9
    82.000: Counter(3): Starting a break for 10 minutes
    92.000: Counter(3): Finished a break, next break at 112
    92.000: Counter(3): Starting helping visitor 13, 10 standard minutes (8 minutes with efficiency 1 1/4)
    93.333: Counter(2): Finished helping visitor 6
    93.333: Counter(2): Starting a break for 10 minutes
   100.000: Counter(1): Finished helping visitor 1
   100.000: Counter(1): Starting a break for 10 minutes
   100.000: Counter(3): Finished helping visitor 13
   100.000: Counter(3): Starting helping visitor 14, 10 standard minutes (8 minutes with efficiency 1 1/4)
   100.000: Counter(4): Finished helping visitor 11
   100.000: Counter(4): Starting a break for 10 minutes
   103.333: Counter(2): Finished a break, next break at 123 1/3
   103.333: Counter(2): Starting helping visitor 15, 10 standard minutes (13 1/3 minutes with efficiency 3/4)
   108.000: Counter(3): Finished helping visitor 14
   108.000: Counter(3): Starting helping visitor 16, 50 standard minutes (40 minutes with efficiency 1 1/4)
   110.000: Counter(1): Finished a break, next break at 130
   110.000: Counter(1): Starting helping visitor 17, 10 standard minutes (20 minutes with efficiency 1/2)
   110.000: Counter(4): Finished a break, next break at 130
   110.000: Counter(4): Starting helping visitor 18, 20 standard minutes (13 1/3 minutes with efficiency 1 1/2)
   116.667: Counter(2): Finished helping visitor 15
   116.667: Counter(2): Starting helping visitor 19, 70 standard minutes (93 1/3 minutes with efficiency 3/4)
   120.000: Counter(0): Finished helping visitor 10
   120.000: Counter(0): Starting a break for 10 minutes
   123.333: Counter(4): Finished helping visitor 18
   123.333: Counter(4): Starting helping visitor 20, 10 standard minutes (6 2/3 minutes with efficiency 1 1/2)
   130.000: Counter(0): Finished a break, next break at 150
   130.000: Counter(0): Starting helping visitor 21, 40 standard minutes (40 minutes with efficiency 1)
   130.000: Counter(1): Finished helping visitor 17
   130.000: Counter(1): Starting a break for 10 minutes
   130.000: Counter(4): Finished helping visitor 20
   130.000: Counter(4): Starting a break for 10 minutes
   130.000: Counter(5): Finished helping visitor 12
   130.000: Counter(5): Starting a break for 10 minutes
   140.000: Counter(1): Finished a break, next break at 160
   140.000: Counter(1): Starting helping visitor 22, 10 standard minutes (20 minutes with efficiency 1/2)
   140.000: Counter(4): Finished a break, next break at 160
   140.000: Counter(4): Starting helping visitor 23, 40 standard minutes (26 2/3 minutes with efficiency 1 1/2)
   140.000: Counter(5): Finished a break, next break at 160
   140.000: Counter(5): Starting helping visitor 24, 60 standard minutes (60 minutes with efficiency 1)
   148.000: Counter(3): Finished helping visitor 16
   148.000: Counter(3): Starting a break for 10 minutes
   158.000: Counter(3): Finished a break, next break at 178
   158.000: Counter(3): Starting helping visitor 25, 40 standard minutes (32 minutes with efficiency 1 1/4)
   160.000: Counter(1): Finished helping visitor 22
   160.000: Counter(1): Starting a break for 10 minutes
   166.667: Counter(4): Finished helping visitor 23
   166.667: Counter(4): Starting a break for 10 minutes
   170.000: Counter(0): Finished helping visitor 21
   170.000: Counter(0): Starting a break for 10 minutes
   170.000: Counter(1): Finished a break, next break at 190
   170.000: Counter(1): Starting helping visitor 26, 40 standard minutes (80 minutes with efficiency 1/2)
   176.667: Counter(4): Finished a break, next break at 196 2/3
   176.667: Counter(4): Starting helping visitor 27, 40 standard minutes (26 2/3 minutes with efficiency 1 1/2)
   180.000: Counter(0): Finished a break, next break at 200
   180.000: Counter(0): Starting helping visitor 28, 20 standard minutes (20 minutes with efficiency 1)
   190.000: Counter(3): Finished helping visitor 25
   190.000: Counter(3): Starting a break for 10 minutes
   200.000: Counter(0): Finished helping visitor 28
   200.000: Counter(0): Starting a break for 10 minutes
   200.000: Counter(3): Finished a break, next break at 220
   200.000: Counter(3): Starting helping visitor 29, 70 standard minutes (56 minutes with efficiency 1 1/4)
   200.000: Counter(5): Finished helping visitor 24
   200.000: Counter(5): No more visitors, counter shutting down
   203.333: Counter(4): Finished helping visitor 27
   203.333: Counter(4): No more visitors, counter shutting down
   210.000: Counter(0): Finished a break, next break at 230
   210.000: Counter(0): No more visitors, counter shutting down
   210.000: Counter(2): Finished helping visitor 19
   210.000: Counter(2): No more visitors, counter shutting down
   250.000: Counter(1): Finished helping visitor 26
   250.000: Counter(1): No more visitors, counter shutting down
   256.000: Counter(3): Finished helping visitor 29
   256.000: Counter(3): No more visitors, counter shutting down
4 4 4 7 7 4
4 3 1 4 5 3

Here is the log for test 6 when I assume that such terminal breaks are not counted:

     0.000: Counter(0): Starting helping visitor 0, 30 standard minutes (60 minutes with efficiency 1/2)
     0.000: Counter(1): Starting helping visitor 1, 40 standard minutes (53 1/3 minutes with efficiency 3/4)
     0.000: Counter(2): Starting helping visitor 2, 30 standard minutes (30 minutes with efficiency 1)
     0.000: Counter(3): Starting helping visitor 3, 40 standard minutes (32 minutes with efficiency 1 1/4)
     0.000: Counter(4): Starting helping visitor 4, 60 standard minutes (120 minutes with efficiency 1/2)
    30.000: Counter(2): Finished helping visitor 2
    30.000: Counter(2): Starting a break for 10 minutes
    32.000: Counter(3): Finished helping visitor 3
    32.000: Counter(3): Starting a break for 10 minutes
    40.000: Counter(2): Finished a break, next break at 60
    40.000: Counter(2): Starting helping visitor 5, 10 standard minutes (10 minutes with efficiency 1)
    42.000: Counter(3): Finished a break, next break at 62
    42.000: Counter(3): Starting helping visitor 6, 30 standard minutes (24 minutes with efficiency 1 1/4)
    50.000: Counter(2): Finished helping visitor 5
    50.000: Counter(2): Starting helping visitor 7, 40 standard minutes (40 minutes with efficiency 1)
    53.333: Counter(1): Finished helping visitor 1
    53.333: Counter(1): Starting a break for 10 minutes
    60.000: Counter(0): Finished helping visitor 0
    60.000: Counter(0): Starting a break for 10 minutes
    63.333: Counter(1): Finished a break, next break at 83 1/3
    63.333: Counter(1): Starting helping visitor 8, 10 standard minutes (13 1/3 minutes with efficiency 3/4)
    66.000: Counter(3): Finished helping visitor 6
    66.000: Counter(3): Starting a break for 10 minutes
    70.000: Counter(0): Finished a break, next break at 90
    70.000: Counter(0): Starting helping visitor 9, 20 standard minutes (40 minutes with efficiency 1/2)
    76.000: Counter(3): Finished a break, next break at 96
    76.000: Counter(3): Starting helping visitor 10, 60 standard minutes (48 minutes with efficiency 1 1/4)
    76.667: Counter(1): Finished helping visitor 8
    76.667: Counter(1): Starting helping visitor 11, 30 standard minutes (40 minutes with efficiency 3/4)
    90.000: Counter(2): Finished helping visitor 7
    90.000: Counter(2): Starting a break for 10 minutes
   100.000: Counter(2): Finished a break, next break at 120
   100.000: Counter(2): Starting helping visitor 12, 40 standard minutes (40 minutes with efficiency 1)
   110.000: Counter(0): Finished helping visitor 9
   110.000: Counter(0): Starting a break for 10 minutes
   116.667: Counter(1): Finished helping visitor 11
   116.667: Counter(1): Starting a break for 10 minutes
   120.000: Counter(0): Finished a break, next break at 140
   120.000: Counter(0): Starting helping visitor 13, 70 standard minutes (140 minutes with efficiency 1/2)
   120.000: Counter(4): Finished helping visitor 4
   120.000: Counter(4): Starting a break for 10 minutes
   124.000: Counter(3): Finished helping visitor 10
   124.000: Counter(3): Starting a break for 10 minutes
   126.667: Counter(1): Finished a break, next break at 146 2/3
   126.667: Counter(1): Starting helping visitor 14, 20 standard minutes (26 2/3 minutes with efficiency 3/4)
   130.000: Counter(4): Finished a break, next break at 150
   130.000: Counter(4): Starting helping visitor 15, 60 standard minutes (120 minutes with efficiency 1/2)
   134.000: Counter(3): Finished a break, next break at 154
   134.000: Counter(3): Starting helping visitor 16, 10 standard minutes (8 minutes with efficiency 1 1/4)
   140.000: Counter(2): Finished helping visitor 12
   140.000: Counter(2): Starting a break for 10 minutes
   142.000: Counter(3): Finished helping visitor 16
   142.000: Counter(3): Starting helping visitor 17, 70 standard minutes (56 minutes with efficiency 1 1/4)
   150.000: Counter(2): Finished a break, next break at 170
   150.000: Counter(2): Starting helping visitor 18, 10 standard minutes (10 minutes with efficiency 1)
   153.333: Counter(1): Finished helping visitor 14
   153.333: Counter(1): Starting a break for 10 minutes
   160.000: Counter(2): Finished helping visitor 18
   160.000: Counter(2): Starting helping visitor 19, 20 standard minutes (20 minutes with efficiency 1)
   163.333: Counter(1): Finished a break, next break at 183 1/3
   163.333: Counter(1): Starting helping visitor 20, 40 standard minutes (53 1/3 minutes with efficiency 3/4)
   180.000: Counter(2): Finished helping visitor 19
   180.000: Counter(2): Starting a break for 10 minutes
   190.000: Counter(2): Finished a break, next break at 210
   190.000: Counter(2): Starting helping visitor 21, 51 standard minutes (51 minutes with efficiency 1)
   198.000: Counter(3): Finished helping visitor 17
   198.000: Counter(3): Starting a break for 10 minutes
   208.000: Counter(3): Finished a break, next break at 228
   208.000: Counter(3): Starting helping visitor 22, 60 standard minutes (48 minutes with efficiency 1 1/4)
   216.667: Counter(1): Finished helping visitor 20
   216.667: Counter(1): Starting a break for 10 minutes
   226.667: Counter(1): Finished a break, next break at 246 2/3
   226.667: Counter(1): Starting helping visitor 23, 40 standard minutes (53 1/3 minutes with efficiency 3/4)
   241.000: Counter(2): Finished helping visitor 21
   241.000: Counter(2): Starting a break for 10 minutes
   250.000: Counter(4): Finished helping visitor 15
   250.000: Counter(4): Starting a break for 10 minutes
   251.000: Counter(2): Finished a break, next break at 271
   251.000: Counter(2): Starting helping visitor 24, 20 standard minutes (20 minutes with efficiency 1)
   256.000: Counter(3): Finished helping visitor 22
   256.000: Counter(3): No more visitors, counter shutting down
   260.000: Counter(0): Finished helping visitor 13
   260.000: Counter(0): No more visitors, counter shutting down
   260.000: Counter(4): Break finished with no more visitors, not counting as break, counter shutting down
   271.000: Counter(2): Finished helping visitor 24
   271.000: Counter(2): No more visitors, counter shutting down
   280.000: Counter(1): Finished helping visitor 23
   280.000: Counter(1): No more visitors, counter shutting down
3 6 8 6 2
2 4 5 4 1

I’m happy to implement whatever policy you intended, but I’m having a hard time reverse engineering your intent. Any thoughts?

#24

Ah your log is extremely helpful, nice work. And, let me start off with saying this contribution makes me think of a real life helpdesk: while designing it I thought ‘how hard can it be’, but when in use, all kind of artifacts appear that others can disagree with or misunderstand.

Anyway, you are almost there: case 5 you have too much breaks, case 6 too little. Indeed, terminal breaks should not be counted, but a break is only a terminal break if it starts at the same moment the last visitor is being served (not if the break starts before a last visitor is being served). It has to do with the following part of the statement:

  • All counters take new visitors or breaks until there are no visitors left waiting, and finish with any visitor or break they started on. A counter will never start a break at the same moment the last visitor starts being served at another counter.

Case 5
At minute 200, counters 0 and 5 are just finished helping a visitor (and are allowed a break), while counter 3 is just finished with a break. There is one visitor (29) in line. Counters 0 and 5 would start on a break before helping this visitor - but counter 3 starts helping this visitor at minute 200. The case A counter will never start a break at the same moment the last visitor starts being served is true here: at minute 200 the last visitor starts at counter 3, so counters 0 and 5 do not start their break.
Actually, your current case 5 implementation is inconsistent: you allow counter 0 to start a break at minute 200, but you do not allow counter 5 to do so.

Case 6
At minute 250, counter 4 is finished helping visitor 15. At that moment, there is still a visitor waiting to be helped (24). All counters take new visitors or breaks until there are no visitors left waiting → there is still a visitor waiting, so counter 4 will take on a break. The case A counter will never start a break at the same moment the last visitor starts being served is not true here, because at minute 250, visitor 24 cannot be served by any other counter. So, counter 4 starts its break, and will finish any break it started on. Hence, counter 4 takes one more break (for a total of 2 breaks, instead of the 1 your code gives). (one minute later, at minute 251, the final visitor can move to a counter)

Rationale
I do think this interpretation makes sense: in case 5 John and Jack from counters 0 and 5 are thinking about coffee and putting their sign to ‘unavailable’, but at that moment they see the last visitor disappearing from the line (to Julia at counter 3). So, they think, what the heck, I can go home.
At case 6, Tim from counter 4 really needs to go to the toilet after helping this slow customer (120 minutes!). There is still a visitor in line, but he is allowed a break, so he turns his sign to ‘unavailable’ and runs to the breakroom. He comes back ten minutes later to find out the final visitor is served while he was on the toilet. He did take a break.

1 Like
#25

Wow, thank you very much for such a thoughtful and complete response–way beyond my expectations. Your explanation led me directly to my mistake: I had incorrectly interpreted “When multiple counters are available, the first visitor in line will go to the first available counter, the second to the second, etcetera.” to mean that for a given point in time, ALL state transitions are processed in order of counter #, including transitions to “on-break”. I simply added a “priority” field to my priority queue, and prioritized (for a given point in time) counters that will accept another visitor over counters that with go on-break. So sort order is now (<lowest-time>, <workers-before-breakers>, <lowest-counter-#>). It now passes all tests.

Again, thank you very much for the time you put into a thoughtful response!

1 Like