0
$\begingroup$

I'm looking to generate a mapping between integers and valid domain names labels.

A domain name label is a sequence of 1 to 63 characters consisting of the letters a through z, the numbers 0 through 9, and a hyphen. The hyphen is restricted such that it cannot occur at the start or end of the label and a hyphen cannot immediately follow another hyphen. Note: I'm intentionally ignoring things like punicode here.

Some examples of valid labels:

  • google
  • 1234
  • a-b
  • 1-22-3333-4444

Some examples of invalid labels:

  • -google (starts with a hyphen)
  • google- (ends with a hyphen)
  • goo--gle (has two hyphens in a row)
  • g##gle (has invalid characters)

I'd like the mapping to keep short labels first, and follow lexicographical ordering:

f(0) => 0
f(1) => 1
...
f(9) => 9
f(10) => a
...
f(35) => z
f(36) => 00
f(36) => 01
...
etc

The one and two digit labels are easily computed, in order using:

DOMAIN_LABEL_CHARS = string.digits + string.ascii_lowercase
def f(i):
    label = ''
    while True:
        label = DOMAIN_LABEL_CHARS[i % len(DOMAIN_LABEL_CHARS)] + label
        i = int(i / len(DOMAIN_LABEL_CHARS))
        if i < 1:
            break
        i -= 1
    return label

I'm getting stuck adding support for the hyphen. It should follow with:

f(1331) => zz
f(1332) => 0-0
f(1333) => 0-1

While, I can special case three character labels as [0-9a-z][-0-9a-z][0-9a-z], longer labels get more complex:

length=4
    [0-9a-z][-][0-9a-z]{2}
AND [0-9a-z]{2}[-][0-9a-z]
AND [0-9a-z]{4}

length=5
    [0-9a-z][-][0-9a-z][-][0-9a-z]
AND [0-9a-z][-][0-9a-z]{3}
AND [0-9a-z]{2}[-][0-9a-z]{2}
AND [0-9a-z]{3}[-][0-9a-z]
AND [0-9a-z]{5}

etc.

I was able to determine that the there are $f(N) = 36 * (f(N-1) + f(N-2))$ possible encodings for the inner characters of the label. Which has a Fibonacci sequence embedded in it.

I found this by focusing on the inner characters which may be hyphens; the outer characters are always alphanumeric with 36 options each and are uninteresting. When $N=1$ the hyphen is not restricted, so $f(N) = 36 + 1$. When $N=2$ the we can have zero hyphens ($36^2$ options) or one hyphen at the start ($1 * 36$ options) or one hyphen at the end ($36 * 1$ options). For higher N, we can start without a hyphen ($36 * f(N-1)$ options) or start with a hyphen followed by an alphanumeric ($1 * 36 * f(N-2)$ options). This gives us $f(N) = 36 * (f(N-1) + f(N-2))$.

Given these constraints and observations, how can I generate the rest of the labels in order?

$\endgroup$

1 Answer 1

0
$\begingroup$

I was able to figure this one out using a recursive approach.

Base cases:

If $i < 36$, then the domain is a single character. Use CHARS=[0-9a-z] as a lookup table.

If $i < 36^2 + 36$, then the domain contains two characters. The least significant character can be computed by looking up $i \% 36$ in CHARS. We then reduce $i \leftarrow int(i / 36)$. Subtract one from $i$ (this let's us wrap from zz to 0.. instead of 1..). Finally lookup $i % 36% in CHARS to get the most significant character.

Recursive step:

Given an index $i$ that produces a domain of length $n$. Observe that the most significant character must be in CHARS. The next character can be a hyphen. If it is, then the remaining characters are a valid domain name (I.E., cannot start or end with a hyphen and cannot contain two hyphens in a row). If it's not then it and the remaining characters are a valid domain name.

We can determine the length of the domain name label using the algorithm mentioned in the question.

You'll need to compute the characters from the most significant side first. For the first recursive step, subtract by the index of the first domain name label of the target length (I.E. the index of 0-0 for a domain of length three). We'll need a divisor that matches the number of labels needed to increment the most significant character (I.E., the number of labels between 0zz and 1-0, when using length three). Divide the index by this divisor, using the result to lookup the most significant character from CHARS. The remainder is then recursively solved until we reach the base cases.

This is perhaps better seen written as code. I've published a module on pypi that solves this problem. The code is on GitHub here.

A couple interesting numbers are referenced in the docs:

index_of_domain_name_label("google") => 1191294986

LAST_63_CHAR_INDEX = 583791014263271482476326569507663027313555716330347307932966791104859150313363146960655804883807043
generate_domain_name_label(LAST_63_CHAR_INDEX) => "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .