Reverse-Engineer the N-Bonacci sequence[s]

15

1

EDIT: I will be accepting an answer Monday, 2/15/2016. May the bytes be ever in your favor!

In his "Print the N-Bonacci Sequence" challenge, @DJMcGoathem describes the N-bonacci sequences, wherein the previous N numbers are summed, instead of the traditional 2 of the Fibonacci sequence (said to be the "duonacci sequence"). He then asked to take two inputs, X and N, then output the Xth N-nacci number.

I propose the opposite.
Given a sequence, output which N-nacci sequence it is a subset of. I say "subset of" because:

  • A) these sequences are infinite
  • B) if given the start of the sequence, you could just count the number of leading 1s

In the case that it could belong to multiple N-nacci sequences, chose the lowest one.
In the case that it does not belong to any N-nacci sequence, then your program may do anything other than print something that could be mistaken for output. These behaviors include (but are not limited to): infinite loop, error, crash, delete itself (*cough cough* vigil *cough cough*), or create a black hole (as long as this black hole does not produce anything that could be mistaken for valid output).
For the sake of this challenge, these sequences start with 1. This means any N-nacci sequence starts with N ones. Furthermore, N must be a positive integer. So no -1-nacci, etc.

Test cases:

1,1,1 -> 1
49, 97 -> 7
55, 89, 144 -> 2
1 -> 1
6765 -> 2
12, 23, 45, 89 -> 12
100, 199 -> 100

Cyoce

Posted 2016-01-31T20:07:11.100

Reputation: 2 690

1create a black hole (as long as this black hole does not produce anything that could be mistaken for valid output). My, the spirals of the black hole are converging to the golden ratio! It must be valid output for a duoacci sequence! – Conor O'Brien – 2016-01-31T20:26:44.930

1

@CᴏɴᴏʀO'Bʀɪᴇɴ It may be a beautiful golden ratio, but Do NOT go near the black hole! https://www.youtube.com/watch?v=TTUQyEr-sg0

– Level River St – 2016-01-31T20:41:21.267

1Oh my, this is much harder than I originally thought... – GamrCorps – 2016-02-01T02:16:56.397

@mbomb007 what's the difference between positive integers and natural numbers? – Not that Charles – 2016-02-03T21:25:56.423

@NotthatCharles Positive integers is a clearer way to say it if you're excluding zero, because natural numbers includes zero. – mbomb007 – 2016-02-03T21:51:36.040

1@mbomb007 ah. I thought 1 was the first natural number. I must have been thinking of counting numbers – Not that Charles – 2016-02-03T22:26:42.583

@NotthatCharles It's actually somewhat ambiguous, but I include zero. See wikipedia.

– mbomb007 – 2016-02-03T22:33:01.660

Answers

7

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
    }
}

Not that Charles

Posted 2016-01-31T20:07:11.100

Reputation: 1 905

How does x=[1]*(s+z=a.size) work exactly? – Cyoce – 2016-02-13T02:35:49.407

@Cyoce If n == 1, then we will never increment, so we need an array of 1's however long the input is. If n > 1, then we need at least n 1's for the sequence. So s+a.size covers n == 1 for any length of a, and it covers the beginning of any other sequence so we can just start adding s digits off the batt. Does that make sense? – Not that Charles – 2016-02-15T04:51:53.737

@Cyoce and if you're asking a different question, in Ruby, [1]*number gives an array of 1's with length number. So x=[1]*(s+z=a.size) assigns a.size to z, then assigns to x an array of 1's length s+z. – Not that Charles – 2016-02-15T04:52:45.977

3

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.

James

Posted 2016-01-31T20:07:11.100

Reputation: 54 537

try the same suggestions I gave to him: change f.append for f+= – Cyoce – 2016-02-02T04:33:38.767

@Cyoce oh duh. I'm can't believe I missed something that basic. fp – James – 2016-02-02T04:58:41.867

Is the trailing ; necessary? – Cyoce – 2016-04-29T00:54:27.403

1

Lua, 324 323 Bytes

When I see other submission, I feel like there's something wrong with my code... But then, I remember that's Lua, and there's isn't all these fancy functionnalities :'(

It was a lot of fun, took me some time actually.

Edit: Saved 1 byte with a simple trick: using a ::label::+goto label instead a infinite loop done with while''.

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

Ungolfed and Explanations

Lua has no way to define a set, subset, or even check if an array/table contains a value without using its index/key. That's why i've decided to remove elements from the array I take as a parameter. that's how I keep record of which elements has already been computed, and if it matched.

  function f(l)
  c=2
  y,z=table.remove,os.exit           -- Create pointers on table.remove and os.exit
                                     -- saves a total of 9 bytes
  while(l[1]<2)                      -- loop used to remove leading 1
  do 
    y(l,1)
    if(#l<1)                         -- we also check if it was a 1-only array
    then 
      print(1)                       -- if so, we print 1 and exit
      z()
    end 
  end

  ::q::                              -- label q, start of the infinite loop
    a={}for i=1,c do a[i]=1 end      -- fill an array with c 1s
    b={}for i=1,#l do b[i]=l[i]end   -- copy the sequence array
    while(a[#a]<b[1])                -- while max(a)<min(b)
    do
      x=0 for i=(#a-c+1>0            -- iterate from index a.length-c to
                    and #a-c+1       -- to a.length
                    or 1),#a 
      do 
        x=x+a[i]                     -- summing a's elements
      end
      a[#a+1]=x                      -- append x to a
      if a[#a]==b[1]then y(b,1)end   -- if x is equal ot a member of the sequence
                                     -- remove it
      if #b<1 then print(c)z()end    -- if b is empty, it means the subset is in a
                                     -- we print c and exit
    end                              -- else we loop again
    c=c+1                            -- with c+1
  goto q                             -- return to the start of this block
end

You can try Lua online, and you can copy/paste the following code sample to run some tests. As this function exit when it founds the answer (infinite loop otherwise), you will have to change the index of test[] used (don't forget lua is 1-indexed :)).

function f(l)c=2 y,z=table.remove,os.exit while(l[1]<2)do y(l,1)if(#l<1)then print(1)z()end end ::q:: a={}for i=1,c do a[i]=1 end b={}for i=1,#l do b[i]=l[i]end while(a[#a]<b[1])do x=0 for i=(#a-c+1>0 and #a-c+1 or 1),#a do x=x+a[i]end a[#a+1]=x if a[#a]==b[1]then y(b,1)end if #b<1 then print(c)z()end end c=c+1 goto q end

test={{1,1,1},
{49, 97},
{55, 89, 144},
{1},
{6765},
{12, 23, 45, 89},
{100, 199}}

print(f(test[1]))

Katenkyo

Posted 2016-01-31T20:07:11.100

Reputation: 2 857