| 31 July 2026 | Challenge 384 |
Special Bases
Task 1: Base N
Submitted by: Mohammad Sajid Anwar
You are given a number and a base integer.
Write a script to convert the given number in the given base integer.
Example 1
Input: $num = 42, $base = 2
Output: 101010
Example 2
Input: $num = 15642094, $base = 16
Output: EEADEE
Example 3
Input: $num = 493, $base = 8
Output: 755
Example 4
Input: $num = 2228519, $base = 36
Output: 1BRJB
Base 36 uses numbers 0-9 and letters A-Z.
Example 5
Input: $num = 123456789, $base = 64
Output: 7MyqL
Base 64 (using 0-9, A-Z, a-z, and extra symbols like + and /)
Solution
There are tools to convert an integer into the representation in any base in Perl and J. These provide each “digit” as an integer. I’m not going to reinvent the wheel for this part.
Here a representation as a digit string is requested.
To this end a list of possible “digits” is required. I’ll use all printable, non-space ASCII characters. This is the same as all alphanumeric and all punctuation characters. The characters come in this order:
- decimal digits
- upper case chars
- lower case chars
- punctuation chars
with ASCII-order within every group. This is a list of 94 characters, which represents the limit for the base with this approach.
Self-imposing an additional restriction:
Build this list from the ASCII character set solely based on this additional information:
- all decimal digits come before the first upper case char
- all upper case chars come before the first lower case char
This restriction prohibits the usage of any magic numbers or strings except the size of the ASCII table.
Then use this list to convert the integer coded digits into their corresponding character.
Perl
- generate all ASCII chars
- restrict to alphanumeric and punctuation
- partition by punctuation / others (others go into the first partition)
- join partitions
- convert integer to requested base, transform integers to “digits” and join to string
use strict;
use warnings;
use experimental 'signatures';
use Math::Prime::Util 'todigits';
sub to_base ($num, $base) {
state $digits = [map @$_, part {/[[:punct:]]/}
grep /[[:alnum:][:punct:]]/, map chr, 0 .. 127];
die "base too large" if $base > @$digits;
join '', $digits->@[todigits $num, $base];
}
Example from the J implementation (Math::Prime::Util utilizes BigInteger if available):
$ perl/ch-1.pl 297829712461832408362507600815312674763284354676329591119111469358145232840695078920147684005047281057483359086751911430655657888701613227571978877146756684207203402365629737450019724398 94
~}|{`_^]\[@?>=<;:/.-,+*)('&%$#"!zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA9876543210
See the full solution to task 1.
J
Almost identical logic to generate the digits. Boxes need to be sorted.
The verb todigits to convert y into base-x digits can naturally be used as a monad as if x were 2.
This monad has a predefined inverse derived from its primitives.
However, there is no predefined dyadic inverse - which would be nice to have.
Therefore a specially crafted ambivalent inverse can be assigned to todigits.
This results in a verb with four different usages:
- as a dyad: convert integer y into a digit string in base x
- as a monad: convert integer y into a binary digit string
- the inverse as a dyad: convert y as a digit string in base x to integer
- the inverse as a monad: convert y as a binary digit string to integer
require 'regex'
to_base =: _(adverb define)
NB. select first 128 characters from alphabet, i.e ASCII chars,
NB. restrict to alphanumeric and punctuation,
NB. box by punctuation / others,
NB. sort the boxes by their keys and
NB. raze boxes
p =. '[[:punct:]]'
all =. '[[:alnum:][:punct:]]+'
digits =. ;@:(/:~/)@:|:@(p&rxE ;/.. ])@(all&rxfirst)@(128&{.) a.
NB. convert integer y to digits in base x (default: 2)
todigits =. {&digits @ (#. inv)
NB. convert base-x digits (default: 2) in y to integer
fromdigits =. 2&$: : (#. digits&i.)
NB. convert in either direction
(todigits :. fromdigits) f.
)
64 to_base 123456789
7MyqL
All four usages:
16 to_base 255
FF
to_base 255
11111111
16 to_base inv 'FF'
255
to_base inv '11111111'
255
Convert a special integer to a digit string made of all digits in descending order in base 94:
]n =: 94x #. |. i. 94
297829712461832408362507600815312674763284354676329591119111469358145232840695078920147684005047281057483359086751911430655657888701613227571978877146756684207203402365629737450019724398
94 to_base n
~}|{`_^]\[@?>=<;:/.-,+*)('&%$#"!zyxwvutsrqponmlkjihgfedcbaZYXWVUTSRQPONMLKJIHGFEDCBA9876543210
See the full solution.
Task 2: Special Binary Substrings
Submitted by: Mohammad Sajid Anwar
You are given a binary string.
Write a script to return all non-empty substrings (distinct) that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Example 1
Input: $binary = "0101"
Output: ("01", "10")
Example 2
Input: $binary = "000111"
Output: ("000111", "0011", "01")
Example 3
Input: $binary = "000011"
Output: ("0011", "01")
Example 4
Input: $binary = "10011100"
Output: ("10", "0011", "01", "1100")
Example 5
Input: $binary = "00000"
Output: ()
Solution
One possible approach would be a scan over all substrings (with even length) and a check if these are “special binary strings”. I already had implemented this approach using a regular expression, but discarded the solution after making the following considerations (for the sake of convenience on strings with an even length \(l = 2n\)):
- A string with length \(l\) has \(n^2\) substrings with even length.¹
- Checking if a string is a special binary string may require further effort.
- Duplicates have to be removed.
versus
- A string with length \(l\) has \(2 n\) candidates for special binary substrings.²
- Special binary strings are nested, i.e. if there is no such string with a certain length then there is no longer special binary string starting with the same digit.
- Selecting unique substrings produces a list of unique values.
Therefore my implementations use a loop over all possible candidates and stop at the first failing match as a substring.
¹ Consider 123456 with length \(2\cdot3 = 6\). It has \(5 + 3 + 1 = 9 = 3^2\) substrings with even length, which are: 12, 23, 34, 45, 56, 1234, 2345, 3456 and 123456.
² A string with length \(2 \cdot 3 = 6\) has \(3 + 3 = 6 = 2 \cdot 3\) candidates for special binary substrings, which are: 01, 0011, 000111, 10, 1100 and 111000.
Perl
One minor tweak: We must not loop over constants if the loop variable is subject to modification. Using an anonymous array to solve this issue.
use strict;
use warnings;
use experimental 'signatures';
use List::Gather;
sub sbs ($str) {
gather {
for my $b (@{[qw(01 10)]}) {
while () {
last if index($str, $b) < 0;
take $b;
$b = substr($b, 0, 1) . $b . substr($b, -1);
}
}
};
}
See the full solution to task 2.
J
For this task I’ll use a loop in J and an explicit verb. The logic is almost identical to the Perl implementation, but it looks very different.
The conjunction “Fold Multiple” F: is very similar to a gather-while-take loop in Perl.
Z: 1acts as a built-in loop counter_2 Z: 1acts likelast- The returned value from each loop cycle is taken as part of the overall result and is used as the argument in the next cycle.
The verb find is called with inital strings '01' and '10' and must be explicit to make use of Z:.
Two tweaks in this implementation:
- Testing the special binary string candidate and extending it happens in the same cycle. As the initial value is not collected in the result list, it would be missing. Suppressing the string extension in the first loop cycle to solve this issue - producing one extra cycle.
- It is an error if a “Fold” does not provide at least one result. Catching this situation by assigning an “adverse” to the “Fold” that provides an empty list.
sbs =: _(adverb define)
find =. {{
NB. prepend/append the first/last character of y to itself,
NB. unless it is the first loop cycle
next =. ({. , ] , {:)^:(* Z: 1) y
NB. terminate the loop if next is not found as a substring in x
next _2&Z: @ -. @ (+./) @: E. x
NB. provide y for the next cycle
next
}}
NB. search for special binary strings starting with zero or one
NB. in increasing length
NB. produce an empty list in case of an error
;@:((< F: find :: (0$0))&.(a:`>))&('01';'10') f.
)
sbs '10011100'
┌──┬────┬──┬────┐
│01│0011│10│1100│
└──┴────┴──┴────┘
See the full solution.