Variable length Fibonacci word

Question

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 code-golf, so the lowest byte count for each language wins!

• caird coinheringaahing: Could you provide a smaller test case, say ABC, DEF, 10?
• l4m2: Can we just output F(∞)?
• zdimension: @user typo, fixed
• zdimension: @LuisMendo yes, I'll add that to the post
• zdimension: @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

Answer 1

Haskell, 15 bytes

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 sequence 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\$.

• caird coinheringaahing: 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 :)
• Delfad0r: @cairdcoinheringaahing Duly noted :(

Answer 2

Jelly, (削除) 6 (削除ここまで) 5 bytes

9;¡5ị

Try it online!

Uses 1 indexing

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

Dyadic ¡ is essentially Jelly's generalised Fibonacci operator

How it works

9;¡5ị - Main link. Takes A on the left, B on the right and I as the third argument
9 - Set the return value to B
 ¡ - I times do the following, swapping the updated arguments each time:
 ; - Concatenate the arguments
 5ị - 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 9 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

• Jonathan Allan: 5 bytes using a leading constant chain instead with 9;¡5ị - TIO.
• caird coinheringaahing: @JonathanAllan That's a brilliant catch, thanks!
• Bubbler: Now we need tribonacci version to make the ¡ unusable :P

Answer 3

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.

• dingledooper: Does f=lambda a,b,i:b[i:i+1]or f(b,b+a,i) work for 36 bytes?
• hyperneutrino: @dingledooper yes, that's clever. thanks!

Answer 4

JavaScript (Node.js), 26 bytes

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

Try it online!

Thank tsh for -1 Byte

• wasif: This answer fails for the last string....
• l4m2: @Wasif Because of insufficant RAM
• tsh: n=>g=a=>b=>b[n]||g(b)(b+a)

Answer 5

Husk, 5 bytes

A rip-off of Delfad0r's beautiful Haskell answer. Go upvote that!

S+S0+

Try it online!

Returns the entire infinite string/list.

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

Safer answer, 8 bytes

!1
S+S1+

Try it online!

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

• Razetime: The non-fix method is shorter here: Try it online!
• user: @Razetime ...wow. Do you want to post that as your own answer?
• Razetime: nah, feel free to modify.
• Leo: 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: 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

Answer 6

R, (削除) 96 (削除ここまで) (削除) 92 (削除ここまで) 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

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

Answer 7

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

Answer 8

Charcoal, 42 bytes

≔−NLζθ≔0εW¬‹θ0«F¬&ε⊗ε≧−+Lζ∧%ε2Lηθ≦⊕廧+ηζθ

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.

≔−NLζθ

Subtract the length of B from n.

≔0ε

Start enumerating Fibbinary numbers.

W¬‹θ0«

Repeat until n is negative.

F¬&ε⊗ε

Is the current index a Fibbinary number?

≧−+Lζ∧%ε2Lηθ

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).

Answer 9

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.

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

Answer 10

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

• Julian: 63 bytes?
• mazzy: "You may choose any format for the input." - Try it online!

Answer 11

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!