Sharing a Bite — But Not Face-to-Face

Wherein we quietly eat alone… again…

THE WEEKLY CHALLENGE – PERL & RAKU #119

---

episode one:
“A Nibble Here, a Nibble There and It’s Gone”

---

Task 1

Swap Nibbles

Submitted by: Mohammad S Anwar

You are given a positive integer $N.

Write a script to swap the two nibbles of the binary representation of the given number and print the decimal number of the new binary representation.

A nibble is a four-bit aggregation, or half an octet.

To keep the task simple, we only allow integer less than or equal to 255.

Method

This task involves two parts: switching back and forth between decimal and binary representations of a number, and manipulating the bits of the binary version before we… renumerate? A sort of remuneration but all mixed up? It’s an oddly fitting play on words.

Performing this little switcheroo would be possible using logical operators and bit shifting, surely. Part of my brain thinks this would be fun, and currently working out the details as I write. But it would also be unnecessarily confusing and complex, as we can simply view the number as a binary string and manipulate that instead. It nice to have a language where numbers and strings coexist nicely — rainbows and unicorns and hey, it’s all text, baby. We can all hang out together.

So how do we do this magic? It kind of depends on how we write it…

PERL 5 SOLUTION

In Perl, we can move over to binary using a sprintf format. Because we’ve been locked into a number less than 256 and greater than 0, we’ll write out 8 bits: "%8b". From there we have an 8-character string, and with some clever use of substr we can swap the front nibble and the back in-place.

We’re using substr in pretty much every one of its forms in this object-lesson. At the left side, it’s an lvalue, meaning we can assign to the characters it selects. Then, working rightward, we have the 4-argument form, listing the string to be acted on, the initial offset from the left, the number of characters to select, and the string with which to replace those characters.The selected characters, the last four, will be removed and assigned to the lvalue, which is selecting the first four characters. Over on the right side, before this assignment takes place, the final substr selects the first four characters (before they are changed) and returns them to in turn replace the last characters in the middle, 4-argument substr.

You may need to reread that. I’ll wait.

… gets more tea …

Cool, huh? It’s directly analogous to

($x, $y) = ($y, $x);

which you can also do in Perl.

my $num = shift @ARGV // 3;

0 < $num < 256 or die "number must be in range 1 to 255 inclusive";

my $bin = sprintf "%08b", $num;
substr( $bin, 0, 4 ) = substr( $bin, 4, 4, substr( $bin, 0, 4));
say oct "0b$bin";

To convert back we use oct, which is a rather poorly named operation for the task, but given the 0b prefix it will identify the number as binary, not octal, and do the right thing. It’s a minor quirk in the big scheme of things.

raku solution

In Raku we’re going to do things a little differently. We’re going to do it all in one chain of functions.

Hang on, this is going to be fun.

As we did in Perl, we’re going to stringify the number into eight 1s and 0s, only this time we’ll be using fmt instead of sprintf. The names have changed, but the format remains. Once that is done we’re going to parse that string and chop it into parts 4 characters long. Two of these, of course, in a list.

Which we will then reverse.

And join back together.

…And finally tell Raku to look at as a base-2 number and tell us what it sees, and report that.

I love writing Raku sometimes.

unit sub MAIN ( Int $num where 256 > $num > 0 = 3) ;

$num.fmt("%08b") 
    .comb(4)
    .reverse
    .join
    .parse-base(2)
    .say;

---

episode two:
“Chaperones Required”

---

task 2

Sequence without 1-on-1

Submitted by: Cheok-Yin Fung

Write a script to generate sequence starting at 1. Consider the increasing sequence of integers which contain only 1’s, 2’s and 3’s, and do not have any doublets of 1’s like below. Please accept a positive integer $N and print the $Nth term in the generated sequence.

1, 2, 3, 12, 13, 21, 22, 23, 31, 32, 33, 121, 122, 123, 131, …

Example

Input: $N = 5
Output: 13

Input: $N = 10
Output: 32

Input: $N = 60
Output: 2223

Method

When I first went at this problem, I focused on creating the sequence, figuring from there I could study the 1s and see where they fell. It was a good plan; a solid plan of pure research.

The sequence is composed of numbers containing only the three digits, 1, 2, and 3, so I figured, after the binary task above, why not ternary? It too has three digits: 0, 1, and 2. What if we added 1? We should end up with 1, 2, and 3.

