I’ve been doing the Weekly
Challenges. The
latest
involved date calculations and numerical decompositions. (Note
that this is open until 21 November 2021.)
Task 1: Jort Sort
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.
Finally I'm allowed to return a Boolean rather than 1/0! Hurrah!
This is of course Jenn Schiffer's Javascript
framework. It must be good, it's got a logo
and everything! (More history
here.)
What's more, with my massive manly and testosterone-soaked brain, I
have improved the algorithm.
Which of course isn't the point, and arguably a sort followed by an
array comparison would be more in the spirit of the original. But I
did get to learn some new language features, so there's that.
The basic idea of this approach is to compare pairs of entries: if an
earlier one is higher than a later one, the list isn't sorted and we
can return without doing the rest of the comparisons. In Perl (the
only language here without explicit Boolean constants) and PostScript
I lay that out by hand using array indices:
sub jortsort {
my $a=shift;
foreach my $i (1..$#{$a}) {
if ($a->[$i-1] > $a->[$i]) {
return 0;
}
}
return 1;
}
/jortsort {
/a exch def
/ret true def
1 1 a length 1 sub {
dup
1 sub a exch get exch
a exch get
gt {
/ret false def
exit
} if
} for
ret
} bind def
In Python I have zip
, which lets me merge two iterables into one.
def jortsort(a):
So I make two separately-iterable copies of the list
j, k = tee(a)
step once through one of them
next(k,None)
then iterate them in parallel
for i in zip(j,k):
if i[0] > i[1]:
return False
return True
And in Raku, Ruby and Rust, as well as zip
as above I have explicit
methods (with wildly different names) for taking overlapping N-sized
chunks off a single iterable. (To be fair, Python gets pairwise
to
do the same thing in 3.10, at least for the case of 2-sized chunks,
but I'm running 3.7 here on Debian/oldstable.) Probably one could wrap
something like any
round them to get rid of the explicit looping
entirely, but eh.
sub jortsort(@a) {
for @a.rotor(2 => -1) -> @i {
if (@i[0] > @i[1]) {
return False;
}
}
return True;
}
def jortsort(a)
a.each_cons(2) { |i|
if i[0] > i[1] then
return false
end
}
return true
end
fn jortsort(a: Vec<i32>) -> bool {
for i in a.windows(2) {
if i[0] > i[1] {
return false;
}
}
true
}
Task 2: Long Primes
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.
OK, there are clearly two steps here: generate primes, then check the
decimal expansion. There's some disagreement in the more general case
over whether 2 should count; it and 5 are the only two primes where
(1/p) has a non-repeating expansion, but the example sets us right. So
it's "full reptend primes" rather than
"long-period primes". (By inspection, 3
and 5 won't qualify under either condition, and therefore I start at
7.)
Step one, a reasonably efficient primality tester, since I haven't got
round to writing one for these things before. Shown in Python, for
compactness, working on the basis that after 2 and 3 every prime
number has the form (6k+1) or (6k-1) (because 6k+(0, 2, 3 or 4) will
always be divisible by 2 or 3).
(Raku has a built-in probabilistic tester, but with numbers these
small I want to be deterministic.)
def is_prime(n):
if n>2 and n%2==0:
return 0
if n>3 and n%3==0:
return 0
lim=int(sqrt(n))
k6=0
while 1:
k6+=6
for t in [k6-1,k6+1]:
if t <= lim:
if n % t == 0:
return False
else:
return True
Then it's a matter of finding the length of the decimal expansion. I
found some
fascinating
blog
posts
on ways of doing this, and ended up using the simple one, optimising
it further because I'm always dealing with fractions of the form
(1/prime).
I use the 6k±1 technique again to find prime candidates, test them,
then get the length of the decimal expansion using Brent's approach
of repeated modulus calculation.
Python again, taking a parameter for the number to produce because a
mere 5 was boring.
def longprime(n):
nn=n
ba=[7]
k6=6
while nn>0:
if len(ba)==0:
k6+=6
ba=[k6+1,k6-1]
b=ba.pop()
if is_prime(b):
k=1
l=0
while 1:
k*=10
l+=1
k %= b
if k==1:
break
if l==b-1:
o.append(b)
nn-=1
return o
The other languages all work basically the same way.
Full code on
github.
Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.