Perl Weekly Challenge 119: Swap Nibbles and Sequence without 1-on-1

These are some answers to the Week 119 of the Perl Weekly Challenge organized by Mohammad S. Anwar.

Spoiler Alert: This weekly challenge deadline is due in a couple of days, on Independence Day (July 4, 2021). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.

Task 1: Swap Nibbles

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.

Example:

Input: $N = 101
Output: 86

Binary representation of decimal 101 is 1100101 or as 2 nibbles (0110)(0101).
The swapped nibbles would be (0101)(0110) same as decimal 86.

Input: $N = 18
Output: 33

Binary representation of decimal 18 is 10010 or as 2 nibbles (0001)(0010).
The swapped nibbles would be (0010)(0001) same as decimal 33.

Swap Nibbles in Raku

Raku has a built-in base method to convert a number to a string representation in a given base, and a parse-base method to perform the reverse operation. I thought it might be clever to use base 4 rather than base 2 to get directly two nibbles, but it turns out that it doesn’t make things any simpler than using a binary representation (as done in the Perl representation below). Note that we use the fmt("%04s") method invocation to pad the base-4 string representation with leading 0’s making the swap of the two nibbles very easy with a regex.

use v6;

for 254, 101, 18 -> $n {
    my $b4 = $n.base(4).fmt("%04s");
    # say $n.base(2).fmt("%08s");
    $b4 ~~ s/(\d**2)(\d**2)/$1$0/;
    # say $b4.parse-base(4).base(2).fmt("%08s");
    say "$n -> ", $b4.parse-base(4);
}

With the built-in test cases, this script displays the following output:

$ raku ./swap-nibbles.raku
254 -> 239
101 -> 86
18 -> 33

Swap Nibbles in Perl

In Perl, we use the built-in sprintf function to convert a number to a binary string representation. And since there is no built-in function to perform the reverse operation, we roll out our own bin2dec subroutine. Otherwise, the Perl implementation is essentially similar to the Raku implementation.

#!/usr/bin/perl
use strict;
use warnings;
use feature qw/say/;

sub bin2dec {
    my $bin = shift;
    my $sum = 0;
    for my $i (split //, $bin) {
        $sum = $sum * 2 + $i;
    }
    return $sum;
}

for my $test (254, 101, 18) {
    my $b2 = sprintf "%08b", $test;
    $b2 =~ s/(\d{4})(\d{4})/$2$1/;
    say bin2dec $b2;;
}

This program displays the following output:

$ perl  swap-nibbles.pl
239
86
33

Task 2: Sequence without 1-on-1

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

Sequence without 1-on-1 in Raku

In Raku, we just build an infinite lazy list representing this sequence. Since it’s a lazy list, Raku will generate only the sequence numbers needed by the program. We convert a list of consecutive integers into base-4 representations and filter out numbers containing 0’s or consecutive 1’s. Note that when we need the nth term of the series, we have to use index n - 1.

use v6;

my $seq-no_1 = grep { not /11 | 0 / }, map { $_.base(4) },
    1..Inf;
say $seq-no_1[$_ - 1] for 5, 10, 60;

This program displays the following output:

raku ./seq_123.raku
13
32
2223

Sequence without 1-on-1 in Perl

If we wanted to use the same principle in Perl, since we don’t have lazy lists, we would have to select a large enough maximum value. For example:

use strict;
use warnings;
use feature "say";

my @seq = grep { not /11/ } grep /^[1-3]+$/, 1..5000;
say $seq[$_ + 1] for (5, 10, 60);

This would display the following correct output:

$ perl seq_123.pl
22
121
2232

But this approach is not very satisfactory because we don’t know how to select a large enough value. If the selected value is too small, the program will fail, and it it is very large we might be doing a lot of useless computation.

The alternative is to build the successive terms of the sequence. We use the incr subroutine to implement the unusual counting rules. And call it as many times as needed to get the proper result:

use strict;
use warnings;
use feature "say";

sub incr {
    my @num = @{$_[0]};
    my $i = $#num;
    while ($i >= 0) {
        if ($num[$i] < 3) {
            $num[$i] ++;
            return \@num;
        } else {
            $num[$i] = 1;
            $i --;
        }
    }
    return [ 1, @num ];
}

for my $i (5, 10, 60) {
    my $res =  [0];
    for (1..$i) {
        $res = incr $res;
        $res = incr $res while (join "", @$res) =~ /11/;
    }
    say @$res;
}

This yields the same output as before:

$ perl seq_123_2.pl
13
32
2223

Wrapping up

The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on July 11, 2021. And, please, also spread the word about the Perl Weekly Challenge if you can.

Leave a comment

About laurent_r

user-pic I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.