[math-fun] [SOLUTION] Combinatorics of shell substitution

26 Aug 2020

      Since Tomas has now found the answer, perhaps it’s time for me to reveal my
method. If you’re still thinking about it, and you don’t want a spoiler,
don’t read on!

.

.

.

.

 SPOILER BREAK

.

.

.

.

The reason this problem is not amenable to naive brute force is that the
strings explode in length very rapidly. So the problem is really to find a
more manageable representation of these strings. What I did – which I
believe is the natural representation in a sense – is to represent
them as **elements
of the group ring of the infinite dihedral group**. Don’t worry, I shall
explain…

Notation: I shall write ‘$x’ to refer to the two-character string
consisting of a dollar sign followed by the letter x, and I shall write $x
to refer to the value of the shell variable x.

If there were no quotation marks, and we were to start, more simply, with:

    x=\$x\$x\$x

then each time we execute

    eval x=$x

the number of occurrences of ‘$x’ would be squared, and so the sequence
would be 3, 9, 81, ... with the (n+1)’st term equal to 3^2^n. This is
therefore an upper bound on the true sequence.

That is not a great deal of use by itself, but it does suggest that the
growth rate of the true sequence could be doubly-exponential – and
certainly that it is no greater than that.

The complication we need to take account of in the real sequence is that
occurrences of ‘$x’ that appear in single quotes inside $x will not be
substituted.

If $x contains α occurrences of ‘$x’ that are in single quotes and β that
are not, then the next value, obtained after executing

    eval x=$x

will contain α + β(α + β) occurrences of ‘$x’.

For example, the initial value has α=1 and β=2, hence the second value of
the sequence is 7.

In order to do this repeatedly, however, we need to know how many of the
occurrences of ‘$x’ in the *new* value of $x occur within single quotes.
And we must retain enough information that we can do this as many times as
we need.

It would suffice to know, for each occurrence of ‘$x’ in $x, the sequence
of ' and " characters to the left of that occurrence. Strings over a
two-character alphabet are, of course, elements of the free monoid on two
generators, which I’ll denote 2*.

So it would be sufficient to represent each value of $x as a set of
elements of 2*. This is not a useful representation, yet, since it’s larger
than just storing the whole string; but we shall improve it.

To determine whether an occurrence of ‘$x’ should be subject to
substitution, we need to know whether it is inside single quotes. There is
a (surjective) homomorphism of monoids from 2* to the symmetric group S_3
that maps ' to the permutation (0 1) and " to the permutation (0 2). I
shall refer to the image under this homomorphism of some string of
quotation marks as the “quotational effect” of that string.

To determine whether an occurrence of ‘$x’ is inside single quotes, we may
take the string of quote marks to the left of that occurrence and compute
the element of S_3 that it maps to under this homomorphism. Consider this
permutation as a bijection π: {0,1,2} → {0,1,2}. If π(0) = 1 then the
occurrence is inside single quotes; if π(0) = 2 then it is inside double
quotes; and if π(0) = 0 then it is not inside quotes at all. So, to
determine whether an occurrence of ‘$x’ should be substituted we need only
check whether or not π(0) = 1.

The element of 2* does, however, contain information that is irrelevant to
us. For example, the strings

    $x
    ''$x
    ""$x
    "''"$x

(and so forth) are all equivalent for our purposes, since the quotational
action is all fully resolved before the occurrence of ‘$x’ has been reached.

On the other hand, we cannot go all the way to elements of S_3, for these
do not contain enough information. For example, the occurences of ‘$x’ in
the strings

    $x
    '"'"'"$x"'"'"'

have the same quotational effect – the identity element of S_3 – but after
one round of evaluation this is no longer the case: the second one has an
additional "' preceding the substituted value of $x, which has a
non-trivial quotational effect (0 2 1).

Therefore a suitable quotient is to ignore paired quotes, i.e. to take the
quotient monoid 〈 a, b | a^2 = 0, b^2 = 0 〉 – where the generators a and b
represent the characters ' and " respectively. This quotient monoid is in
fact a group: the infinite dihedral group D_∞.

