dev.to staff

Posted on Jul 17, 2019

Daily Challenge #17 - Double Trouble

#challenge

Good morning! We're back with another challenge which comes from AlexisHappy on Codewars. Today, you are asked to write a program that will return the name of the person who will drink the n-th Cola at the vending machine

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. The input data consist of an array which contains at least 1 name, and single integer n which may go as high as the biggest number your language of choice supports (if there's such limit, of course). The output data returns the single line — the name of the person who drinks the n-th can of cola. The cans are numbered starting from 1.

Good luck, and happy coding!

Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge for a future post? Email yo+challenge@dev.to with your suggestions!

Top comments (20)

Alvaro Montoro • Jul 18 '19 • Edited

JavaScript

const cola = (number, people) => {
  const length = people.length;
  const iteration = Math.floor(Math.log2(((number - 1) / length) + 1));
  const post = 2 ** iteration;

  return people[Math.floor((number - ((post - 1) * length + 1)) / post)]
}

The way it works, the series follows an exponential pattern in which the first iteration has n elements (5 in this case), and from then on each iteration has double the elements than the previous iteration:

Iteration(0) = S, L, P, R, H (5 elements)
Iteration(1) = S, S, L, L, P, P, R, R, H, H (10 elements)
Iteration(2) = S, S, S, S, L, L, L, L, P, P, P, P, R, R, R, R, H, H, H, H (20 elements)
Iteration(3) = S, S, S, S, S, S, S, S, S, L, L, L, L, L, L, L, L, ... (40 elements);
Iteration(4) = S, S, S, S, S, S, S, S, S, S, S, S, S, S, S, S, S, S, ... (80 elements)

With that in mind, it is possible to calculate in which iteration we are by doing log₂(number / 5), and from there we can get which element within the actual iteration we need to check. After doing some numbers, trying to figure out the pattern, and all that jazz, I think this may work... although I haven't fully tested it.

Live demo on Codepen.

K.V.Harish • Oct 4 '19

I like what you are doing here. Kudos :)

Olivier “Ölbaum” Scherler • Aug 20 '19

It seems to work. I tested it (ported to Erlang) with N up to 22 on a queue of 3 people.

Olivier “Ölbaum” Scherler • Aug 20 '19 • Edited

I couldn’t figure out the formula like @alvaromontoro did, but here’s my blunt Erlang version. It was really easy to write and it still runs under a second for N = 10 million:

-module( double ).

-include_lib("eunit/include/eunit.hrl").

% when it’s the first person, return the head
double( [ Person | Rest ], 1, More ) ->
    Person;
% when it’s not the first person, add the head to the More list twice and decrement N
% the More list is the rest of the queue, where we can append at the head
% imagine that the full queue at all times is Queue ++ lists:reverse( More )
double( [ Person | Rest ], N, More ) ->
    double( Rest, N - 1, [ Person, Person | More ] );
% when the queue is empty, take the More list, reverse it and start over
double( [], N, More ) ->
    double( lists:reverse( More ), N, [] ).

double( Queue, N ) when N > 0 ->
    double( Queue, N, [] ).

