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:
- Digits are monotonically increasing, or monotonically decreasing. This means 789 and 987 would be valid, but 989 would not. This was my interpretation.
- 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.