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
– James Thorpe, Commented Apr 5, 2016 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
– Aides, Commented Apr 5, 2016 at 14:29
Currently at work, I'll look at it in about... 2 hours or so — Aides
– Aides, Commented Apr 5, 2016 at 14:32

Nina Scholz · Accepted Answer · 2016-04-05 15:31:12Z

5

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>');
}

edited Apr 5, 2016 at 15:31

answered Apr 5, 2016 at 14:51

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Flame_Phoenix Over a year ago

Does your function take into account the fact that the first name is duplicated, while the others are not?

Flame_Phoenix Over a year ago

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!

Nina Scholz Over a year ago

@Flame_Phoenix, where do you see 10?

Flame_Phoenix Over a year ago

Ahhh, got it ! This is it!

Aides · Accepted Answer · 2016-04-05 16:36:55Z

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.

Collectives™ on Stack Overflow

Double Cola Challenge, JavaScript code wrong?

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related