From ae3e42824c7cb46ce76f5c9a795693a6b27afaac Mon Sep 17 00:00:00 2001 From: irifkin Date: Thu, 2 Nov 2023 14:23:46 -0400 Subject: perl solutions --- challenge-241/ianrifkin/perl/ch-1.pl | 37 +++++++++ challenge-241/ianrifkin/perl/ch-2.pl | 142 +++++++++++++++++++++++++++++++++++ 2 files changed, 179 insertions(+) create mode 100644 challenge-241/ianrifkin/perl/ch-1.pl create mode 100644 challenge-241/ianrifkin/perl/ch-2.pl diff --git a/challenge-241/ianrifkin/perl/ch-1.pl b/challenge-241/ianrifkin/perl/ch-1.pl new file mode 100644 index 0000000000..2fdc858d18 --- /dev/null +++ b/challenge-241/ianrifkin/perl/ch-1.pl @@ -0,0 +1,37 @@ +use v5.30.3; +use warnings; +use strict; + +# Task 1: Arithmetic Triplets +# You are given an array (3 or more members) of integers in increasing order and a positive integer. +# Write a script to find out the number of unique Arithmetic Triplets satisfying the following rules: +# a) i < j < k +# b) nums[j] - nums[i] == diff +# c) nums[k] - nums[j] == diff + +# Example 1 +my @nums = (0, 1, 4, 6, 7, 10); +my $diff = 3; +find_triplets($diff, \@nums); + +# Example 2 +@nums = (4, 5, 6, 7, 8, 9); +$diff = 2; +find_triplets($diff, \@nums); + +sub find_triplets { + my ($diff, $nums) = @_; + my $nums_length = scalar @{$nums}; + my $total_finds = 0; + for (my $i = 0; $i < $nums_length - 2; $i++) { + for (my $j = $i + 1; $j < $nums_length - 1; $j++) { + for (my $k = $j + 1; $k < $nums_length; $k++) { + if (@{$nums}[$j] - @{$nums}[$i] eq $diff && @{$nums}[$k] - @{$nums}[$j] eq $diff) { + $total_finds++; + } + } + } + } + print "$total_finds\n"; +} + diff --git a/challenge-241/ianrifkin/perl/ch-2.pl b/challenge-241/ianrifkin/perl/ch-2.pl new file mode 100644 index 0000000000..95e484fb96 --- /dev/null +++ b/challenge-241/ianrifkin/perl/ch-2.pl @@ -0,0 +1,142 @@ +use v5.30.3; +use warnings; +use strict; +use Getopt::Long; +use Pod::Usage; + +#accept cmd line input +my $man = 0; +my $help = 0; +my $str_input; +GetOptions ('help|?' => \$help, man => \$man, + "int_input=s" => \$str_input) + or pod2usage(2); + +pod2usage(1) if $help; +pod2usage(-exitstatus => 0, -verbose => 2) if $man; + +# Prepare input array +my @int_input; +# if values provided at cmd line split on comma +if ( $str_input ) { + @int_input = (split(/,/, $str_input) ); +} +# else set default values from example if no cmd line input +else { + @int_input = (11, 8, 27, 4) unless @int_input; +} + +# run the program +prime_order(\@int_input); + + +sub prime_order { + my ($int_input) = @_; + + my %results; + # Let's calcuate how many prime factors of each input number + foreach (@{$int_input}) { + my $num = $_; + $num =~ s/^\s+//; #remove whitespace is provided at cmd line just for prettiness + + die("Invalid input") if $num <= 2; #This shouldn't happen based on task instructions + + #Every number will have at least one prime (self) + $results{$num} = 1; + + # Find the first prime factor (or self if it is prime) + my $find_prime = prime_finder($num); + + next unless $find_prime; # go to next num if no prime found (e.g. input is 3) + + next if ($find_prime == $num); # go to next $num in loop if input number was prime + + # since input num was not prime, increment for smallest factor + # then we will loop below to find the other factors + $results{$num}++; + + # Calc all remaining prime factors + my $smallest = $num / $find_prime; #the smallest prime so loop knows when to stop + while ($find_prime > $smallest) { + my $new_find_prime = prime_finder($find_prime); #calc next prime + last unless $new_find_prime; #exit loop if no prime found + last if $find_prime == $new_find_prime; #exit loop if prime found is same + $results{$num}++; #incr. if prime found + $find_prime = $new_find_prime; #start next loop or exit loop + } + + next; #expclitly showing that we're going to next $num (just for clarity) + } + + # Now we need to prepare the ouptut + # Create a sorted array from the results hash + my @sorted_output; + # This should should by the count first ($results{$a} <=> $results{$b}) then the input numbers ($b cmp $a) + foreach my $ordered_num (sort { $results{$a} <=> $results{$b} or $a <=> $b } keys %results) { + push(@sorted_output, $ordered_num); + } + + # Finally, print the sorted output + say "(" . join(", ", @sorted_output) . ")"; +} + +# This subroutine outputs a prime number from the provided input $num +sub prime_finder { + my ($num) = @_; + my $num_was_prime; + for (my $i = 2; $i <= sqrt($num); $i++) { + if ($num % $i == 0) { + return $num / $i; + $num_was_prime = 0; + last; + } + else { + $num_was_prime = 1; + } + + } + return $num if $num_was_prime; +} + + +__END__ + +=head1 Challenge 241, Task 2, by IanRifkin: Prime Order + +See https://theweeklychallenge.org/blog/perl-weekly-challenge-241/#TASK2 for more information on this challenge + +=head1 SYNOPSIS + +perl ./ch-2.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<-int_input> + +An optional comma separated list of numbers (else defaults to values from example 1) + +=back + +=head1 DESCRIPTION + +Task 2 in Challenge 241 states: + + - You are given an array of unique positive integers greater than 2. + + - Write a script to sort them in ascending order of the count of their prime factors, tie-breaking by ascending value. + +This program accepts an optional comma separated list of numbers else defaults to the provided numbers from example 1. + +Note: There is an assumption that "tie-breaking by ascending value" means the value of the input number (vs. the value of their prime factor) + +=cut -- cgit From 25b7cd78a7df9fff61c3975713fae77b3ca8eadd Mon Sep 17 00:00:00 2001 From: irifkin Date: Thu, 2 Nov 2023 15:05:40 -0400 Subject: Challenge 241 README Blog --- challenge-241/ianrifkin/README.md | 157 +++++++++++++++++++++++++------------- challenge-241/ianrifkin/blog.txt | 1 + 2 files changed, 107 insertions(+), 51 deletions(-) create mode 100644 challenge-241/ianrifkin/blog.txt diff --git a/challenge-241/ianrifkin/README.md b/challenge-241/ianrifkin/README.md index a3d7bf545f..3c47888b88 100644 --- a/challenge-241/ianrifkin/README.md +++ b/challenge-241/ianrifkin/README.md @@ -1,83 +1,138 @@ # A.A.B.A. (Acronym And Build Array) -Challenge 240: https://theweeklychallenge.org/blog/perl-weekly-challenge-240/ +Challenge 241: https://theweeklychallenge.org/blog/perl-weekly-challenge-241/ -## Task 1: Acronym +## Task 1: Arithmetic Triplets -> You are given an array of strings and a check string. +``` +You are given an array (3 or more members) of integers in increasing order and a positive integer. -> Write a script to find out if the check string is the acronym of the words in the given array. +Write a script to find out the number of unique Arithmetic Triplets satisfying the following rules: +a) i < j < k +b) nums[j] - nums[i] == diff +c) nums[k] - nums[j] == diff Example 1 -``` -Input: @str = ("Perl", "Python", "Pascal") - $chk = "ppp" -Output: true -``` +Input: @nums = (0, 1, 4, 6, 7, 10) + $diff = 3 +Output: 2 +Index (1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3. +Index (2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3. Example 2 -``` -Input: @str = ("Perl", "Raku") - $chk = "rp" -Output: false -``` +Input: @nums = (4, 5, 6, 7, 8, 9) + $diff = 2 +Output: 2 -Example 3 -``` -Input: @str = ("Oracle", "Awk", "C") - $chk = "oac" -Output: true +(0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2. +(1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2. ``` -I am sure there are plenty of more interesting ways to solve this but the way my mind works is to create a real acronym by looping through each word in the in the input array to get the first letter. +A quick read of this task was overwhelming to me because it sounded like it was going to be more math than I could handle, but upon closer inspection the answer is in the description. -``` -sub check_acronym { - my ($acronym, $words) = @_; - my $real_acronym; - foreach (@{$words}) { - $real_acronym .= substr($_, 0, 1); - } -``` +I kept it simple and just explicitely created the three loops with the three specified iterators. It's very helpful to match the incrementor names in my code with the task's description. -With that in place just compare the strings, forcing them both into uppercase so that it's a case insensitive comparison. You could also do this with a simple RegEx compare but this feels simpler to write/read to my brain. +I started by looping through the input array with an incrementer `$i`. We know that $i is needed for the first value so the max $i is going to be 2 less than the total array length: `for (my $i = 0; $i < $nums_length - 2; $i++)` -``` -uc($acronym) eq uc($real_acronym) ? print "true\n" : print "false\n"; -``` +Within this loop I just make the next loop with `$j` which is 1 more than `$i` to 1 less than the array length: `for (my $j = $i + 1; $j < $nums_length - 1; $j++)` -I did a similar approach with Raku and Python. With Perl the final print statement is a conditional so that it will print the words "true" or "false" instead of 0 or 1 but that's not needed with Python and Raku. +Finally within that loop I create the loop with `$k` which is going to be 1 more than `$j` to the end of the array: `for (my $k = $j + 1; $k < $nums_length; $k++)` -## Task 2: Build Array +Now that I have my loops I go back to the instructions which stated: +nums[j] - nums[i] == diff +and +nums[k] - nums[j] == diff -> You are given an array of integers. +which in my Perl code is simple: `(@{$nums}[$j] - @{$nums}[$i] eq $diff && @{$nums}[$k] - @{$nums}[$j] eq $diff)` -> Write a script to create an array such that new[i] = old[old[i]] where 0 <= i < new.length. +Anytime the above is true it increments a counter `$total_finds`. After the loops are complete it prints the `$total_finds` counter. + +The complete `sub find_triplets` is as follows: -Example 1 ``` -Input: @int = (0, 2, 1, 5, 3, 4) -Output: (0, 1, 2, 4, 5, 3) +sub find_triplets { + my ($diff, $nums) = @_; + my $nums_length = scalar @{$nums}; + my $total_finds = 0; + for (my $i = 0; $i < $nums_length - 2; $i++) { + for (my $j = $i + 1; $j < $nums_length - 1; $j++) { + for (my $k = $j + 1; $k < $nums_length; $k++) { + if (@{$nums}[$j] - @{$nums}[$i] eq $diff && @{$nums}[$k] - @{$nums}[$j] eq $diff) { + $total_finds++; + } + } + } + } + print "$total_finds\n"; +} ``` -Example 2 + +Full script with comments available at https://github.com/ianrifkin/perlweeklychallenge-club/blob/ianrifkin-challenge-241/challenge-241/ianrifkin/perl/ch-1.pl + + +## Task 2: Prime Order ``` -Input: @int = (5, 0, 1, 2, 3, 4) -Output: (4, 5, 0, 1, 2, 3) +You are given an array of unique positive integers greater than 2. + +Write a script to sort them in ascending order of the count of their prime factors, tie-breaking by ascending value. + +Example 1 +Input: @int = (11, 8, 27, 4) +Output: (11, 4, 8, 27)) + +Prime factors of 11 => 11 +Prime factors of 4 => 2, 2 +Prime factors of 8 => 2, 2, 2 +Prime factors of 27 => 3, 3, 3 ``` -Doing `new[i] = old[old[i]]` seemed simple enough but I do have trouble mentally processing `where 0 <= i < new.length`. If `i` is a postion of the input array it is always going to be equal to or greater than 0 because of how arrays are numbered. Since each new[i] is mapped to a value calculated from the old array they should naturally end up the same length, so `i` should never be longer than new.length because `i` shouldn't be less than old.length either. +This one sounded simple enough but I needed to write WAY more code to accomplish. Though to be fair, part of the length is a lot more code commends and documentation. + +I split up the work into 2 subroutines. The second one is simpler so let's talk about that first. I created a `prime_finder` to accept a number and output its prime. + +In the sub I have a for loop where the iterator goes from 2 to the square root of the number, which I calculated with the sqrt() function. I have it find the prime by taking the number and dividing by the iterator and seeing if it equals 0. -With that out of the way, I did a simple for loop using the iterator variable `$i` -- within the loop I am literally just doing the exact mapping from the question: `new[i] = old[old[i]]` +When it finds the prime instead of returning that value I'm returning the number / that prime iterator value so that I can use it later to calcuate the remaining values. + +For example, given the input 8 it will find the value 2 then return 4 (because 8/2=4). This will allow the other subroutine to calculate the complete list: 2,2,2 for input 8. + +The only other things that `prime_finder` does is if $num % $i does not equal to 0 in any of the loops then that means that the input number was actually prime so it will return the input number. ``` -for (my $i = 0; $i < @ints; $i++) { - $new_ints[$i] = $ints[$ints[$i]]; +sub prime_finder { + my ($num) = @_; + my $num_was_prime; + for (my $i = 2; $i <= sqrt($num); $i++) { + if ($num % $i == 0) { + return $num / $i; + $num_was_prime = 0; + last; + } + else { + $num_was_prime = 1; + } + + } + return $num if $num_was_prime; } ``` -That's it! After the loop I print the new array in the desired format: -``` -print "(" . join(', ', @new_ints) . ")\n"; -``` +The subroutine that calls the above and does the sorting and output printing took a notable amount of time to think through and test and troubleshoot, especially since I wanted it to work for any input (and any amount of input). + +The sub accepts the input array of numbers and loops through each one. It creates a hash `%results` to store the count of prime factors for each number. + +The loop starts by setting `$results{$num} = 1;` because every number will have at least the prime factor of itself. + +Next I use the `prime_finder()` sub on the input number to get the value. + +If the `prime_finder()` value is undefined or equal to the input number, we're done and can proceed to the next number in the loop. + +If `prime_finder()` returned a new number I increment `$results{$num}` to account for the smallest factor than loop to find the remaining factors, if applicable. + +The loop goes from the initial value returned by `prime_finder()` to the value of the input number devided by that `prime_finder()` value, which should be the smallest factor (hence why I already incremented for the smallest factor above). + +In the loop I calculate the next prime with `prime_finder()` then either increment the counter or exit the loop if no new prime is found. If a prime was found, in addition to incrementing the counter I then loop back through using the new `prime_finder()` value. + +With all the looping complete I sort the `%results` hash first by its values (the counter) then do a secondary sort on the key (the input number), which I save in an array. I am assuming that `tie-breaking by ascending value` mean the value of the input number. At the end I just print the `@sorted_output` array. -This task sounded more complicated so I will be curious to see if others took a more interesting approach. \ No newline at end of file +The full code with comments is available at https://github.com/ianrifkin/perlweeklychallenge-club/blob/ianrifkin-challenge-241/challenge-241/ianrifkin/perl/ch-2.pl \ No newline at end of file diff --git a/challenge-241/ianrifkin/blog.txt b/challenge-241/ianrifkin/blog.txt new file mode 100644 index 0000000000..409085ddee --- /dev/null +++ b/challenge-241/ianrifkin/blog.txt @@ -0,0 +1 @@ +https://github.com/ianrifkin/perlweeklychallenge-club/blob/ianrifkin-challenge-240/challenge-241/ianrifkin/README.md -- cgit From 2299a0cae293bf36b96d6add038d03b9109c3a91 Mon Sep 17 00:00:00 2001 From: irifkin Date: Thu, 2 Nov 2023 15:08:37 -0400 Subject: blog title --- challenge-241/ianrifkin/README.md | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/challenge-241/ianrifkin/README.md b/challenge-241/ianrifkin/README.md index 3c47888b88..79bab2131b 100644 --- a/challenge-241/ianrifkin/README.md +++ b/challenge-241/ianrifkin/README.md @@ -1,7 +1,9 @@ -# A.A.B.A. (Acronym And Build Array) +# Math is hard Challenge 241: https://theweeklychallenge.org/blog/perl-weekly-challenge-241/ +Some of The Weekly Challenges are more intimidating for me based on how math-heavy the task feels. The first task seemed overwhelming but was pretty quick to create a solution, yet the second task took me much longer. + ## Task 1: Arithmetic Triplets ``` -- cgit From 701bbe6c70ba04a11b669d0c0ff9f47c648abb1a Mon Sep 17 00:00:00 2001 From: irifkin Date: Thu, 2 Nov 2023 15:19:59 -0400 Subject: documentation formatting edits and fixing a typo in task 1 code --- challenge-241/ianrifkin/README.md | 28 +++++++++++++++------------- challenge-241/ianrifkin/perl/ch-1.pl | 2 +- 2 files changed, 16 insertions(+), 14 deletions(-) diff --git a/challenge-241/ianrifkin/README.md b/challenge-241/ianrifkin/README.md index 79bab2131b..fcbd11b19e 100644 --- a/challenge-241/ianrifkin/README.md +++ b/challenge-241/ianrifkin/README.md @@ -34,18 +34,20 @@ A quick read of this task was overwhelming to me because it sounded like it was I kept it simple and just explicitely created the three loops with the three specified iterators. It's very helpful to match the incrementor names in my code with the task's description. -I started by looping through the input array with an incrementer `$i`. We know that $i is needed for the first value so the max $i is going to be 2 less than the total array length: `for (my $i = 0; $i < $nums_length - 2; $i++)` +I started by looping through the input array with an incrementer `$i`. We know that `$i` is needed for the first value so the max `$i` is going to be 2 less than the total array length: `for (my $i = 0; $i < $nums_length - 2; $i++)` Within this loop I just make the next loop with `$j` which is 1 more than `$i` to 1 less than the array length: `for (my $j = $i + 1; $j < $nums_length - 1; $j++)` Finally within that loop I create the loop with `$k` which is going to be 1 more than `$j` to the end of the array: `for (my $k = $j + 1; $k < $nums_length; $k++)` Now that I have my loops I go back to the instructions which stated: +``` nums[j] - nums[i] == diff and nums[k] - nums[j] == diff +``` -which in my Perl code is simple: `(@{$nums}[$j] - @{$nums}[$i] eq $diff && @{$nums}[$k] - @{$nums}[$j] eq $diff)` +which in my Perl code is literally that same thing: `$nums[$j] - $nums[$i] == $diff && $nums[$k] - $nums[$j] == $diff` Anytime the above is true it increments a counter `$total_finds`. After the loops are complete it prints the `$total_finds` counter. @@ -88,17 +90,17 @@ Prime factors of 8 => 2, 2, 2 Prime factors of 27 => 3, 3, 3 ``` -This one sounded simple enough but I needed to write WAY more code to accomplish. Though to be fair, part of the length is a lot more code commends and documentation. +This one sounded simple enough but I needed to write WAY more code to accomplish. Though to be fair, part of the length is a lot more code comments and documentation -- critial because this quickly got confusing for me! -I split up the work into 2 subroutines. The second one is simpler so let's talk about that first. I created a `prime_finder` to accept a number and output its prime. +I split up the work into 2 subroutines. The second one is simpler so let's talk about that first. I created a `prime_finder()` to accept a number and output a prime factor. -In the sub I have a for loop where the iterator goes from 2 to the square root of the number, which I calculated with the sqrt() function. I have it find the prime by taking the number and dividing by the iterator and seeing if it equals 0. +In the sub I have a `for` loop where the iterator goes from 2 to the square root of the number, which I calculated with the `sqrt()` function. I have it find the prime by taking the number and dividing by the iterator and seeing if it equals 0. -When it finds the prime instead of returning that value I'm returning the number / that prime iterator value so that I can use it later to calcuate the remaining values. +When it finds the prime instead of returning that value I'm returning the number divided by that prime iterator value so that I can use it later to calcuate the remaining values. -For example, given the input 8 it will find the value 2 then return 4 (because 8/2=4). This will allow the other subroutine to calculate the complete list: 2,2,2 for input 8. +For example, given the input 8 it will find the value 2 then return 4 (because 8/2=4). This will allow the other subroutine to calculate the complete list of prime factors: 2,2,2 for input 8. -The only other things that `prime_finder` does is if $num % $i does not equal to 0 in any of the loops then that means that the input number was actually prime so it will return the input number. +The only other things that `prime_finder` does is if `$num % $i` does not equal to 0 in any of the loops then that means that the input number was actually prime so it will return the input number. ``` sub prime_finder { @@ -123,18 +125,18 @@ The subroutine that calls the above and does the sorting and output printing too The sub accepts the input array of numbers and loops through each one. It creates a hash `%results` to store the count of prime factors for each number. -The loop starts by setting `$results{$num} = 1;` because every number will have at least the prime factor of itself. +The loop starts by setting `$results{$num} = 1;` because every number will have at least have the prime factor of itself. -Next I use the `prime_finder()` sub on the input number to get the value. +Next I use the `prime_finder()` sub on the input number to get the value I decribed. If the `prime_finder()` value is undefined or equal to the input number, we're done and can proceed to the next number in the loop. -If `prime_finder()` returned a new number I increment `$results{$num}` to account for the smallest factor than loop to find the remaining factors, if applicable. +If `prime_finder()` returned a new number, then I increment `$results{$num}` to account for the smallest factor than loop to find the remaining factors, if applicable. The loop goes from the initial value returned by `prime_finder()` to the value of the input number devided by that `prime_finder()` value, which should be the smallest factor (hence why I already incremented for the smallest factor above). -In the loop I calculate the next prime with `prime_finder()` then either increment the counter or exit the loop if no new prime is found. If a prime was found, in addition to incrementing the counter I then loop back through using the new `prime_finder()` value. +In the loop, I calculate the next prime with `prime_finder()` then either increment the counter or exit the loop if no new prime is found. If a prime was found, in addition to incrementing the counter I then loop back through using the new `prime_finder()` value. -With all the looping complete I sort the `%results` hash first by its values (the counter) then do a secondary sort on the key (the input number), which I save in an array. I am assuming that `tie-breaking by ascending value` mean the value of the input number. At the end I just print the `@sorted_output` array. +With all the (potentially mind-boggling) looping complete I sort the `%results` hash first by its values (the counter) then do a secondary sort on the key (the input number), which I save in an array. I am assuming that `tie-breaking by ascending value` mean the value of the input number. At the end I just print the `@sorted_output` array. The full code with comments is available at https://github.com/ianrifkin/perlweeklychallenge-club/blob/ianrifkin-challenge-241/challenge-241/ianrifkin/perl/ch-2.pl \ No newline at end of file diff --git a/challenge-241/ianrifkin/perl/ch-1.pl b/challenge-241/ianrifkin/perl/ch-1.pl index 2fdc858d18..2b9d7a6d8e 100644 --- a/challenge-241/ianrifkin/perl/ch-1.pl +++ b/challenge-241/ianrifkin/perl/ch-1.pl @@ -26,7 +26,7 @@ sub find_triplets { for (my $i = 0; $i < $nums_length - 2; $i++) { for (my $j = $i + 1; $j < $nums_length - 1; $j++) { for (my $k = $j + 1; $k < $nums_length; $k++) { - if (@{$nums}[$j] - @{$nums}[$i] eq $diff && @{$nums}[$k] - @{$nums}[$j] eq $diff) { + if (@{$nums}[$j] - @{$nums}[$i] == $diff && @{$nums}[$k] - @{$nums}[$j] == $diff) { $total_finds++; } } -- cgit From 331981ef44321e04939ed96a027d1a9bacee6972 Mon Sep 17 00:00:00 2001 From: irifkin Date: Fri, 3 Nov 2023 15:36:09 -0400 Subject: refactorign ch-2 and updating README --- challenge-241/ianrifkin/README.md | 64 +++++++++++++++++------------------- challenge-241/ianrifkin/perl/ch-2.pl | 57 ++++++++++---------------------- 2 files changed, 48 insertions(+), 73 deletions(-) diff --git a/challenge-241/ianrifkin/README.md b/challenge-241/ianrifkin/README.md index fcbd11b19e..ece05ca910 100644 --- a/challenge-241/ianrifkin/README.md +++ b/challenge-241/ianrifkin/README.md @@ -1,4 +1,4 @@ -# Math is hard +# Math is hard? Challenge 241: https://theweeklychallenge.org/blog/perl-weekly-challenge-241/ @@ -90,53 +90,51 @@ Prime factors of 8 => 2, 2, 2 Prime factors of 27 => 3, 3, 3 ``` -This one sounded simple enough but I needed to write WAY more code to accomplish. Though to be fair, part of the length is a lot more code comments and documentation -- critial because this quickly got confusing for me! +This one sounded simple enough but I needed to write WAY more code to accomplish. Though to be fair, part of the length is a lot more code comments and documentation -- critial because this quickly got confusing for me! After I completed it and it was working, I wasn't happy with how long the code got and how I was handling the looping so I refactored it a bit. The main different is the first attempt I really started by trying to find the prime factors and then counting them up. This was useful because it allowed me to check as I went along to make sure I was counting the right things appropriately. But once I got a good sense of it I realized it could be done quicker -- though mostly it's to reduce what felt like messy extra loops in code. -I split up the work into 2 subroutines. The second one is simpler so let's talk about that first. I created a `prime_finder()` to accept a number and output a prime factor. +I split up the work into 2 subroutines. -In the sub I have a `for` loop where the iterator goes from 2 to the square root of the number, which I calculated with the `sqrt()` function. I have it find the prime by taking the number and dividing by the iterator and seeing if it equals 0. -When it finds the prime instead of returning that value I'm returning the number divided by that prime iterator value so that I can use it later to calcuate the remaining values. +The main sub, `prime_order()`, accepts an array of integers. It loops through the array to create a hash where the key is the input number from the array and the value is number of prime factors for that number. It generates the count of prime factors by calling a sub `prime_finder()`. -For example, given the input 8 it will find the value 2 then return 4 (because 8/2=4). This will allow the other subroutine to calculate the complete list of prime factors: 2,2,2 for input 8. - -The only other things that `prime_finder` does is if `$num % $i` does not equal to 0 in any of the loops then that means that the input number was actually prime so it will return the input number. +```prime_finder``` +After the loop is complete `prime_order()` will create and print a sorted array based on the hash results. ``` -sub prime_finder { - my ($num) = @_; - my $num_was_prime; - for (my $i = 2; $i <= sqrt($num); $i++) { - if ($num % $i == 0) { - return $num / $i; - $num_was_prime = 0; - last; - } - else { - $num_was_prime = 1; - } - + foreach my $ordered_num (sort { $results{$a} <=> $results{$b} or $a <=> $b } keys %results) { + push(@sorted_output, $ordered_num); } - return $num if $num_was_prime; -} -``` -The subroutine that calls the above and does the sorting and output printing took a notable amount of time to think through and test and troubleshoot, especially since I wanted it to work for any input (and any amount of input). + # Finally, print the sorted output + say "(" . join(", ", @sorted_output) . ")"; +``` -The sub accepts the input array of numbers and loops through each one. It creates a hash `%results` to store the count of prime factors for each number. +The sub `prime_finder()` is what actually cacluates the number of prime factors for a given input number. -The loop starts by setting `$results{$num} = 1;` because every number will have at least have the prime factor of itself. -Next I use the `prime_finder()` sub on the input number to get the value I decribed. +I start by having a while loop set to repeat endlessly with a manual condition flag. This will be important based on my approach. -If the `prime_finder()` value is undefined or equal to the input number, we're done and can proceed to the next number in the loop. +Within the while loop I have a for loop that will find the biggest prime factor for a given number. The loop starts at the square root of the number `$i = int(sqrt($num))` and checks if a prime is found by seeing if dividing the number by the iterator has a remainder: `if ($num % $i == 0)` -If `prime_finder()` returned a new number, then I increment `$results{$num}` to account for the smallest factor than loop to find the remaining factors, if applicable. +Some examples: -The loop goes from the initial value returned by `prime_finder()` to the value of the input number devided by that `prime_finder()` value, which should be the smallest factor (hence why I already incremented for the smallest factor above). +input is 11 --> int of square root is 3 --> first prime factor found is 1 (meaning 11 is a prime number). In this case it increments the counter by 1 then exits the parent while loop. -In the loop, I calculate the next prime with `prime_finder()` then either increment the counter or exit the loop if no new prime is found. If a prime was found, in addition to incrementing the counter I then loop back through using the new `prime_finder()` value. +input is 27 --> int of square root is 5 --> first prime factor found is 3. The counter gets incremented to 1. To determine how many other prime factors it would take, I set the `$num` variable to `27 / 3` which is 9 and I exit the `for` loop, restarting it with the new `$num`. In this next iteration the prime found is 3. I increment the counter. Then it goes one more time where it determines that 3 is a prime number and does the final increment. -With all the (potentially mind-boggling) looping complete I sort the `%results` hash first by its values (the counter) then do a secondary sort on the key (the input number), which I save in an array. I am assuming that `tie-breaking by ascending value` mean the value of the input number. At the end I just print the `@sorted_output` array. +``` + while ($calculating) { + for (my $i = int(sqrt($num)); $i >= 1; $i--) { + #looping backwards to find biggest prime factor first + if ($num % $i == 0) { #if prime factor found + $counter++; #increment that we found a prime factor + $calculating = 0 if ($i == 1); #if the prime factor is 1 stop the parent while loop + $num = $num / $i; #otherwise reset num lower to search for the next prime factor + last; #and restart for loop with new number + } + + } + } +``` The full code with comments is available at https://github.com/ianrifkin/perlweeklychallenge-club/blob/ianrifkin-challenge-241/challenge-241/ianrifkin/perl/ch-2.pl \ No newline at end of file diff --git a/challenge-241/ianrifkin/perl/ch-2.pl b/challenge-241/ianrifkin/perl/ch-2.pl index 95e484fb96..18c5c5a206 100644 --- a/challenge-241/ianrifkin/perl/ch-2.pl +++ b/challenge-241/ianrifkin/perl/ch-2.pl @@ -29,7 +29,6 @@ else { # run the program prime_order(\@int_input); - sub prime_order { my ($int_input) = @_; @@ -40,36 +39,12 @@ sub prime_order { $num =~ s/^\s+//; #remove whitespace is provided at cmd line just for prettiness die("Invalid input") if $num <= 2; #This shouldn't happen based on task instructions - - #Every number will have at least one prime (self) - $results{$num} = 1; - - # Find the first prime factor (or self if it is prime) - my $find_prime = prime_finder($num); - - next unless $find_prime; # go to next num if no prime found (e.g. input is 3) - - next if ($find_prime == $num); # go to next $num in loop if input number was prime - # since input num was not prime, increment for smallest factor - # then we will loop below to find the other factors - $results{$num}++; - - # Calc all remaining prime factors - my $smallest = $num / $find_prime; #the smallest prime so loop knows when to stop - while ($find_prime > $smallest) { - my $new_find_prime = prime_finder($find_prime); #calc next prime - last unless $new_find_prime; #exit loop if no prime found - last if $find_prime == $new_find_prime; #exit loop if prime found is same - $results{$num}++; #incr. if prime found - $find_prime = $new_find_prime; #start next loop or exit loop - } - - next; #expclitly showing that we're going to next $num (just for clarity) + # Get number of prime factors + $results{$num} = prime_finder($num); } - # Now we need to prepare the ouptut - # Create a sorted array from the results hash + # Prepare the ouptut in a nice sorted array my @sorted_output; # This should should by the count first ($results{$a} <=> $results{$b}) then the input numbers ($b cmp $a) foreach my $ordered_num (sort { $results{$a} <=> $results{$b} or $a <=> $b } keys %results) { @@ -80,22 +55,24 @@ sub prime_order { say "(" . join(", ", @sorted_output) . ")"; } -# This subroutine outputs a prime number from the provided input $num sub prime_finder { + # This sub finds the number of prime factors for a given number my ($num) = @_; - my $num_was_prime; - for (my $i = 2; $i <= sqrt($num); $i++) { - if ($num % $i == 0) { - return $num / $i; - $num_was_prime = 0; - last; + my $counter = 0; #the number of prime factors + my $calculating = 1; + while ($calculating) { + for (my $i = int(sqrt($num)); $i >= 1; $i--) { + #looping backwards to find biggest prime factor first + if ($num % $i == 0) { #if prime factor found + $counter++; #increment that we found a prime factor + $calculating = 0 if ($i == 1); #if the prime factor is 1 stop the parent while loop + $num = $num / $i; #otherwise reset num lower to search for the next prime factor + last; #and restart for loop with new number + } + } - else { - $num_was_prime = 1; - } - } - return $num if $num_was_prime; + return $counter; } -- cgit