Perl Weekly Challenge 119.
My solutions (task 1, task 2 and task 2 to the The Weekly Challenge - 119.
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.
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
# Task 1: Swap Nibbles
#
# See https://wlmb.github.io/2021/06/28/PWC119/#task-1-swap-nibbles
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
#
# See https://wlmb.github.io/2021/06/28/PWC119/#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
#
# See https://wlmb.github.io/2021/06/28/PWC119/#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.