double_test_() ->
    Three = [ sheldon, leonard, penny ],
    Everyone = [ sheldon, leonard, penny, rajesh, howard ],
    [
        ?_assertEqual( sheldon, double( [ sheldon ], 1 ) ),
        ?_assertEqual( sheldon, double( [ sheldon ], 2 ) ),
        ?_assertEqual( sheldon, double( [ sheldon ], 3 ) ),
        ?_assertEqual( sheldon, double( [ sheldon ], 4 ) ),

        ?_assertEqual( sheldon, double( [ sheldon, leonard ], 1 ) ),
        ?_assertEqual( leonard, double( [ sheldon, leonard ], 2 ) ),
        ?_assertEqual( sheldon, double( [ sheldon, leonard ], 3 ) ),
        ?_assertEqual( sheldon, double( [ sheldon, leonard ], 4 ) ),
        ?_assertEqual( leonard, double( [ sheldon, leonard ], 5 ) ),
        ?_assertEqual( leonard, double( [ sheldon, leonard ], 6 ) ),

        ?_assertEqual( sheldon, double( Everyone, 1 ) ),
        ?_assertEqual( penny,   double( Everyone, 3 ) ),
        ?_assertEqual( sheldon, double( Everyone, 6 ) ),
        ?_assertEqual( leonard, double( Everyone, 8 ) ),
        ?_assertEqual( leonard, double( Everyone, 9 ) ),
        ?_assertEqual( sheldon, double( Everyone, 19 ) ),

        ?_assertEqual( sheldon, double( Three, 1 ) ),
        ?_assertEqual( leonard, double( Three, 2 ) ),
        ?_assertEqual( penny,   double( Three, 3 ) ),
        ?_assertEqual( sheldon, double( Three, 4 ) ),
        ?_assertEqual( sheldon, double( Three, 5 ) ),
        ?_assertEqual( leonard, double( Three, 6 ) ),
        ?_assertEqual( leonard, double( Three, 7 ) ),
        ?_assertEqual( penny,   double( Three, 8 ) ),
        ?_assertEqual( penny,   double( Three, 9 ) ),
        ?_assertEqual( sheldon, double( Three, 10 ) ),
        ?_assertEqual( sheldon, double( Three, 11 ) ),
        ?_assertEqual( sheldon, double( Three, 12 ) ),
        ?_assertEqual( sheldon, double( Three, 13 ) ),
        ?_assertEqual( leonard, double( Three, 14 ) ),
        ?_assertEqual( leonard, double( Three, 15 ) ),
        ?_assertEqual( leonard, double( Three, 16 ) ),
        ?_assertEqual( leonard, double( Three, 17 ) ),
        ?_assertEqual( penny,   double( Three, 18 ) ),
        ?_assertEqual( penny,   double( Three, 19 ) ),
        ?_assertEqual( penny,   double( Three, 20 ) ),
        ?_assertEqual( penny,   double( Three, 21 ) ),
        ?_assertEqual( sheldon, double( Three, 22 ) )
    ].

E. Choroba • Jul 17 '19 • Edited

Iterating over the whole queue is slow when the number is really large. I wasn't able to find an exact formula, but I was able to find a good upper bound from which I can find the exact solution in linear time.

The solution is in Perl:

#!/usr/bin/perl
use warnings;
use strict;

sub slow {
    my ($queue, $n) = @_;
    push @$queue, (shift @$queue) x 2 while --$n;
    return $queue->[0]
}

sub fast {
    my ($queue, $n) = @_;
    return $queue->[0] if 1 == $n;
    my $upper_bound = 5 + int(log($n / @$queue) / log(2));

    my $x;
    do {
        --$upper_bound;
        $x = (2 ** $upper_bound - 1) * @$queue + 1;
    } until $x <= $n;
    return $queue->[($n - $x) / (2 ** $upper_bound)]
}

use Test::More;

is slow([qw[ Sheldon Leonard Penny Rajesh Howard ]], 3), 'Penny';
is slow([qw[ Sheldon Leonard Penny Rajesh Howard ]], 7), 'Sheldon';
is slow([qw[ Sheldon Leonard Penny Rajesh Howard ]], 8), 'Leonard';

my @queue;
for my $char ('a' .. 'z') {
    push @queue, $char;
    is fast(\@queue, $_), slow([@queue], $_),
        "t_$_\_" . scalar @queue for 2 .. 2000;
}
done_testing();

Benchmarking is easy using the Benchmark module:

use Benchmark qw{ cmpthese };
cmpthese(-2, {
    slow_1000 => sub { slow(['a' .. 'h'], 1_000) },
    fast_1000 => sub { fast(['a' .. 'h'], 1_000) },
    slow_10_000 => sub { slow(['a' .. 'h'], 10_000) },
    fast_10_000 => sub { fast(['a' .. 'h'], 10_000) },
});

The output shows a table ordered from the slowest to the fastest.

                Rate slow_10_000   slow_1000   fast_1000 fast_10_000
slow_10_000    271/s          --        -90%       -100%       -100%
slow_1000     2845/s        952%          --        -99%        -99%
fast_1000   415531/s     153512%      14505%          --         -0%
fast_10_000 415531/s     153512%      14505%          0%          --

Unfortunately, it breaks for longer sequences, as the rounding error becomes too large. Switching to arbitrary precision is too slow, increasing the upper bound helps - the failures are easy to detect as the function returns undef instead of an element of the queue.

sub fast {
    my ($queue, $n, $correction) = @_;
    return $queue->[0] if 1 == $n;
    $correction ||= 4;
    my $upper_bound = $correction
        + int((log $n - log @$queue) / log 2);

    my $x;
    do {
        $x = (2 ** --$upper_bound - 1) * @$queue + 1;
    } until $x <= $n;
    my $r = $queue->[($n - $x) / (2 ** $upper_bound)]
        // fast($queue, $n, $correction + 2);
    return $r
}

Yozen Hernandez • Jul 18 '19 • Edited

So I think I was able to get this with an exact calculation. I thought it was going to turn out to be pretty convoluted, but I guess it's not. I think got it right, at least:

#!/usr/bin/perl

use v5.24;
use strict;
use warnings;
use feature qw(signatures);
no warnings "experimental::signatures";
use Carp;
use List::Util qw(sum0);
use POSIX qw(ceil);

sub cola ( $n, @queue ) {
    my $q_len    = @queue;
    my $i        = 0;
    my $last_idx = @queue;

    $last_idx += ( ( 2**++$i ) * @queue ) while ( $n > $last_idx );

    my $prev_last_idx = $last_idx - ( ( 2**($i) ) * @queue );
    my $nth_can       = ceil( ( $n - $prev_last_idx ) / 2**$i ) - 1;
    return $queue[$nth_can];
}

my @queue = qw(Sheldon Leonard Penny Rajesh Howard);

use Test::More tests => 4;
is( cola( 4,  @queue ), "Rajesh" );
is( cola( 6,  @queue ), "Sheldon" );
is( cola( 12, @queue ), "Rajesh" );
is( cola( 27, @queue ), "Penny" );

Benchmarking with timethis in Benchmark got me this result:

use Benchmark qw(timethis);

timethis( -2, sub{ cola( 12, @queue ) } );

#timethis for 2:  2 wallclock secs ( 2.00 usr +  0.00 sys =  2.00 CPU) @ 859529.50/s (n=1719059)

Basically, I just keep track of how many nodes there are in a tree structure which represents the doubling of the people in the queue. In each level of the tree, you double the number of nodes in the level before it, but we want the running total so far (which I call $last_index above because that is the index of the last node in the level where the $nth cola would be).

Once you figure out which "level" of the tree the $nth cola would be, you get the last index of the level before so that you can zero out the current level and any indices there. That makes it easy to figure out "where" on the current level of the tree the $nth cola is, and you just divide by the depth of the tree so far to turn that into an index that works on the initial array. Subtract one to get the 0-index value into the original array.

Edit Looks like Corey figured out the same thing, but with more math.

Bárbara Perdigão • Jul 17 '19 • Edited

My entry, written in Java:


    protected static void doubleTrouble() {

        List<String> people = new ArrayList<>();
        people.add("Sheldon");
        people.add("Leonard");
        people.add("Penny");
        people.add("Rajesh");
        people.add("Howard");


        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            String first = people.iterator().next();
            String person = people.get(people.indexOf(first));
            people.add(person);
            people.add(person);
            people.remove(first);

        }

        System.out.println(people.get(people.size() - 1));
    }

Corey Alexander • Jul 18 '19 • Edited

This was one of my favorites in a while!

I had a feeling I could get this answer in constant time, by just 'mathing' the value out! So I got out my good old pen and paper, and started working through it!

The repeating pattern of the list made me start thinking of the long list in cycles. Where one cycle was each person in line going as many times as they are supposed to in that cycle. I thought I would be able to determine how long the list would need to be to 'index' into it with the soda number, based on how many cycles it took! And we can! Since the cycles lengths follow the patter of: P, 2P, 3P, etc. I knew this could be represented as a summation formula, and I was pretty sure it had an algebraic solution! After a bit of googling I was able to find it! Applied to this problem the formula is as follows:

P = Number of People in the Line
C = Number of Cycles

Length = P / 2 * C * (C+1)

