Edit - Code Golf Stack Exchange

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Rev

Required fields*

What kind of Fibonacci subword at this offset?

When in the Fibonacci number recurrence f_n+2=f_n+f_n+1 one replaces the "+" with string concatenation one will get the sequence of Fibonacci words. If we start with F₀=a and F₁=b, then the first few elements will be a,b,ab,bab,abbab,bababbab,abbabbababbab,... etc.

If N>1 and n<N then F_n will naturally occur as a substring in F_N:

For example, if n=3 and N=6, Then F₄, by construction, contains a copy of F₃ at its end. F₅, being the concatenation of F₃ and F₄, therefore contains two copies, and F₆ three copies, one from F₄ and two from F₅. We can find these copies at offsets 2,5 and 10:

a
b
ab
bab
-->
abbab
 -->
bababbab
--> -->
abbabbababbab
 -->--> -->

But, we cannot rule out more occurrences, for example, there is one at offset 7 that is not directly explained by the recursion formula:

abbabbababbab
 ***

We'll call such occurrences "strange" as opposed to the "regular" occurrences above.

Task:

Given N>n and offset o your program or function must return one out of three consistent values indicating whether F_n occurs in F_N at offset o and if so which kind of occurrence it is.

Test cases:

N n o answer
------------------------------------------
4 0 0 regular
4 0 1 wrong
4 0 2 wrong
4 0 3 regular
4 0 4 wrong
5 0 0 wrong
5 0 1 regular
5 0 2 wrong
5 0 3 regular
5 0 4 wrong
5 0 5 wrong
5 0 6 regular
5 0 7 wrong
4 1 0 wrong
4 1 1 regular
4 1 2 regular
4 1 3 wrong
4 1 4 regular
5 1 0 regular
5 1 1 wrong
5 1 2 regular
5 1 3 wrong
5 1 4 regular
5 1 5 regular
5 1 6 wrong
5 1 7 regular
1 0 0 wrong
10 2 7 wrong
7 3 0 regular
7 3 7 strange
7 3 9 wrong
7 3 10 regular
7 3 11 wrong
14 7 47 strange
14 7 479 strange
14 7 335 strange
14 7 335 strange
14 7 369 strange
14 7 513 strange
14 7 100 wrong
14 7 200 wrong
14 7 300 wrong
14 7 13 regular
14 7 123 regular
14 7 233 regular
14 7 322 regular

If you need even more test cases here is the Python script that generated the above.

Inspired by this puzzling SE post:

https://puzzling.stackexchange.com/q/122866/71595

Answer*

# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), 30 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)

 1ÝλN¹›i‚»ë«]¹I‚è`IF¦¶Û}Dþ‚sδÅ?

Inputs in the order \$n,N,o\$. Outputs `[1,1]` for regular; `[0,1]` for strange; and `[0,0]` for wrong.

[Try it online](https://tio.run/##AUMAvP9vc2FiaWX//zHDnc67TsK54oC6aeKAmsK7w6vCq13CuUnigJrDqGBJRsKmwrbDm31Ew77igJpzzrTDhT///zMKNgo3) or [verify all test cases](https://tio.run/##S0oszvifnFiiYKeQnJ@SqpdfnJiUmapgY6Pg6u/GZa@k8KhtkoKSfVBMQmjYoZUxMUr/DQ/PPbfbL@JRw67MRw2zDu0@vPrQ6tiISCD78IqYhEPr3A4tO7Tt8Oxal8P7gGLF57YcbrX/r6QX5mLvr1RelJ@XrlBcUpSYl56qUJSaXpqTWKSkXHx4hZKCxuH9mko6XCBrucozMnNA8okpCpl5XCn5XAoK@vkFJfoQ10EpNAfbKKiA1eal/o821jHTMYrlAtOmUNrQAMowh9IWQNoIKAwVMNcxgNIwviWUNoRJGBoCGUDKRMfEHMGyhDGNjU3hTDO4qKmhMYxpaGAAYxohmMYIJpJSIzjTyBjONDYC@coA5GigHgA).

**Explanation:**



 λ # Create a recursive environment,
 # to output the infinite sequence
 1Ý # Starting with a(0)=0 and a(1)=1
 # Where every following a(x) is calculated as:
 # (implicitly push the previous terms a(x-2) and a(x-1))
 N¹›i # If x is larger than first input `n`:
 ‚ # Pair the two previous terms: [a(x-2),a(x-1)]
 » # Join this pair with newline-delimiter
 ë # Else:
 « # Append term a(x-1) to a(x-2) instead
 ] # Close both the if-statement and recursive environment
 ¹I‚ # Push a pair of the first two inputs: [n,N]
 è # (0-based) index those into the infinite list
 ` # Pop and push both separated to the stack
 IF # Loop the third input `o` amount of times:
 ¦ # Remove the first bit
 ¶Û # And also trim a potential leading newline character
 }D # After the loop: duplicate the off-set result
 þ # Remove all newlines from the copy, by only keeping digits
 ‚ # Pair the two together
 δ # Map over this pair:
 s Å? # Check for both whether it starts with the n'th term
 # (after which this pair is output implicitly as result)

If this is an answer to a challenge…

…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one. Explanations of your answer make it more interesting to read and are very much encouraged.
…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.

More generally…

…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).

Draft saved

Draft discarded

Edit Summary*

Cancel

\$\begingroup\$ FYI, I've fixed my code for \$n<2\$ at the cost of +6 bytes. \$\endgroup\$

Arnauld
– Arnauld

2024年09月23日 13:14:11 +00:00
Commented Sep 23, 2024 at 13:14
1

\$\begingroup\$ @Arnauld Thanks for the heads up, but with the way my recursive method is build up, a straight-forward fix seems to be 8 bytes (¹„abD²èu©²ǝSλè«N²Qiu©]³.$Du‚®δÅ?). Can probably be golfed a bit to 6-7, but that would still tie it with my current approach, so I'll just leave it as is. \$\endgroup\$

Kevin Cruijssen
– Kevin Cruijssen

2024年09月23日 13:47:51 +00:00
Commented Sep 23, 2024 at 13:47
\$\begingroup\$ Feels weird to see an IF in 05AB1E... \$\endgroup\$

Neil
– Neil

2024年09月23日 14:29:19 +00:00
Commented Sep 23, 2024 at 14:29

Add a comment |

How to Edit

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

How to Format

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or **bold**
indent code by 4 spaces
backtick escapes `like _so_`
quote by placing > at start of line
to make links (use https whenever possible)

<https://example.com>

[example](https://example.com)

<a href="https://example.com">example</a>
MathJax equations \$\sin^2 \theta\$

formatting help »
answering help »

MathJax help »

How to Tag

A tag is a keyword or label that categorizes your question with other, similar questions. Choose one or more (up to 5) tags that will help answerers to find and interpret your question.

complete the sentence: my question is about...
use tags that describe things or concepts that are essential, not incidental to your question
favor using existing popular tags
read the descriptions that appear below the tag

If your question is primarily about a topic for which you can't find a tag:

combine multiple words into single-words with hyphens (e.g. code-golf), up to a maximum of 35 characters
creating new tags is a privilege; if you can't yet create a tag you need, then post this question without it, then ask the community to create it for you

popular tags »