RogerBW's Blog

I’ve been doing the Perl Weekly Challenges. The latest involved fake binary manipulation and an unusual number sequence. (Note that this is open until 4 July 2021.)

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.

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

Well now. In my day we called them nybbles, for consistency with bytes. But anyway…

The "binary representation" is the trap here; I mean, I could convert to a string of 1s and 0s, then string-manipulate into the right answer and convert back, but that's not what's needed. In fact this can be regarded as purely mathematical: the high nybble is $N divided by 16 (integer part), the low is $N mod 16, and 16×low + high will be the answer.

So in Perl that's:

  return 16*($n % 16)+int($n/16);

Raku gets us an integer-division operator:

  return 16*($n mod 16)+($n div 16);

Python and Ruby offer a combined divide-modulus function:

  t=divmod(n,16)
  return 16*t[1]+t[0]

but Rust doesn't. (Well, not in the language core; there's an external crate, but going to an external module for something that can be done quite readily without one doesn't seem worth the extra fuss.)

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 1s, 2s and 3s, and do not have any doublets of 1s 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, …

Well, there's a sequence that isn't in the OEIS! I thought about various means of generating this directly, and noted that there is a sequence that gives the index of the first number of length n: OEIS #A293005. But I can't treat it as base-3 or base-4 because we have three symbols and each of them is significant at the start of a number… in fact it's a little like the Excel column numbering system, which I did for PWC #60… except for that exclusion of double-1s. So I'd need another function that worked out an offset from how many of those there have been…

In the end it seemed simpler just to increment an integer, filter with regular expressions, and skip numbers that weren't allowed. It might be quicker to generate the sequence by more conventional means to build a list of values already matching /^[123+]$/, and then filter only those few to make sure they don't match /11/, but I didn't check this.

In Raku:

sub sw($c is copy) {
  my $n=0;
  while ($c) {
    $n++;
    if ($n ~~ /<[04..9]>/ || $n ~~ /11/) {
      next;
    }
    $c--;
  }
  return $n;
}

and the others work similarly, though in Python, Ruby and Rust I can explicitly compile the regexp just once. But even the Rust version is basically recognisable as kin to that Raku.

fn sw (cc: u32) -> u32 {
    let mut c=cc;
    let mut n=0;
    let p=Regex::new(r"([04-9]|11)").unwrap();
    while c>0 {
        n+=1;
        if p.is_match(&n.to_string()) {
            continue;
        }
        c-=1;
    }
    return n;
}

Full code on github.