Infinite string

Question

We are given N words, each of length at max 50.All words consist of small case alphabets and digits and then we concatenate all the N words to form a bigger string A.An infinite string S is built by performing infinite steps on A recursively: In ith step, A is concatenated with ′$′ i times followed by reverse of A. Eg: let N be 3 and each word be '1','2' and '3' after concatenating we get A= 123 reverse of a is 321 and on first recursion it will be A=123$321 on second recursion it will be A=123$321$$123$321 And so on… The infinite string thus obtained is S.Now after ith recursion we have to find the character at index say k.Now recursion can be large as pow(10,4) and N which can be large as (pow(10,4)) and length of each word at max is 50 so in worst case scenario our starting string can have a length of 5*(10**5) which is huge so recursion and adding the string won't work.

What I came up with is that the string would be a palindrome after 1 st recursion so if I can calculate the pos of '$'*I I can calculate any index since the string before and after it is a palindrome.I came up with a pattern that looks like this:

string='123'
k=len(string)
recursion=100
lis=[]
for i in range(1,recursion+1):
    x=(2**(i-1))
    y=x*(k+1)+(x-i)
    lis.append(y)
print(lis[:10])

Output: [4, 8, 17, 36, 75, 154, 313, 632, 1271, 2550]

Now I have two problems with it first I also want to add position of adjacent '$' in the list because at position 8 which is the after 2nd recursion there will be more (recursion-1)=1 more '$' at position 9 and likewise for position 17 which is 3rd recursion there will be (3-1) two more '$' in position 18 and 19 and this would continue until ith recursion and for that I would have to insert while loop and that would make my algorithm to give TLE

string='123'
k=len(string)
recursion=100
lis=[]
for i in range(1,recursion+1):
    x=(2**(i-1))
    y=x*(k+1)+(x-i)
    lis.append(y)
    count=1
    while(count<i):
        y=y+1
        lis.append(y)
        count+=1
print(lis[:10])

Output: [4, 8, 9, 17, 18, 19, 36, 37, 38, 39]

The idea behind finding the position of $ is that the string before and after it is a palindrome and if the index of $ is odd the element before and after it would be the last element of the string and it is even the element before and after it would be the first element of the string.

Answer 1

The number of dollar signs that S will have in each group of them follows the following sequence:

1 2 1 3 1 2 1 4 1 2 1 ...

This corresponds to the number of trailing zeroes that i has in its binary representation, plus one:

 bin(i) | dollar signs
--------+-------------
 00001  |     1
 00010  |     2
 00011  |     1
 00100  |     3
 00101  |     1
 00110  |     2
  ...       ...

With that information you can use a loop that subtracts from k the size of the original words and then subtracts the number of dollars according to the above observation. This way you can detect whether k points at a dollar or within a word.

Once k has been "normalised" to an index within the limits of the original total words length, there only remains a check to see whether the characters are in their normal order or reversed. This depends on the number of iterations done in the above loop, and corresponds to i, i.e. whether it is odd or even.

This leads to this code:

def getCharAt(words, k):
    size = sum([len(word) for word in words]) # sum up the word sizes
    i = 0

    while k >= size:
        i += 1
        # Determine number of dollars: corresponds to one more than the 
        #   number of trailing zeroes in the binary representation of i
        b = bin(i)
        dollars = len(b) - b.rindex("1")
        k -= size + dollars

    if k < 0:
        return '$'
    if i%2: # if i is odd, then look in reversed order
        k = size - 1 - k
    # Get the character at the k-th index    
    for word in words:
        if k < len(word):
            return word[k]
        k -= len(word)

You would call it like so:

print (getCharAt(['1','2','3'], 13)) # outputs 3

Generator Version

When you need to request multiple characters like that, it might be more interesting to create a generator, which just keeps producing the next character as long as you keep iterating:

def getCharacters(words):
    i = 0
    while True:
        i += 1
        if i%2:
            for word in words:
                yield from word
        else:
            for word in reversed(words):
                yield from reversed(word)
        b = bin(i)
        dollars = len(b) - b.rindex("1")
        yield from "$" * dollars

If for instance you want the first 80 characters from the infinite string that would be built from "a", "b" and "cd", then call it like this:

import itertools
print ("".join(itertools.islice(getCharacters(['a', 'b', 'cd']), 80)))

Output:

abcd$dcba$$abcd$dcba$$$abcd$dcba$$abcd$dcba$$$$abcd$dcba$$abcd$dcba$$$abcd$dcba$

Answer 2

Here is my solution to the problem (index starts at 1 for findIndex) I am basically counting recursively to find the value of the findIndex element.

def findInd(k,n,findIndex,orientation):
  temp = k # no. of characters covered.
  tempRec = n # no. of dollars to be added
  bool = True # keeps track of if dollar or reverse of string is to be added.
  while temp < findIndex:
    if bool:
      temp += tempRec
      tempRec += 1
      bool = not bool
    else:
      temp += temp - (tempRec - 1)
      bool = not bool
  # print(temp,findIndex)
  if bool:
    if findIndex <= k:
      if orientation: # checks if string must be reversed.
        return A[findIndex - 1]
      else:
        return A[::-1][findIndex - 1] # the string reverses when there is a single dollar so this is necessary
    else:
      if tempRec-1 == 1:
        return findInd(k,1,findIndex - (temp+tempRec-1)/2,False) # we send a false for orientation as we want a reverse in case we encounter a single dollar sign.
      else:
        return findInd(k,1,findIndex - (temp+tempRec-1)/2,True) 
  else:
    return "$"


A = "123"                                         # change to suit your need
findIndex = 24 # the index to be found            # change to suit your need




k = len(A) # length of the string.

print(findInd(k,1,findIndex,True))

I think this will satisfy your time constraint also as I do not go through each element.