PWC 052 › Stepping Numbers

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Task #1 this week is straightforward. Here’s what Mohammad had to say about it:

Write a script to accept two numbers between 100 and 999. It should then print all Stepping Numbers between them.

A number is called a stepping number if the adjacent digits have a difference of 1. For example, 456 is a stepping number but 129 is not.

Update [2020-Mar-28]

There seem to have been two interpretations to this problem. In my weekly review, I noticed there were several people in both of the following groups:

1. Digits are monotonically increasing, or monotonically decreasing. This means 789 and 987 would be valid, but 989 would not. This was my interpretation.
2. Digits can increase or decrease by 1. This means 789, 987, and 989 would all be valid.

With the benefit of hindsight, and finding the sequence on OEIS (A033705), I believe interpretation #2 is correct, but given how many people went with #1, including Mohammad himself, I don’t feel quite as bad about it as I did an hour ago!

Perl

It would be easy to brute-force a solution by iterating for (100..999) and printing all the Stepping numbers, but since it’s easy to see that only a very small percentage of numbers are Stepping numbers, I went straight to a constructive solution instead.

I start with an empty array and then build it up:

my @step;
for my $n (1..9) {
    push @step, map { $n . join '',        $n+1..$_   }   $n..9;
    push @step, map { $n . join '', reverse  $_..$n-1 }    0..$n-1;
}

At this point, @step contains every stepping number. That’s right, all of them. While that may sound impressive, there are actually only 90 of them between 1 and 9876543210. We can either print the 3-digit ones, as specified in the task, or we can print all 90 of them:

# Only 3-digit results, per problem description
say join ' ', sort { $a <=> $b } grep 3 == length, @step;

# All results, because why not
say join ' ', sort { $a <=> $b } @step;

For the curious, the Stepping numbers are [edit: not quite]:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98, 123, 210, 234, 321, 345, 432, 456, 543, 567, 654, 678, 765, 789, 876, 987, 1234, 2345, 3210, 3456, 4321, 4567, 5432, 5678, 6543, 6789, 7654, 8765, 9876, 12345, 23456, 34567, 43210, 45678, 54321, 56789, 65432, 76543, 87654, 98765, 123456, 234567, 345678, 456789, 543210, 654321, 765432, 876543, 987654, 1234567, 2345678, 3456789, 6543210, 7654321, 8765432, 9876543, 12345678, 23456789, 76543210, 87654321, 98765432, 123456789, 876543210, 987654321, 9876543210

[Edit: See OEIS A033075 for the real sequence.]

Raku

I took the same approach in Raku, and the code ended up being rather similar as a result:

my @step;
for 1..9 -> $n {
    @step.push: |map { $n ~ ($n+1..$_)        .join: '' }, $n..9;
    @step.push: |map { $n ~ ($_..$n-1).reverse.join: '' },  0..$n-1;
}

say @step».Int.grep( 100 ≤ * ≤ 999 ).sort;

That’s it! Of course removing the grep(...) from the above expression would print all Stepping numbers.