# Perl Weekly Challenge 119.

``````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.

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.
``````

This seems apt for a oneliner: Convert to binary left-padding with 0s, substitute nibbles by each other and convert to decimal.

``````perl -E 'map {\$s=\$o=sprintf("%08b", \$_); \$s=~s/^(.{4})(.{4})\$/\$2\$1/;\
say sprintf("Input: %s (%s), Output: %s(%s)", \$_,\$o, oct("0b\$s"), \$s)} @ARGV;' 101 18
``````

Results:

``````Input: 101 (01100101), Output: 86(01010110)
Input: 18 (00010010), Output: 33(00100001)
``````

The full version:

``````# Perl weekly challenge 119
#

use strict;
use warnings;
use v5.32;

map {
die "Keep to range 0-255" unless 0<=\$_<=255;
my \$s=my \$o=sprintf("%08b", \$_);
\$s=~s/^(.{4})(.{4})\$/\$2\$1/;
say sprintf("Input: %s (%s), Output: %s(%s)", \$_,\$o, oct("0b\$s"), \$s)
} @ARGV;
``````

Examples:

``````./ch-1.pl 101 18
``````

Results:

``````Input: 101 (01100101), Output: 86(01010110)
Input: 18 (00010010), Output: 33(00100001)
``````

Other examples:

``````./ch-1.pl `seq 10`
``````

Results:

``````Input: 1 (00000001), Output: 16(00010000)
Input: 2 (00000010), Output: 32(00100000)
Input: 3 (00000011), Output: 48(00110000)
Input: 4 (00000100), Output: 64(01000000)
Input: 5 (00000101), Output: 80(01010000)
Input: 6 (00000110), Output: 96(01100000)
Input: 7 (00000111), Output: 112(01110000)
Input: 8 (00001000), Output: 128(10000000)
Input: 9 (00001001), Output: 144(10010000)
Input: 10 (00001010), Output: 160(10100000)
``````

# 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
``````

The easiest solution is to start producing numbers, discarding those with consecutive ones, until I reach the `\$N`-th. I can just increment a counter repeatedly and convert it to base four, throwing away any number with 0’s or with repeated 1’s. (I first thought I could use base 3 and map 012 to 123, but I was wrong, as leading 1’s would correspond to leading 0’s in base 3).

``````# Perl weekly challenge 119
# Task 2: sequence without 1-on-1
#

use strict;
use warnings;
use v5.12;
use integer;

map {say "Input: \$_, Output: ", get(\$_)} @ARGV;
sub get {
my \$want=shift;
my \$n=1; #counter
my \$r;
while(\$want-- > 0){
while(!defined (\$r=convert(\$n++))){};
}
return \$r;
}

sub convert {
my \$n=shift;
my \$r="";
return 0 if \$n==0;
while(\$n>0){
\$r=\$n%4 . \$r;
\$n/=4;
}
return (\$r=~m/11/ || \$r=~/0/)?undef:\$r;
}
``````

Example:

``````./ch-2.pl 5 10 60
``````

Results:

``````Input: 5, Output: 13
Input: 10, Output: 32
Input: 60, Output: 2223
``````

Other examples:

``````time (./ch-2.pl 1000) 2>&1
time (./ch-2.pl 100000) 2>&1
``````

Results:

``````Input: 1000, Output: 1332223

real	0m0.058s
user	0m0.054s
sys	0m0.004s
Input: 100000, Output: 33132122212

real	0m7.365s
user	0m7.355s
sys	0m0.008s
``````

The time grows linearly. A slightly better approach is to count directly using the symbols `123` adding with carry recursively and jumping over sequences with `11`.

``````# Perl weekly challenge 119
# Task 2: sequence without 1-on-1
#

use strict;
use warnings;
use v5.12;
use integer;

map {say "Input: \$_, Output: ", get(\$_)} @ARGV;
sub get {
my \$want=shift;
my \$r="1";
\$r=increment(\$r) while(\$r=~/11/ || --\$want > 0);
\$r;
}
sub increment {
my \$r=shift;
while(1){
\$r=~/(.*)(.)\$/;
my \$high=\$1||0;
my \$low=\$2+1;
return \$low>3?increment(\$high)."1":\$high?\$high.\$low:\$low;
}
}
``````

Example:

``````./ch-2a.pl 5 10 60
``````

Results:

``````Input: 5, Output: 13
Input: 10, Output: 32
Input: 60, Output: 2223
``````

Other examples:

``````time (./ch-2a.pl 1000) 2>&1
time (./ch-2a.pl 100000) 2>&1
time (./ch-2a.pl 1000000) 2>&1
``````

Results:

``````Input: 1000, Output: 1332223

real	0m0.007s
user	0m0.007s
sys	0m0.000s
Input: 100000, Output: 33132122212

real	0m0.377s
user	0m0.372s
sys	0m0.004s
Input: 1000000, Output: 13122223122312

real	0m4.687s
user	0m4.687s
sys	0m0.000s
``````

So this approach is about ten times faster, but it still is linear in the size of the sequence number. I’m sure there is an alternative with constant time or at most logarithmic.

Written on June 28, 2021