Daily Challenge #25 - Double Cola

Today's otherworldly soda machine comes from AlexIsHappy on CodeWars.

Sheldon, Leonard, Penny, Rajesh and Howard are in the queue for a "Double Cola" drink vending machine; there are no other people in the queue. The first one in the queue (Sheldon) buys a can, drinks it and doubles! The resulting two Sheldons go to the end of the queue. Then the next in the queue (Leonard) buys a can, drinks it and gets to the end of the queue as two Leonards, and so on.

Write a program that will return the name of the person who will drink the n-th cola.

For example, Penny drinks the third can of cola and the queue will look like this: Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny

The input data will consist of an array containing at least one name and a single integer n. Return the single line - the name of the person who drinks the n-th can of cola. The cans are numbered starting from 1.

who_is_next(["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], 1) == "Sheldon"
who_is_next(["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], 52) == "Penny"
who_is_next(["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], 7230702951) == "Leonard"

What a weird queue, this one's pretty different from some of the other challenges.
Good luck!

---

Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge for a future post? Email [e-mail] with your suggestions!

Comments

[Avalander]

Naïve implementation in Haskell.

who_is_next :: [String] -> Int -> String
who_is_next names i
  | length names >= i = names!!(i - 1)
  | otherwise         = who_is_next new_names (i - 1)
  where
    (x:rest) = names
    new_names = rest ++ [x, x]

[Corey Alexander]

@thepracticaldev We already did this one as number 17 in the series!

dev.to/thepracticaldev/daily-chall...

[La blatte]

Had to do a few tweaks to allow large numbers to be used as index:

const whoIsNext = (queue, index) => {
  queue = queue.map(e=>[e,1]);
  let qi = 0, j = 0;
  while (j < index) {
    j += queue[qi][1]*=2;
    qi = (qi+1) % queue.length;
  }
  return queue[(queue.length+qi-1)%queue.length][0];
}

Instead of pushing values in a large array, everything is stored in a 2-dimensional one:

whoIsNext(["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"], 7230702951)
"Leonard"

// "queue" will store the following value in the end:
[["Sheldon", 1073741824],
 ["Leonard", 1073741824],
 ["Penny", 536870912],
 ["Rajesh", 536870912],
 ["Howard", 536870912]]

[willsmart]

Completely untested one written on a phone in js.
I’m guessing this’ll work 🙏🏻

Edit: mostly did work 🙌. Couple of minor tweaks after testing on kata

function whoIsNext(names, r){
  // index is 1-based, arrays are 0-based
  r = r - 1; 

  while (r >= names.length) {
    r = Math.floor((r - names.length) / 2);
  }
  return names[r];
}

[willsmart]

Here's a bit of explanation and a rewrite to make the code block look less like I'm trying to be confusing.

First thing to note is that the ordinal value is 1-based -- i.e. drinkerNameAtOrdinal([Bert,Ernie], 1) is Bert, not Ernie. We usually deal with arrays as 0-based so to make out lives easier we may as well subtract one from the ordinal to get an index for the rest of the algorithm.

Given the two drinkers, here's who turns up to the machine (and calling each cycle of all the names as a "round"):

<< round 1
0:Bert
1:Ernie

<< round 2
2:Bert
3:Bert
4:Ernie
5:Ernie

<< round 3
6:Bert
7:Bert
8:Bert
9:Bert
10:Ernie
11:Ernie
12:Ernie
13:Ernie

<< round 4
14:Bert
15:Bert
16:Bert
17:Bert
18:Bert
19:Bert
20:Bert
21:Bert
22:Ernie
23:Ernie
24:Ernie
25:Ernie
26:Ernie
27:Ernie
28:Ernie
29:Ernie
...

Grouping things to show the pattern more clearly:
<< round 1
0: Bert
1: Ernie

<< round 2
2: 2 x Bert
4: 2 x Ernie

<< round 3
6: 4 x Bert
10: 4 x Ernie

<< round 4
14: 8 x Bert
22: 8 x Ernie
...

So each round, the same names are in the same order, but each name is written twice as many times.
The code takes advantage of how this <1,1,2,2,4,4,8,8,16,16,32,32,64,...> pattern is self-similar.

Let's say we have an index drinkerIndex for some drinker that is after the first round, then we subtract 2 to rebase the index from the time the first best and Ernie have had their sodas.

roundTwoDrinkerIndex = drinkerIndex - 2

The pattern as far as this new index is concerned looks like this:
<2,2,4,4,8,8,16,16,32,32,64,64,128,...>

Which is just like the first round's task, but with indexes that are twice as finely-grained.
If we divide that index in two, we'll be pointing to a drinker from the previous round, the one who spawned the one we're aiming for.

So the code just bounces along finding the index of each successive clone's parent, until it gets to an index in the first round which is easily dealt with.

Here's a marked up algorithm (recursive this time to show the self-similar thing more clearly):

function drinkerNameAtOrdinal(drinkerNamesArray, drinkerOrdinal) {
  return drinkerNameAtIndex(drinkerOrdinal - 1);

  function drinkerNameAtIndex(drinkerIndex) {
    // base case: if the ordinal is in the first round, just return that name
    if (drinkerIndex < drinkerNamesArray.length) return drinkerNamesArray[drinkerIndex];

    // If the drinker isn't in the first round, rebase the index to refer to an
    //   equivalent drinker from the previous round, and solve for that.
    const indexBasedOffSecondRound = drinkerIndex - drinkerNamesArray.length;
    const equivDrinkerIndexInPreviousRound = Math.floor(indexBasedOffSecondRound/2);
    return drinkerNameAtIndex(equivDrinkerIndexInPreviousRound);
  }
}

[LBcoyote]

Pure mathematical solution in JS. For larger n's it can be faster than the loop version by roughly a factor of log₂ n.

function who_is_next(names,n){
    let p=2**Math.floor(Math.log2(1+--n/names.length))
    return names[Math.floor((n-(p-1)*names.length)/p)]
}

[Mat-R-Such]

Python

def who_is_next(names, r): 
    if len(names)>= r:
        return names[r-1]
    w= 5
    z=1
    while r:
        if (w+ (pow(2,z))* 5) >= r:
            for i in range(5):
                w+=pow(2,z)
                if  w >= r:
                    return names[i]
        else:
            z+=1
            w=w+ (pow(2,z-1))* 5