As for the logic, why yes, yes we would. We’re not really doing addition in base-3, and if we change the glyphs in the representations, by adding 1 to each of them, we do indeed get a sequence containing only the digits 1, 2, and 3. It’s ascending, even. The only problem is it doesn’t match what we need. To demonstrate:

The ternary numbers from 1 to 10:

1, 2, 10, 11, 12, 20, 21, 22, 100, 101

Now once we add 1 to each digit:

2, 3, 21, 22, 23, 31, 32, 33, 211, 212

But to match the given sequence it needs to be:

2, 3, 12, 13, 21, 22, 23, 31, 32, 33

Ahh, I see. We have no leading 0s in our sequence to augment into 1s. It seems every time we need a new digit position we need to start the entire sequence over with the appropriate number of leading zeros. The base we need would be 1, 2, 01, 02, 10, 11… This is troublesome.

Ok, new plan. What if we were to use base-4? That would already have all the numbers we need in it, with a few extra. We could filter them out.

Further, this nicely avoids having to survey and assess a mathematical pattern underlying the pairs of 1s: when we filter the sequence, we can filter out those as well.

And we can do both jobs using the same regular expression. I like it.

PERL 5 SOLUTION

In Perl it’s not super easy to convert back and forth into random bases. Hex, octal, binary — we can use a sprintf format. Outside of that we need to do it ourselves. We’ll employ some Euclidean division to divide the input down to do the conversion.

That’s really not a big deal after all. Then for our filter we skip over values that either have a 0 in them or the 11 forbidden formation. If a number survives the gauntlet it is added to a sequence.

As we don’t know when we start how many values will be excluded, we loop the steps until we have enough values to produce the n-th member of the sequence on demand.

my $ele = shift // 60;

say make_sequence( $ele )->[$ele-1];

## faster, base-4
sub make_sequence ($quan, $i = 0) {   
    my @seq;
    while (@seq < $quan) {
        my ($num, $rem) = (++$i, '');
        my $val = '';
        while ( $num > 0  ) {
            ($num, $rem) = (int( $num/4 ), $num % 4);   
            $val = $rem . $val;
        }
        next if $val =~ /0|11/;
        push @seq, $val;
    }
    return \@seq;
}

As an afterthought it occurred to me that the whole numbers, intact, is another sequence that contains our selected values, and that too could just be filtered to get the values we want, in the same way. The filter now picks out, instead of a wayward 0, any value that is not 1, 2 or 3, in addition to the 11s. This has many more numbers wasted — created and tossed aside — but has the virtue of minimal computation as we don’t need to do any division to get to the starting position.

## simpler, but more chaff, less wheat
sub make_sequence10 ( $quan, $i = 0 ) {
    my @seq;
    while ( ++$i ) {
        next if $i =~ /[^123]|11/;
        push @seq, $i;
        last if @seq == $quan;
    }
    return \@seq;
}

As the comments already give away, this is only about half as fast. Constructing only the base-4 numbers to start wins out by a wide margin.

Raku Solution

In Raku we can be lazy and sublime: we can create an infinite sequence of possibilities and access that only as we need it.

We start with an infinite list of the whole numbers.

This sequence of values, when we ask for them, are first expressed in base 4 using a simple function. Then those elements are filtered using grep, using the souped-up Raku regex engine, to only those that do not contain either a 0 or the 11 formation.

Now we can take this theoretical ordered list of values-we-might-want as a first-class citizen and access it positionally, which sets in motion the reifying of the $ele minus-one-th element to print. We can do all of this anonymously, without even instantiating a container to hold anything. How cool is that?

unit sub MAIN ( Int $ele where $ele > 0 = 60 ) ;

( (1 … ∞).map(*.base(4))
         .grep({! / 0 | 11 /}) )[$ele-1].say

In a side note, I had previously worked out the various sequences used in the demonstration we saw above: the lists of the ternary numbers and adding 1 to each digit, but hadn’t kept them around. Or I don’t think I did. Instead of looking through my notes I was able to recreate them by altering the completed Raku code in a few minutes:

unit sub MAIN () ;

#     1, 2, 10, 11, 12, 20, 21, 22, 100, 101
my @tre = ( (1 … ∞).map(*.base(3)))[^10];
say @tre.join(', ');

#     2, 3, 21, 22, 23, 31, 32, 33, 211, 212
@tre.map({ $_.comb
             .map(*+1)
             .join})
    .join(', ')
    .say;

I seem to have discovered that once you stop fighting with it, Raku can be really amazing. I’m not exactly sure when that happened, but I welcome the change wholeheartedly. It’s both beautiful and amazing.