One (2) One (1) Jump Street

Wherein we learn that the way we talk about things is sometimes more important than the things themselves. Skipping ahead across the context in the middle can speed the journey but often overshoots the goal.

THE WEEKLY CHALLENGE – PERL & RAKU #91

---

episode one:
“Just Say What You Mean!”

---

TASK #1 › Count Number

Submitted by: Mohammad S Anwar

You are given a positive number $N.

Write a script to count number and display as you read it.

Example 1:

Input: $N = 1122234
Output: 21321314

as we read "two 1 three 2 one 3 one 4"

Example 2:

Input: $N = 2333445
Output: 12332415

as we read "one 2 three 3 two 4 one 5"

Example 3:

Input: $N = 12345
Output: 1112131415

as we read "one 1 one 2 one 3 one 4 one 5"

Method

The challenge description here is asking us to present a number, that when read as a sequence of digits, describes the input number as quantifiers and values: “one one, three sixes, four eights” for the number 16668888. These digits and quantifiers would produce the output pairs (1-1), (3-6), (4-8), which when combined make the number 113648. One might consider this a version of Run Length Encoding.

So the puzzle here is to read the number left-to-right, counting the instances of a given digit as we go. When a digit is the same as the one previously, the count goes up; if it changes, we report the quantity and value and begin the count anew with the new value.

So essentially we need to notice when a number isn’t the same as the one previously, and to keep tabs on the number of steps we take progressing through the digits. If we keep appending our quantifier-value pairings to the output string as we go, then we’re good. Just remember that we’re creating a string of characters that looks like a number, rather than computing a number mathematically.

I put this kind of work into the broad category of what I call “Concrete Number Theory”, akin to concrete poetry, where the positioning and typography of the text itself is part of the poem.

An acute observer might also notice a serious deficiency in the encoding as well, but we’ll get to that.

PERL 5 SOLUTION

To accomplish the goal, we’ll need to keep track of two things: the current digit we are counting, and the count itself. As we read across, we can compare each new digit: if it’s the same as the current one we increment the counter and move on. If it’s changed, however, we concatenate the count and value pair onto an output string, make the new digit the current digit and loop back.

We proceed like this until we run out of digits, at which point we append the remaining count and digit combination to produce the final construct.

The steps of the process are condensed into a nice compact routine, speak_number. In fact once worked out, I thought it a little too easy. I can’t find any fault in the idea of iteratively parsing through the digits like this, especially as it reduced to three lines in the loop. But I wanted to play around some more. And furthermore, there was a problem.

“What’s this?” You say. Ahh, well from the example I came up with you may have noticed a fundamental limitation to not my method but rather the challenge itself: the whole idea only works for single-digit quantities. The solution, according to the rules, for this input:

12227786622222222222222222222222222222

is

1132271826292

We can see that 292 is a correct labeling of the 29 trailing twos, but it no longer reads correctly. It’s not two 9s and a stray 2, is it? That doesn’t mean anything; there’s no way to indicate that the first 2 and the 9 following mean “twenty-nine”. That trailing stray 2 might be an important clue, but should this multiple-digit pairing fall somewhere in the middle of the number there would be no way to tell which digits were quantifiers and which were values. This limitation is built into the structure of the problem itself, from the point when we run all of the numbers together without an explicit delimiter. If the implicit delimiter is one character per division, then, in base 10, there can only be 10 values. Or really 9, because in the context of the output, saying “there are no fours” doesn’t make any sense, as we are only list what is there. So what if we did want to read larger numbers correctly, somehow? How could we do that?

Well as the language of the description is that of reading, rather than encoding, it seemed to me that to properly read the number we could quite literally read it, and speak the description out loud, in English words.

Having finished the iterative loop version, I set out to modify the routine to speak properly. I immediately reached for Damien Conway’s excellent Lingua::EN::Inflexion module to handle the pluralization.

Although the module does provide a noun()->cardinal method to convert numbers to words, combining it with the markup interface proved more trouble than it was worth, so I made a quick lookup, providing the plural forms. The module seems to handle converting nouns back to singular better than going the other way. For some reason it kept on wanting to construct “twoes”, which my spellchecker is having a real problem with right now. In any case feeding it “twos” and letting it switch back as required works quite well, so I landed there. I also had to convert the output string to an array of quantity-noun pairings , so that I could join them together with commas, and added a $mult flag to set if there was more than one group, to handle the “and” at the end of the phrase. On success with the first steps I kept throwing complexities at the problem until I was satisfied with every little part, ending up with a complete well-constructed sentence. A little capitalization and punctuation and voila!

It wasn’t what was asked for, but it was what was asked for, as well, in another sense. Nice.

