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"

First solution, a naive (though cunning) approach

  /**
   * We apply the rules, to run the computations, within a tailrec function.
   * On each call, we pop the queue's head, and push it back twice:
   *
   *   q1 = [S,L,P,R,H]
   *   q2 = [L,P,R,H,S,S]
   *   q3 = [P,R,H,S,S,L,L]
   *   ...
   *   q7 = [S,S,L,L,P,P,R,R,H,H]
   *   q8 = [S,L,L,P,P,R,R,H,H,S,S]
   *   q9 = [L,L,P,P,R,R,H,H,S,S,S,S]
   *   ...
   *
   * Such an implementation would cause a lot of memory troubles
   * below a certain number (not that big) of iterations
   * as the queue length always grows
   *
   * We see that each identical elements are contiguous
   * (considering the list is kinda circular)
   * Hense, wanna an RLE algorithm, could minimise the memory cost
   * and the queue length will always be 5 or 6
   * 
   *   q1 = [S-1, L-1, P-1, R-1, H-1]
   *   q2 = [L-1, P-1, R-1, H-1, S-2]
   *   ...
   *   q8 = [S-1, L-2, P-2, R-2, H-2, S-3]
   *   q9 = [L-2, P-2, R-2, H-2, S-4]
   *   ...
   */

Even if it works, the complexity is still problematic: O(n*log(n)),
we see its limits as the number of iterations grows

• ~0.3 seconds when cans == 1,000,000
• ~15 seconds when cans == 100,000,000
• ~2 minutes when cans == 1,000,000,000
• ~15 minutes when cans == 7,230,702,951

object Main:

  import scala.util.control.TailCalls.{ TailRec, tailcall, done }

  case class P(name: String, qty: Long = 1)

  def drink(n: Long, ps: List[P]): TailRec[List[P]] =
    if (1 == n) done(ps)
    else ps match
      case P(a,1) +: xs :+ P(b,y) if a == b => tailcall(drink(n-1, xs :+ P(b, y+1)))
      case P(a,x) +: xs :+ P(b,y) if a == b => tailcall(drink(n-1, P(a, x-1) +: xs :+ P(b, y+1)))
      case P(a,1) :: xs                     => tailcall(drink(n-1, xs :+ P(a,   2)))
      case P(a,x) :: xs                     => tailcall(drink(n-1, P(a, x-1) +: xs :+ P(a, x+1)))
      case Nil                              => done(Nil)
 
  def whoIsNext(names: List[String], cans: Long): String =
    if (names.isEmpty || cans < 1) "Nothing to compute"
    else drink(cans, names.map(P(_))).result.head.name

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

Second, a very efficient solution

  /**
   * Rather than testing every rotation through each iteration
   * we take a real advantage from the RLE, and pack every operation.
   *
   * As we know how much iterations we still have (through the `n` parameter)
   * we can instantly pop and push back any target element in the queue, using `n`
   *
   * Actually, we simply have to decrement `n`
   *  - with the RLE value (x) of the queues's head, if `n > x`
   *      meaning head and last, won't be the same Person
   *      then pop `x`, and push back `x*2`
   *  - to 1, if `n <= x`
   *      meaning head and last, will be the same Person
   *      then decrement head and increment last, with `n`: [(S, x-n)..(S,x+n)]
   * 
   * This time, the solution's code is even shorter,
   * and tail call optimization is not mandatory anymore.
   */

Even if we keep the same logic (RLE + recursion),
this time we almost got the best complexity: O(log(n))

object Main:

  case class P(name: String, qty: Long = 1)

  def drink(n: Long, ps: List[P]): List[P] =
    if (n <= 1) ps else ps match
      case P(a,x) :: xs if x < n => drink(n-x, xs :+ P(a, x*2))
      case P(a,x) :: xs          => drink(1, P(a, x-n) +: xs :+ P(a, x+n))
      case Nil                   => Nil

  def whoIsNext(names: List[String], cans: Long): String =
    drink(cans, names.map(P(_))).headOption.fold("Nothing to compute")(_.name)

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

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