diff options
| -rw-r--r-- | ch-1.pl | 122 | ||||
| -rw-r--r-- | ch-2.pl | 316 |
2 files changed, 438 insertions, 0 deletions
diff --git a/ch-1.pl b/ch-1.pl new file mode 100644 index 0000000000..4f95be5d11 --- /dev/null +++ b/ch-1.pl @@ -0,0 +1,122 @@ +#!/usr/bin/perl
+use strict;
+{
+package lr;
+
+sub new {
+ my ($class) = @_;
+ bless{
+ _value=> $_[1],
+ _bl=>$_[2],
+ _br=>$_[3],
+ }, $class;
+}
+
+sub bl{ $_[0]->{_bl}}
+sub br{ $_[0]->{_br}}
+sub value{ $_[0]->{_value} }
+
+}
+
+$ARGV[0] eq "0" || die "no argument input!" if not(defined($ARGV[0]));
+
+my @binaryint = split //, $ARGV[0];
+my @block;
+
+if ($binaryint[0]==0) {
+ @block = (-1,) ;
+ } else {@block = (1,) ;}
+
+#begin: special case of 1111..
+my %specialcase = {0=>0, 1=>0};
+$specialcase{$_}++ foreach @binaryint;
+if ($specialcase{1} == $#binaryint + 1) {
+ print "L = ", $_, ", R = ", $_, "\n" foreach (0.. $#binaryint);
+ exit;
+}
+#end of the special case
+
+
+
+
+sub increase_magnitude {
+ if ($_[1] == 0) {
+ return ($_[0]-1);
+ } else {
+ return ($_[0]+1);
+ }
+}
+
+
+my $h = 0;
+for (1..$#binaryint) {
+ if ($binaryint[$_-1] == $binaryint[$_]) {
+ $block[$h] = increase_magnitude($block[$h], $binaryint[$_]);
+ } else {
+ $h++;
+ if ($binaryint[$_] == 0) {
+ $block[$h] = -1 ;
+ } else {$block[$h] = 1;}
+ }
+}
+
+
+my $g; # g is ahead of h
+
+if ($binaryint[0] == 0) {
+ $g = 0
+} else {$g = 1;}
+
+sub sumblock {
+ my $v = 0;
+ my $a = $_[0];
+ my $b = $_[1];
+ if ($a==0) {$v = $block[$a] if $block[$a] > 0 ;}
+ if ($a >= 1) {for (0..$a-1) {
+ $v += $block[$_] if $block[$_] > 0;}}
+ for ($a..$b) {
+ $v += $block[$_]*(-1) if $block[$_]<0;}
+ if ($b < $h) {for ($b+1..$h) {
+ $v += $block[$_] if $block[$_] > 0;}}
+
+ return $v;
+}
+
+my @maxlr = ();
+my $max = sumblock(0,0);
+
+my $i; my $j;
+for ($i=$g; $i<=$h; $i=$i+2) {
+ for ($j=$i; $j<=$h; $j=$j+2 ){
+ my $temp = lr->new( sumblock($i,$j) , $i, $j);
+ if ($temp->value > $max) {
+ @maxlr = ();
+ $max = $temp->value;
+ }
+ if ($temp->value == $max)
+ {push @maxlr, $temp;}
+ }
+}
+
+
+
+sub magnitude {
+ if ($_[0] > 0) {return $_[0]} else {return -$_[0]}
+}
+
+
+foreach (@maxlr) {
+ my $ref;
+ my $L = 0;
+ if ($_->bl > 0) {
+ for $ref (0..$_->bl-1) {$L += magnitude($block[$ref]);}
+ }
+ my $R = 0;
+ if ($_->br >= 0) {
+ for $ref (0..$_->br) {
+ $R += magnitude($block[$ref]);}
+ }
+ $R = $R-1;
+ print "L = ", $L, ", R = ", $R, "\n";
+}
+
diff --git a/ch-2.pl b/ch-2.pl new file mode 100644 index 0000000000..9861cd586b --- /dev/null +++ b/ch-2.pl @@ -0,0 +1,316 @@ +#!/usr/bin/perl
+use strict;
+use Algorithm::Combinatorics qw/combinations/;
+use integer;
+
+# Usage: ch-2.pl N (LIST of N integers)
+# e.g. ch-2.pl 4 1 2 3 4
+# 4 2 3 1
+# 4 1 3 2
+# 3 2 4 1
+# 3 1 4 2
+# 2 1 4 3
+#
+# BUG!!!: need to fix when number_of_elements_of_median >= number_of_all_elements/2
+# for example, input: 1 2 2 2 2 3
+# in those situation, it will repeat some arrays.
+
+my $oN = shift @ARGV;
+my @userinput = sort {$a<=>$b} @ARGV;
+if (($#userinput + 1) != $oN) {die "The number of terms does not match.";}
+
+my @tempuserin;
+my @begin = map {-1} @userinput;
+my %bigbag;
+my $starter;
+my $N = $oN;
+my $j;
+
+sub transformer {
+ @tempuserin = ($userinput[0]);
+ for (1..$#userinput) {
+ if ($userinput[$_] != $userinput[$_-1]) {
+ push @tempuserin, $userinput[$_];
+ }
+ }
+
+ $j = 1;
+ $bigbag{1} = 1;
+ for (1..$#userinput) {
+ if ($userinput[$_] == $userinput[$_-1]) {
+ $bigbag{$j}++;
+ } else {
+ $j++;
+ $bigbag{$j} = 1;
+ }
+ }
+
+ @begin = map {-1} @userinput;
+ $starter = $j;
+
+ # print %bigbag, " ";
+}
+
+sub reverse_transformer_and_print { #argv: a wave array in canoical form
+
+ if ($oN%2 == 0) {pop @_;}
+ #remove the effect of &add_a_largest_ele_to_end
+
+ foreach (@_) {
+ print $tempuserin[$_-1], " ";
+ }
+ print "\n";
+}
+
+sub add_a_largest_ele_to_end {
+ #making even number of balls to odd number of balls
+ if ($oN%2 == 0) { push @begin, $j+1; $N=$oN+1;}
+}
+
+
+
+
+transformer;
+add_a_largest_ele_to_end;
+place_the_heaviest_balls_of_bag_in_urns(\$starter, \@begin, \%bigbag);
+
+
+
+sub place_the_heaviest_balls_of_bag_in_urns {
+ #argv: ref of the common value of those balls, ref of the array, ref of the hash
+if (${$_[0]} == 1) {ending(1, $_[1]);} else {
+ my $current = ${$_[0]};
+ my @a = @{ $_[1] };
+ my %hashbag = %{ $_[2] };
+
+
+ #three consective urns with the same labelled balls
+
+ my @loc_flatHLHurns = ();
+ for (my $i=1; $i < $N-1; $i += 2) {
+ if ($a[$i] == -1 and $a[$i-1] == -1 and $a[$i+1] == -1) {
+ push @loc_flatHLHurns, $i;
+ }
+ }
+
+ my $maxs = min(int( $hashbag{$current} / 3), 1+$#loc_flatHLHurns) ;
+ if (scalar @loc_flatHLHurns != 0 and $maxs != 0) {
+ for my $bully (1..$maxs) {
+ my $flatiter = combinations(\@loc_flatHLHurns, $bully);
+ while (my $flatx = $flatiter->next) {
+ my @p = @{$flatx};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ $newa[$_+1] = $current;
+ $newa[$_-1] = $current;
+ }
+ my %newhashbag = %hashbag;
+ $newhashbag{$current} -= 3 * $bully;
+ my $newcurrent = $current;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+ }
+
+
+ #doublet: getstronger ..(LHL)H**(LHLHLH)..
+ my @loc_stronger = ();
+ for (my $i=1; $i < $N-1; $i += 2) {
+ if ($a[$i] == -1 and $a[$i+1] == -1 and $a[$i-1] > $current) {
+ push @loc_stronger, $i;
+ }
+ }
+ my $maxst = min(int( $hashbag{$current} / 2), 1+$#loc_stronger) ;
+ if (scalar @loc_stronger != 0 and $maxst != 0) {
+ for my $b_st (1..$maxst) {
+ my $stronger = combinations(\@loc_stronger, $b_st);
+ while (my $b_stx = $stronger->next) {
+ my @p = @{$b_stx};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ $newa[$_+1] = $current;
+ }
+ my %newhashbag = %hashbag;
+ $newhashbag{$current} -= 2 * $b_st;
+ my $newcurrent = $current;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+ }
+
+
+ #doublet: getweaker ..(LHL)**H(LHLHLH)..
+ my @loc_weaker = ();
+ for (my $i=2; $i < $N-1; $i += 2) {
+ if ($a[$i] == -1 and $a[$i+1] == -1 and $a[$i+2] > $current) {
+ push @loc_weaker, $i;
+ }
+ }
+
+ my $maxwk = min(int( $hashbag{$current} / 2), 1+$#loc_weaker) ;
+ if (scalar @loc_weaker != 0 and $maxwk != 0) {
+ for my $b_wk (1..$maxwk) {
+ my $weaker = combinations(\@loc_weaker, $b_wk);
+ while (my $b_wkx = $weaker->next) {
+ my @p = @{$b_wkx};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ $newa[$_+1] = $current;
+ }
+ my %newhashbag = %hashbag;
+ $newhashbag{$current} -= 2 * $b_wk;
+ my $newcurrent = $current;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+ }
+
+
+
+ #which light urns can be placed the heavy balls?
+ for (1..$N-2) {
+ if ($_ % 2 == 1 and $a[$_] == -1 and $a[$_+1] > 0 and $a[$_-1] > 0) {
+ $a[$_] = 0;
+ }
+ }
+
+
+
+ my @loc_empty_and_putable_urns = ();
+ #locations of heavy/"eatmoreed" and empty urns
+ for (2..$N-3) { #original: for (0..$N-1);
+ if ( ($_ % 2 == 0 and $a[$_] == -1) or $a[$_] == 0 ) {
+ push @loc_empty_and_putable_urns , $_;
+ }
+ }
+
+
+
+ my $lefts = (($a[0] <= 0) and ($a[1] <= 0) and ($a[2] > 0));
+ my $rights = (($a[-1] <= 0) and ($a[-2] <= 0) and ($a[-3] > 0) and ($N%2==1));
+
+ ########################################
+
+
+ if ($hashbag{$current} >= 4 and $lefts and $rights and $#loc_empty_and_putable_urns+1 >= $hashbag{$current}-4 ) {
+ my $lriter = combinations(\@loc_empty_and_putable_urns, $hashbag{$current}-4);
+ while (my $lrx = $lriter->next) {
+ my @p = @{$lrx};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ }
+ ($newa[0], $newa[1], $newa[-1], $newa[-2]) =
+ ($current, $current, $current, $current );
+ my $newcurrent = $current-1;
+ my %newhashbag = %hashbag;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+
+
+
+ ########################################
+
+ if ($hashbag{$current} >= 2 and $lefts and $#loc_empty_and_putable_urns+1 >= $hashbag{$current}-2) {
+ my $liter = combinations(\@loc_empty_and_putable_urns, $hashbag{$current}-2);
+ while (my $lx = $liter->next) {
+ my @p = @{$lx};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ }
+ ($newa[0], $newa[1]) = ($current, $current);
+ my $newcurrent = $current-1;
+ my %newhashbag = %hashbag;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+
+
+ ########################################
+
+ if ($hashbag{$current} >= 2 and $rights and $#loc_empty_and_putable_urns+1 >= $hashbag{$current}-2) {
+ my $riter = combinations(\@loc_empty_and_putable_urns, $hashbag{$current}-2);
+ while (my $rx = $riter->next) {
+ my @p = @{$rx};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ }
+ ($newa[-1], $newa[-2]) = ($current, $current);
+ my $newcurrent = $current-1;
+ my %newhashbag = %hashbag;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+
+
+ ########################################
+
+
+ if ($a[0] == -1) {
+ unshift @loc_empty_and_putable_urns, 0;
+ }
+
+ if ($a[1] == 0) {
+ unshift @loc_empty_and_putable_urns, 1;
+ }
+
+ if ( ( ( ($N-2)%2 == 0 and $a[$N-2] == -1) or $a[$N-2] == 0 ) ) {
+ push @loc_empty_and_putable_urns, $N-2;
+ }
+
+ if (( ( ($N-1)%2 == 0 and $a[$N-1] == -1) or $a[$N-1] == 0 ) ) {
+ push @loc_empty_and_putable_urns, $N-1;
+ }
+
+ my $remainballs = $hashbag{$current} - ($#loc_empty_and_putable_urns+1);
+
+ # @loc_empty_and_putable_urns + already occupied --> all heavy urns
+ # for loop allow the current 1.. $hashbag - $heavy urns
+
+ if ($remainballs <= 0) {
+ my $iter = combinations(\@loc_empty_and_putable_urns, $hashbag{$current});
+ while (my $x = $iter->next) {
+ my @p = @{$x};
+ my @newa = @a;
+ foreach (@p) {
+ $newa[$_] = $current;
+ }
+ my $newcurrent = $current-1;
+ my %newhashbag = %hashbag;
+ place_the_heaviest_balls_of_bag_in_urns(\$newcurrent, \@newa, \%newhashbag);
+ }
+ }
+
+}
+}
+
+
+
+sub ending {
+ my @e = @{$_[1]};
+ if ($_[0] == 1) {
+
+ for (0..$N-1) {
+ if ( $e[$_] <= 0 ) {$e[$_] = 1;}
+ }
+
+ reverse_transformer_and_print @e;
+ #finally
+ #print join ",", @e, "\n";
+ }
+}
+
+
+
+sub min {
+ $_[0] < $_[1] ? return $_[0] : return $_[1] ;
+}
+
+
+
|