# Challenge

For any two non-empty strings A and B, we define the following sequence :

F(0) = A
F(1) = B
F(n) = F(n-1) + F(n-2)


Where + denotates the standard string concatenation.

The sequence for strings "A" and "B" starts with the following terms: A, B, BA, BAB, BABBA, ...

Create a function or program that, when given two strings A and B, and a positive integer I returns the I-th character of F(∞).

You may choose to use 0-indexing or 1-indexing for I, just specify it in your answer.

You may assume the strings contain only uppercase (or lowercase) letters.

This is a variation of Project Euler's Problem 230, where the two strings were strings of digits of equal length, which trivialize the problem.

# Input/Output

You may choose any format for the input. The output should only contain the desired character, with trailing spaces/newlines allowed.

# Test Cases

ABC, DEF, 1234567890 → A
ACBB, DEFGH, 45865 → B
A, B, 3 → B
ABC, DEF, 10 → E


This is , so the lowest byte count for each language wins!

• Could you provide a smaller test case, say ABC, DEF, 10? – caird coinheringaahing Apr 12 at 15:42
• Can we just output F(∞)? – l4m2 Apr 12 at 15:43
• @user typo, fixed – zdimension Apr 12 at 15:49
• @LuisMendo yes, I'll add that to the post – zdimension Apr 12 at 18:27
• @user that makes sense, I hadn't understood it that way. I guess outputting the string isn't an issue, as long as the required output (nth character) is easily seen – zdimension Apr 13 at 0:54

a#b=b++b#(a++b)


Try it online!

Takes strings a and b as input, returns the whole infinite Fibonacci word, as is usually allowed in challenges.

## How?

Not much to say. This answer relies on the identity $$F(a,b)=b+F(b,a+b),$$ where $$\F(a,b)\$$ is the infinite Fibonacci word with starting words $$\a\$$ and $$\b\$$.

