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]

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:

With that in mind, it is possible to calculate in which iteration we are by doing log_{2}(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.

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/perlusewarnings;usestrict;sub slow{my($queue,$n)=@_;push@$queue,(shift@$queue)x2while--$n;return$queue->[0]}sub fast{my($queue,$n)=@_;return$queue->[0]if1==$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)]}useTest::More;isslow([qw[ Sheldon Leonard Penny Rajesh Howard ]],3),'Penny';isslow([qw[ Sheldon Leonard Penny Rajesh Howard ]],7),'Sheldon';isslow([qw[ Sheldon Leonard Penny Rajesh Howard ]],8),'Leonard';my@queue;formy$char('a'..'z'){push@queue,$char;isfast(\@queue,$_),slow([@queue],$_),"t_$_\_".scalar@queuefor2..2000;}done_testing();

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]if1==$n;$correction||=4;my$upper_bound=$correction+int((log$n-log@$queue)/log2);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}

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/perlusev5.24;usestrict;usewarnings;usefeatureqw(signatures);nowarnings"experimental::signatures";useCarp;useList::Utilqw(sum0);usePOSIXqw(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);useTest::Moretests=>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:

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.

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)whenN>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))].

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.

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!

fnfind_index_iter(num_people:u64,soda_num:u64)->u64{letmutcurrent_group_size=num_people;letmuttotal_size=num_people;letmuttotal_groups=1;whilesoda_num>total_size{current_group_size+=num_people;total_size+=current_group_size;total_groups+=1;}letlocal_group_index=current_group_size-(total_size-soda_num)-1;local_group_index/(total_groups+0)}fnfind_index_math(num_people:usize,soda_num:u64)->usize{letsoda_index=soda_num-1;letnumber_of_groups=((-1.0+(1.0+(8.0/num_peopleasf64*soda_numasf64)).sqrt())/2.0).ceil();letnum_before_last_group=num_peopleasf64/2.0*number_of_groups*(number_of_groups-1.0);letlocal_group_index=soda_indexasf64-num_before_last_group;letans=((local_group_index/number_of_groups).floor())asusize;ans}pubfnwhos_soda<'a>(people:&'a[&str],soda_num:u64)->&'astr{people[find_index_math(people.len(),soda_num)]// people[find_index_iter(people.len() as u64, soda_num) as usize]}#[cfg(test)]modtests{usecrate::*;#[test]fnit_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]fnit_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");}}pubfnmain(){letmutcurrent_timing_iter=0.0;letmutcurrent_timing_math=0.0;forpeoplein1..10{foriin1..2000000{usestd::time::Instant;letnow=Instant::now();letmath_ans=find_index_math(peopleasusize,i);letelapsed=now.elapsed();letmath_sec=(elapsed.as_secs()asf64)+(elapsed.subsec_nanos()asf64/1000_000_000.0);letnow=Instant::now();letiter_ans=find_index_iter(people,i)asusize;letelapsed=now.elapsed();letiter_sec=(elapsed.as_secs()asf64)+(elapsed.subsec_nanos()asf64/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);}

## Daily Challenge #17 - Double Trouble

## dev.to staff on July 17, 2019

JavaScript

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

_{2}(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.

I like what you are doing here. Kudos :)

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

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:

Benchmarking is easy using the Benchmark module:

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

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

thinkgot it right, at least:Benchmarking with

`timethis`

in`Benchmark`

got me this result: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`$n`

th cola would be).Once you figure out which "level" of the tree the

`$n`

th cola would be, you get the last index of the levelbeforeso 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`$n`

th 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.EditLooks like Corey figured out the same thing, but with more math.I couldn’t figure out the formula like @alvaromontoro did, but here’s my blunt

Erlangversion. It was really easy to write and it still runs under a second for N = 10 million:My entry, written in Java:

Some Smalltalk

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

To execute:

PHP:

It returns

`b`

for`cola(10, array("a", "b", "c", "d"))`

which I think should return`c`

.Thank you, that's a good catch - I fixed this by replacing

`floor()`

with`round()`

.I'm still not sure it's correct.

`cola(9, array(1, 2))`

returns 2 instead of 1.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.

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

Elixir:

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: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!

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!

Here is my full rust solution and tests!

Ruby.

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

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!