From 90414975c41c640a776944ed76255e7b7e2baed3 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Tue, 5 May 2020 20:15:02 -0500 Subject: jaredor and PWC 059 --- challenge-059/jaredor/perl/ch-1.pl | 82 ++++++++++++++++++++++++++++++++++++++ challenge-059/jaredor/perl/ch-2.pl | 1 + 2 files changed, 83 insertions(+) create mode 100755 challenge-059/jaredor/perl/ch-1.pl create mode 100755 challenge-059/jaredor/perl/ch-2.pl (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-1.pl b/challenge-059/jaredor/perl/ch-1.pl new file mode 100755 index 0000000000..3151ca881c --- /dev/null +++ b/challenge-059/jaredor/perl/ch-1.pl @@ -0,0 +1,82 @@ +#!/usr/bin/env perl + +use v5.012; +use warnings; +use Data::Dump qw(pp); +use Getopt::Long; +use List::Util qw(all); +use Scalar::Util qw(looks_like_number); + +# PWC 059, TASK #1 : Linked List + +# You are given a linked list and a value k. Write a script to partition the +# linked list such that all nodes less than k come before nodes greater than or +# equal to k. Make sure you preserve the original relative order of the nodes in +# each of the two partitions. + +# For example: + +# Linked List: 1 → 4 → 3 → 2 → 5 → 2 + +# k = 3 + +# Expected Output: 1 → 2 → 2 → 4 → 3 → 5. + +# Linked list provided as a list of arguments on the command line. +# +# If I were to claim that a linked list is simply an array of numbers, then +# I could declare victory like this: +# +# given a value, $k, set by user option, via Getopt::Long, say, then the rest +# of the command line arguments are the linked list in the @ARGV array: +# +# print join(' ', (grep { $_ < $k } @ARGV), (grep { $_ >= $k } @ARGV)), "\n"; +# +# But I will *not* submit that, I won't even run it, once, for a linked list +# must have at least one pointer in it ;-) + +Getopt::Long::Configure( 'bundling_values', 'ignorecase_always', + 'pass_through' ); + +GetOptions( 'k=f' => \( my $k ) ); + +die "The --k option must set a numeric value for the partitioning definition." + unless looks_like_number $k; + +die "The node values of the linked list must all be numeric." + unless all { looks_like_number $_ } @ARGV; + +die "No node values provided for the linked list." + unless @ARGV; + +# Create the Linked list: + +sub get_node { return [ $_[0], [] ]; } + +my $ll_head = get_node; +my $ll_curr = $ll_head; + +# Load the linked list from the input arguments. + +$ll_curr = ( $ll_curr->[1] = get_node $_ ) for @ARGV; +$ll_head = pop @$ll_head; + +# Split the input linked list into "less than" and "greater than or equal" +# linked lists. + +my ( $lt_head, $ge_head ) = ( get_node, get_node ); +my ( $lt_curr, $ge_curr ) = ( $lt_head, $ge_head ); + +while ( defined $ll_head and @$ll_head) { + my $curr_ptr = $ll_head->[0] < $k ? \$lt_curr : \$ge_curr; + $ll_head = ( $$curr_ptr = ( $$curr_ptr->[1] = $ll_head ) )->[1]; +} + +undef $lt_head unless defined( $lt_curr->[0] ) and $lt_head = pop @$lt_head; +undef $ge_head unless defined( $ge_curr->[0] ) and $ge_head = pop @$ge_head; + +$lt_curr->[1] = $ge_head and $ge_curr->[1] = [] if defined $ge_head; + +my $ll_out = defined $lt_head ? $lt_head : defined $ge_head ? $ge_head : undef; + +pp $ll_out; diff --git a/challenge-059/jaredor/perl/ch-2.pl b/challenge-059/jaredor/perl/ch-2.pl new file mode 100755 index 0000000000..5ba39a26a0 --- /dev/null +++ b/challenge-059/jaredor/perl/ch-2.pl @@ -0,0 +1 @@ +#!/usr/bin/env perl -- cgit From a5fae668cff444e500cfc688b57df67f74e4c6e1 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Thu, 7 May 2020 08:16:01 -0500 Subject: Updated variable names, comments and output print. --- challenge-059/jaredor/perl/ch-1.pl | 80 ++++++++++++++++---------------------- 1 file changed, 33 insertions(+), 47 deletions(-) (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-1.pl b/challenge-059/jaredor/perl/ch-1.pl index 3151ca881c..97b1b78426 100755 --- a/challenge-059/jaredor/perl/ch-1.pl +++ b/challenge-059/jaredor/perl/ch-1.pl @@ -9,32 +9,6 @@ use Scalar::Util qw(looks_like_number); # PWC 059, TASK #1 : Linked List -# You are given a linked list and a value k. Write a script to partition the -# linked list such that all nodes less than k come before nodes greater than or -# equal to k. Make sure you preserve the original relative order of the nodes in -# each of the two partitions. - -# For example: - -# Linked List: 1 → 4 → 3 → 2 → 5 → 2 - -# k = 3 - -# Expected Output: 1 → 2 → 2 → 4 → 3 → 5. - -# Linked list provided as a list of arguments on the command line. -# -# If I were to claim that a linked list is simply an array of numbers, then -# I could declare victory like this: -# -# given a value, $k, set by user option, via Getopt::Long, say, then the rest -# of the command line arguments are the linked list in the @ARGV array: -# -# print join(' ', (grep { $_ < $k } @ARGV), (grep { $_ >= $k } @ARGV)), "\n"; -# -# But I will *not* submit that, I won't even run it, once, for a linked list -# must have at least one pointer in it ;-) - Getopt::Long::Configure( 'bundling_values', 'ignorecase_always', 'pass_through' ); @@ -43,40 +17,52 @@ GetOptions( 'k=f' => \( my $k ) ); die "The --k option must set a numeric value for the partitioning definition." unless looks_like_number $k; -die "The node values of the linked list must all be numeric." +die "The link values of the linked list must all be numeric." unless all { looks_like_number $_ } @ARGV; -die "No node values provided for the linked list." +die "No link values provided for the linked list." unless @ARGV; -# Create the Linked list: +# Convenience constructs. -sub get_node { return [ $_[0], [] ]; } +use constant NULL => []; +sub make_link { return [ $_[0], NULL ]; } -my $ll_head = get_node; -my $ll_curr = $ll_head; +# Create the linked list from the input arguments. -# Load the linked list from the input arguments. +my $ll_input = make_link; +my $ll_curpt = $ll_input; -$ll_curr = ( $ll_curr->[1] = get_node $_ ) for @ARGV; -$ll_head = pop @$ll_head; +$ll_curpt = ( $ll_curpt->[1] = make_link $_ ) for @ARGV; +$ll_input = pop @$ll_input; -# Split the input linked list into "less than" and "greater than or equal" -# linked lists. +# Split the input linked list into "<" and ">=" linked lists. +# This is a destructive rearrangement of the $ll_input linked list. -my ( $lt_head, $ge_head ) = ( get_node, get_node ); -my ( $lt_curr, $ge_curr ) = ( $lt_head, $ge_head ); +my ( $lt_subll, $ge_subll ) = ( make_link, make_link ); +my ( $lt_curpt, $ge_curpt ) = ( $lt_subll, $ge_subll ); -while ( defined $ll_head and @$ll_head) { - my $curr_ptr = $ll_head->[0] < $k ? \$lt_curr : \$ge_curr; - $ll_head = ( $$curr_ptr = ( $$curr_ptr->[1] = $ll_head ) )->[1]; +while (@$ll_input) { + my $curr_ptr = $ll_input->[0] < $k ? \$lt_curpt : \$ge_curpt; + $ll_input = ( $$curr_ptr = ( $$curr_ptr->[1] = $ll_input ) )->[1]; } -undef $lt_head unless defined( $lt_curr->[0] ) and $lt_head = pop @$lt_head; -undef $ge_head unless defined( $ge_curr->[0] ) and $ge_head = pop @$ge_head; +( $lt_curpt->[1], $ge_curpt->[1] ) = ( NULL, NULL ); +( $lt_subll, $ge_subll ) = ( pop @$lt_subll, pop @$ge_subll ); + +# Attach the ">=" linked list to the "<" list if "<" exists. + +$lt_curpt->[1] = $ge_subll if defined $lt_subll->[0]; + +# Create output re-linked list. + +my $ll_ltge = defined $lt_subll->[0] ? $lt_subll : $ge_subll; + +# Print linked list data from head to tail. +# This is a non-destructive walk of the $ll_ltge linked list. -$lt_curr->[1] = $ge_head and $ge_curr->[1] = [] if defined $ge_head; +my ( $ll_print, $delim, @outlist ) = ( $ll_ltge, ' -> ', ); -my $ll_out = defined $lt_head ? $lt_head : defined $ge_head ? $ge_head : undef; +( $outlist[@outlist], $ll_print ) = @$ll_print while @$ll_print; -pp $ll_out; +say join( $delim, @outlist ); -- cgit From f27afeb2622c5db9c2a6701c9f4435263af44369 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Thu, 7 May 2020 09:16:16 -0500 Subject: Remove debugging lib. --- challenge-059/jaredor/perl/ch-1.pl | 1 - 1 file changed, 1 deletion(-) (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-1.pl b/challenge-059/jaredor/perl/ch-1.pl index 97b1b78426..14a277516d 100755 --- a/challenge-059/jaredor/perl/ch-1.pl +++ b/challenge-059/jaredor/perl/ch-1.pl @@ -2,7 +2,6 @@ use v5.012; use warnings; -use Data::Dump qw(pp); use Getopt::Long; use List::Util qw(all); use Scalar::Util qw(looks_like_number); -- cgit From 8c07c3e93f48b59e6d8aa89414274b1d1cdc6d88 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Thu, 7 May 2020 09:17:03 -0500 Subject: Pretty much the final version of Task #2 unless I want to handle huge integers --- challenge-059/jaredor/perl/ch-2.pl | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-2.pl b/challenge-059/jaredor/perl/ch-2.pl index 5ba39a26a0..9acee3e679 100755 --- a/challenge-059/jaredor/perl/ch-2.pl +++ b/challenge-059/jaredor/perl/ch-2.pl @@ -1 +1,29 @@ #!/usr/bin/env perl + +use v5.012; +use warnings; +use Config; +use List::Util qw(all sum); + +# PWC 059, TASK #2 : Bit Sum + +# Answer based on perl doc for unpack and www.perlmonks.org/?node_id=407933 + +my ( $LL, $NN ) = + defined $Config{longlongsize} + ? ( 8 * $Config{longlongsize}, 'Q' ) + : ( 8 * $Config{longsize}, 'N' ); + +die "This script requires one or more positive integer arguments." + unless @ARGV; + +die "Not all arguments to the script are positive integers." + unless all { /\A [1-9] \d* \Z/xms } @ARGV; + +my @nums = map { pack "${NN}*", $_ } @ARGV; + +my (@diffbits, $num); +while ($num = shift @nums) { + push @diffbits, unpack( "%${LL}b*", $num ^ $_ ) for @nums; +} +say @diffbits ? sum @diffbits : 0; -- cgit From 177df50b7a6f4702e666b5e7377a8ffe4eef61f1 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Sat, 9 May 2020 16:57:34 -0500 Subject: The polished version of the limited-to-a-64-bit-word version. --- challenge-059/jaredor/perl/ch-2.pl | 14 +++++++------- 1 file changed, 7 insertions(+), 7 deletions(-) (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-2.pl b/challenge-059/jaredor/perl/ch-2.pl index 9acee3e679..ce5ae1f0cd 100755 --- a/challenge-059/jaredor/perl/ch-2.pl +++ b/challenge-059/jaredor/perl/ch-2.pl @@ -9,21 +9,21 @@ use List::Util qw(all sum); # Answer based on perl doc for unpack and www.perlmonks.org/?node_id=407933 -my ( $LL, $NN ) = - defined $Config{longlongsize} - ? ( 8 * $Config{longlongsize}, 'Q' ) - : ( 8 * $Config{longsize}, 'N' ); - die "This script requires one or more positive integer arguments." unless @ARGV; die "Not all arguments to the script are positive integers." unless all { /\A [1-9] \d* \Z/xms } @ARGV; +my ( $LL, $NN ) = + defined $Config{longlongsize} + ? ( 8 * $Config{longlongsize}, 'Q' ) + : ( 8 * $Config{longsize}, 'L' ); + my @nums = map { pack "${NN}*", $_ } @ARGV; -my (@diffbits, $num); -while ($num = shift @nums) { +my ( @diffbits, $num ); +while ( $num = pop @nums ) { push @diffbits, unpack( "%${LL}b*", $num ^ $_ ) for @nums; } say @diffbits ? sum @diffbits : 0; -- cgit From 545b1ac0f487c742b81ee0772cae1f3de36978d1 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Sat, 9 May 2020 16:59:52 -0500 Subject: use bigint and chop arbitrarilly large numbers into words to be bitwise diffed. --- challenge-059/jaredor/perl/ch-2.pl | 38 +++++++++++++++++++++++++++++--------- 1 file changed, 29 insertions(+), 9 deletions(-) (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-2.pl b/challenge-059/jaredor/perl/ch-2.pl index ce5ae1f0cd..4cd8a0563b 100755 --- a/challenge-059/jaredor/perl/ch-2.pl +++ b/challenge-059/jaredor/perl/ch-2.pl @@ -2,28 +2,48 @@ use v5.012; use warnings; +use bigint; use Config; -use List::Util qw(all sum); +use List::Util qw(all sum max); # PWC 059, TASK #2 : Bit Sum # Answer based on perl doc for unpack and www.perlmonks.org/?node_id=407933 +my ( $LL, $NN ) = + defined $Config{longlongsize} + ? ( 8 * $Config{longlongsize}, 'Q' ) + : ( 8 * $Config{longsize}, 'L' ); + +my $CHOP_SIZE = 2**${LL}; +my $CHOP_ZERO = pack "${NN}", 0; + die "This script requires one or more positive integer arguments." unless @ARGV; die "Not all arguments to the script are positive integers." unless all { /\A [1-9] \d* \Z/xms } @ARGV; -my ( $LL, $NN ) = - defined $Config{longlongsize} - ? ( 8 * $Config{longlongsize}, 'Q' ) - : ( 8 * $Config{longsize}, 'L' ); +#my @nums = map { pack "${NN}*", $_ } @ARGV; + +sub chop_up { + my ( $num, @chopped ) = ( 0 + $_[0], ); + while ($num) { + push @chopped, $num % $CHOP_SIZE; + $num = int( $num / $CHOP_SIZE ); + } + return [ map { pack "${NN}", $_ } @chopped ]; +} -my @nums = map { pack "${NN}*", $_ } @ARGV; +my @nums = map { chop_up $_ } @ARGV; +my $chops = max map { $#$_ } @nums; +( $chops - $#$_ ) and push @$_, ($CHOP_ZERO) x ( $chops - $#$_ ) for @nums; -my ( @diffbits, $num ); -while ( $num = pop @nums ) { - push @diffbits, unpack( "%${LL}b*", $num ^ $_ ) for @nums; +my ( @diffbits, $numa ); +while ( $numa = shift @nums ) { + for my $numb (@nums) { + push @diffbits, unpack( "%${LL}b*", $numa->[$_] ^ $numb->[$_] ) + for 0 .. $chops; + } } say @diffbits ? sum @diffbits : 0; -- cgit From 43761bc6e29b86d43551883c7f11f97c3b74afdd Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Sat, 9 May 2020 17:01:24 -0500 Subject: Simpler version for arbitrarilly large numbers. --- challenge-059/jaredor/perl/ch-2.pl | 41 ++++++++++++++------------------------ 1 file changed, 15 insertions(+), 26 deletions(-) (limited to 'challenge-059') diff --git a/challenge-059/jaredor/perl/ch-2.pl b/challenge-059/jaredor/perl/ch-2.pl index 4cd8a0563b..873484518a 100755 --- a/challenge-059/jaredor/perl/ch-2.pl +++ b/challenge-059/jaredor/perl/ch-2.pl @@ -4,46 +4,35 @@ use v5.012; use warnings; use bigint; use Config; -use List::Util qw(all sum max); +use List::Util qw(all sum); # PWC 059, TASK #2 : Bit Sum # Answer based on perl doc for unpack and www.perlmonks.org/?node_id=407933 -my ( $LL, $NN ) = - defined $Config{longlongsize} - ? ( 8 * $Config{longlongsize}, 'Q' ) - : ( 8 * $Config{longsize}, 'L' ); - -my $CHOP_SIZE = 2**${LL}; -my $CHOP_ZERO = pack "${NN}", 0; - die "This script requires one or more positive integer arguments." unless @ARGV; die "Not all arguments to the script are positive integers." unless all { /\A [1-9] \d* \Z/xms } @ARGV; -#my @nums = map { pack "${NN}*", $_ } @ARGV; +my ( $LL, $NN ) = + defined $Config{longlongsize} + ? ( 8 * $Config{longlongsize}, 'Q' ) + : ( 8 * $Config{longsize}, 'L' ); + +my $WORD = 2**$LL; -sub chop_up { - my ( $num, @chopped ) = ( 0 + $_[0], ); - while ($num) { - push @chopped, $num % $CHOP_SIZE; - $num = int( $num / $CHOP_SIZE ); - } - return [ map { pack "${NN}", $_ } @chopped ]; +sub num2bitstr { + my ( $numstr, $bitstr ) = ( $_[0], ); + $bitstr .= pack "${NN}", $numstr % $WORD and $numstr /= $WORD while $numstr; + return $bitstr; } -my @nums = map { chop_up $_ } @ARGV; -my $chops = max map { $#$_ } @nums; -( $chops - $#$_ ) and push @$_, ($CHOP_ZERO) x ( $chops - $#$_ ) for @nums; +my @nums = map { num2bitstr $_ } @ARGV; -my ( @diffbits, $numa ); -while ( $numa = shift @nums ) { - for my $numb (@nums) { - push @diffbits, unpack( "%${LL}b*", $numa->[$_] ^ $numb->[$_] ) - for 0 .. $chops; - } +my ( @diffbits, $num ); +while ( $num = pop @nums ) { + push @diffbits, unpack( "%${LL}b*", $num ^ $_ ) for @nums; } say @diffbits ? sum @diffbits : 0; -- cgit From 9ffc8302194a0c269422c4ed2ae4f50db5fb3124 Mon Sep 17 00:00:00 2001 From: Jared Martin Date: Sun, 10 May 2020 01:52:30 -0500 Subject: The blog entry explaining or excusing it all. --- challenge-059/jaredor/blog.txt | 1 + 1 file changed, 1 insertion(+) create mode 100644 challenge-059/jaredor/blog.txt (limited to 'challenge-059') diff --git a/challenge-059/jaredor/blog.txt b/challenge-059/jaredor/blog.txt new file mode 100644 index 0000000000..5b7a3e390d --- /dev/null +++ b/challenge-059/jaredor/blog.txt @@ -0,0 +1 @@ +http://blogs.perl.org/users/jared_martin/2020/05/pwc-059-task-1-linked-list-task-2-bit-sum.html -- cgit