#!/usr/bin/perl
use List::Util qw[ max min ];
use strict;

my ($TARGET, @TIMERS) = @ARGV ? @ARGV : (10, 4, 7);
print "Can you get $TARGET minutes using only {@TIMERS}-minute timers?\n";

my ($GCD, @c) = bezout(@TIMERS);
die "$TARGET is not egg-timer-able!" if $TARGET % $GCD;

my $max_timer = max @TIMERS;
my $remainder = $TARGET % $max_timer;
my $scale     = $remainder / $GCD;

## start a queue of timer jobs to be run, by the left hand and right hand.
## a timer "job" is [a,b] where a is the capacity of the timer, and b will
## reduce as the timer is going to show how much time is left on that timer

my (@left, @right);
for my $t (0 .. $#TIMERS) {
    if ($c[$t] > 0) {
        push @left, [ $TIMERS[$t], $TIMERS[$t] ]
            for 1 .. $scale * $c[$t];
    } elsif ($c[$t] < 0) {
        push @right, [ $TIMERS[$t], $TIMERS[$t] ]
            for 1 .. $scale * abs $c[$t];
    }
}

print ">> GOAL: get ${remainder}min onto the ${max_timer}min timer.\n";
print ">> Then the rest of the time (@{[ $TARGET-$remainder ]}min) is a multiple of ${max_timer}min.\n";

my $T = 0;

if ($remainder) {
    print "At time 0:\n";
    print " - Start $left[0][0]min timer.\n";
    print " - Start $right[0][0]min timer.\n";
}

while (@left and @right) {
    my $tick = min( $left[0][1], $right[0][1] );
    $T += $tick;
    print "At time $T:\n";
    
    for my $active (\@left, \@right) {
        $active->[0][1] -= $tick;
    
        if ($active->[0][1] == 0) {
            print " - $active->[0][0]min timer expires.\n";
            shift @$active;
            print " - Start $active->[0][0]min timer.\n"
                if @$active;
        } else {
            print " - $active->[0][0]min has $active->[0][1]min remaining.\n";
        }
    }
}

## left hand will still have timers pending in the queue if we needed
## $remainder

if ($remainder and $left[0][0] != $max_timer) {
    print ">> NOW READY TO LOAD UP ${max_timer}min TIMER WITH ${remainder}min.\n";
    print " - Start ${max_timer}min timer.\n";
    
    my $loaded = 0;
    while (@left) {
        $T += $left[0][1];
        $loaded += $left[0][1];
        
        print "At time $T:\n";
        print " - $left[0][0]min timer expires.\n";
        print " - ${max_timer}min timer has @{[ $max_timer-$loaded ]}min remaining.\n";
        shift @left;
        
        print " - Start $left[0][0]min timer.\n"
            if @left;
    }
} else {
    print ">> ${max_timer}min TIMER ALREADY LOADED UP WITH ${remainder}min.\n";
}


print ">> NOW START TIMING!\n";
print " - Flip ${max_timer}min timer: was @{[ $max_timer-$remainder ]}min remaining, now ${remainder}min remaining.\n"
    if $remainder;

$T += $remainder;
print "At time $T:\n";
print " - ${max_timer}min timer expires.\n"
    if $remainder;

for (1 .. int($TARGET/$max_timer)) {
    print " - Start ${max_timer}min timer.\n";
    $T += $max_timer;
    print "At time $T:\n";
    print " - ${max_timer}min timer expires.\n";
}

print ">> STOP TIMING!\n";


sub bezout {
    if ( @_ > 2 ) {
        my ($g1, @c1) = bezout( @_[0,1] );
        my ($g2, @c2) = bezout( $g1, @_[2..$#_] );

        return ( $g2, (map { $c2[0]*$_ } @c1), @c2[1 .. $#c2] );
    }

    my ($x, $y) = @_;
    return ($y,0,1) if $x % $y == 0;

    my ($g, $s, $t) = bezout( $y, $x % $y );
    return ($g, $t, $s - $t * int($x/$y));
}