DoubleCola.md

Description:

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.

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

Rajesh, Howard, Sheldon, Sheldon, Leonard, Leonard, Penny, Penny Write a program that will return the name of the person who will drink the n-th cola.

Input

The input data consist of an array which contains at least 1 name, and single integer n.

1  ≤  n  ≤  1000000000

Output / Examples

Return the single line — the name of the person who drinks the n-th can of cola. The cans are numbered starting from 1.

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

Finally, the fastest solution

  /**
   * As I was writing the first solution, already thinking at the second one,
   * I had to debug my code a bit.
   * When printing the output of each iterations, a pattern was quite easily visible.
   * 
   * Even if I wanted to solve this problem with a "loop style" and this RLE algorithm,
   * the blueprint of a kinda `O(1)` algorithm was getting clearer and clearer.
   * 
   * As each group of clones within the queue, eventually sums up to a power of 2
   * hence, on every iteration that is a power of 2, all the groups are even.
   * 
   * Something like this:
   *   q1   = [S-1, L-1, P-1, R-1, H-1]           # every group of clones here is even (1 == 2**0)
   *   ...
   *   q256 = [S-256, L-256, P-256, R-256, H-256] # on each power of 2, every group of clone is even
   *
   * Therefore, we first need to find the maximum even number of clones possible,
   * before a single group will eventually be uneven, before every can is drunk.
   * Then, every other variable of this equation will be easy to deduce.
   */

Let's dive into this simple algorithm yet faster:

• get the queue length
• get maximum power of 2 (maximum number of even groups of clones)
• get max iteration (nth can drunk) until a group is eventually uneven
• get the numbers of iterations left, unil the last can is drunk
• get the index (in names) of the first person in the queue
• return names(index)

object Main:

  def getMaximumEvenClones(cans: Long, queueLen: Long): Option[Long] =
    LazyList.from(0).map(2L << _).takeWhile(_ <= cans / queueLen).lastOption

  def whoIsNext(names: List[String], cans: Long): String = (for {
    len   <- Option(names.size).filter(size => size > 0 && cans > size)
    max   <- getMaximumEvenClones(cans, len)
    until <- Option(len * (max - 1)).map(m => cans - m)
    index <- util.Try(until / max).toOption.orElse(Option(0L))
  } yield names(index.toInt)).getOrElse(if (cans <= 0) "Nothing to compute" else names(cans.toInt - 1))

  def main(av: Array[String]): Unit =
    List(1L, 52L, 7230702951L).foreach { n => println(
      whoIsNext(List("Sheldon", "Leonard", "Penny", "Rajesh", "Howard"), n))
    }