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!

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

Answer 2

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

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.

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

Answer 5

Husk, 5 bytes

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

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

Safer answer, 8 bytes

!₁
S+S₁+

Try it online!

This one gets the Ith character, at the cost of 3 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

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

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

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

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.

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

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!