Image

Communities

Writing
Writing
Codidact Meta
Codidact Meta
The Great Outdoors
The Great Outdoors
Photography & Video
Photography & Video
Scientific Speculation
Scientific Speculation
Cooking
Cooking
Electrical Engineering
Electrical Engineering
Judaism
Judaism
Languages & Linguistics
Languages & Linguistics
Software Development
Software Development
Mathematics
Mathematics
Christianity
Christianity
Code Golf
Code Golf
Music
Music
Physics
Physics
Linux Systems
Linux Systems
Power Users
Power Users
Tabletop RPGs
Tabletop RPGs
Community Proposals
Community Proposals
tag:snake search within a tag
answers:0 unanswered questions
user:xxxx search by author id
score:0.5 posts with 0.5+ score
"snake oil" exact phrase
votes:4 posts with 4+ votes
created:<1w created < 1 week ago
post_type:xxxx type of post
Search help
Notifications
Mark all as read See all your notifications »
Challenges

Find the garden of Eden

+2
−0

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]
History

0 comment threads

Sign up to answer this question »