DEV Community

Discussion on: Daily Challenge #25 - Double Cola

Collapse
 
willsmart profile image
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);
  }
}