Double Cola Challenge, JavaScript code wrong?

Question

Five friends are drinking magic cola in an line. When the first friend drinks the cola he disappears, and multiplies into two copies! After that, those new copies go to the end of the line and the next friend drinks the magic cola, repeating the proccess.

For example, imagine we have the following friends:

[Sheldon, Leonard, Penny, Rajesh, Howard]

After Sheldon drinking the first cola, the line will look like this:

[Leonard, Penny, Rajesh, Howard, Sheldon, Sheldon]

After Leonard drinking the cola, the line gets like this:

[Penny, Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard]

And so on...

My objective is to write a function in JavaScript, that given an array with the names of the people in the line, and a number N, it will return the the name of the N-ith person drinking the magic cola.

So, for example, doing console.log(whoIsNext([Sheldon, Leonard, Penny, Rajesh, Howard], 1)) should return Sheldon.

To achieve this, I made this code:

function whoIsNext(names, r){
  var fistInLine;

  if(r <= names.length){
    return names[r-1];
  }else{

    while(r > names.length){
      fistInLine = names.shift();
      names.push(fistInLine, fistInLine);
    }
    return names[r-1];
  }
}

This function works well for the following case:

names = ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"];
Test.assertEquals(whoIsNext(names, 1), "Sheldon");

But it fails for the test:

names = ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"];
Test.assertEquals(whoIsNext(names, 52), "Penny");

And if I try with a really big number, like:

names = ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"];
Test.assertEquals(whoIsNext(names, 7230702951), "Leonard");

It doesn't even stop running (takes forever).

So obviously, my solution is not only incorrect, it seems to be inneficient as well. How can I fix it?

@epascarello Because it's not a simple queue - when removing from the front, the entry gets duplicated at the end. That's what makes it a harder puzzle. — James Thorpe, Apr 05 '16 at 14:22
Why not just take a mathematical approach? After all you always append twice the amount of names each time you went through everyone... There should be a clear pattern to be recognizable which could probably be calculated by getting the highest combination by a power of 2 lower than your checking number. From there calculate back until you get a number between 0 and 4 and get the index. Should have no need to calculate it all the way through. — Aides, Apr 05 '16 at 14:29
@JamesThorpe I dont need to decrement `r` because the length of teh array keeps growing. Eventually, `r` will be smaller than the array's length, and when that happens, I stop. — Flame_Phoenix, Apr 05 '16 at 14:30
@Aides I also thought about a mathematical pattern, but I completely suck at it. Do you have any suggestions? — Flame_Phoenix, Apr 05 '16 at 14:31
Currently at work, I'll look at it in about... 2 hours or so — Aides, Apr 05 '16 at 14:32
@Aides that will be worth kudos++. In fact, I am giving rep++ to you now for the initiave! — Flame_Phoenix, Apr 05 '16 at 14:41
@ÁlvaroGonzález The person who created the challenge. So I assume he is correct :D — Flame_Phoenix, Apr 05 '16 at 14:42
Is it online? Can we have access to tests or sample results or something? — Álvaro González, Apr 05 '16 at 15:07

Nina Scholz · Accepted Answer · 2016-04-05T15:31:12.763

A zero based recursive proposal which returns the index of the array, here with length base = 5.

                           1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3
number 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9
index  0 1 2 3 4 0 0 1 1 2 2 3 3 4 4 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 0 0 0 0 0

It become visible, the pattern is based on 5 and goes up for every round by factor 2.

5 -> 10- > 20 -> 40

Example of calculation

                Array after step
                0 1 2 3 4 5 6 7 8 9 
  0: 0 Sheldon  | 
  1: 1 Leonard  | |
  2: 2 Penny    | | |
  3: 3 Rajesh   | | | |
  4: 4 Howard   | | | | |
  5: 0 Sheldon    | | | | |
  6: 0 Sheldon    | | | | | |
  7: 1 Leonard      | | | | | |
  8: 1 Leonard      | | | | | | |
  9: 2 Penny          | | | | | |
 10: 2 Penny          | | | | | |
 11: 3 Rajesh           | | | | |
 12: 3 Rajesh           | | | | |
 13: 4 Howard             | | | |
 14: 4 Howard             | | | |
 15: 0 Sheldon              | | |
 16: 0 Sheldon              | | |
 17: 0 Sheldon                | |
 18: 0 Sheldon                | |
 19: 1 Leonard                  |
 20: 1 Leonard                  |
 21: 1 Leonard
 22: 1 Leonard

var friends = ['Sheldon', 'Leonard', 'Penny', 'Rajesh', 'Howard'],
    base = friends.length;

function getIndex(n, i) {
    i = i || base;
    if (n < i) {
        return Math.floor(n * base / i);
    }
    return getIndex(n - i, 2 * i);
}

var i = 0, index;

document.write(friends[getIndex(1 - 1)] + '<br>');          // "Sheldon"
document.write(friends[getIndex(52 - 1)] + '<br>');         // "Penny"
document.write(friends[getIndex(7230702951 - 1)] + '<hr>'); // "Leonard"

for (i = 0; i < 200; i++) {
    index = getIndex(i);
    document.write(i + ': ' + index + ' ' + friends[index] + '<br>');
}

Does your function take into account the fact that the first name is duplicated, while the others are not? — Flame_Phoenix, Apr 05 '16 at 15:11
Also, the array does not double the size every round. I don't see how it does that. It just goes up by 1 value. Think about it, you remove one value from the queue, and add 2. The total offset, is +1. The rest stays the same. So if the array has 5 names, after the first run, it will have 6, not 10! — Flame_Phoenix, Apr 05 '16 at 15:13

score 0 · Answer 2 · answered Apr 05 '16 at 16:36

Okay, here we go, this is a really simplistic approach and I'll come up with a better one (it's half way through my mind, I'll just have to fit it together)

function whoIsNext(names, index, multiplyFactor)
{
    var count = names.length;

    var fullLoops = 0;
    var currIndex = 0;

    while(currIndex <= index)
    {
        for(var i = 0; i < count; i++)
    {
            currIndex += Math.pow(multiplyFactor, fullLoops);
            if(currIndex > index)
            {
            return names[i];
            }
        }
        fullLoops++;
    }
}

The idea is that the amount the same person comes is doubled each time the people do a full loop (countPerson = Math.pow(2, countFullLoops)). If you then accumulate the amount of people before the set index until you reach the index, you then get the right person (I feel like I just explained a really easy thing really hard).

Also you can substitute any input (change the amount of people on start, change the multiplication factor (did someone say quadruple coke?)) as you want.

Double Cola Challenge, JavaScript code wrong?

2 Answers2