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