use strict;
use warnings;
use feature 'say';
use PDL;
use MCE::Flow;
use MCE::Candy;

use Time::HiRes 'time';
my $t = time;

# PDL Quick Reference
# https://www.perlmonks.org/?node_id=1214437

sub collatz_seq {
    my ( $chunk_id, $seq_beg, $seq_end ) = @_;
    my $max = $seq_end - $seq_beg + 2;
    my $top = $max < 20 ? $max : 20;

    my $seqs = pdl( longlong, 1, $seq_beg..$seq_end );
    $seqs-> setbadat( 0 );
    $seqs-> badvalue( 2 );

    my $lengths = 1 + ones( short, $max );
    $lengths-> set( 0, 1 );

    while ( any my $good_mask = $seqs-> isgood ) {

        my ( $seqs_odd, $lengths_odd_masked )
            = where( $seqs, $lengths, $seqs & 1 );

        $lengths_odd_masked ++;
        $lengths-> where( $good_mask ) ++;
        ( $seqs_odd *= 3 ) ++;
        $seqs >>= 1;
    }

    my $sorted_i = $lengths-> qsorti;
    my $sorted   = $lengths-> index( $sorted_i );
    my $value    = $sorted-> at( $max - $top );
    my $pos      = vsearch_insert_leftmost( $value, $sorted );
    my $top_i    = $sorted_i-> slice([ $max - 1 , $pos ]);

    ( my $result = $lengths
        -> index( $top_i )
        -> longlong
        -> bitnot
        -> cat( $top_i + 1 )
        -> transpose
        -> qsortvec
        -> slice([], [ 0, $top - 1 ])

    )-> slice([ 0 ], [])
     -> inplace
     -> bitnot;

    # From PDL to Perl: [ 0 1 ] becomes [ 1, 0 ],
    my $str = $result->string;
    $str =~ s/(\d+)\s+(\d+)(.*)/$2,$1$3,/g;

    my $ret = eval $str;
    $_->[0] = $_->[0] + $seq_beg - 2 for @$ret;

    MCE->gather( $chunk_id, @$ret );
}

my $size = shift || 1e6;
$size = 1e6 if $size < 1e6;  # minimum
$size = 1e9 if $size > 1e9;  # maximum

my $chunk_size = $size >> 5;
my @seqs;

mce_flow_s {
    max_workers => MCE::Util::get_ncpu(),
    chunk_size  => $chunk_size > 100000 ? 100000 : $chunk_size,
    bounds_only => 1,
    gather      => MCE::Candy::out_iter_array(\@seqs),
}, sub {
    my ( $mce, $chunk_ref, $chunk_id ) = @_;
    collatz_seq( $chunk_id, @{ $chunk_ref } );
}, 2, $size;

MCE::Flow->finish;

@seqs = ( sort { $b->[1] <=> $a->[1]} @seqs )[ 0..19 ];

printf "Collatz(%5d) has sequence length of %3d steps\n", @$_
    for @seqs;

say {*STDERR} time - $t;