Find the garden of Eden
The Fibonacci sequence starts with [1,1] and then continues to the right with each number being the sum of the previous number. For example the first 10 terms are [1,1,2,3,5,8,13,21,34,55].
We can also extend the sequence to the left, trying to keep the rules consistent. In order for 1 to follow 1, there must have been a proceeding 0. In order to extend to the left we add the difference of the first two numbers (second number minus first). This gets us everything to the left of the start too
...,13,-8,5,-3,2,-1,1,0,1,1,2,3,5,8,13,21,34,55,...
A common idea is to take the rules of the Fibonacci sequence but start with a different seed. For example,
- if we start with
[45,83]:...,55,-24,31,7,38,45,83,128,211,339,550,889,... - if we start with
[1,2,1]...,5,-3,2,-1,1,0,1,1,2,1,3,4,7,11,18,29,47,...
We will call a seed list like this the "Garden of Eden" for the particular sequence.
Our task today will be to take a portion of a sequence and work out where the Garden of Eden is. That is we will find the smallest list that could seed the larger sequence.
This can be done by taking the input following the following algorithm:
- If the last entry is the sum of the two entries before it, remove it and recurse.
- If the third entry is the sum of the two entries before it, remove the first entry and recurse.
- If neither of these holds return the input list.
Sometimes the answer is ambiguous. This happens exactly when there is a Garden of Eden of size 2. For example if the input is [1,1,2] then both [1,1] and [1,2] generate the larger sequence. In this case both are acceptable outputs.
- Input A finite list of integers of length at least 2.
- Output A minimal Garden of Eden for the sequence generated by the input.
This is code-golf. The goal is to minimize the size of your source code as measured in bytes.
Test cases
[2,1,3,1,4,5,9,14] -> [1,3,1]
[17,-13,4,-9,6,-3,3,0,3,3,6,9] -> [4,-9,6]
[1,1,3,4,7,11,18,29,47,75] -> [1,1,3,4,7,11,18,29,47,75]
[-1,1,0,1,1,-1,1,0,1,1] -> [1,1,-1,1]
Ambiguous cases:
[1,1,2,3,5,8,13,21,34,55] -> [5,8]
[-1,3,2,5,7,12,19,31,50,81] -> [3,2]
[34,55] -> [0,1]

0 comment threads