diff options
| -rw-r--r-- | challenge-160/cheok-yin-fung/perl/ch-2.pl | 73 |
1 files changed, 38 insertions, 35 deletions
diff --git a/challenge-160/cheok-yin-fung/perl/ch-2.pl b/challenge-160/cheok-yin-fung/perl/ch-2.pl index d6e71a769a..0c1fb3e121 100644 --- a/challenge-160/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-160/cheok-yin-fung/perl/ch-2.pl @@ -1,9 +1,15 @@ #!/usr/bin/perl # The Weekly Challenge 160 # Task 2 Equilibrium Index +# Post-Deadline Modification +# see https://e7-87-83.github.io/coding/challenge_160.html +# or +# https://e7-87-83.github.io/code/ch-2-wk160-positive.pl +# Tuesday, April 19, 2022 AM01:12:42 HKT + use v5.22.0; use warnings; -use List::Util qw/sum/; +use List::Util qw/sum all/; say ei(@ARGV) if defined($ARGV[0]); @@ -12,21 +18,26 @@ say ei(@ARGV) if defined($ARGV[0]); sub ei { my @n = @_; + my @trial = (undef) x scalar @n; + $trial[0] = 1; + $trial[$#n] = 1; my $ind = int $#n/2; - my $previous_ind = $ind; my $new_ind = $ind; my $hint_lower = sum(@n[0..$ind-1]); my $hint_upper = sum(@n[$ind+1..$#n]); my $step = 0; my $expired_ind = $ind; - my $guessed_step = 0; my $success = $hint_lower == $hint_upper; return $ind if $success; - while (!$success) { - return -1 if $ind < 1 or $ind > $#n-1; + return -1 if all {$_} @trial; + $trial[$ind] = 1; + # say "LOWER: ", $hint_lower, "; MID: ", + # $n[$ind], "($ind)", "; UPPER: ",$hint_upper, + # " ; DIRECTION: ", $step; + my $cur_val = $n[$ind]; @@ -40,48 +51,40 @@ sub ei { $hint_upper = $hint_upper + $n[$expired_ind]; } + # Check whether we get an equilibrium index + $success = $hint_lower == $hint_upper; + return $ind if $success; # Decide which direction going to move - if ($hint_lower+$cur_val < $hint_upper) { - $new_ind = $ind+1; - } - elsif ($hint_lower > $hint_upper+$cur_val) { - $new_ind = $ind-1; - } - elsif ($hint_lower+$cur_val == $hint_upper) { - $new_ind = $ind+$step; # follow the previous direction - } - elsif ($hint_lower == $hint_upper+$cur_val) { - $new_ind = $ind+$step; # follow the previous direction - } - - else { - if ($hint_lower+$cur_val > $hint_upper) { - $new_ind = $ind+1; - } - if ($hint_lower < $hint_upper+$cur_val) { - $new_ind = $ind-1; - } - } + $step = (int rand(2)) % 2 ? +1 : -1; # Prepare for the next loop block, or, stop - $step = $new_ind-$ind; - $success = $hint_lower == $hint_upper; - return $ind if $success; - return -1 if $guessed_step == -$step; # No back and fro! - $guessed_step = $step; + $new_ind = $ind + $step; + if ($new_ind == 0) { + $step = +1; + $new_ind = 2; + } + if ($new_ind == $#n) { + $step = -1; + $new_ind = $#n-2; + } ($expired_ind, $ind) = ($ind, $new_ind); } } -use Test::More tests=>500; +use Test::More tests=>50; say "TESTING:"; my @n_temp; -for my $case (1..500) { - $n_temp[$_] = 1 + int rand(40) for (0..31); - ok ei_simple(@n_temp) == ei(@n_temp); +for my $case (1..50) { + $n_temp[$_] = 20 - int rand(40) for (0..31); + my $i = ei(@n_temp); + ok ( + ei_simple(@n_temp) == $i + || + sum(@n_temp[0..$i-1]) == sum(@n_temp[$i+1..$#n_temp]) + ); } done_testing(); |