Reverse-Engineer the N-Bonacci sequence[s]
Ruby, 94
I'm quite surprised how far I've been able to golf this within the same algorithm! I started with over 200!
->a{1.step.find{|s|x=[1]*(s+z=a.size)
x<<x[-s,s].inject(:+)while x.max<a.max&&s>1
x[-z,z]==a}}
Ungolfed:
l=->a{
# ooh! a built-in infinite incrementer!
1.step.find{|s|
# if n == 1, z is important, otherwise s.
x=[1]*(s+z=a.size)
## add the next nacci number until we hit or overshot max.
## if s == 1, we don't increment, so don't bother
x<<x[-s,s].inject(:+)while x.max<g&&s>1
# eval to true if there's a match, false if not
x[-z,z]==a
}
}
APL (Dyalog Unicode), 46 bytes
{∧/0<⍵:⊃⊃⍸A⍷↑{⍵((+/↑),⊢)⍣{</+/¨A⍵}⍵⍴1}¨⍳⊃A←⌽⍵}
Try it online!
Anonymous prefix function, taking a vector of integers.
How?
∧/0<⍵: ⍝ If the given sequence contains any non-positive integers, then return nothing. Otherwise...
A←⌽⍵ ⍝ Set A to be the reverse of the given sequence
{...}¨⍳⊃ ⍝ For each n in 1 to last element of given sequence, we generate the n-bonacci sequence in reverse order:
⍵⍴1 ⍝ Initialize a vector of n 1s (first n terms of the n-bonacci sequence)
⍣ ⍝ Do:
⍵((+/↑),⊢) ⍝ Prepend the sum of the most-recent (first) n elements of the vector to the rest of the vector
⍝ While
{</+/¨A⍵} ⍝ the sum of the n-bonacci sequence generated so far is less than the sum of A
⍝ (this doesn't terminate prematurely because:
⍝ For n=1, this produces k+2 1s if A consists of k 1s
⍝ Otherwise, worst-case is that A has 1 element
⍝ For n=2, F_0+F_1+F_2 ... + F_{k-2} = F_k (identity)
⍝ F_0 + ... F_{k-1} > F_k, and APL terminates the ⍣-loop in the next step,
⍝ after F_k generated
⍝ For n>2, F_0+F_1+F_2 ... + F_{k-2} < F_k, so an excess of terms are generated
⍝ )
↑ ⍝ Mix to form a matrix, where the n-th row is the n-bonacci sequence
⍸A⍷ ⍝ Find the (row, column) positions of A in the matrix
⊃⊃ ⍝ Take the row of the first one (which would have minimum n)
Python 2, 176 bytes
def r(n,x):i,f=n,[1]*n;exec"f+=sum(f[i-n:]),;i+=1;"*(x-n);return f
l=input()
m=max(l)+len(l)
for i in range(1,m):
if any(l==r(i,m)[b:b+len(l)]for b in range(m)):print i;break;
Note that this requires input in this format:
[1, 1, 2, 3...]
rather than
1, 1, 2, 3...
Fairly straightforward solution, just to get things rolling. I'll work more on golfing it down once somebody else answers. This uses a slightly modified version of the N-Bonnaci generator from @Data's answer, so props to him. Then for each N-Bonnaci in range of the input, checks if the input is a subsequence of it.