From 1f3aee3539964c567010c11f189ddba4cbb873cc Mon Sep 17 00:00:00 2001 From: Alexander Pankoff Date: Mon, 12 Oct 2020 11:50:09 +0200 Subject: add perl solution for wk-081 ch-1 --- challenge-082/alexander-pankoff/perl/ch-1.pl | 53 ++++++++++++++++++++++++++++ 1 file changed, 53 insertions(+) create mode 100755 challenge-082/alexander-pankoff/perl/ch-1.pl diff --git a/challenge-082/alexander-pankoff/perl/ch-1.pl b/challenge-082/alexander-pankoff/perl/ch-1.pl new file mode 100755 index 0000000000..ef11c95c46 --- /dev/null +++ b/challenge-082/alexander-pankoff/perl/ch-1.pl @@ -0,0 +1,53 @@ +#!/usr/bin/env perl +use v5.20; +use utf8; +use strict; +use warnings; +use autodie; +use feature qw(say signatures); +no warnings 'experimental::signatures'; + +use Pod::Usage; + +use List::Util qw(min all any); +use Scalar::Util qw(looks_like_number); + +=pod + +=head1 SYNOPSIS + +This Script will print a list of common factors from M and N + +=head1 USAGE + +ch-1.pl + +=cut + +pod2usage( + -message => "$0: Expects 2 postive numbers", + -exitval => 1, + -verbose => 99, + -sections => "USAGE|SYNOPSIS", + ) + if @ARGV != 2 + or any { !looks_like_number($_) || $_ < 1 } @ARGV; + +my ( $M, $N ) = @ARGV; +say format_list( common_factors( $M, $N ) ); + +sub common_factors ( $m, $n ) { + grep { + my $check_factor = $_; + all { is_factor( $check_factor, $_ ) } ( $m, $n ); + } 1 .. min( $m, $n ); +} + +sub is_factor ( $divisor, $value ) { + return $value % $divisor == 0; +} + +sub format_list(@list) { + return '(' . join( ', ', @list ) . ')'; +} + -- cgit From fa79198d1c52baf12689a02d6594ab027c2f921d Mon Sep 17 00:00:00 2001 From: Alexander Pankoff Date: Mon, 12 Oct 2020 12:30:57 +0200 Subject: add perl solution for wk-081 ch-2 --- challenge-082/alexander-pankoff/perl/ch-2.pl | 59 ++++++++++++++++++++++++++++ 1 file changed, 59 insertions(+) create mode 100755 challenge-082/alexander-pankoff/perl/ch-2.pl diff --git a/challenge-082/alexander-pankoff/perl/ch-2.pl b/challenge-082/alexander-pankoff/perl/ch-2.pl new file mode 100755 index 0000000000..a5c586d085 --- /dev/null +++ b/challenge-082/alexander-pankoff/perl/ch-2.pl @@ -0,0 +1,59 @@ +#!/usr/bin/env perl +use v5.20; +use utf8; +use strict; +use warnings; +use autodie; +use feature qw(say signatures); +no warnings 'experimental::signatures'; + +use Pod::Usage; + +use List::Util qw(min all any); +use Scalar::Util qw(looks_like_number); + +=pod + +=head1 SYNOPSIS + +Given three strings , and this script will return whether can be +created by interleaving and + +=head1 USAGE + +ch-2.pl + +=cut + +pod2usage( + -message => "$0: Need exactly three arguments", + -exitval => 1, + -verbose => 99, + -sections => "USAGE|SYNOPSIS", +) if @ARGV != 3; + +my ( $A, $B, $C ) = @ARGV; +say is_creatable_by_interleaving( $C, $A, $B ); + +sub is_creatable_by_interleaving ( $target, $a, $b ) { + return 0 if length($target) != length($a) + length($b); + return 1 if !length($target); + + my $head = substr( $target, 0, 1 ); + my $rest = substr( $target, 1 ); + + return ( + starts_with( $head, $a ) + ? is_creatable_by_interleaving( $rest, substr( $a, 1 ), $b ) + : 0 + ) + || ( + starts_with( $head, $b ) + ? is_creatable_by_interleaving( $rest, $a, substr( $b, 1 ) ) + : 0 + ); +} + +sub starts_with ( $char, $str ) { + return $str =~ m/^$char/; +} -- cgit From dbdc30ba7ecd35eea30c094654583405259e85cc Mon Sep 17 00:00:00 2001 From: Alexander Pankoff Date: Tue, 13 Oct 2020 21:04:46 +0200 Subject: improve comments/docs in wk-081 ch-1 --- challenge-082/alexander-pankoff/perl/ch-1.pl | 46 ++++++++++++++++++---------- 1 file changed, 30 insertions(+), 16 deletions(-) diff --git a/challenge-082/alexander-pankoff/perl/ch-1.pl b/challenge-082/alexander-pankoff/perl/ch-1.pl index ef11c95c46..1b9916d7b5 100755 --- a/challenge-082/alexander-pankoff/perl/ch-1.pl +++ b/challenge-082/alexander-pankoff/perl/ch-1.pl @@ -12,31 +12,22 @@ use Pod::Usage; use List::Util qw(min all any); use Scalar::Util qw(looks_like_number); -=pod - -=head1 SYNOPSIS - -This Script will print a list of common factors from M and N - -=head1 USAGE - -ch-1.pl - -=cut - pod2usage( - -message => "$0: Expects 2 postive numbers", - -exitval => 1, - -verbose => 99, - -sections => "USAGE|SYNOPSIS", + -message => "$0: Expects 2 natural numbers", + -exitval => 1, ) if @ARGV != 2 or any { !looks_like_number($_) || $_ < 1 } @ARGV; my ( $M, $N ) = @ARGV; + say format_list( common_factors( $M, $N ) ); sub common_factors ( $m, $n ) { + + # we grep for numbers from 1 to min($m,$n) that are factors of both $m and + # $n. since all numbers larger than min($m,$n) can't be a factor of that + # minimum we don't have to check them grep { my $check_factor = $_; all { is_factor( $check_factor, $_ ) } ( $m, $n ); @@ -51,3 +42,26 @@ sub format_list(@list) { return '(' . join( ', ', @list ) . ')'; } +=pod + +=head1 NAME + +wk-082 ch-1 - Common Factors + +=head1 SYNOPSIS + +Prints the common factors of two given natural numbers M and N + +ch-1.pl + +=head1 ARGUMENTS + +=over 8 + +=item B The first natural number + +=item B The second natural number + +=back + +=cut -- cgit From 7096482a45824706243a25a0e15dac097f35f61c Mon Sep 17 00:00:00 2001 From: Alexander Pankoff Date: Tue, 13 Oct 2020 21:07:22 +0200 Subject: improve and explain wk-082 ch-2 --- challenge-082/alexander-pankoff/perl/ch-2.pl | 103 ++++++++++++++++++--------- 1 file changed, 69 insertions(+), 34 deletions(-) diff --git a/challenge-082/alexander-pankoff/perl/ch-2.pl b/challenge-082/alexander-pankoff/perl/ch-2.pl index a5c586d085..c8587624a5 100755 --- a/challenge-082/alexander-pankoff/perl/ch-2.pl +++ b/challenge-082/alexander-pankoff/perl/ch-2.pl @@ -9,51 +9,86 @@ no warnings 'experimental::signatures'; use Pod::Usage; -use List::Util qw(min all any); +use List::Util qw(min all any pairs); use Scalar::Util qw(looks_like_number); -=pod +pod2usage( + -message => "$0: Need exactly three arguments", + -exitval => 1, +) if @ARGV != 3; -=head1 SYNOPSIS +my ( $A, $B, $C ) = @ARGV; -Given three strings , and this script will return whether can be -created by interleaving and +say is_creatable_by_interleaving( $C, $A, $B ) ? 1 : 0; -=head1 USAGE +sub is_creatable_by_interleaving ( $target, $a, $b ) { -ch-2.pl + # first check whether the total lenght of $a and $b match with the target + # length + return 0 if length($target) != length($a) + length($b); -=cut + # we now check wether any of $a or $b starts with the same char as $target + # if so, we recurse with the rest of $target and the matching item to + # check the remaining input. + # otherwise we can't find a way to interleave $a and $b to make $target + # + # to prevent checking the length condition above in every recursive case we + # define a helper without that check. since we consume the input charwise + # and pairwise, either from $target and $a or from $target and $b that + # condition won't change + my $go; + $go = sub ( $target, $a, $b ) { + # base case. we consumed all inputs - $target is $a and $b interleaved + # since we already made sure that the total lengths match up we only + # need to check wether $target became empty here. + return 1 if !length($target); -pod2usage( - -message => "$0: Need exactly three arguments", - -exitval => 1, - -verbose => 99, - -sections => "USAGE|SYNOPSIS", -) if @ARGV != 3; + my $head = substr( $target, 0, 1 ); + my $rest = substr( $target, 1 ); -my ( $A, $B, $C ) = @ARGV; -say is_creatable_by_interleaving( $C, $A, $B ); + # the order of $a and $b in the recursice call doesn't matter + # so we can just run the same routine on (a,b) and (b,a) instead of + # using two routines with the arguments flipped + return any( + sub { + starts_with( $_->[0], $head ) + && $go->( $rest, substr( $_->[0], 1 ), $_->[1] ); + }, + pairs( $a, $b, $b, $a ) + ); -sub is_creatable_by_interleaving ( $target, $a, $b ) { - return 0 if length($target) != length($a) + length($b); - return 1 if !length($target); - - my $head = substr( $target, 0, 1 ); - my $rest = substr( $target, 1 ); - - return ( - starts_with( $head, $a ) - ? is_creatable_by_interleaving( $rest, substr( $a, 1 ), $b ) - : 0 - ) - || ( - starts_with( $head, $b ) - ? is_creatable_by_interleaving( $rest, $a, substr( $b, 1 ) ) - : 0 - ); + }; + + $go->( $target, $a, $b ); } -sub starts_with ( $char, $str ) { +sub starts_with ( $str, $char ) { return $str =~ m/^$char/; } + +=pod + +=head1 NAME + +wk-082 ch-2 - Interleave String + +=head1 SYNOPSIS + +Given three strings , and this script prints whether can be +created by interleaving and + +ch-2.pl + +=head1 ARGUMENTS + +=over 8 + +=item B The first input string + +=item B The first input string + +=item B The target string + +=back + +=cut -- cgit