ETOOBUSY 🚀 minimal blogging for the impatient
PWC193 - Binary String
TL;DR
Here we are with TASK #1 from The Weekly Challenge #193. Enjoy!
The challenge
You are given an integer,
$n > 0
.Write a script to find all possible binary numbers of size
$n
.Example 1
Input: $n = 2 Output: 00, 11, 01, 10
Example 2
Input: $n = 3 Output: 000, 001, 010, 100, 111, 110, 101, 011
The questions
I think that by “all possible binary numbers” we mean “all possible
strings of length $n
that can be build over an alphabet comprising 0
and 1
only”. This is because I’m not sure I would consider 0123
a
decimal number of size 4, to be honest.
Also… I’m not sure how we’re supposed to produce the strings. I guess any order will do.
The solution
Each challenge lives on its own little monad, and has its own rules. But
(you knew there was a but) I can’t help observing that the binary
strings here can happily start with a string of 0
characters, while
no later than the last week they had to definitely start with a 1
, or
bad things would have happened.
So shouldn’t this go in the questions sections somehow? Well, no. The
challenge is subtly worded as to find all possible binary numbers of
size $n
, which means that we don’t get to do any conversion if we
don’t want to.
OK, as usual let’s start with Raku:
#!/usr/bin/env raku
use v6;
sub MAIN (Int:D $n where * > 0 = 2) { .put for binary-strings($n) }
sub binary-strings (Int:D $n where * > 0) {
my $prefix = '0' x ($n - 1);
my $i = 0;
return gather loop {
my $raw = ($i++).base(2).Str;
my $len = $raw.chars;
last if $len > $n;
take ('0' x ($n - $len)) ~ $raw;
};
}
We’re just counting from 0 upwards, stopping when the binary
representation gets too long. To cope with the length requirement, we
just pre-pend each produced string with a suitable number of 0
characters.
I know, this solution is neither efficient nor scalable. Raku has
built-in big integers, but we’re computing/accumulating all strings
up-front and we’re also using gather
/take
, which is not the best
efficiency-wise. I like it too much though.
For the Perl alternative we move on to good old iterators - they
play nicer for bigger values of the input $n
, as we start seeing stuff
immediately and we keep memory consumption to a minimum.
#!/usr/bin/env perl
use v5.24;
use warnings;
use experimental 'signatures';
no warnings 'experimental::signatures';
use Math::BigInt;
my $it = binary_strings_iterator(shift // 2);
while (defined(my $binary_string = $it->())) {
say $binary_string;
}
sub binary_strings_iterator ($n) {
my $i = Math::BigInt->bzero;
return sub {
return unless defined $i;
my $raw = ($i++)->to_bin;
my $len = length $raw;
return $i = undef if $len > $n;
return ('0' x ($n - $len)) . $raw;
};
}
So go ahead, feed it with 1000 as input and stop it when you’ve got enough!
Stay safe!