From 17dda0ee12bbf463ed51227721db164b7cf76bb8 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Wed, 25 Aug 2021 11:40:06 +0800 Subject: week 127 --- challenge-127/cheok-yin-fung/perl/ch-1.pl | 49 ++++++++++++++++ challenge-127/cheok-yin-fung/perl/ch-2.pl | 93 +++++++++++++++++++++++++++++++ 2 files changed, 142 insertions(+) create mode 100644 challenge-127/cheok-yin-fung/perl/ch-1.pl create mode 100644 challenge-127/cheok-yin-fung/perl/ch-2.pl diff --git a/challenge-127/cheok-yin-fung/perl/ch-1.pl b/challenge-127/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..8a663a6a81 --- /dev/null +++ b/challenge-127/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,49 @@ +#!/usr/bin/perl +# The Weekly Challenge 127 +# Task 1 Disjoint Sets +# Usage: $ ch-1.pl +use v5.12.0; +no warnings; +use experimental qw/signatures/; +use Test::More tests => 5; + +sub disjoint ($s1 , $s2) { + my @S1 = sort $s1->@*; + my @S2 = sort $s2->@*; + + my (@Ss, @Sl); + + if (scalar @S1 > scalar @S2) { + @Ss = @S2; + @Sl = @S1; + } + else { + @Ss = @S1; + @Sl = @S2; + } + + my $ref_ind = 0; + for (0..$#Ss) { + while ($Sl[$ref_ind] < $Ss[$_]) { + last if $ref_ind == $#Sl; + $ref_ind++; + } + return 0 if $Sl[$ref_ind] == $Ss[$_]; + } + + return 1; +} + +ok disjoint( [1, 2, 5, 3, 4], [4, 6, 7, 8, 9] ) == 0, + "Example 1"; +ok disjoint( [1, 3, 5, 7, 9], [0, 2, 4, 6, 8] ) == 1, + "Example 2"; + +ok disjoint( [1, 3, 5, 7], [0, 2, 4, 6, 7] ) == 0, + "Test case 1"; + +ok disjoint( [7], [0, 2, 4, 6, 7] ) == 0, + "Test case 2"; + +ok disjoint( [2], [0, 2, 4, 6, 7] ) == 0, + "Test case 3"; diff --git a/challenge-127/cheok-yin-fung/perl/ch-2.pl b/challenge-127/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..3a4a49c7f3 --- /dev/null +++ b/challenge-127/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,93 @@ +#!/usr/bin/perl +# The Weekly Challenge 127 +# Task 2 Conflict Intervals +# Usage: $ ch-2.pl 1 4 3 5 6 8 +# for checking intervals (1, 4), (3, 5), (6, 8) +use warnings; +use v5.12.0; +use List::Util qw/max min/; +use Test::More tests => 2; +use Test::Deep; + +my @inp; + +@inp = ([1,3], [3,4], [7,9]) if !defined($ARGV[0]); +if ((scalar @ARGV) % 2 == 1) { + die "Even number of terms should be entered.\n"; +} + +for (my $i = 0; $i <= $#ARGV ;$i+=2) { + die "Invalid interval: ($ARGV[$i], $ARGV[$i+1])\n" if $ARGV[$i] >= $ARGV[$i+1]; + push @inp, [$ARGV[$i], $ARGV[$i+1]]; +} + +my $answer = conflict_intervals(@inp); + +if (scalar $answer->@* > 0) { + say "($_->[0], $_->[1])" for $answer->@*; +} +else { + say "No conflicts found." +} + +sub conflict_intervals { + my @intervals = @_; + my @pre_intervals; + my @new_intervals; + my @ans; + push @new_intervals, $intervals[0]; + + for my $i (1..$#intervals) { + my $bool_cf = undef; + @pre_intervals = @new_intervals; + @new_intervals = (); + for my $interv (@pre_intervals) { + if (conf( $intervals[$i], $interv)) { + push @new_intervals, merge($intervals[$i], $interv); + $bool_cf = 1; + } + else { + push @new_intervals, $interv; + } + } + push @new_intervals, $intervals[$i] if !$bool_cf; + push @ans, $intervals[$i] if $bool_cf; + } + return [@ans]; +} + +sub merge { + return [ + min($_[0]->[0], $_[1]->[0]), + max($_[0]->[1], $_[1]->[1]) + ]; +} + +sub conf { + my $i1; + my $i2; + if ($_[0]->[0] < $_[1]->[0]) { + $i1 = $_[0]; + $i2 = $_[1]; + } + elsif ($_[0]->[0] > $_[1]->[0]) { + $i1 = $_[1]; + $i2 = $_[0]; + } + else { + return 1; + } + return 1 if $i1->[1] > $i2->[0]; + return 0; +} + +cmp_deeply( + conflict_intervals([1,4], [3,5], [6,8], [12, 13], [3, 20]), + [[3,5],[3,20]] , + "Example 1" +); +cmp_deeply( + conflict_intervals([3,4], [5,7], [6,9], [10,12], [13, 15]), + [[6,9]], + "Example 2" +); -- cgit From 45cb517f6f850e54d4479227ae35d8e1bf3ed20d Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Sat, 28 Aug 2021 14:54:25 +0800 Subject: week 127 --- challenge-127/cheok-yin-fung/perl/ch-1.pl | 30 ++++++++++++++++++++++++------ challenge-127/cheok-yin-fung/perl/ch-2.pl | 18 +++++++++++++++++- 2 files changed, 41 insertions(+), 7 deletions(-) diff --git a/challenge-127/cheok-yin-fung/perl/ch-1.pl b/challenge-127/cheok-yin-fung/perl/ch-1.pl index 8a663a6a81..36fb6ab2df 100644 --- a/challenge-127/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-127/cheok-yin-fung/perl/ch-1.pl @@ -1,11 +1,29 @@ #!/usr/bin/perl # The Weekly Challenge 127 # Task 1 Disjoint Sets -# Usage: $ ch-1.pl +# Usage: +# $ ch-1.pl $a1[0] $a1[1] ... $a1[$#a1] x $a2[0] ... $a2[$#a2] use v5.12.0; no warnings; use experimental qw/signatures/; -use Test::More tests => 5; +use Test::More tests => 6; + +my (@a, @a1, @a2); +@a = @ARGV; +@a = (1, 2, 3, 'x', 3, 5, 7) if !defined($ARGV[0]); +my $i = 0; + +while ($a[$i] ne 'x' && $i < scalar @a) { + push @a1, $a[$i]; + $i++; +} + +while ($i < scalar @a) { + push @a2, $a[$i]; + $i++; +} + +say disjoint( [@a1], [@a2]); sub disjoint ($s1 , $s2) { my @S1 = sort $s1->@*; @@ -41,9 +59,9 @@ ok disjoint( [1, 3, 5, 7, 9], [0, 2, 4, 6, 8] ) == 1, ok disjoint( [1, 3, 5, 7], [0, 2, 4, 6, 7] ) == 0, "Test case 1"; - -ok disjoint( [7], [0, 2, 4, 6, 7] ) == 0, +ok disjoint( [3, 11, 13, 27, 20], [0, 2, 4, 6, 7] ) == 1, "Test case 2"; - -ok disjoint( [2], [0, 2, 4, 6, 7] ) == 0, +ok disjoint( [ 29, 16, 23, 22, 25 ], [0, 2, 4, 6, 7] ) == 1, "Test case 3"; +ok disjoint( [14, 0, 29, 8, 22], [1, 14, 12, 11, 24]) == 0, + "Test case 4"; diff --git a/challenge-127/cheok-yin-fung/perl/ch-2.pl b/challenge-127/cheok-yin-fung/perl/ch-2.pl index 3a4a49c7f3..611ba5f202 100644 --- a/challenge-127/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-127/cheok-yin-fung/perl/ch-2.pl @@ -6,7 +6,7 @@ use warnings; use v5.12.0; use List::Util qw/max min/; -use Test::More tests => 2; +use Test::More tests => 4; use Test::Deep; my @inp; @@ -91,3 +91,19 @@ cmp_deeply( [[6,9]], "Example 2" ); +cmp_deeply( + conflict_intervals( + [0, 2], [11, 15], [12, 19], [16, 23], [17, 18], + [15, 17], [19, 25], [7, 9], [1, 3], [3, 8] + ), + [ [12,19], [16,23], [17,18], [15,17], [19, 25], [1, 3], [3, 8]], + "Test 1" +); +cmp_deeply( + conflict_intervals( + [14, 28], [9, 13], [6, 16], [12, 15], [28, 36], + [6, 24], [15, 22], [13, 16], [1, 16], [8, 27] + ), + [[6,16], [12, 15], [6, 24], [15, 22], [13, 16], [1, 16], [8, 27]], + "Test 2" +); -- cgit