Perl Weekly Challenge 119: Sequence without 1-on-1

I could not think of a way to directly generate the \(N\)th number of the sequence.

But there is a straight forward way to, given a number in the sequence, generate the next number in the sequence.

Let the sequence be \(a_0, a_1, a_2, \ldots\). Let \(a_n\) be a number in the sequence, such that \(a_n = d_1 d_2 d_3 \ldots d_m c \overbrace{3 \ldots 3}^{k \text{ times}}, c \neq 3 \). That is, \(a_n\) consists of a possibly empty, sequence of digits \(d_i\) then a digit, \(c\), not equal to \(3\), followed by a, possibly empty, sequence of \(k\) \(3\)s. So, \(c\) is the last digit in \(a_n\) which is not a \(3\). If \(a_n\) consists of only \(3\)s, we can always prepend \(a_n\) with a \(0\), so, in that case, \(c = 0\).

We now first construct an intermediate number \(t = d_1 d_2 d_3 \ldots d_m (c + 1) \overbrace{1 \ldots 1}^{k \text{ times}}\).

Then we construct \(a_{n + 1}\) from \(t\) by replacing each non-overlapping \(11\) in \(t\) by \(12\). Note that the sequence \(d_i\) cannot contain the pattern \(11\); otherwise, \(a_n\) is not part of the sequence. Also, the only way for \(c + 1\) to be \(1\) is if the sequence \(d_i\) is empty (in that case, \(a_n\) consists of only \(3\)s).

With this in mind, it's easy to generate the generate the \(N\)th number: starting with \(0\), we apply the construction above \(N\) times.

In each of our implementations below, we start of with prepending a \(0\) to number. That way, we will always find a \(c\) as above. And we'll strip off a leading \(0\) when we're done.

First, the method which takes a number in the sequence, and return the next number. It makes extensive use of the /r modifier on substitutions: this tells perl not to modify the string it's acting on, but to return the modified string instead.

sub next_num ($prev_num) {
    "0$prev_num" =~ s!([012])(3*)$!($1 + 1) . ($2 =~ s/3/1/rg)!re
                 =~ s!11!12!rg
                 =~ s!^0!!r
}

The pattern in the first substitution captures the last digit which is not a 3, and any 3s following that. This is replaced with the non-3 digit incremented by 1, and a string of 1s of the same length as the string of 3. We do this by using the /e modifier, which tells Perl to execute the replacement part, and use the return value as the replacement. Note that we use another substitution here — with a modern enough Perl, the regexp engine is reentrant.

The second substitution simply replaces any 11 with a 12 — this is the part which prevents a 1-1 sequence.

The final substitution removes any leading 0 which still may be there.

We can now calculate the $Nth element of the sequence, where $_ contains $N:

my $n = 0;
$n = next_num $n for 1 .. $_;
say $n;

Find the full program on GitHub.

AWK doesn't have capture groups (GNU AWK does though), so we have to work a little bit harder. It does have RSTART, which indicates the position in the string where the match started , and RLENGTH, which indicates the length of the matched substring. Our next_num function then becomes:

function next_num (prev_num, tail) {
    match (prev_num, /3*$/)
    tail = substr (prev_num, RSTART)

Now tail contains the trailing 3s of prev_num (tail may be the empty string). We first replace the 3s with 1s:

    gsub (/3/, 1, tail)

We now put tail back into prev_num, after incrementing the number before the trailing 3s. If no such number exists (that is, prev_number consists of just 3s) we just put a 1 before tail:

    if (RLENGTH == length (prev_num)) {
        prev_num = 1 tail
    }
    else {
        prev_num = substr (prev_num, 1, RSTART - 2)      \
                  (substr (prev_num, RSTART - 1, 1) + 1) \
                   tail
    }

Now we just replace any 11 with 12, and return the result.

    gsub (/11/, "12", prev_num)

    return prev_num
}

Find the full program on GitHub.

The Bash function to calculate the next number is surprisingly compact:

function next_number () {
     [[ 0$1 =~ ^(.*)([012])(3*)$ ]]
     next_num=${BASH_REMATCH[1]}$((BASH_REMATCH[2] + 1))${BASH_REMATCH[3]//3/1}
     next_num=${next_num//11/12}
     next_num=${next_num/0/}
}

The first line capturings any leading digits, then the last digit which is not a 3, and the any trailing 3s. Capture groups are availabe in the array BASH_REMATCH.

A new number is constructed by concatenating the first part with the second (incremented by one), and then the third, where each 3 is replaced by a 1. The increment is done using the $((EXPR)) construct, which evaluates EXPR and substitutes its value. The replacement is done by the ${word//pat/replacement} construct, which expands word, then replaces each occurance of pat with replacement.

Then, in the new number, we replace any 11 with 12, and strip off any remaining leading 0.

Find the full program on GitHub.

C doesn't have build in pattern matching, nor much of support for strings. We therefore have to do a lot of manual work. We will be assuming any answer will not require more than 32 digits.

With the input number ($N) in the variable num, we get:

# define BUF_SIZE 32
char number [BUF_SIZE + 1];
for (int i = 0; i < BUF_SIZE; i ++) {
    number [i] = '0';
}
number [BUF_SIZE] = `\0`;

This initializes a NUL-terminated string number of 32 0s.

while (num --) {
    for (i = BUF_SIZE - 1; i > 0 && number [i] == '3'; i --) {
        number [i] = '1';
    }
    number [i] ++;

Set all trailing 3s to 1s, and increment the last digit which is not a 3.

    for (i = 0; i < BUF_SIZE - 1; i ++) {
        if (number [i] == '1' && number [i + 1] == '1') {
            number [i + 1] = '2';
        }
    }

This replaces any 11 with 12.

Now we get to print the number, without any leading 0:

    int i;
    for (i = 0; i < BUF_SIZE && number [i] == '0'; i ++);
    printf ("%s\n", number + i);
}

Find the full program on GitHub.

function next_number (prev_num)
    local _, _, prefix, num, tail =
        ("0" .. prev_num) : find ("(.*)([012])(3*)$")

    return (prefix .. tostring (tonumber (num) + 1) 
                   .. tail : gsub ("3", "1")) : gsub ("11", "12")
                                              : gsub ("^0", "")
end

The Node.js solution is very similar to the Lua solution:

function next_number (prev_number) {
    let [match, prefix, num, tail] =
        ("0" + prev_number) . match (/^(.*)([012])(3*)$/)

    return (prefix + (+ num + 1) + (tail . replace (/3/g,  "1"))) .
                                           replace (/11/g, "12")  .
                                           replace (/^0/,  "")
}

Find the full program on GitHub.

In Python, a regular expression match returns a match object. Which we can query for its capture groups.

def next_num (prev_num):
    match = re . match ('^(.*)([012])(3*)$', "0" + prev_num)
    return (re . sub ('^0', '',  \
                 re . sub ('11', '12', match . group (1) +                 \
                                       str (int (match . group (2)) + 1) + \
                                       re . sub ('3', '1', match . group (3)))))

Find the full program on GitHub.

def next_num (prev_num)
    ("0" + prev_num) . match (/^(.*)([012])(3*)$/) do
        |match|
        return (match [1] + (1 + match [2] . to_i) . to_s +
                match [3] . gsub(/3/, "1")) . gsub(/11/, "12") . gsub(/^0/, "")
    end
end