From here, I wanted to kinda reverse that formula. I wanted to know how many cycles it would take to achieve a specific length. After re-arranging that formula I was able to use the quadratic equation to rearrange, and solve for C, given Length and P. The quadratic formula gives two answers, and we are able to throw out one since we can guarantee it is negative and not relevant to our problem.
So now we have this!

C = (-1 + sqrt(1 + * (8 / P) * Length)) / 2

So now if we take the soda bottle number input as the Length, and the number of people in line as P, we can get a discrete value of the number of cycles it will take!

To figure out which person got the bottle I really only needed to index into the last cycle. And know I was able to figure out which cycle that was!
From here it was just some index math, to figure out which person/index we were looking for!

I wanted to make sure this solution worked, so I also wrote an iterative version to compare! I wrote a quick main function that compares the two results and they were equivalent for everything I tested! I also timed the two versions to see the speed differences, and as expected the constant time solution is orders of magnitudes faster than the iterative solution!

Math Took: 2.316656937049712 Iter Took: 77.97191874496184

Here is my full rust solution and tests!

fn find_index_iter(num_people: u64, soda_num: u64) -> u64 {
    let mut current_group_size = num_people;
    let mut total_size = num_people;
    let mut total_groups = 1;

    while soda_num > total_size {
        current_group_size += num_people;
        total_size += current_group_size;
        total_groups += 1;
    }

    let local_group_index = current_group_size - (total_size - soda_num) - 1;

    local_group_index / (total_groups + 0)
}

fn find_index_math(num_people: usize, soda_num: u64) -> usize {
    let soda_index = soda_num - 1;
    let number_of_groups =
        ((-1.0 + (1.0 + (8.0 / num_people as f64 * soda_num as f64)).sqrt()) / 2.0).ceil();

    let num_before_last_group =
        num_people as f64 / 2.0 * number_of_groups * (number_of_groups - 1.0);

    let local_group_index = soda_index as f64 - num_before_last_group;

    let ans = ((local_group_index / number_of_groups).floor()) as usize;

    ans
}

pub fn whos_soda<'a>(people: &'a [&str], soda_num: u64) -> &'a str {
    people[find_index_math(people.len(), soda_num)]
    // people[find_index_iter(people.len() as u64, soda_num) as usize]
}

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn it_for_first_few_groups_with_3_names() {
        assert_eq!(whos_soda(&["a", "b", "c"], 1), "a");
        assert_eq!(whos_soda(&["a", "b", "c"], 2), "b");
        assert_eq!(whos_soda(&["a", "b", "c"], 3), "c");
        assert_eq!(whos_soda(&["a", "b", "c"], 4), "a");
        assert_eq!(whos_soda(&["a", "b", "c"], 5), "a");
        assert_eq!(whos_soda(&["a", "b", "c"], 6), "b");
        assert_eq!(whos_soda(&["a", "b", "c"], 7), "b");
        assert_eq!(whos_soda(&["a", "b", "c"], 8), "c");
        assert_eq!(whos_soda(&["a", "b", "c"], 9), "c");
    }

    #[test]
    fn it_for_first_few_groups_with_5_names() {
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 1), "a");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 2), "b");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 3), "c");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 4), "d");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 5), "e");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 6), "a");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 7), "a");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 8), "b");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 9), "b");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 10), "c");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 11), "c");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 12), "d");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 13), "d");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 14), "e");
        assert_eq!(whos_soda(&["a", "b", "c", "d", "e"], 15), "e");
    }
}

pub fn main() {
    let mut current_timing_iter = 0.0;
    let mut current_timing_math = 0.0;
    for people in 1..10 {
        for i in 1..2000000 {
            use std::time::Instant;
            let now = Instant::now();

            let math_ans = find_index_math(people as usize, i);

            let elapsed = now.elapsed();
            let math_sec =
                (elapsed.as_secs() as f64) + (elapsed.subsec_nanos() as f64 / 1000_000_000.0);

            let now = Instant::now();

            let iter_ans = find_index_iter(people, i) as usize;

            let elapsed = now.elapsed();
            let iter_sec =
                (elapsed.as_secs() as f64) + (elapsed.subsec_nanos() as f64 / 1000_000_000.0);

            current_timing_math += math_sec;
            current_timing_iter += iter_sec;

            assert_eq!(iter_ans, math_ans, "{}x{}", people, i);
        }
    }

    println!(
        "Math Took: {} Iter Took: {}",
        current_timing_math, current_timing_iter
    );
}

