RogerBW's Blog

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.