RogerBW's Blog

Perl Weekly Challenge 116: Square Sequence 10 June 2021

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.


  1. Posted by RogerBW at 06:35pm on 14 June 2021

    Part 1: a couple of bloggers built every possible partition of the input string and then tested each of them. Gosh!

    I did assume that the difference between elements is always +1, and that they'd be positive.

    Part 2: most of the answers looked like my main version, squaring each digit, and to be fair my optimisation probably doesn't save much time until you get to truly huge numbers – but I find it more elegant.

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 2300ad 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech bayern beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 essen 2024 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1