I’ve been doing the Perl Weekly
Challenges. The
latest
involved lots of digit splitting. (Note that this is open until 13
June 2021.)
TASK #1 › Number Sequence
You are given a number $N >= 10
.
Write a script to split the given number such that the difference
between two consecutive numbers is always 1 and it shouldn’t have
a leading 0.
Print the given number if it's impossible to split the number.
I don't want to have multiple return types, so if the breakdown fails
I return a list with one entry in it rather than a bare number.
A couple of extra test cases this time:
910911 → [910,911]
– the 1-length and 2-length initial substrings
don't work, but the 3-length one does.
(I don't think there can ever be an input that's validly breakable
at two different substring lengths, but if there is, my code will
return just the shorter one.)
9109119 → [9109119]
– everything is going well until we run out of
characters. (I didn't actually need this but it seemed as though it
might be useful.)
But basically this comes down to: for each initial substring length
from 1 up to half the string length, get the initial number, and then
extend the list with more numbers to see if it matches the input.
In Raku:
sub ns($n) {
my $l=chars($n);
for 1..floor($l/2) -> $sl {
my $i=$sl;
my @e=(substr($n,0,$sl))+0;
while (1) {
if ($l-$i == 0) {
last;
}
push @e,@e[*-1]+1;
my $el=chars(@e[*-1]);
if ($l-$i < $el ||
substr($n,$i,$el) ne @e[*-1]) {
@e=();
last;
}
$i+=$el;
}
if (@e) {
return @e;
}
}
return [$n];
}
Python, Rust and even Ruby are more wedded to their
string-as-list-of-characters ideas, so one indexes into them with
ranges rather than using a substr
-equivalent… which means caring
about which languages have a inclusive range and which don't. (The
main argument for end exclusivity, so a range of "0 to 10" actually
runs from 0 to 9, seems to be that it makes it easier not to run off
the end of an array. I'm not convinced. But a lot of this is probably
what I'm used to.)
Another approach that occurred to me later was, for each initial
substring, to build the string until it's long enough and only then
check whether it matches. That will clearly be slower with a very long
input (because it has to build up the whole input length before it
starts to check) but it's easier to write. Here it is, also in Raku
for ease of comparison:
sub ns($n) {
my $l=chars($n);
for 1..floor($l/2) -> $sl {
my @e=(substr($n,0,$sl))+0;
while (1) {
push @e,@e[*-1]+1;
my $es=@e.join('');
if ($es.chars>$l) {
last;
}
if ($es.chars==$l &&
$es eq $n) {
return @e;
}
}
}
return [$n];
}
The list of numbers that can be broken into at least two consecutive
integers in this way is in the OEIS.
TASK #2 › Sum of Squares
You are given a number $N >= 10
.
Write a script to find out if the given number $N
is such that sum
of squares of all digits is a perfect square. Print 1 if it is
otherwise 0.
Like many of these problems I don't see an application for this, but…
here's the Rust version (with an intermediate variable ii
so that I
can avoid using a power function).
fn sos (n: u32) -> u8 {
let mut t=0;
for i in n.to_string().chars() {
let ii=i.to_digit(10).unwrap();
t+=ii*ii;
}
let s=(t as f64).sqrt() as u32;
if s*s == t {
return 1;
} else {
return 0;
}
}
If I were doing this with larger numbers, I'd build a hash of
digits and counts: so the input 32172304220 would become {0 => 2, 1 => 1, 2 => 4, 3 => 2, …}
. Then I'd iterate over that hash:
- 1²=1 ×1 = 1
- 2²=4 ×4 =16
- 3²=9 ×2 =18
- etc.
and add up all of those. Here's the (slightly longer) Rust to
calculate t
that way, replacing the first five lines of the above:
let mut d: HashMap<u32,u32>=HashMap::new();
for i in n.to_string().chars() {
let en=d.entry(i.to_digit(10).unwrap()).or_insert(0);
*en += 1;
}
let t=d.iter().map(|(k,v)| k*k*v).sum();
Thanks to Ilmari for pointing out entry()
for this bit of hash
manipulation I've been finding very frustrating in Rust. Also note the
convenient iter()
method on a HashMap for an efficient way of
iterating over all key-value pairs as pairs; in Perl this is each
but for some reason I rarely use it. I like that last line; that
chain of transformations is what a functional programming style is all
about, as far as I'm concerned. It's just a pity that the variable
definition and assignment still has to be on the left.
For further optimisation, there are squareness tests that are partly
effective (they'll flag up some, but not all, numbers that definitely
aren't perfect squares) which don't involve the lengthy calculation of
the square root, so if I had to plough through huge numbers of these
I'd use them to avoid that calculation where possible.
Here
is an example of the sort of thing I'm talking about. I didn't bother
to code them up, though.
(And yes, the sequence of numbers for which this is true is in the
OEIS.)
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.