Alex Bligh's blog

•

Algorithm puzzle: Elves, Cakes and Gremlins

A locker room contains a number of lockers (L), and a number of elves (E). The elves are attempting to put cakes in the lockers, cake by cake, to feed cake-eating gremlins (obviously) that have access to the lockers through a rear door. We can assume E << L, and that some external entity is regulating the supply of cake and rate of cake consumption.

Your algorithm is repeatedly asked to find an empty locker, and place a cake in it. The cake is eaten some time later (unknown to you) by a gremlin.

Each elf may open any locker to see whether it it has a cake in, but opening and checking the locker is a time consuming process. Further, whilst one elf is opening and checking the locker, other elves may be checking (and filling) other lockers. If a one elf attempts to open a locker, and another attempts to open the same one, they are queued (i.e. assume there is a locker-specific mutex on each locker).

What is the most efficient way (i.e. requiring the least average number of locker checks) to find a free locker?

A reasonable strategy would simply be to pick a locker at random, and if it already has a cake in it, pick another. This tends to perform badly when nearly all the lockers have cakes in, as any given full locker may be tried several times before an empty one is found. Specifically, the maximum number of attempts to find a free locker is (technically) infinite, meaning it’s impossible to put an upper bound on the time taken to find an empty locker. And I’m after consistent low-latency cake placement.

Another reasonable strategy would be to pick a locker at random, and if it’s full try the next one along. However, this creates ‘bunching’ of full lockers – contiguous lockers all full of cake. If a subsequent elf picks one in this line, he’ll have to work his way right to the end of it before finding a free locker.

To avoid this being too easy, I’ve introduced three additional restrictions:

  1. I’ve switched the lights off and forbade the elves to talk, so they can’t tell what each other are doing. We have no IEC (inter elf communication).
  2. We can assume the number of lockers is sufficiently large and the elves sufficiently forgetful that no elf can remember what lockers it’s tried, let alone anything about its last attempt to place a cake.
  3. Assuming there is at least one locker that remains empty throughout an elf’s attempt to find a free locker, it must find that empty locker in no more than L attempts.

I have what I believe is a reasonable solution to this which appears to work in practice. I’ll post this in a few days. In the mean time, I’d be interested in other ideas in the comments below.

Addition based on comments off-line: you can assume that it takes much longer for a gremlin to eat a cake than it takes for an elf to check all the lockers.