Our “quotational effect” homomorphism 2* → S_3 factors through this
quotient, so we have 2* → D_∞ → S_3.

Therefore a suitable representation for our strings is as multisets of
elements of D_∞, which we can more conveniently think of as elements of the
group ring of D_∞ (over the integers, say).

Since D_∞ is the group of isometries of the integers, we may represent an
element of D_∞ as a pair (t, r), where t ∈ ℤ and r ∈ {+1, -1}. The action
of such a pair on the integers is z ↦ r(z + t): “t” stands for “translate”,
and “r” for “reflect”. Our generators a and b will be represented by (0,
-1) and (-1, -1), i.e. z ↦ -z and z ↦ 1 - z, respectively.

Composition is: (t1, r1) ; (t2, r2) = (t1 + r1 × t2, r1 × r2).

Now we need only work out how to compute, for each element of D_∞:

 * which element of D_∞ it becomes after evaluation; and
 * whether the occurrences of ‘$x’ it represents should be substituted.

It is not too hard to see that (t, r) reduces to (⌈t/3⌉, r'), where r'
depends only on r and the value of t modulo 3. In fact, reducing t modulo 3
is essentially the “quotational effect” homomorphism, so we can also decide
whether or not to substitute these occurrences of ‘$x’ from the values of r
and (t mod 3). The mapping from (r, t mod 3) to (r', substitute?) is:

(0, +1) ↦ (+1, True)    # ()
(1, +1) ↦ (-1, False)   # (0 1 2)
(2, +1) ↦ (-1, True)    # (0 2 1)
(0, -1) ↦ (+1, False)   # (0 1)
(1, -1) ↦ (-1, True)    # (1 2)
(2, -1) ↦ (+1, True)    # (0 2)

where I have also annotated each line with the relevant quotational effect.

All of this means that the following Python (3) program should print out
the values of the sequence:

import math

TABLE = {
    (0, +1): (+1, True),   # ()
    (1, +1): (-1, False),  # (0 1 2)
    (2, +1): (-1, True),   # (0 2 1)
    (0, -1): (+1, False),  # (0 1)
    (1, -1): (-1, True),   # (1 2)
    (2, -1): (+1, True)    # (0 2)
}

def compose(tr1, tr2):
    (t1, r1), (t2, r2) = tr1, tr2
    return (t1 + r1*t2, r1*r2)

def subst(x, y):
    z = {}
    for ((t0, r0), n0) in x.items():
        # Let tr1 be the dequoted version of (t0, r0)
        t1 = -math.ceil(t0 / 3)
        r1, should_substitute = TABLE[t0 % 3, r0]
        tr1 = (t1, r1)

        # and substitute where appropriate
        if should_substitute:
            for (tr2, n2) in y.items():
                tr3 = compose(tr1, tr2)
                z[tr3] = z.get(tr3, 0) + n0 * n2
        else:
            z[tr1] = z.get(tr1, 0) + n0

    return z

x = { (-1, +1): 1, (0, +1): 1, (+1, +1): 1 }
print(sum(x.values()))
for i in range(10):
    x = subst(x, x)
    print(sum(x.values()))

Indeed, running the program produces:

3
7
37
973
642493
274981436065
50075673362453978752897
1660424958340272612902157434339071057416705025
1828659082532127294015555219377679316426731045207698280944194119017937814697416523736342529
2221932973262746587938621327316508263261099068744811444411319257981535885894143217671769171584514785091039842436855683166325319643148964213893272271303784306333684832769323249729537
3284840218479775743047790632317572154909424991433212164298865481805700811352338269615571535863546774083036854200912305419781334801792798527519528263346227635678885261969168464305471249372299734845553556695985956938868825596778725419448920773764852977163215319470541619936785213643936937876887597557533802625700859018364222540571399561867801071781407682811002881

where the last line is the answer to the puzzle, and matches what Tomas
found with a different method.

Cheers,
Robin

Robin Houston

Tomas Rokicki

Robin Houston

tags

participants (2)