Merge pull request #9088 from ianrifkin/ianrifkin-challenge-243

Submissions for perl and python - and a brief blog post

6 files changed, 315 insertions, 89 deletions

diff --git a/challenge-243/ianrifkin/README.md b/challenge-243/ianrifkin/README.md
index a519c9fd16..10bfcf4aa0 100644
--- a/challenge-243/ianrifkin/README.md
+++ b/challenge-243/ianrifkin/README.md
@@ -1,131 +1,113 @@
-# I'm a Map
+# loop-de-loop
 
-Challenge 242: https://theweeklychallenge.org/blog/perl-weekly-challenge-242/
+Challenge 243: https://theweeklychallenge.org/blog/perl-weekly-challenge-243/
 
-This week's challenge is pretty fun because it's one of those types of problems that seems really easy but you can end up spending a bunch of time trying to figure out how to solve it in a way that makes some sense.
+I decided to take what I think is a simple approcah to solving this week's problems (and I basically did the same approach in both tasks).
 
-## Task 1: Missing Members
+## Task 1: Reverse Pairs
 ```
-You are given two arrays of integers.
+You are given an array of integers.
 
-Write a script to find out the missing members in each other arrays.
+Write a script to return the number of reverse pairs in the given array.
+
+A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].
 
 Example 1
-Input: @arr1 = (1, 2, 3)
-       @arr2 = (2, 4, 6)
-Output: ([1, 3], [4, 6])
+Input: @nums = (1, 3, 2, 3, 1)
+Output: 2
 
-(1, 2, 3) has 2 members (1, 3) missing in the array (2, 4, 6).
-(2, 4, 6) has 2 members (4, 6) missing in the array (1, 2, 3).
+(1, 4) => nums[1] = 3, nums[4] = 1, 3 > 2 * 1
+(3, 4) => nums[3] = 3, nums[4] = 1, 3 > 2 * 1
 Example 2
-Input: @arr1 = (1, 2, 3, 3)
-       @arr2 = (1, 1, 2, 2)
-Output: ([3])
+Input: @nums = (2, 4, 3, 5, 1)
+Output: 3
 
-(1, 2, 3, 3) has 2 members (3, 3) missing in the array (1, 1, 2, 2). Since they are same, keep just one.
-(1, 1, 2, 2) has 0 member missing in the array (1, 2, 3, 3).
+(1, 4) => nums[1] = 4, nums[4] = 1, 4 > 2 * 1
+(2, 4) => nums[2] = 3, nums[4] = 1, 3 > 2 * 1
+(3, 4) => nums[3] = 5, nums[4] = 1, 5 > 2 * 1
 ```
 
-My command-line knowledge makes me think of just having two files and `diff`'ing them. If I needed to solve this for a real purpose I would probably look to using List::Compare to get it done. But for the challenges I like to think about how else I could go about solving for it.
-
-When I first started writing code I tried to:
-1) create an hash for each array
-2) create an array using the hash to grep values in the other array
-3) process the output array to de-duplicate
-4) parse the de-duped output array for pretty printing
+I added some extra code to my solutions in support of features like supporting command-line input, but let's focus on the code that actually solves the task.
 
-It worked but it felt messy. Taking a step back to refactor I realized that I could create an array of hashes for the output, very succicintly:
+I pass the `@nums` array to a subroutine `reverse_pairs` which has a nested `for` loop in it. We want to count how many times `$nums[$i]` is `>` `$nums[$j] * 2` where `$j` is any item after `$i` in the array. Since there is no point to look at an `$i` with no `$j` the parent loop should contain every array element except the last one:
 
 ```
-my @result_hashes = (
-    {map { $_ => check_if_exists($_, $arr2) } @{$arr1}},
-    {map { $_ => check_if_exists($_, $arr1) } @{$arr2}}
-    );
+for (my $i = 0; $i < @nums-1; $i++)
 ```
 
-This sets each hash's key to the the value from the array. Then `check_if_exists` just `grep`s the other array for the value and returns true or false:
+Within the above loop I created a nested loop to compare `$nums[$i]` to every value after it in the array. We know that `$j` is after `$i` so the loop can start at the element after `$i` and continues to the end of the array:
 ```
-sub check_if_exists {
-    my ($k, $arr) = @_;
-    return 1 if grep /$k/, @{$arr};
-    return 0;
-}
+for (my $j = $i+1; $j < @nums; $j++)
 ```
 
+Within that loop I increment a counter whenever `$nums[$i] > $nums[$j] * 2`
 