But I still wasn’t finished mucking about. On a roll now, of course I found myself having to write the whole thing as a regular expression. In this, finding boundaries between digits but only if they were changed proved to be rather formidable task. After playing around with all manner of zero-width lookahead and lookbehind constructions, I settled on an alternating set of options for each value, to match one or more times. It’s a little wordy for my tastes but it’s complete and gets the job done. Matching on this results in a list of the broken apart single-digit sequences of varying lengths, which we can then parse to determine the digit and the quantity. Putting the processing for this into a map function yields an array of alternating quantity and digit values that can be joined up to be printed.

And yes, I did make an expression to construct the regex pattern, but the expression was longer than the pattern, and considerably more complex. Sometimes the code that writes code is longer than the code itself, and is pretty much certain to be harder to read. So nothing gained there. It remains hard-coded for you in its repetitive glory.

===============================================================
Dec 19, 2020 at 3:17:07 PM
~/Code/PWC/91_1_number-speak.pl
---------------------------------------------------------------
input:               12227786622222222222222222222222222222
numerically:         1132271826292
now using a regex:   1132271826292
now as she is spoke: "One one, three twos, two sevens, one eight, two sixes and twenty-nine twos."

use warnings;
use strict;
use feature ":5.26";

## ## ## ## ## MAIN:


my  $num = shift @ARGV // '12227786622222222222222222222222222222';

## mention our input
say "input:               ",$num;

## split and count...
say "numerically          ", speak_number( $num );

## ...using regex...
say "now using a regex:         ",
    join '', map { length($_), substr($_,0,1) } $num =~ m/1+|2+|3+|4+|5+|6+|7+|8+|9+|0+/g;

## ...and spoken
say "now as she is spoke: ", speak_english( $num );


## ## ## ## ## SUBS:

sub speak_number {
    my ($current, @digits)  = split //, shift;
    my $count = 1;
    my $output = '';

    for (@digits) {
        ($count++, next) if ($_ == $current);
        $output .= $count . $current;
        ($current, $count) = ($_, 1);
    }

    return $output . $count . $current;

}

