Discussion on: Daily Challenge #17 - Double Trouble

[Yozen Hernandez]

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.