16 responses to “Algorithm puzzle: Elves, Cakes and Gremlins”

  1. Paul M Avatar
    Paul M

    what are we allowed to know about G, the number of gremlins and the rate at which they empty lockers?

    if G is small but gremlins are quick, quicker generally than elves filling lockers, then we can have less lockers as not too many will be full except at peak times.
    if G is small and gremlins are slow, locker occupancy will be high, and we could see elves having to wait.

    Are we allowed to know the delay in finding an empty locker and trying another? If it’s relatively long, and locker occupancy is generally low, then it might be worth simply having an elf pause and retry the same locker?

    Reply
    1. Alex Bligh Avatar
      Alex Bligh

      I don’t think the elves know about the gremlins, at least quantitively. They just know they have to put cakes in empty lockers. Sometimes the lockers can be in general full, and sometimes the lockers can be in general empty, but they don’t know whether that’s more gremlins, or gremlins increasing their appetite.

      I think though it’s reasonable to assume that the time taken for a gremlin to remove and eat a cake is much longer than the time taken to check a locker. If a cake disappeared almost as soon as it was put in, the problem would be pretty trivial. We can thus assume there’s some locker contention. As you say, the elf could merely pause and retry if there were not.

      Reply
  2. Mark Avatar
    Mark

    One simple solution to the bunching problem is for each elf, instead of going to the next locker when encountering a full one, to go N lockers along, with N being different for each elf.

    A drawback of this is that if N, for any given elf, is a divisor of L, then the elf will rotate round the same subset of lockers and may never reach an empty one. So, while it ensures that every empty locker will be found by an elf, it cannot guarantee that any given elf will find an empty locker. That breaks rule three.

    To maintain rule 3 compatibility, therefore, N needs to be variable. Probably the simplest way of doing that is for N to be N++ each time the elf passes (or lands on) the first locker.

    Reply
  3. Ben Curthoys Avatar
    Ben Curthoys

    I think it might be easier to find answers if the puzzle were phrased as a more traditional telephone switchboard, with calls that last for random lengths of time and need to be assigned a circuit.

    Also, given the number of things that the elves don’t know and can’t remember, it’s really a question of probability, not algorithms.

    When the gremlins eat cake faster than the elves deliver cake then most of the lockers will be empty (the average call duration and arrival rates are such that the average number of new calls that arrive in the duration of a call is less than one, and most of the circuits are clear), and the “start random, move next” approach is fine. The bunches are broken up by calls ending / cakes being eaten.

    When the elves deliver cake faster than the gremlins can eat it, most of the lockers are going to be full, and finding 1 free locker amongst all the the full ones is always going to be slow. If your lockers are 99% full, it’s probably ok to drop the cake.

    The more interesting question is: for a given cake arrival rate and eating time in the busiest hour of the day, how many lockers do I need to ensure that every cake has somewhere to be put? Mr Erlang is your friend there.

    Reply
    1. Alex Bligh Avatar
      Alex Bligh

      Well if you modify the problem, it will tend to get easier. In the telephone system you suggest, you don’t care about the upper bound on latency to place a call, and you don’t care if you drop calls when your lockers are 99% full. So you can simply hunt across the available lockers. That’s a poor solution to my puzzle, though I’m sure it’s fine for telephone call placing where opening the lockers (or determining whether a trunk is in use) is not expensive.

      Reply
  4. Ben Curthoys Avatar
    Ben Curthoys

    Plus:

    If a one elf attempts to open a locker, and another attempts to open the same one, they are queued (i.e. assume there is a locker-specific mutex on each locker).

    is a stupid system. There is absolutely no point in the 2nd elf queuing, as it will ALWAYS find the locker full. Either the first elf found the locker empty, and then filled it with cake, or the first elf found the locker full. Either way, the locker is full of cake now. If a locker is being checked by another elf, then you can safely skip over it.

    Reply
    1. Alex Bligh Avatar
      Alex Bligh

      It may be a stupid system for phone calls, but that’s actually how the relevant bit of technology works. There’s no ‘trylock(er)’ function which allows an elf to determine whether a locker is already being tested by another elf, so if it is, he merely has to wait longer.

      Again, if you modify the puzzle to get rid of ‘the annoying stupid bits’ it will get easier!

      Reply
  5. Tom H Avatar
    Tom H

    That an elf can pick a locker at random, suggests that each elf has knowledge of at least of the number of lockers n. (or how do you select a random integer from between 1 and n?)

    So as an increment to Marks N+x incremental solution… I would suggest that

    1) elf picks a locker at random
    2) if the locker is full on try i, then move along floor(n/i) lockers and try that.
    3) loop back to the beginning if moving along n/i is past the end of the line of lockers
    4) move along 1, if n/i < 1 (so eventually checking all N lockers

    Reply
    1. Alex Bligh Avatar
      Alex Bligh

      Yes, we can assume the each elf knows the number of lockers N.

      Reply
  6. Tom H Avatar
    Tom H

    Ah, I see that you have already defined the number of lockers as L.

    Reply
  7. Tom H Avatar
    Tom H

    Or probably better would be to halve the increment each time so move along L/(2^i) each time its full, otherwise you might be taking a while to get down to a suitably granular check, if L was very large.

    Reply
  8. Tom H Avatar
    Tom H

    Actually not, because you would only check thoroughly the last bit…before checking all the first half with increments of 1… ummm. maybe I should think this through before posting any more rambling comments.. 😉

    Reply
  9. Tom H Avatar
    Tom H

    I would round L up to the nearest 2^n integer. Then draw out a matrix with sides each 2^(n-1) and map lockers 1 to L, to the first L elements of the matrix… (1,1),(1,2)…..(x,y), possibly leaving some blanks. (assuming that the elves don’t need time to check the non-existence of the lockers in the part of the grid mapped to >L).

    Then you have a squared grid with sides of a base-2, which can be divided into segments as many times down as you wish until you have just individual points.

    Reply
  10. Tom H Avatar
    Tom H

    You can then systematically take a sample from each segment, and loop to the start again, until you exhaust all the elements in each segment.

    Reply
  11. Tom H Avatar
    Tom H

    Oops, I was assuming there that the 2**n numbers were also squared numbers, which is stoopid.

    So you would end up with some sort of oblong grid with sides base-2, but it would give you a trivial method to exhaustively sample the space

    Reply
  12. Tom H Avatar
    Tom H

    OK, map it to the next highest 2^2n integer, would give a square binary number, and hence a 2n by 2n square grid would be the sample space. A “segment” size S=1 would sample exhaustively, but never “skip”, as there would be a segment per locker, and also the same for S=2n, where the segment would be the full square. I think the idea method would be to have as many segments as elves, and randomly scatter the elves starting across the grid, (but there would be no way to estimate those, except by “customer feedback” from the gremlins and their cake consumption)

    Reply

Leave a Reply

Discover more from Alex Bligh's blog

Subscribe now to keep reading and get access to the full archive.

Continue reading