# Project Euler #230: Fibonacci Words

# Project Euler #230: Fibonacci Words

+ 4 comments We don't need to build string, just set up the string length counter to get the first on bigger than the Number n. Then decompose the F(n)= F(n-1) + F(n-2). This structure indicate the string is always prefix with F(n-1). If number is bigger then F(n-1), then decompose the F(n-2), otherwise decompose F(n-1). This is my Java Version which pass all test:

`static int getResult(String one, String two, BigInteger n) { List<BigInteger> fcount = new ArrayList<BigInteger>(); BigInteger oneInt = BigInteger.valueOf(one.length()); BigInteger twoInt = BigInteger.valueOf(two.length()); fcount.add(oneInt); fcount.add(twoInt); int result = -1; do{ fcount.add(oneInt.add(twoInt)); oneInt = twoInt; twoInt = fcount.get(fcount.size()-1); }while(twoInt.compareTo(n)<0); int i = fcount.size() -3; int currentIndex = i; while(i>=0) { BigInteger current = fcount.get(i); if(n.compareTo(current)>0) { n = n.subtract(current); i--; currentIndex = i; } else { if(i==0) result = one.charAt(n.intValue() - 1); if(i==1) result = two.charAt(n.intValue() - 1); i = currentIndex - 2; currentIndex = i; } } if(result == -1) result = two.charAt(n.intValue() - 1); return (result - 48); }`

+ 2 comments Here are some hints

1) There is no way you are going to be able to build an actual string of most fibonacci words involved here.

2) The trick is to track where a and b are in each word in the sequence, and the total length of each word,

*without copying anything*.3) You can't avoid dealing with numbers that are higher than most built-in long int data types. I used javascript and wrote some simple functions to do arithmetic with integers in strings (i.e., '134534234345' instead of 134534234345).

+ 7 comments Here's another python version that is (hopefully?) reasonably well-commented to make it clear what's happening.

BTW I have to admit that I really find it astonishing how much cleaner the Python solutions to many of these problems look compared to other languages! To me, it's really

*much*closer to the pseudocode I'd write. Or is it just me?import os def find_digit(A, B, n): lengths = [len(A)] if n <= len(A): return A[n-1] lengths.append(len(B)) if n <= len(B): return B[n-1] idx = 1 # Building up until we hit total digit length n. # Only count length though, do not build the actual string! while True: idx = idx + 1 lengths.append(lengths[idx-2] + lengths[idx-1]) if lengths[idx] >= n: break # Going back recursively until we know where exactly to # find digit n. Use the fact that # sequence[i] = [sequence[i-2], sequence[i-1]]. len_diff = n while idx > 1: if lengths[idx-2] < len_diff: # Digit n is in the second part of the sequence # section currently considered. len_diff = len_diff - lengths[idx-2] idx = idx - 1 else: # Digit n is in first part of the sequence section # currently considered. idx = idx - 2 if idx == 0: return A[len_diff-1] else: return B[len_diff-1] if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') num_tests = int(input().strip()) tests = [] for i in range(num_tests): A, B, n_str = input().rstrip().split() num = find_digit(A, B, int(n_str)) fptr.write(str(num) + '\n') fptr.close()

+ 1 comment any one knows what test1 is about ? it is the only one I am failing...

+ 2 comments def findlengthofterm(n): if n == 1: return len(A) elif n==2: return len(B) a=len(A) b=len(B) c=0 i=2 while(i<n): c= a+b a,b=b,c i+=1 return c def findIndex(n) : if (n <= 1) : return n a = len(A) b = len(B) c = 0 res = 2 while (c < n) : c = a + b res = res + 1 a = b b = c return res if __name__=='__main__': num = int(input()) output =[] for i in range(num): A,B, x = input().split() s=int(x) n=findIndex(s) a=s while(n > 2): l=findlengthofterm(n-2) if a>l: a=a-l else: n-=1 n-=1 if n==1: output.append(A[a-1]) else: output.append(B[a-1]) for out in output: print(out)

Sort 63 Discussions, By:

Please Login in order to post a comment