Oleksii Filonenko • Jul 17 '19

Elixir:

defmodule DoubleCola do
  def nth_drinker([head | tail], 1), do: head

  def nth_drinker([head | tail], n)
      when n > 1,
      do: nth_drinker_recursive(tail ++ [head, head], n - 1)
end

K.V.Harish • Oct 4 '19 • Edited

Not a better solution compared to @alvaromontoro but here is mine in js


const doubleTrouble = (queue, nthCola) => {
  let person;
  for(let index = 0; index < nthCola; index++) {
    if(index+1 === nthCola) {
      person = queue[0];
      break;
    }
    queue = queue.flat(queue.push(Array(2).fill(queue.shift())));
  }
  return person;
};

Payton Bice • Jul 17 '19 • Edited

PHP:

function cola (int $x, array $y): string {
    $z = count($y);

    while ($x > $z) {
        $x = round($x / $z);
    }

    return $y[$x - 1];
}

E. Choroba • Jul 17 '19

It returns b for cola(10, array("a", "b", "c", "d")) which I think should return c.

Payton Bice • Jul 18 '19

Thank you, that's a good catch - I fixed this by replacing floor() with round().

E. Choroba • Jul 18 '19

I'm still not sure it's correct. cola(9, array(1, 2)) returns 2 instead of 1.

Payton Bice • Jul 18 '19

Hm, you're right. It looks like I didn't test it thoroughly enough yesterday, and the tests I did came back with the right answers for the wrong reason. I'm trying to get better at solving math problems so I'll look more into this when I'm off work.

maxmattone • Jul 18 '19 • Edited

Some Smalltalk
Defining a subclass of Array that would act like an "infinite collection" (just because it is fun).

Class {
    #name : #DoubleCola,
    #superclass : #Array,
    #type : #variable,
    #category : #''
}

{ #category : #accessing }
DoubleCola >> at: anIndex [
    ^ anIndex <= self size
        ifTrue: [ super at: anIndex ]
        ifFalse: [ self at: anIndex inGroup: 1 ]
]

{ #category : #accessing }
DoubleCola >> at: anIndex inGroup: anIteration [
    ^ anIndex <= (self groupSize: anIteration)
        ifTrue: [ (self group: anIteration) at: anIndex ]
        ifFalse: [ self
                at: anIndex - (self groupSize: anIteration)
                inGroup: anIteration + 1 ]
]

{ #category : #accessing }
DoubleCola >> group: anInteger [
    ^ self
        flatCollect: [ :aPlayer | (1 to: 2 ** anInteger) collect: [ :i | aPlayer ] ]
        as: OrderedCollection
]

{ #category : #accessing }
DoubleCola >> groupSize: anIteration [
    ^ self size * (2 ** (anIteration - 1))
]

To execute:

(DoubleCola withAll: #( Sheldon Leonard Penny Rajesh Howard )) at: 3. "#Penny"
(DoubleCola withAll: #( Sheldon Leonard Penny Rajesh Howard )) at: 7. "#Sheldon"
(DoubleCola withAll: #( Sheldon Leonard Penny Rajesh Howard )) at: 8. "#Leonard"

Philip Hallstrom • Jul 18 '19

Ruby.

def drinker(queue = [], nth = 1)
  drinker = nil
  can = 0
  while can < nth
    drinker = queue.shift
    drinker = {name: drinker, arity: 1} unless drinker.is_a?(Hash)
    can += drinker[:arity]
    drinker[:arity] *= 2
    queue << drinker
  end

  drinker[:name]
end

View full discussion (20 comments)

DEV Community

Daily Challenge #17 - Double Trouble

Top comments (20)

Read next

Next.js containerization using Docker

Lendo e gravando arquivos usando fluxos de bytes

Why Clean Architecture Struggles in Golang and What Works Better

Why Next.js is Better than React for Building an E-commerce Website