The Bear's Den

Enter at your own risk

14 August 2026 Challenge 386

Periodic Bases

Task 1: Reverse Base

Submitted by: Mohammad Sajid Anwar

You are given a string representing a number, and an integer specifying the base of that representation.

Write a function to convert this string to an integer. (For bases greater than 10, use characters A-Z, a-z, + and / in that order.)

Example 1

Input: $num = "101010", $base = 2
Output: 42

Example 2

Input: $num = "EEADEE", $base = 16
Output: 15642094

Example 3

Input: $num = "755", $base = 8
Output: 493

Example 4

Input: $num = "1BRJB", $base = 36
Output: 2228519

Example 5

Input: $num = "7MyqL", $base = 64
Output: 123456789

Solution

This task asks for the inverse of week 384’s task 1.

It can be solved by applying the inverse operations from the previous task in reversed order:

Perl

Reusing the digits from week 384 in a hash for the reverse-lookup and using Math::Prime::Util’s fromdigits to convert to an integer.

use strict;
use warnings;
use List::MoreUtils 'part';
use Math::Prime::Util 'fromdigits';
use experimental 'signatures';

{
    my @digits;
    my %digits;

    BEGIN {
        @digits = map @$_, part {/[[:punct:]]/}
            grep /[[:alnum:][:punct:]]/, map chr, 0 .. 127;
        @digits{@digits} = (0 .. $#digits);
    }

    sub from_base ($num, $base) {
        die "base too large" if $base > @digits;

        fromdigits([@digits{split //, $num}], $base)
    }
}

The last expression represents the described inverse of the corresponding expression from week 384:

    join '', $digits->@[todigits $num, $base];

See the full solution to task 1.

J

The solution from week 384 already provides the inverse function.

This is my solution from week 384:

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

Applied to Example 5 from the current week:

   64 to_base inv '7MyqL'
123456789

I’m not going to resubmit this solution.

Task 2: Rational Numbers

Submitted by: Mohammad Sajid Anwar

You are given two strings representing non-negative rational numbers.

Write a script to return true if the two given rational numbers are same otherwise false.

Example 1

Input: $rat1 = "0.(12)"
       $rat2 = "0.(121)"
Output: false

Expansion of "0.(12)"  = 0.12 12 12 12
Expansion of "0.(121)" = 0.121 121 121

Example 2

Input: $rat1 = "0.1(23)"
       $rat2 = "0.12(32)"
Output: false

Example 3

Input: $rat1 = "0.1(234)"
       $rat2 = "0.12(342)"
Output: true

Expansion of "0.1(234)"  = 0.1 234 234 234
Expansion of "0.12(342)" = 0.12 342 342 342

Example 4

Input: $rat1 = "12.99(99)"
       $rat2 = "13."
Output: true

Example 5

Input: $rat1 = "0.(123)"
       $rat2 = "0.1(231)"
Output: true

Solution

My interpretation of this task: Check if both given rational numbers are strictly equal, not just approximately. The conversion to numbers in (fixed sized) floating point format and comparing these with a small tolerance would not produce the desired results.

Consider 0.(1234567890) and 0.123456789012345678901234567890123456789. These numbers are obviously different, though even in quadruple-precision floating-point format their representations are identical as this format can hold a maximum of 36 decimal places.

Therefore acting on arbitrary precision rational numbers.

A rational number may be represented in decimal notation with a periodic broken part or as a common fraction. Neither representation is unique but comparing fractions for equality is very simple. Using a genuine rational data type reduces it to the “(numerically) equal” operation.

Converting the given rational numbers from decimal notations to common fractions and comparing these.

Consider a rational number \(x\) in decimal notation:

\[x = I_1 \ldots I_m \, . \, F_1 \ldots F_n (P_1 \ldots P_q)\]

where \(I_j\) represent the integer part, \(F_k\) represent a fixed broken part and \((P_l)\) represent a periodic broken part.

Defining some integers from their decimal representation:

\[\begin{align*} i &= I_1 \ldots I_m\\ f &= F_1 \ldots F_n\\ p &= P_1 \ldots P_q \end{align*}\]

In case of a missing periodic part we may set

\[\begin{align*} p &= 0\\ q &= 1 \end{align*}\]

Now consider the rational number \(r\) with the periodic decimal representation:

\[r = 0.(P_1 \ldots P_q)\]

From its periodicity we find:

\[\begin{align*} r\, 10^q &= P_1 \ldots P_q \, . \, (P_1 \ldots P_q)\\ &= p + r\\ r\, (10^q - 1) &= p\\ r &= \frac{p}{10^q - 1} \end{align*}\]

Thus \(x\) can be written as a common fraction:

\[\begin{align*} x &= i + \frac{f + r}{10^n}\\ &= \frac{i\,10^n + f + r}{10^n}\\ &= \frac{i\,10^n + f + \frac{p}{10^q - 1}}{10^n}\\ &= \frac{(i\,10^n + f)\, (10^q - 1) + p}{10^n\, (10^q - 1)}\\ \end{align*}\]

Consider $rat2 from example 3:

\(\begin{align*} x &= 0.12(342)\\ i &= 0\\ f &= 12\\ n &= 2\\ p &= 342\\ q &= 3\\ x &= \frac{(0 + 12)(10^3 - 1) + 342}{10^2 (10^3 - 1)}\\ &= \frac{12330}{99900}\\ &= \frac{137}{1110}\\ &\approx 0.123423423 \end{align*}\)

Perl

The core of this implementation is the conversion routine from periodic decimal to fraction.

Using a regular expression to extract the parts, convert strings to BigRat, calculate the required integer values and apply the above formula.

use v5.24;
use warnings;
use bigrat;
my $verbose;

sub to_frac :prototype(_) {
    my ($i, $f, $p) = shift =~ /^(\d*)\.(\d*)(?:\((\d+)\))?$/;
    die "no valid number" unless defined $i;
    my ($en, $eq) = map 10**length, $f, ($p //= 0);
    my $eqd = $eq - 1;
    ($i, $f, $p) = map 0 + ($_ || 0), $i, $f, $p;

    (($i * $en + $f) * $eqd + $p) / ($en * $eqd);
}

sub equal_rationals {
    my ($x, $y) = map to_frac, @_;
    say "$x $y" if $verbose;

    $x == $y;
}

See the full solution to task 2.

J

A very similar implementation.

Here the operations are applied in a slightly different order. While this produces the correct value \(p = 0\) for a missing periodic part, the resulting length \(q = 0\) is not usable. As the factor \(10^q - 1\) cancels out for \(p = 0\), any non-zero value may be chosen. For simplicity setting it to one.

Arbitrary precision rational numbers are a built-in type in J. The quotient of extended precision integers produces a rational number (unless it is integer).

Note that J sentences are evaluated right to left, which gives the formula a funny look.

require 'regex'
to_frac =: verb define
  NB. a temporary verb to pick the parts from y,
  NB. convert the strings to extended integers and
  NB. calculate the decimal powers of their lengths
  rh =. rxcomp '^(\d*)\.(\d*)(?:\((\d+)\))?$'
  parse =. (0&".@(,&'x') , 10x ^ #) S:0 @((rh;1 2 3)&(rxmatch rxfrom ]))

  NB. parse y and assign values
  'i em f en p eq' =. , parse y

  NB. provide a default for an empty periodic part and
  NB. decrement eq
  eqd =. p <:@(2:^:(-.@*@[)) eq

  NB. insert the values into the formula
  (p + eqd * f + en * i) % (eqd * en)
)

Example 1:

   to_frac '0.(12)'
4r33
   to_frac '0.(121)'
121r999

These are obviously not equal.

See the full solution.