sub speak_english {
    use Lingua::EN::Inflexion;
    my ($current, @digits)  = split //, shift;
    my $count = 1;
    my @output;
    my $mult = 0;
    my %cardinal = (    1 => 'ones',
                        2 => 'twos',
                        3 => 'threes',
                        4 => 'fours',
                        5 => 'fives',
                        6 => 'sixes',
                        7 => 'sevens',
                        8 => 'eights',
                        9 => 'nines',
                        0 => 'zeros'  );

    for (@digits) {
        ($count++, next) if ($_ == $current);
        my $exp = inflect("<#nfw300:$count> <N:$cardinal{$current}>");
        push @output, $exp;
        ($current, $count) = ($_, 1);
        $mult = 1;
    }

    my $str = (join ', ', @output) . ($mult? " and " : "");
    return q(") . "\u$str" . inflect("<#nw300:$count> <N:$cardinal{$current}>") . q(.");

}

raku solution

For Raku, I thought the regular expression was the most idiomatic way to go about things — working a list of values until the answer is formed. As usual, it has a nice look to it. We do need to make a slip lest the quantity and digit values will become their own little tuple arrays and we need all the elements to be container-neutral to get them to join correctly. And yes, “container neutral” is a term I just made up. Keeping multiple levels of reference straight in a complex data structure is for me one of the most different aspects of the language from Perl 5, and requires quite a bit of care to make sure things are at the same level. Just remember dd is a good friend to have around, to tell you what the new friends you just met are really made of.

unit sub MAIN (Int $num = 2244444431111111) ;

say $num;

my $regex = /1+|2+|3+|4+|5+|6+|7+|8+|9+|0+/;

($num ~~ m:g/$regex/)
    .map({|($_.chars, substr($_,0,1))})     ## need slip to slip in
    .join
    .say;

---

episode two:
“Just a Hop, Skip and a Jump”

---

TASK #2

Jump Game

Submitted by: Mohammad S Anwar

You are given an array of positive numbers @N, where value at each index determines how far you are allowed to jump further.

Write a script to decide if you can jump to the last index. Print 1 if you are able to reach the last index otherwise 0.

Example 1:

Input: @N = (1, 2, 1, 2)
Output: 1

as we jump one place from index 0 and then twoe places from index 1 to reach the last index.

Example 2:

Input: @N = (2,1,1,0,2)
Output: 0

it is impossible to reach the last index. as we jump two places from index 0 to reach index 2, followed by one place jump from index 2 to reach the index 3. once you reached the index 3, you can't go any further because you can only jump 0 position further.

Method

It’s a silly little game, really, and to play it we should consider some questions, to make sure we’re playing by the rules. First, do we need to land exactly on the last element, or can we overshoot? The language states we should be jumping to the last index, not past the last index. So if we overshoot, we’ve fallen off the edge of the world. Autovivification may keep us alive, but without values to fuel us there is no way back from that undefined void. Alone in a fog of uncertainty we fail. It kind of sounds like a terrible fate, to be honest.

With that being the case, then there are two ways to lose the game: to either land on a zero and be unable to continue forward, or to overshoot the mark and be unable to get back.

I also need to point out that 0 is not a positive number, but it is used here in an example. Taking the example as canon, I think we will simply rephrase the valid input to be “an array of non-negative numbers” which will allow us to include the number 0.

As far as playing the game goes, we need only keep track of a single changing value: that of the current index that defines our location. Every jump takes all of our energy; at every stop we refuel with the value of the array element at that location. If the value waiting for us is 0, or worse yet, undefined, then we are stuck depleted and cannot reach our destination. We fail, we lose, and there’s nothing to be done. If our landing spot works out to be the last element of the array, then we are lucky and we have won.

This is a rather merciless, fatalistic game I’m afraid. Once we start, we have no choice but to continue until we either win or lose. Our destiny is preordained and in this world we walk the path that is given us, to a place of success or failure. It’s kind of heady stuff.

PERL 5 SOLUTION

Practically the script is very simple . We enter into a loop where we assign a variable to be the value of the next jump forward. Assignment operations are evaluated by their assigned value; if this value is 0 or undefined, the condition fails and the fallback returns 0. Once a jump amount has been assigned, this is then added to the current index. If that value is the last index, we win, else we loop again. Eventually we will always exit the loop.

One thing I did notice though is that the restriction to positive numbers is basically unnecessary. I rather like the idea of allowing negative values to move backwards. In fact the game plays quite well, needing only small modification, and becomes a little more interesting for it. We’ve already added 0, why not add the rest?

So I implemented this as jump_around().

In this case the failure modes would be the same, with the addition of a third: if we ever visited an element twice it would indicate we have entered a loop — as the path forward is fixed we know this will repeat eventually, never reaching the end.

The undefined limbo off the edges of the world is still the same etherial void it ever was, but it’s now possible to fall off either end of the array. As negative indices mean something rather different to arrays than to us, we need to have our plucky pilot fail should the index go below 0.

It ends up being a little more complicated in the possible pathways available, but still will always resolve sooner or later to the fate encoded in the numbers.

use warnings;
use strict;
use feature ":5.26";


## ## ## ## ## SUBS:

sub jump_forward {
## minimal version as described.
## Array -> 1|0
## returns 1 on success, 0 on failure
    my $idx = 0;
    while ( my $jump = $_[$idx] ) {
        $idx += $jump;
        return 1 if $idx == @_ - 1;
    }
    return 0;
}

sub jump_around {
## a more robust game allowing negative values.
## fails on
##   exceeding array bounds,
##   landing on 0 (cannot jump further)
##   landing on position twice (signifying a closed loop)
## wins
##   by landing on last element
## returns on determination
    my @array = @_;
    my $idx = 0;
    my $last = scalar @array - 1;
    my %visited;
    while (1) {
        my $next = $idx + $array[$idx];
        return 1 if $next == $last;              ## win
        return 0 if $next == $idx;               ## stuck
        return 0 if $next < 0 or $next > $last;  ## out of bounds
        return 0 if exists $visited{$next};      ## looping
        $idx = $next;
        $visited{$idx} = 1;
    }
}

use Test::More;

is jump_forward(1, 2, 1, 2), 1, 'forward ex 1: success!';
is jump_forward(2,1,1,0,2),  0, 'forward ex 2: stuck on 0';
is jump_forward(2,1,1,1,0),  1, 'forward: ok, last ele 0';

is jump_around(1, 2, 1, 2),  1, 'around ex 1: success!';
is jump_around(2,1,1,0,2),   0, 'around ex 2: stuck on 0';
is jump_around(2,1,1,1,0),   1, 'around: ok, last ele 0';
is jump_around(2,3,1,-2,5),  1, 'around: ok: back and forth and home';
is jump_around(2,3,1,-12,5), 0, 'around: fail: back too far';
is jump_around(2,13,1,-2,5), 0, 'around: fail: forward too far';

done_testing();

Raku Solution

Another pathological case occurred to me doing the Raku version: what if the array given only has one element? Well you’d win of course, because you start on the last element. Should this even be allowed? I don’t know. I doubt it. But we’re taking command-line input for this version so we’ll implement it, and give some default data should anyone try and give it no data at all. We should probably also validate the input to be integers as well, but enough is enough. It’s pretty and clean.

unit sub MAIN (*@array) ;

@array.elems == 0 and @array = 1,2,15,2;
@array.elems == 1 and do { say 1; exit };

my $idx = 0;
while my $jump = @array[$idx] {
    $idx += $jump;
    $idx == @array.end and do { say 1; exit };
}
say 0;