April 01, 2016

Palindromic Fibonacci in python

In the process of being interviewed for a job, I had to write a simple software. It was a nice exercise, and I liked it.

The problem was this:

A contiguous sequence of unsigned integers is considered a "Fibonacci palindrome" if two conditions hold:

    1. the sequence is the same whether read backward or forward.
    2. either the sequence has fewer than three elements, or every contiguous three-element sequence {a, b, c} in it satisfies at least one of these conditions: $a==c, a+b==c, or a==b+c$.

Write a python function that takes as input a non-empty sequence of unsigned integers and efficiently finds the longest Fibonacci palindrome in that sequence. If there are multiple Fibonacci palindromes of the largest length, finding any one of them is sufficient.

Please use the following prototype:

def find_fibonacci_palindrome(sequence)

For the given sequence of numbers (list) the return should be
(start_index, length), where start_index is the index at which the
largest Fibonacci Palindrome starts and length its length.




I liked it because I had the opportunity to write 3 different version of the same function, using 3 different coding styles.
  • Imperative style (C-like solution of the problem)
  • Functional style (Haskell-like)
  • Recursive style 
I have published my solution on this page on GitHub, along with 5 pages of $\LaTeX$ documentation and an extensive (and thought) testset.

Imho, the imperative version was easyer to write, because was easy to decompose the problem in smaller blocks. The recursive version was the messiest and looking through the recursive tree of calls, I think it might be optimized further. The functional version was the one which gave me feeling of "I'm sure that this function does the thing I want" as soon as I finished to write it.


gg