String concatenation queries

Question

I have a list of characters, say x in number, denoted by b[1], b[2], b[3] ... b[x]. After x,

• b[x+1] is the concatenation of b[1],b[2].... b[x] in that order. Similarly,

• b[x+2] is the concatenation of b[2],b[3]....b[x],b[x+1].

• So, basically, b[n] will be concatenation of last x terms of b[i], taken left from right.

• Given parameters as p and q as queries, how can I find out which character among b[1], b[2], b[3]..... b[x] does the q^th character of b[p] corresponds to?

Note: x and b[1], b[2], b[3]..... b[x] is fixed for all queries.

I tried brute-forcing but the string length increases exponentially for large x.(x<=100).

---

Example:

• When x=3,

  b[] = a, b, c, a b c, b c abc, c abc bcabc, abc bcabc cabcbcabc, //....  
  //Spaces for clarity, only commas separate array elements
  

• So for a query where p=7, q=5, answer returned would be 3(corresponding to character 'c').

I am just having difficulty figuring out the maths behind it. Language is no issue

Answer 1

I wrote this answer as I figured it out, so please bear with me.

As you mentioned, it is much easier to find out where the character at b[p][q] comes from among the original x characters than to generate b[p] for large p. To do so, we will use a loop to find where the current b[p][q] came from, thereby reducing p until it is between 1 and x, and q until it is 1.

Let's look at an example for x=3 to see if we can get a formula:

p  N(p)  b[p]
-  ----  ----
1  1     a
2  1     b
3  1     c
4  3     a b c
5  5     b c abc
6  9     c abc bcabc
7  17    abc bcabc cabcbcabc
8  31    bcabc cabcbcabc abcbcabccabcbcabc
9  57    cabcbcabc abcbcabccabcbcabc bcabccabcbcabcabcbcabccabcbcabc

The sequence is clear: N(p) = N(p-1) + N(p-2) + N(p-3), where N(p) is the number of characters in the pth element of b. Given p and x, you can just brute-force compute all the N for the range [1, p]. This will allow you to figure out which prior element of b b[p][q] came from.

To illustrate, say x=3, p=9 and q=45.

1. The chart above gives N(6)=9, N(7)=17 and N(8)=31. Since 45>9+17, you know that b[9][45] comes from b[8][45-(9+17)] = b[8][19].
2. Continuing iteratively/recursively, 19>9+5, so b[8][19] = b[7][19-(9+5)] = b[7][5].
3. Now 5>N(4) but 5<N(4)+N(5), so b[7][5] = b[5][5-3] = b[5][2].
4. b[5][2] = b[3][2-1] = b[3][1]
5. Since 3 <= x, we have our termination condition, and b[9][45] is c from b[3].

Something like this can very easily be computed either recursively or iteratively given starting p, q, x and b up to x. My method requires p array elements to compute N(p) for the entire sequence. This can be allocated in an array or on the stack if working recursively.

Here is a reference implementation in vanilla Python (no external imports, although numpy would probably help streamline this):

def so38509640(b, p, q):
    """
    p, q are integers. b is a char sequence of length x.
    list, string, or tuple are all valid choices for b.
    """
    x = len(b)

    # Trivial case
    if p <= x:
        if q != 1:
            raise ValueError('q={} out of bounds for p={}'.format(q, p))
        return p, b[p - 1]

    # Construct list of counts
    N = [1] * p
    for i in range(x, p):
        N[i] = sum(N[i - x:i])
    print('N =', N)

    # Error check
    if q > N[-1]:
        raise ValueError('q={} out of bounds for p={}'.format(q, p))

    print('b[{}][{}]'.format(p, q), end='')

    # Reduce p, q until it is p < x
    while p > x:
        # Find which previous element character q comes from
        offset = 0
        for i in range(p - x - 1, p):
            if i == p - 1:
                raise ValueError('q={} out of bounds for p={}'.format(q, p))
            if offset + N[i] >= q:
                q -= offset
                p = i + 1
                print(' = b[{}][{}]'.format(p, q), end='')
                break
            offset += N[i]
    print()
    return p, b[p - 1]

Calling so38509640('abc', 9, 45) produces

N = [1, 1, 1, 3, 5, 9, 17, 31, 57]
b[9][45] = b[8][19] = b[7][5] = b[5][2] = b[3][1]
(3, 'c') # <-- Final answer

Similarly, for the example in the question, so38509640('abc', 7, 5) produces the expected result:

N = [1, 1, 1, 3, 5, 9, 17]
b[7][5] = b[5][2] = b[3][1]
(3, 'c') # <-- Final answer

Sorry I couldn't come up with a better function name :) This is simple enough code that it should work equally well in Py2 and 3, despite differences in the range function/class.

I would be very curious to see if there is a non-iterative solution for this problem. Perhaps there is a way of doing this using modular arithmetic or something...