-That's it! Since the `@result_hashes` array contains hashes it is de-duped by naturely. The only remaining step is printing. Interestingly I expended more lines of code to get the printing in the desired format.
+The full sub is as follows:
 
-Parse hashed results into an @output array where the output array will end up having two values (one for each input).
-
-I loop through the array of hashed results putting the key from the hash in an array if the hash key's value is false (meaning the number was not found in the other array):
 ```
-foreach (@result_hashes) {
-	my %h = %{$_};
-	my @tmp_out = ();
-
-	foreach my $key ( keys %h ) { 
-	    push(@tmp_out, $key) unless $h{$key};
+sub reverse_pairs {
+    my @nums = @_;
+    my $pairs_found = 0;
+    for (my $i = 0; $i < @nums-1; $i++) {
+	for (my $j = $i+1; $j < @nums; $j++) {
+	    $pairs_found++ if ($nums[$i] > $nums[$j] * 2);
 	}
-```
-Then I put that output into the @output array. Note that that point of having the @tmp_out step is solely to have separation between the two inputs. e.g. I want the output from example 1 to be `(['3','1'],['4','6'])` and not `('3','1','4','6')`:
-```
-push(@output, \@tmp_out) if @tmp_out;
-```
-
-For the final step (and not to make this any longer) I used `Data::Dumper` to return the `@output` array in the desired format:
-```
-$Data::Dumper::Terse = 1; #don't print VAR names
-$Data::Dumper::Indent = 0; #keep output on one line
-return '(' . join(',', Dumper(@output)) . ')';
+    }
+    return $pairs_found;
+}
 ```
 
-## Task 2: Flip Matrix
 
+## Task 2: Floor Sum
 ```
-You are given n x n binary matrix.
+You are given an array of positive integers (>=1).
 
-Write a script to flip the given matrix as below.
+Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.
 
-1 1 0
-0 1 1
-0 0 1
-
-a) Reverse each row
-
-0 1 1
-1 1 0
-1 0 0
-
-b) Invert each member
-
-1 0 0
-0 0 1
-0 1 1
 
 Example 1
-Input: @matrix = ([1, 1, 0], [1, 0, 1], [0, 0, 0])
-Output: ([1, 0, 0], [0, 1, 0], [1, 1, 1])
+Input: @nums = (2, 5, 9)
+Output: 10
+
+floor(2 / 5) = 0
+floor(2 / 9) = 0
+floor(5 / 9) = 0
+floor(2 / 2) = 1
+floor(5 / 5) = 1
+floor(9 / 9) = 1
+floor(5 / 2) = 2
+floor(9 / 2) = 4
+floor(9 / 5) = 1
 Example 2
-Input: @matrix = ([1, 1, 0, 0], [1, 0, 0, 1], [0, 1, 1, 1], [1, 0, 1, 0])
-Output: ([1, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1], [1, 0, 1, 0])
+Input: @nums = (7, 7, 7, 7, 7, 7, 7)
+Output: 49
 ```
 
-This was a fun task becasuse it's really simple to just look at the examples to know the output (especially with short array lenghts). Reversing numbers and flipping 0's and 1's is easy to do in your head. But how to do it in code? It ends up that it doesn't have to be very tricky either.
+My solution to this task is very similar to my approach to solving task 1. Again I start with a loop of every array item, but this time the parent loop does include the last element in the array:
+```
+for (my $i = 0; $i < @nums; $i++)
+```
 
-I solved this task by passing the matrix array to a sub `matrix_flip` which just uses Perl's native `reverse` to put the array in backwards order then a simple conditional `map` that sets 1's to 0 and 0's to 1. Other than that is just some parentheses and commas for output readability.
+Likewise, the nested loop within it needs to include every element (including where `$i == $j`) so it's basically the same loop as its parent:
+```
+for (my $j = 0; $j < @nums; $j++)
+```
+
+Within that loop I take the floor of `$nums[$i] / $nums[$j]` and add it to the sum of the previous values. To calculate the floor I was going to use the actual `floor()` from `POSIX` but just used `int()` -- I think it's good enough for this task but note that `int()` can sometimes produce counterintuitive results (see https://perldoc.perl.org/functions/int).
+
+The full sub is as follows:
 
 ```
-sub matrix_flip {
-    my @matrix_rows = @_;
-    my @new_matrix = ();
-    
-    foreach my $row (@matrix_rows) {
-	#the actual flipping - use reverse to swap order and the map to flip values
-	my @new_row = '[' . join (", ", reverse map {$_ == 0 ? 1 : 0} @{$row}) . ']';
-	push (@new_matrix, @new_row);
+sub sum_floors {
+    my @nums = @_;
+    my $sum_floors = 0;
+    for (my $i = 0; $i < @nums; $i++) {
+	for (my $j = 0; $j < @nums; $j++) {
+	    $sum_floors += int($nums[$i] / $nums[$j]);
+	}
     }
-    return '(' . join (", ", @new_matrix) . ')';
+    return $sum_floors;
 }
 ```
 
