DEV Community

Daily Challenge #17 - Double Trouble

dev.to staff on July 17, 2019

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 ...
Read full post
Collapse
 
alvaromontoro profile image
Alvaro Montoro • • 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)]
}
Enter fullscreen mode Exit fullscreen mode

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 log2(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.

Collapse
 
kvharish profile image
K.V.Harish •

I like what you are doing here. Kudos :)

Collapse
 
oscherler profile image
Olivier “Ölbaum” Scherler •

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

Collapse
 
oscherler profile image
Olivier “Ölbaum” Scherler • • 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 ) )
    ].
Collapse
 
choroba profile image
E. Choroba • • 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
}
Collapse
 
yzhernand profile image
Yozen Hernandez • • 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.

Collapse
 
barbaraips profile image
Bárbara Perdigão • • 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));
    }
Collapse
 
coreyja profile image
Corey Alexander • • 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
    );
}
Collapse
 
brightone profile image
Oleksii Filonenko •

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
Collapse
 
kvharish profile image
K.V.Harish • • 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;
};
Collapse
 
p810 profile image
Payton Bice • • Edited

PHP: 

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

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

    return $y[$x - 1];
}
Collapse
 
choroba profile image
E. Choroba •

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

Collapse
 
p810 profile image
Payton Bice •

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

Thread Thread
 
choroba profile image
E. Choroba •

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

Thread Thread
 
p810 profile image
Payton Bice •

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.

Collapse
 
mattonem profile image
maxmattone • • 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"
Collapse
 
phallstrom profile image
Philip Hallstrom •

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
Collapse
 
tobiassn profile image
Tobias SN • • Edited 
queue = ["Sheldon", "Leonard", "Penny", "Rajesh", "Howard"];

for (i=0; i<n; i++) {
    curr = queue.shift();
    queue.push(curr, curr);
}

result = queue.pop();
Collapse
 
alvaromontoro profile image
Alvaro Montoro •

I didn't get the notification for this challenge even when I'm following dev.to staff

Collapse
 
coreyja profile image
Corey Alexander •

Oh huh, I didn't notice but I didn't get my notification either 🤔

And while we're on the subject, it would be really cool to be able to follow specific series! So I could just follow this series of posts!