13
\$\begingroup\$

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!

\$\endgroup\$
13
  • 1
    \$\begingroup\$ Could you provide a smaller test case, say ABC, DEF, 10? \$\endgroup\$ Apr 12, 2021 at 15:42
  • 3
    \$\begingroup\$ Can we just output F(∞)? \$\endgroup\$
    – l4m2
    Apr 12, 2021 at 15:43
  • 1
    \$\begingroup\$ @user typo, fixed \$\endgroup\$
    – zdimension
    Apr 12, 2021 at 15:49
  • 1
    \$\begingroup\$ @LuisMendo yes, I'll add that to the post \$\endgroup\$
    – zdimension
    Apr 12, 2021 at 18:27
  • 2
    \$\begingroup\$ @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 \$\endgroup\$
    – zdimension
    Apr 13, 2021 at 0:54

11 Answers 11

11
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 :) \$\endgroup\$ Apr 12, 2021 at 17:33
  • \$\begingroup\$ @cairdcoinheringaahing Duly noted :( \$\endgroup\$
    – Delfad0r
    Apr 12, 2021 at 17:42
10
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ 5 bytes using a leading constant chain instead with ⁹;¡⁵ị - TIO. \$\endgroup\$ Apr 12, 2021 at 18:02
  • \$\begingroup\$ @JonathanAllan That's a brilliant catch, thanks! \$\endgroup\$ Apr 12, 2021 at 18:03
  • \$\begingroup\$ Now we need tribonacci version to make the ¡ unusable :P \$\endgroup\$
    – Bubbler
    Apr 13, 2021 at 0:25
9
\$\begingroup\$

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.

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

JavaScript (Node.js), 26 bytes

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

Try it online!

Thank tsh for -1 Byte

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

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.

\$\endgroup\$
9
  • \$\begingroup\$ The non-fix method is shorter here: Try it online! \$\endgroup\$
    – Razetime
    Apr 12, 2021 at 16:32
  • \$\begingroup\$ @Razetime ...wow. Do you want to post that as your own answer? \$\endgroup\$
    – user
    Apr 12, 2021 at 16:33
  • 1
    \$\begingroup\$ nah, feel free to modify. \$\endgroup\$
    – Razetime
    Apr 12, 2021 at 16:36
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Leo
    Apr 12, 2021 at 22:44
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Leo
    Apr 12, 2021 at 23:57
3
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ At risk of outgolfing my own attempt, I think you can save a few bytes using substr instead of strsplit: try it... \$\endgroup\$ Apr 13, 2021 at 11:05
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 42 bytes

≔⁻NLζθ≔⁰εW¬‹θ⁰«F¬&ε⊗ε≧⁻⁺Lζ∧﹪ε²Lηθ≦⊕廧⁺ηζθ

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.

≔⁰ε

Start enumerating Fibbinary numbers.

W¬‹θ⁰«

Repeat until n is negative.

F¬&ε⊗ε

Is the current index a Fibbinary number?

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

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Take b and a separately for 66 bytes \$\endgroup\$
    – Giuseppe
    Apr 13, 2021 at 11:14
  • \$\begingroup\$ @Giuseppe - Oh, for goodness sake! That's so obvious now you've suggested it! Thanks! \$\endgroup\$ Apr 13, 2021 at 11:19
1
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 63 bytes? \$\endgroup\$
    – Julian
    Apr 13, 2021 at 0:21
  • \$\begingroup\$ "You may choose any format for the input." - Try it online! \$\endgroup\$
    – mazzy
    Apr 13, 2021 at 4:32
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.