diff options
| -rwxr-xr-x | challenge-192/tim-potapov/perl/ch-2.pl | 128 |
1 files changed, 90 insertions, 38 deletions
diff --git a/challenge-192/tim-potapov/perl/ch-2.pl b/challenge-192/tim-potapov/perl/ch-2.pl index c1ed1b9a81..12e1a6b03c 100755 --- a/challenge-192/tim-potapov/perl/ch-2.pl +++ b/challenge-192/tim-potapov/perl/ch-2.pl @@ -3,61 +3,113 @@ use strict; use warnings; use Test::More; +use List::Util qw( sum uniq ); +use feature qw(say); =pod Task 2: Equal Distribution You are given a list of integers greater than or equal to zero, @list. -Write a script to distribute the number so that each members are same. If you succeed then print the total moves otherwise print -1. - -Example 1: -Input: @list = (1, 0, 5) -Output: 4 - -Move #1: 1, 1, 4 -(2nd cell gets 1 from the 3rd cell) - -Move #2: 1, 2, 3 -(2nd cell gets 1 from the 3rd cell) - -Move #3: 2, 1, 3 -(1st cell get 1 from the 2nd cell) - -Move #4: 2, 2, 2 -(2nd cell gets 1 from the 3rd cell) -Example 2: -Input: @list = (0, 2, 0) -Output: -1 - -It is not possible to make each same. -Example 3: -Input: @list = (0, 3, 0) -Output: 2 - -Move #1: 1, 2, 0 -(1st cell gets 1 from the 2nd cell) - -Move #2: 1, 1, 1 -(3rd cell gets 1 from the 2nd cell) +Write a script to distribute the number so that each members are same. +If you succeed then print the total moves otherwise print -1. =cut -sub function { - my ( $input ) = @_; - +sub equal_shares { + my ( $list ) = @_; + my $sum = sum @$list; + my $elems = @$list; + + # Cant's be split since remainder. + return -1 if $sum % $elems; + + my $goal_size_per_cell = $sum / $elems; + my $count = 0; + my $first_index = 0; + my $last_index = $#$list; + my $n; + my $run = sub { uniq( @$list ) > 1 }; + + LOOP: + while ( $run->() ) { + say ""; + say "loop: (@$list)"; + for my $i ( $first_index .. $last_index ) { + my $val = $list->[$i]; + next if $val == $goal_size_per_cell; + + # Tool big so lets split the cell. + if ( $val > $goal_size_per_cell ) { + if ( $i > $first_index ) { + $list->[$i]--; + $list->[ $i - 1 ]++; + $count++; + say " <-- (@$list)"; + last LOOP if not $run->(); + } + if ( $i < $last_index ) { + $list->[$i]--; + $list->[ $i + 1 ]++; + $count++; + say " --> (@$list)"; + last LOOP if not $run->(); + } + } + } + last if $n++ > 10; # Stop infinite loop. + } + + # After writing this, then I came up with the idea + # to use a balanced binary tree approach... + # maybe one day. + + $count; } my @cases = ( + + { + Name => 'Example 1', + Input => [ 1, 0, 5 ], + Output => 4, + + # Move #1: 1, 1, 4 + + # (2nd cell gets 1 from the 3rd cell) + # + # Move #2: 1, 2, 3 + # (2nd cell gets 1 from the 3rd cell) + # + # Move #3: 2, 1, 3 + # (1st cell get 1 from the 2nd cell) + # + # Move #4: 2, 2, 2 + # (2nd cell gets 1 from the 3rd cell) + + }, + { + Name => 'Example 2', + Input => [ 0, 2, 0 ], + Output => -1, + + # It is not possible to make each same. + }, { - Name => 'Example1', - Input => 1, - Output => 1, + Name => 'Example 3', + Input => [ 0, 3, 0 ], + Output => 2, + + # Move #1: 1, 2, 0 + # (1st cell gets 1 from the 2nd cell) + # + # Move #2: 1, 1, 1 + # (3rd cell gets 1 from the 2nd cell) }, ); for ( @cases ) { - is function( $_->{Input} ), $_->{Output}, "$_->{Name} - $_->{Input}"; + is equal_shares( $_->{Input} ), $_->{Output}, $_->{Name}; } done_testing(); |