• Just a reminder that marking something as non-competitive does not allow it to be invalid, so if it turns out that it isn't allowed to output F(∞), then you should modify your answer :) – caird coinheringaahing Apr 12 at 17:33
• @cairdcoinheringaahing Duly noted :( – Delfad0r Apr 12 at 17:42

# Jelly, 6 5 bytes

⁹;¡⁵ị


Try it online!

Uses 1 indexing

-1 byte thanks to Jonathan Allan, noticing that we could avoid ⁵ becoming the right argument to ;¡ by forcing ;¡ into a nilad-dyad pair with ⁹!

Dyadic ¡ is essentially Jelly's generalised Fibonacci operator

## How it works

⁹;¡⁵ị - Main link. Takes A on the left, B on the right and I as the third argument
⁹     - Set the return value to B
¡   - I times do the following, swapping the updated arguments each time:
;    -   Concatenate the arguments
⁵ị - Yield the i'th character of the result


When ;¡ is run with 2 arguments, it does the following (calling the initial left argument B and the initial right argument A, as ⁹ essentially "swaps" the order of the arguments. We'll do 3 iterations):

• Iteration 1: ; concatenates B and A, yielding BA. We then move B to the right and take BA as our left argument for the next iteration
• Iteration 2: ; concatenates BA and B, yielding BAB. Our arguments become BAB on the left and BA on the right
• Iteration 3: ; concatenates BAB and BA, yielding BABBA. This is the last iteration, so we return BABBA
• 5 bytes using a leading constant chain instead with ⁹;¡⁵ị - TIO. – Jonathan Allan Apr 12 at 18:02
• @JonathanAllan That's a brilliant catch, thanks! – caird coinheringaahing Apr 12 at 18:03
• Now we need tribonacci version to make the ¡ unusable :P – Bubbler Apr 13 at 0:25

# Python 3, 36 bytes

f=lambda a,b,i:b[i:i+1]or f(b,b+a,i)


Try it online!

-8 bytes thanks to dingledooper

Not a particularly creative approach. In fact, basically this is just what l4m2 did but Python will error when accessing out of bounds instead of returning undefined. Using b[i:i+1] returns b[i] (for strings) if it's in range, but doesn't error and instead gives "" if it's out of range. Thanks to dingledooper for that.

Go upvote this answer too. This isn't really intentionally a port because I thought of the same idea but it's an identical approach.

• Does f=lambda a,b,i:b[i:i+1]or f(b,b+a,i) work for 36 bytes? – dingledooper Apr 12 at 17:34
• @dingledooper yes, that's clever. thanks! – hyper-neutrino Apr 12 at 19:40

# JavaScript (Node.js), 26 bytes

n=>g=a=>b=>b[n]||g(b)(b+a)


Try it online!

Thank tsh for -1 Byte

• This answer fails for the last string.... – Wasif Apr 12 at 15:59
• @Wasif Because of insufficant RAM – l4m2 Apr 12 at 16:01
• n=>g=a=>b=>b[n]||g(b)(b+a) – tsh Apr 13 at 2:18

# Husk, 5 bytes

S+S₀+


Try it online!

Returns the entire infinite string/list.

S+S₀+ a b is (S+) ((S₀) (+a)) b, which expands to (+b) ((S₀ (+a)) b) (where ₀ is a self-reference to the main function) and then to (+b) (₀ b (+a b)), which is basically b + F(b, a + b).

!₁
S+S₁+


Try it online!

This one gets the Ith character, at the cost of 3 bytes.

• The non-fix method is shorter here: Try it online! – Razetime Apr 12 at 16:32
• @Razetime ...wow. Do you want to post that as your own answer? – user Apr 12 at 16:33
• nah, feel free to modify. – Razetime Apr 12 at 16:36
• Unfortunately both options seem to return 'A' for input 'ABC','DEF',1 while they should return 'D' instead. They are also not equivalent to each other for other inputs – Leo Apr 12 at 22:44
• That's very nice! I was struggling to find a short solution for this... The only problem with both this and the Haskell answer is that the challenge does not explicitly allow printing the full sequence... I hope they'll change their mind, but at worst this would be fixable with just 2 or 3 extra bytes – Leo Apr 12 at 23:57

# R, 9692 84 bytes

function(A,B,I,!=function(k)"if"(k,"if"(k>1,paste0(!k-1,!k-2),B),A))substr(!I,I,I)


Try it online!

Takes I 1-indexed.

-8 bytes thanks to @Dominic

• At risk of outgolfing my own attempt, I think you can save a few bytes using substr instead of strsplit: try it... – Dominic van Essen Apr 13 at 11:05

# 05AB1E, 6 5 bytes

-1 byte by assuming the input words consist only of letters (è implicitly swaps arguments if the first one doesn't look like a number)

Takes inputs [A, B] and n.

λèì}è


Try it online!

Commented:

λè }    # get the nth element of the sequence generated by:
ì     #   prepending the current string to the last string
# that starts with [A, B]
è  # index with n into the nth element of the sequence


# Charcoal, 42 bytes

≔⁻ＮＬζθ≔⁰εＷ¬‹θ⁰«Ｆ¬＆ε⊗ε≧⁻⁺Ｌζ∧﹪ε²Ｌηθ≦⊕ε»§⁺ηζθ


Try it online! Link is to verbose version of code. Takes the index as the first input. Explanation: I wanted to avoid building up a humunguous string but the code is still slow because I don't know a good way of calculating Fibbinary numbers.

≔⁻ＮＬζθ


Subtract the length of B from n.

≔⁰ε


Start enumerating Fibbinary numbers.

Ｗ¬‹θ⁰«


Repeat until n is negative.

Ｆ¬＆ε⊗ε


Is the current index a Fibbinary number?

≧⁻⁺Ｌζ∧﹪ε²Ｌηθ


If so then subtract the length of either B or BA from n depending on whether the current index is even or odd.

≦⊕ε


Increment the index.

»§⁺ηζθ


Output the nth character of AB (since n is negative here, Charcoal counts back from the end).

# R, 76 66 bytes

Edit: -10 bytes thanks to Giuseppe

f=function(b,a,n)if(nchar(b)>n,substr(b,n,n),f(paste0(b,a),b,n))


Try it online!

Recursive function: input the starting strings b and a (note reversed order), and the 1-based index to output.

Could be a bit shorter (53 bytes) if inputs are vectors of characters instead of strings.

# R, 48 bytes

function(a,b)repeat{c=b;cat(b<-paste0(b,a));a=c}


Try it online!

Prints the infinite string.

• Take b and a separately for 66 bytes – Giuseppe Apr 13 at 11:14
• @Giuseppe - Oh, for goodness sake! That's so obvious now you've suggested it! Thanks! – Dominic van Essen Apr 13 at 11:19

# PowerShell, 63 bytes

param($x,$y,$n)$a=$x,$y
1..$n|%{$a+=$a[$_]+$a[$_-1]}
$a[-1][$n]


Try it online!

-11 bytes thanks to julian

• 63 bytes? – Julian Apr 13 at 0:21
• "You may choose any format for the input." - Try it online! – mazzy Apr 13 at 4:32

# Java (JDK), 70 bytes

(a,b,n)->{for(var t=a;b.length()<=n;a=b,b=t)t=b+a;return b.charAt(n);}


Try it online!