From 4b000992aa6abf7f9d5d74700e87722e7c3db7d7 Mon Sep 17 00:00:00 2001 From: Abigail Date: Thu, 6 May 2021 13:51:20 +0200 Subject: Second Perl implementation --- challenge-111/abigail/README.md | 3 ++ challenge-111/abigail/perl/ch-1.pl | 78 ++++++++++++++++++++++++++++------ challenge-111/abigail/t/ctest.ini | 9 ++++ challenge-111/abigail/t/input-1-4 | 7 +++ challenge-111/abigail/t/input-1-5 | 7 +++ challenge-111/abigail/t/input-1-6 | 10 +++++ challenge-111/abigail/t/output-1-4.exp | 2 + challenge-111/abigail/t/output-1-5.exp | 2 + challenge-111/abigail/t/output-1-6.exp | 5 +++ 9 files changed, 109 insertions(+), 14 deletions(-) create mode 100644 challenge-111/abigail/t/input-1-4 create mode 100644 challenge-111/abigail/t/input-1-5 create mode 100644 challenge-111/abigail/t/input-1-6 create mode 100644 challenge-111/abigail/t/output-1-4.exp create mode 100644 challenge-111/abigail/t/output-1-5.exp create mode 100644 challenge-111/abigail/t/output-1-6.exp diff --git a/challenge-111/abigail/README.md b/challenge-111/abigail/README.md index 978fa5fdee..39cfe578f6 100644 --- a/challenge-111/abigail/README.md +++ b/challenge-111/abigail/README.md @@ -30,6 +30,9 @@ Only for language lacking hashes/maps/dictionaries/tables, we will make use of the fact the input is sorted. For the majority of languages, the fact input is sorted does not offer additional benefits. +For Perl, we make two implementations: one based on a hash, the +other using binary search. + ### Solutions * [AWK](awk/ch-1.awk) * [Bash](bash/ch-1.sh) diff --git a/challenge-111/abigail/perl/ch-1.pl b/challenge-111/abigail/perl/ch-1.pl index 00f6e2502d..ca06d26dea 100644 --- a/challenge-111/abigail/perl/ch-1.pl +++ b/challenge-111/abigail/perl/ch-1.pl @@ -14,7 +14,7 @@ use experimental 'lexical_subs'; # # -# Run as: perl ch-1.pl < input-file +# Run as: perl ch-1.pl [bsearch] < input-file # # @@ -29,22 +29,72 @@ use experimental 'lexical_subs'; # Perhaps the intend was a subroutine which takes a matrix and a target # number, but that was not what is being asked. The challenge explicitly # asks for *a script*, which means we have to spend a linear amount of -# time reading data anyway. So, that's what you get. +# time reading data anyway. # -# The only part where we use the fact we are given a matrix is for the -# input: the first five lines are assumed to contain the matrix. The -# rest of the input is taken as numbers to search for. +# Just to cover our bases, we'll do two implementation. Without arguments, +# we'll do that fast, hash bases, implementation. If the program is +# given the 'bsearch' argument, we will make use of a subroutine which +# takes a 2-d matrix and a target number as parameters, and which uses +# a bog standard binary search implementation to find out whether the +# target exists. # my $MATRIX_SIZE = 5; -# -# Read in a matrix of data -# -my %matrix; -@matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE; +my $HASH = 0; +my $BSEARCH = 1; -# -# Print 0/1 depending on whether the given number is in the matrix or not. -# -chomp, say exists $matrix {$_} || 0 while <> +my $TYPE = $HASH; + $TYPE = $BSEARCH if @ARGV && $ARGV [0] eq "bsearch"; + +@ARGV = (); + +if ($TYPE == $HASH) { + # + # Read in a matrix of data + # + my %matrix; + @matrix {<> =~ /-?[0-9]+/g} = () for 1 .. $MATRIX_SIZE; + + # + # Print 0/1 depending on whether the given number is in the matrix or not. + # + chomp, say exists $matrix {$_} || 0 while <>; + + exit; +} + +if ($TYPE == $BSEARCH) { + # + # Use binary search to find a target value into a sorted set. + # + my sub bsearch ($matrix, $target) { + my ($min, $max) = (0, $MATRIX_SIZE * $MATRIX_SIZE); + while ($min < $max) { + use integer; + my $mid = ($min + $max) / 2; + # + # To map a 1-d coordinate c to a 2-d pair x, y, we use + # x = floor (c / size), y = c % size. + # + my $cmp = $$matrix [$mid / $MATRIX_SIZE] + [$mid % $MATRIX_SIZE] <=> $target; + if ($cmp < 0) {$min = $mid + 1} + elsif ($cmp > 0) {$max = $mid} + else {return 1} + } + return (0) + } + + # + # Read in the matrix + # + my $matrix = [map {[<> =~ /-?[0-9]+/g]} 1 .. $MATRIX_SIZE]; + + # + # Check for existence for the rest of the data + # + say bsearch ($matrix, $_) for <>; + + exit; +} diff --git a/challenge-111/abigail/t/ctest.ini b/challenge-111/abigail/t/ctest.ini index 0c0dfde484..1cfc7fa7ae 100644 --- a/challenge-111/abigail/t/ctest.ini +++ b/challenge-111/abigail/t/ctest.ini @@ -7,10 +7,19 @@ 1-1 = Given example 1-2 = Use large numbers 1-3 = Use negative numbers +1-4 = Given example (binary search) +1-5 = Use large numbers (binary search) +1-6 = Use negative numbers (binary search) 2-1 = Enable.lst 2-2 = /usr/share/dict/words 2-3 = infochimps.com +[1-4,1-5,1-6] +skip = Only one implementation + +[1-4,1-5,1-6/perl] +skip = 0 + [2-1] input_file = /Users/abigail/Words/enable.lst diff --git a/challenge-111/abigail/t/input-1-4 b/challenge-111/abigail/t/input-1-4 new file mode 100644 index 0000000000..fa2f7e3fa1 --- /dev/null +++ b/challenge-111/abigail/t/input-1-4 @@ -0,0 +1,7 @@ + 1 2 3 5 7 + 9 11 15 19 20 +23 24 25 29 31 +32 33 39 40 42 +45 47 48 49 50 +35 +39 diff --git a/challenge-111/abigail/t/input-1-5 b/challenge-111/abigail/t/input-1-5 new file mode 100644 index 0000000000..14b659ea7d --- /dev/null +++ b/challenge-111/abigail/t/input-1-5 @@ -0,0 +1,7 @@ + 1000000 2000000 3000000 5000000 7000000 + 9000000 11000000 15000000 19000000 20000000 +23000000 24000000 25000000 29000000 31000000 +32000000 33000000 39000000 40000000 42000000 +45000000 47000000 48000000 49000000 50000000 +35000000 +39000000 diff --git a/challenge-111/abigail/t/input-1-6 b/challenge-111/abigail/t/input-1-6 new file mode 100644 index 0000000000..e5dd243924 --- /dev/null +++ b/challenge-111/abigail/t/input-1-6 @@ -0,0 +1,10 @@ +-9 -7 -5 -3 -2 + 0 11 15 19 20 +23 24 25 29 31 +32 33 39 40 42 +45 47 48 49 50 +-5 +-1 +0 +1 +11 diff --git a/challenge-111/abigail/t/output-1-4.exp b/challenge-111/abigail/t/output-1-4.exp new file mode 100644 index 0000000000..0d66ea1aee --- /dev/null +++ b/challenge-111/abigail/t/output-1-4.exp @@ -0,0 +1,2 @@ +0 +1 diff --git a/challenge-111/abigail/t/output-1-5.exp b/challenge-111/abigail/t/output-1-5.exp new file mode 100644 index 0000000000..0d66ea1aee --- /dev/null +++ b/challenge-111/abigail/t/output-1-5.exp @@ -0,0 +1,2 @@ +0 +1 diff --git a/challenge-111/abigail/t/output-1-6.exp b/challenge-111/abigail/t/output-1-6.exp new file mode 100644 index 0000000000..33f911e8c0 --- /dev/null +++ b/challenge-111/abigail/t/output-1-6.exp @@ -0,0 +1,5 @@ +1 +0 +1 +0 +1 -- cgit