-The full code with comments is available at https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-242/ianrifkin
\ No newline at end of file
+The full code with comments is available at https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-243/ianrifkin
\ No newline at end of file
diff --git a/challenge-243/ianrifkin/blog.txt b/challenge-243/ianrifkin/blog.txt
new file mode 100644
index 0000000000..08c5105786
--- /dev/null
+++ b/challenge-243/ianrifkin/blog.txt
@@ -0,0 +1 @@
+https://github.com/manwar/perlweeklychallenge-club/tree/master/challenge-243/ianrifkin#readme
diff --git a/challenge-243/ianrifkin/perl/ch-1.pl b/challenge-243/ianrifkin/perl/ch-1.pl
new file mode 100644
index 0000000000..073c9ee761
--- /dev/null
+++ b/challenge-243/ianrifkin/perl/ch-1.pl
@@ -0,0 +1,83 @@
+use v5.30.3;
+use warnings;
+use strict;
+use Getopt::Long;
+use Pod::Usage;
+
+# Challenge 243, Task 1: Reverse Pairs
+
+my $man = 0;
+my $help = 0;
+my $str_input;
+GetOptions ('help|?' => \$help, man => \$man,
+	    "nums=s" => \$str_input)
+    or pod2usage(2);
+
+pod2usage(1) if $help;
+pod2usage(-exitstatus => 0, -verbose => 2) if $man;
+
+# Prepare input array
+my @nums;
+# if values provided at cmd line split on comma
+if ( $str_input ) {
+    say reverse_pairs(split(/,/, $str_input));    
+}
+# else set default values from example if no cmd line input
+else {
+    # Example 1
+    my @nums = (1, 3, 2, 3, 1);
+    say reverse_pairs(@nums);
+
+    #Example 2
+    @nums = (2, 4, 3, 5, 1);
+    say reverse_pairs(@nums);    
+}
+
+sub reverse_pairs {
+    my @nums = @_;
+    my $pairs_found = 0;
+    for (my $i = 0; $i < @nums-1; $i++) {
+	for (my $j = $i+1; $j < @nums; $j++) {
+	    $pairs_found++ if ($nums[$i] > $nums[$j] * 2);
+	}
+    }
+    return $pairs_found;
+}
+
+__END__
+
+=head1 Challenge 243, Task 1, by IanRifkin: Reverse Pairs
+
+You are given an array of integers.
+
+Write a script to return the number of reverse pairs in the given array.
+
+A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].
+
+See https://theweeklychallenge.org/blog/perl-weekly-challenge-243/#TASK1 for more information on this challenge
+
+=head1 SYNOPSIS
+
+perl ./ch-1.pl [options]
+
+=head1 OPTIONS
+
+=over 8
+
+=item B<-help>
+
+Print a brief help message and exits.
+
+=item B<-man>
+
+Prints the manual page and exits.
+
+=item B<-nums>
+
+An optional comma separated list of positive integers (else defaults to values from examples)
+
+=back
+
+
+
+
diff --git a/challenge-243/ianrifkin/perl/ch-2.pl b/challenge-243/ianrifkin/perl/ch-2.pl
new file mode 100644
index 0000000000..343465b811
--- /dev/null
+++ b/challenge-243/ianrifkin/perl/ch-2.pl
@@ -0,0 +1,82 @@
+use v5.30.3;
+use warnings;
+use strict;
+use Getopt::Long;
+use Pod::Usage;
+
+# Challenge 243, Task 2: Floor Sum
+
+my $man = 0;
+my $help = 0;
+my $str_input;
+GetOptions ('help|?' => \$help, man => \$man,
+	    "nums=s" => \$str_input)
+    or pod2usage(2);
+
+pod2usage(1) if $help;
+pod2usage(-exitstatus => 0, -verbose => 2) if $man;
+
+
+# Prepare input array
+my @nums;
+# if values provided at cmd line split on comma
+if ( $str_input ) {
+    say sum_floors(split(/,/, $str_input));    
+}
+# else set default values from example if no cmd line input
+else {
+    # Example 1
+    @nums = (2, 5, 9);
+    say sum_floors(@nums);
+
+    #Example 2
+    @nums = (7, 7, 7, 7, 7, 7, 7);
+    say sum_floors(@nums);
+}
+    
+sub sum_floors {
+    my @nums = @_;
+    my $sum_floors = 0;
+    for (my $i = 0; $i < @nums; $i++) {
+	for (my $j = 0; $j < @nums; $j++) {
+	    $sum_floors += int($nums[$i] / $nums[$j]);
+	}
+    }
+    return $sum_floors;
+}
+
+__END__
+
+=head1 Challenge 242, Task 2, by IanRifkin: Floor Sum
+
+You are given an array of positive integers (>=1).
+
+Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.
+
+See https://theweeklychallenge.org/blog/perl-weekly-challenge-243/#TASK2 for more information on this challenge
+
+=head1 SYNOPSIS
+
+perl ./ch-1.pl [options]
+
+=head1 OPTIONS
+
+=over 8
+
+=item B<-help>
+
+Print a brief help message and exits.
+
+=item B<-man>
+
+Prints the manual page and exits.
+
+=item B<-nums>
+
+An optional comma separated list of integers (else defaults to values from examples)
+
+=back
+
+
+
+
diff --git a/challenge-243/ianrifkin/python/ch-1.py b/challenge-243/ianrifkin/python/ch-1.py
new file mode 100644
index 0000000000..2dc99b736c
--- /dev/null
+++ b/challenge-243/ianrifkin/python/ch-1.py
@@ -0,0 +1,40 @@
+#!/usr/local/bin/python3
+import sys, argparse
+
+# Challenge 243, Task 1: Reverse Pairs
+
+# You are given an array of integers.
+# Write a script to return the number of reverse pairs in the given array.
+# A reverse pair is a pair (i, j) where: a) 0 <= i < j < nums.length and b) nums[i] > 2 * nums[j].
+# See https://theweeklychallenge.org/blog/perl-weekly-challenge-243/#TASK1 for more information on this challenge
+
+def main(argv):
+    argParser = argparse.ArgumentParser()
+    argParser.add_argument("-n", "--nums", nargs='+', type=int, help="space seperated list of integers e.g. -n 10 30 4 5")
+    args = argParser.parse_args()
+
+    if args.nums:
+        nums = args.nums
+        print( reverse_pairs(nums) )
+    else:
+        #Example 1
+        nums = (1, 3, 2, 3, 1)
+        print( reverse_pairs(nums) )     
+        #Example 2
+        nums = (2, 4, 3, 5, 1)
+        print( reverse_pairs(nums) )        
+        
+def reverse_pairs(nums):
+    pairs_found = 0
+    for i, inum in enumerate(nums):
+        for j, jnum in enumerate(nums):
+            if i >= j:
+                pass
+            else:
+                if inum > jnum * 2:
+                    pairs_found = pairs_found + 1
+    return pairs_found
+                    
+        
+if __name__ == "__main__":
+   main(sys.argv[1:])
diff --git a/challenge-243/ianrifkin/python/ch-2.py b/challenge-243/ianrifkin/python/ch-2.py
new file mode 100644
index 0000000000..f12c1dcfc1
--- /dev/null
+++ b/challenge-243/ianrifkin/python/ch-2.py
@@ -0,0 +1,38 @@
+#!/usr/local/bin/python3
+import sys, argparse
+import math
+
+# Challenge 243, Task 2: Floor Sum
+
+# You are given an array of positive integers (>=1).
+# Write a script to return the sum of floor(nums[i] / nums[j]) where 0 <= i,j < nums.length. The floor() function returns the integer part of the division.
+# See https://theweeklychallenge.org/blog/perl-weekly-challenge-243/#TASK2 for more information on this challenge
+
+# else set default values from example if no cmd line input
+
+def main(argv):
+    argParser = argparse.ArgumentParser()
+    argParser.add_argument("-n", "--nums", nargs='+', type=int, help="space seperated list of positive integers e.g. -n 10 30 4 5")
+    args = argParser.parse_args()
+
+    if args.nums:
+        nums = args.nums
+        print( sum_floors(nums) )
+    else:
+        #Example 1
+        nums = (2, 5, 9)
+        print( sum_floors(nums) )     
+        #Example 2
+        nums = (7, 7, 7, 7, 7, 7, 7)
+        print( sum_floors(nums) )        
+        
+def sum_floors(nums):
+    sum_of_floors = 0
+    for i, inum in enumerate(nums):
+        for j, jnum in enumerate(nums):
+            sum_of_floors = sum_of_floors + math.floor(inum / jnum)
+    return sum_of_floors
+                    
+        
+if __name__ == "__main__":
+   main(sys.argv[1:])