Perl Weekly Challenge 139.
My solutions (task 1, and task 2 ) to the The Weekly Challenge - 139.
Task 1: JortSort
Submitted by: Mohammad S Anwar
You are given a list of numbers.
Write a script to implement JortSort. It should return
true/false depending if the given list of numbers are already
sorted.
Example 1:
Input: @n = (1,2,3,4,5)
Output: 1
Since the array is sorted, it prints 1.
Example 2:
Input: @n = (1,3,2,4,5)
Output: 0
Since the array is NOT sorted, it prints 0.
I just have to move along the array comparing consecutive
elements and quiting when I find a pair out of order. If I
reach the end, the array is sorted. I can use none from
List::Util to test pairs. I use variables $x, $y to keep
the previous and current value.
perl -MList::Util=none -E 'say "Input: ", join " ",@ARGV; $y=shift @ARGV;
say "Output: ", (none {($x,$y)=($y,$_); $x>$y}@ARGV)?1:0' 1 2 3 4 5
perl -MList::Util=none -E 'say "Input: ", join " ",@ARGV; $y=shift @ARGV;
say "Output: ", (none {($x,$y)=($y,$_); $x>$y}@ARGV)?1:0' 1 3 2 4 5
Results:
Input: 1 2 3 4 5
Output: 1
Input: 1 3 2 4 5
Output: 0
I check the edge cases of only one element in the list or none.
perl -MList::Util=none -E 'say "Input: ", join " ",@ARGV; $y=shift @ARGV;
say "Output: ", (none {($x,$y)=($y,$_); $x>$y}@ARGV)?1:0' 1
perl -MList::Util=none -E 'say "Input: ", join " ",@ARGV; $y=shift @ARGV;
say "Output: ", (none {($x,$y)=($y,$_); $x>$y}@ARGV)?1:0'
Results:
Input: 1
Output: 1
Input:
Output: 1
I believe it is correct to consider these cases as sorted, as there is no pair of consecutive values out of order.
The full version would be almost identical.
# Perl weekly challenge 139
# Task 1: JortSort
#
# See https://wlmb.github.io/2021/11/16/PWC139/#task-1-jortsort
use v5.12;
use warnings;
use List::Util qw(none);
say "Input: (", (join " ",@ARGV), ")";
my $x; # previous element
my $y=shift @ARGV; # current element
say "Output: ", (none {($x,$y)=($y,$_); $x>$y}@ARGV)?1:0;
Examples:
./ch-1.pl 1 2 3 4 5
./ch-1.pl 1 3 2 4 5
./ch-1.pl 1
./ch-1.pl
Results:
Input: (1 2 3 4 5)
Output: 1
Input: (1 3 2 4 5)
Output: 0
Input: (1)
Output: 1
Input: ()
Output: 1
I read somewhere that the jortsort algorithm first sorts the list and then compares the two lists, but it seems that is more work than needed. Anyway, it is simple enough to merit a onliner.
perl -MList::Util=all -MList::MoreUtils=pairwise -E '
@a=@ARGV; say "Input: ", join " ",@a; @s=sort {$a<=>$b}@a;
say "Output: ", (all {$_} pairwise{$a==$b}@a, @s)?1:0' 1 2 3 4 5
perl -MList::Util=all -MList::MoreUtils=pairwise -E '
@a=@ARGV; say "Input: ", join " ",@a; @s=sort {$a<=>$b}@a;
say "Output: ", (all {$_} pairwise{$a==$b}@a, @s)?1:0' 1 3 2 4 5
Results:
Input: 1 2 3 4 5
Output: 1
Input: 1 3 2 4 5
Output: 0
Task 2: Long Primes
Submitted by: Mohammad S Anwar
Write a script to generate first 5 Long Primes.
A prime number (p) is called Long Prime if (1/p) has an
infinite decimal expansion repeating every (p-1) digits.
Example
7 is a long prime since 1/7 = 0.142857142857...
The repeating part (142857) size is 6 i.e. one less than the
prime number 7.
Also 17 is a long prime since 1/17 =
0.05882352941176470588235294117647...
The repeating part (0588235294117647) size is 16 i.e. one less
than the prime number 17.
Another example, 2 is not a long prime as 1/2 = 0.5.
There is no repeating part in this case.
The succesive digits of 1/p may be obtained using long division, i.e., we start dividing 10/p using integer arithmetic to get a residue r1, then we divide 10r1/p to obtain the residue r2, which is also the residue of 100/p, 10r2/p to obtain r3, the residue of 1000/p, and so on. If some residue becomes 0, we terminate. If some residue repeats itself after n divisions, then we have an infinite repeating cycle of length n. As the residues cannot exceed p, their possible values are 0,1,…p-1. If p is a long prime, then the sequence of residues has to take all values 1,2,…p-1 once before repeating, though not generally in order. Thus, to check if the prime p is a long prime, it would be enough to check that 10p-1 has a residue 1 when divided by p and that there are no shorter cycles, i.e., that 10q for 0<q<p-1 doesn’t have a residue of 1.
perl -Mbignum=a,50 -MMath::Prime::Util=next_prime -MList::Util=first -E '
$p=2;$c=0; while($c<5){$p=next_prime($p); say("$p, as 1/$p=",1./$p),++$c
if (first {$x=10**$_%$p; $x==1}(1..$p-1))==$p-1}'
Results:
7, as 1/7=0.14285714285714285714285714285714285714285714285714
17, as 1/17=0.058823529411764705882352941176470588235294117647059
19, as 1/19=0.052631578947368421052631578947368421052631578947368
23, as 1/23=0.043478260869565217391304347826086956521739130434783
29, as 1/29=0.034482758620689655172413793103448275862068965517241
I used the bignum package so that I can go beyond the built in precision. I used the Math::Prime::Util package to generate consecutive primes. Finally, I used the List::Util package to look for the first repetition and check it coincides with the (p-1)-th.
The full version follows.
# Perl weekly challenge 139
# Task 2: Long Primes
#
# See https://wlmb.github.io/2021/11/16/PWC139/#task-2-long-primes
use v5.12;
use warnings;
use bignum;
use Math::Prime::Util qw(next_prime);
use List::Util qw(first);
use Text::Wrap qw(wrap $columns $break);
$columns=62;
$break=qr/\s|_/;
my $max_count=shift @ARGV//5; # get number of long primes from command line
my $prime=2; #current prime (will skip '2')
my $count=0;
my @lines;
while($count<$max_count){
$prime=next_prime($prime);
my $length=$prime-1; # expected length of large cycle
Math::BigFloat->accuracy(3.5*$length); # allow 3+ repetitions
my @groups= grep {$_} split /(\d{$length})/, 1./$prime; # groups of digits
pop @groups; # throw away last (guard) repetition (posibly inexact)
++$count, push @lines,
"long_prime[$count] is $prime",
" as 1/$prime = " . shift(@groups) . join "_", @groups,"..."
if (first # if cycle doesn't stop early
{my $x=10**$_%$prime; $x==1||$x==0}
(1..$prime-1))
== $prime-1
}
say wrap("", " _", $_) for @lines;
I used the join...split... trick to mark explicitly the beginning and end of
each cycle. I chose an accuracy of 3+ repetitions to
display three full repetitions and throw away the last, which
could have rounding errors. I used Text::Wrap to manage the
large lines expected for large repetition cycles.
Example: Print the first 10 long primes.
./ch-2.pl 10
Results:
1-th long prime is 7
as 1/7 = 0.142857_142857_142857_...
2-th long prime is 17
as 1/17 = 0.0588235294117647_0588235294117647
_0588235294117647_...
3-th long prime is 19
as 1/19 = 0.052631578947368421_052631578947368421
_052631578947368421_...
4-th long prime is 23
as 1/23 = 0.0434782608695652173913
_0434782608695652173913
_0434782608695652173913_...
5-th long prime is 29
as 1/29 = 0.0344827586206896551724137931
_0344827586206896551724137931
_0344827586206896551724137931_...
6-th long prime is 47
as 1/47 =
_0.0212765957446808510638297872340425531914
_893617
_021276595744680851063829787234042553191489
_3617
_021276595744680851063829787234042553191489
_3617_...
7-th long prime is 59
as 1/59 =
_0.0169491525423728813559322033898305084745
_762711864406779661
_016949152542372881355932203389830508474576
_2711864406779661
_016949152542372881355932203389830508474576
_2711864406779661_...
8-th long prime is 61
as 1/61 =
_0.0163934426229508196721311475409836065573
_77049180327868852459
_016393442622950819672131147540983606557377
_049180327868852459
_016393442622950819672131147540983606557377
_049180327868852459_...
9-th long prime is 97
as 1/97 =
_0.0103092783505154639175257731958762886597
_938144329896907216494845360824742268041237
_11340206185567
_010309278350515463917525773195876288659793
_814432989690721649484536082474226804123711
_340206185567
_010309278350515463917525773195876288659793
_814432989690721649484536082474226804123711
_340206185567_...
10-th long prime is 109
as 1/109 =
_0.0091743119266055045871559633027522935779
_816513761467889908256880733944954128440366
_97247706422018348623853211
_009174311926605504587155963302752293577981
_651376146788990825688073394495412844036697
_247706422018348623853211
_009174311926605504587155963302752293577981
_651376146788990825688073394495412844036697
_247706422018348623853211_...