3
\$\begingroup\$

I solved the Fibonacci Golf problem on checkio.org:

The Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21...

This is not the only interesting integer sequence however; there are many various sequences like the Fibonacci numbers, where each element is calculated using the previous elements. Let's take a look at a few of them. Described below are several integer sequences which you should try to implement:

fibonacci:
f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2)

tribonacci:
f(0)=0, f(1)=1, f(2)=1, f(n)=f(n-1)+f(n-2)+f(n-3)

lucas:
f(0)=2, f(1)=1, f(n)=f(n-1)+f(n-2)

jacobsthal:
f(0)=0, f(1)=1, f(n)=f(n-1)+2*f(n-2)

pell:
f(0)=0, f(1)=1, f(n)=2*f(n-1)+f(n-2)

perrin:
f(0)=3, f(1)=0, f(2)=2, f(n)=f(n-2)+f(n-3)

padovan:
f(0)=0, f(1)=1, f(2)=1, f(n)=f(n-2)+f(n-3)

You are given the name of a sequence and a number "n". You should find the n-th element for that given sequence. In this mission the main goal is to make your code as short as possible. The system will check the length of your compiled code and assign a point value. The shorter your compiled code, the better. Your score for this mission is dynamic and directly related to the length of your code.

For reference, scoring is based on the number of characters used. 1000 bytes is the maximum allowable.

Input: Two arguments. The name of a sequence as a string and a number "n" as a positive integer.

Output: The n-th element of the sequence as an integer.

Who can make this better? My code is some bytes larger than it's supposed to be.

def fibgolf(type, n):
    if type=="fibonacci":
        a,b=0,1
        for i in range(n):
            a,b=b,a+b
        return a
    elif type == "tribonacci":
        a,b,c=0,1,1
        for i in range(n):
            a,b,c=b,c,a+b+c
        return a
    elif type == "lucas":
        a,b=2,1
        for i in range(n):
            a,b=b,a+b
        return a
    elif type == "jacobsthal":
        a,b=0,1
        for i in range(n):
            a,b=b,a*2+b
        return a
    elif type == "pell":
        a,b=0,1
        for i in range(n):
            a,b=b,b*2+a
        return a
    elif type == "perrin":
        a,b,c=3,0,2
        for i in range(n):
            a,b,c=b,c,a+b
        return a
    elif type == "padovan":
        a,b,c =0,1,1
        for i in range(n):
            a,b,c=b,c,a+b
        return a
\$\endgroup\$
3
\$\begingroup\$

The easiest way to simplify this is to come up with a method to represent the various sequences efficiently. For example, the following represents each as a tuple of starting values, and a function that takes one tuple and returns another (the next step):

SEQUENCES = {
    'fibonacci': ((0, 1), lambda a, b: (b, a+b)),
    'tribonacci': ((0, 1, 1), lambda a, b, c: (b, c, a+b+c)),
    ...
}

The function to apply these is then a trivial dictionary lookup and a loop over the number of steps:

def fibgolf(name, n):
    """Calculate the nth value of the named sequence."""
    vals, func = SEQUENCES[name]
    for _ in range(n):
        vals = func(*vals)
    return vals[0]
\$\endgroup\$
  • \$\begingroup\$ Coding is really interesting, what I did in 30 lines weights about 1100 bytes, your code following the examples however can be written in 15 lines but it weights 1500 bytes... You can use the local checker to determine the compiled size locally, github.com/cielavenir/checkio-task-fibonacci-golf/blob/master/… \$\endgroup\$ – Juanvulcano Apr 6 '15 at 18:20
  • \$\begingroup\$ @Juanvulcano you can take out whitespace, factor out some of the repeated lambdas, shorten identifiers, etc.; but Python doesn't really lend itself to byte-counting, we tend to aspire to clear, readable code rather than minimising the number of characters. \$\endgroup\$ – jonrsharpe Apr 6 '15 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.