algorithm - String concatenation queries -

i have list of characters, x in number, denoted b[1], b[2], b[3] ... b[x]. after x,

• b[x+1] concatenation of b[1],b[2].... b[x] in order. similarly,

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

• so, basically, b[n] concatenation of last x terms of b[i], taken left right.

• given parameters p , q queries, how can find out character among b[1], b[2], b[3]..... b[x] q^th character of b[p] corresponds to?

note: x , b[1], b[2], b[3]..... b[x] fixed queries.

i tried brute-forcing string length increases exponentially large x.(x<=100).

---

example:

• when x=3,

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

• so query p=7, q=5, answer returned 3(corresponding character 'c').

i having difficulty figuring out maths behind it. language no issue

i wrote answer figured out, please bear me.

as mentioned, easier find out character @ b[p][q] comes among original x characters generate b[p] large p. so, use loop find current b[p][q] came from, thereby reducing p until between 1 , x, , q until 1.

let's @ example x=3 see if can formula:

p  n(p)  b[p] -  ----  ---- 1  1     2  1     b 3  1     c 4  3     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 clear: n(p) = n(p-1) + n(p-2) + n(p-3), n(p) number of characters in pth element of b. given p , x, can brute-force compute n range [1, p]. allow figure out prior element of b b[p][q] came from.

to illustrate, x=3, p=9 , q=45.

1. the chart above gives n(6)=9, n(7)=17 , n(8)=31. since 45>9+17, know b[9][45] comes b[8][45-(9+17)] = b[8][19].
2. continuing iteratively/recursively, 19>9+5, b[8][19] = b[7][19-(9+5)] = b[7][5].
3. now 5>n(4) 5<n(4)+n(5), 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, have our termination condition, , b[9][45] c b[3].

something can computed either recursively or iteratively given starting p, q, x , b x. method requires p array elements compute n(p) entire sequence. can allocated in array or on stack if working recursively.

here reference implementation in vanilla python (no external imports, although numpy streamline this):

def so38509640(b, p, q):     """     p, q integers. b char sequence of length x.     list, string, or tuple valid choices b.     """     x = len(b)      # trivial case     if p <= x:         if q != 1:             raise valueerror('q={} out of bounds p={}'.format(q, p))         return p, b[p - 1]      # construct list of counts     n = [1] * p     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 p={}'.format(q, p))      print('b[{}][{}]'.format(p, q), end='')      # reduce p, q until p < x     while p > x:         # find previous element character q comes         offset = 0         in range(p - x - 1, p):             if == p - 1:                 raise valueerror('q={} out of bounds p={}'.format(q, p))             if offset + n[i] >= q:                 q -= offset                 p = + 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, example in question, so38509640('abc', 7, 5) produces expected result:

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

sorry couldn't come better function name :) simple enough code should work equally in py2 , 3, despite differences in range function/class.

i curious see if there non-iterative solution problem. perhaps there way of doing using modular arithmetic or something...