Monday Mini-Golf #1: Reverse Fibonacci Solver

Question

Monday Mini-Golf: A series of short code-golf challenges, posted (hopefully!) every Monday.

A Fibonacci-like sequence is obtained using the same method as the famous Fibonacci sequence; that is, each number F(n) is found by adding the previous two numbers in the sequence (F(n) = F(n-1) + F(n-2)), or by subtracting the next two numbers (F(n) = F(n+2) - F(n+1)). The main difference is that these sequences can start with any two numbers. The zero-indexing of these sequences is disputable, but for now, we're going to use this rule:

• The 0th number in a Fibonacci-like sequence is the last number which is smaller than the preceding number.

As an example, the Fibonacci sequence could be written as 1, 0, 1, 1, 2, 3, 5..., so the 0th number in the sequence is the lone 0.

Challenge

The goal of the challenge is to write a program or function that takes in three integers, in any format:

• A and B, the two numbers with which to start generating a sequence.
• N, the length of the resulting sequence to output.

And outputs the first N numbers of the sequence, starting at the 0th.

Details

• A, B, and N may be taken in any order and format, as long as they are visibly separated. If you use a different order/format, please specify what it is.
• You may assume that A, B, and N are always positive integers.
• You may assume that N is no more than 100, and the resulting sequence will not contain x >= 2^31.
• If A is larger than B, then B is the 0th number in the sequence.
• The output must be separated by spaces, commas, and/or newlines.
• A trailing space or newline is allowed, but not a trailing comma.

Test-cases

Example 1:

8 13 10

Working backward from 8 13 until we find a number larger than the previous, we get 13 8 5 3 2 1 1 0 1. Thus, 0 is the 0th number in this sequence. Working forward from this, we print out 0 and the next 9 members:

0 1 1 2 3 5 8 13 21 34

Example 2:

23 37 5

Again working backward to find the 0th number, we find 37 23 14 9 5 4 1 3. The 0th number this time is 1, so we print it out, along with the next 4 members:

1 4 5 9 14

Example 3:

4 3 8

With this one, we don't have to work backward to find the 0th number, because 3 is smaller than 4:

3 7 10 17 27 44 71 115

Example 4:

29 47 11

Result:

1 3 4 7 11 18 29 47 76 123 199

Scoring

This is code-golf, so shortest valid code in bytes wins. Tiebreaker goes to earlier posted submission. The winner will be chosen next Monday, Sep 28. Good luck!

Edit: Congrats to your winner, @Jakube, using Pyth for an amazing 23 bytes!

Answer 1

Pyth, 23 bytes

AQWgHGA,-HGG)VvwHA,H+GH

Try it online: Demonstration or Test Suite

Quite unusual style of Pyth programming. Sometimes functional programming has its downsides.

Explanation:

AQWgHGA,-HGG)VvwHA,H+GH  Q = input list of the two starting numbers
AQ                       G, H = Q (unpacking Q)
  WgHG                   while H >= G:
      A,-HGG                G, H = [H - G, G]
            )            end while
              vw         read a number from input
             V           for N in range(^):
                H           print H
                 A,H+GH     G, H = [H, G + H]

Answer 2

Retina, 65 54 bytes

+`(1*),\1(1*)
$2,$1
+`(1*)(,1*);1\B
$1$2$2$1;
^1*,|;1
<empty>

Here, <empty> represents an empty trailing line. Run the code as a single file with the -s flag.

The input format is

A,B;N

where the numbers are represented in unary. The output is a comma-separated list, also in unary. For instance:

8 13 10

would be

11111111,1111111111111;1111111111

and yield

,1,1,11,111,11111,11111111,1111111111111,111111111111111111111,1111111111111111111111111111111111

Explanation

+`(1*),\1(1*)
$2,$1

First, we reduce A and B to the 0th and -1st element. The + tells Retina to keep repeating this regex substitution until either the regex stops matching or the substitution doesn't modify the string. The regex captures A into group 1 with (1*), and then makes sure that B is at least as big as A while capturing B-A with \1(1*) into group 2. This ensures that this loop terminates once A>B.

The substitution simply turns A,B into B-A,A by setting the match to $2,$1.

+`(1*)(,1*);1\B
$1$2$2$1;

Now we've already got the first number of the required output in the string (as well as the one before it, which we'll need to get rid off later). This substitution now adds another number as the sum of the last two numbers while taking a 1 from N. Because we already have one number we want this to happen only N-1. We do this by ensuring with \B that there is still at least ;11 at the end of the string. If we call the last two values of the sequence C and D, then the regex captures C into group 1 and ,D into group two. We write those back with $1$2. Then we also write $2$1 which translates to ,D+C. Note that we don't write back the single 1 we matched in N, thereby decrementing it.

^1*,|;1
<empty>

Finally, we need to get rid of -1st element of the sequence, as well the leftover ;1 from N, which we simply do by matching either of those and replacing it with the empty string.

Answer 3

Python 2, 93 87 67 61 60 bytes

i,j,l=input()
while j/i:i,j=j-i,i
exec"i,j=j,i+j;print i;"*l

Gets the input (as a literal python list [8,10,13])

Works out the 0th term

Then prints out the sequence of additions until the length has been reached

Answer 4

CJam, 26 23 bytes

Thanks to Dennis for saving 3 bytes.

q~{_@\-_g)}g\@{_@+_p}*t

Takes input in order N B A (separated by any kind of white space). Prints the result as a newline-separated list and terminates with an error.

Test it here.

Explanation

This goes one step further when finding the 0th element. That is, it terminates once one of the values is negative.

q~      e# Read and evaluate input, pushing N, B and A on the stack.
{       e# do while...
  _@\-  e#   B, A = A, B-A
  _W>   e#   Check if A is still non-negative.
}g
\@      e# Reorder N B A into A B N.
{       e# Run the following N times...
  _@+   e#   A, B = B, A+B
  _p    e#   Print B.
}*
t       e# The last A, B are still on the stack. We remove them by trying to
        e# execute a ternary operator: it pops the first two values but then
        e# terminates the program with an error, because there is no third value.

Answer 5

Labyrinth, 58 54 49 46 44 bytes

Thanks to Sp3000 for suggesting the use of bitwise negation, which saved two bytes.

??#"{=
  ;  -
@"~~:}
~""
?
"}}:=
(   +
{{\!:

Input format is B A N. The output is a newline separated list.

Explanation

(Slightly outdated. The basic idea is still the same, but the layout of the code is different now.)

This uses the same idea as my CJam answer (so credits still go to Dennis): when backtracking the sequence we don't stop until we get a negative value (which leaves us with the -1st and -2nd element of the sequence). Then, we start adding them before printing the first value.

This uses a couple of nifty Labyrinth golfing tricks. Let's go through the code in sections:

?"
}

The IP starts on the ? going right (which reads A). On the " (a no-op) it hits a dead end, so it turns around, executing the ? again (reading B). Lastly, } moves B over to the auxiliary stack. The dead end saves a byte over the naive

?
?
}

Now the loop which finds the beginning of the sequence:

)(:{
"  -
" "`?...
=}""

The )( (increment-decrement) is a no-op, but it's necessary to ensure that the top of the stack is positive on the junction (such that the IP turns east). : duplicates A, { moves B back to the main stack, - computes A-B. What we really want is B-A though, so ` negates the value.

This is now a four-way junction. For negative results, the IP takes a left-turn towards the ?, reading N and moving to the next part of the program. If the result is zero, the IP keeps moving south, takes a turn in the corner, and remains in the loop. If the result is positive, the IP takes a right-turn (west), turns in the corner, and takes another right-turn (west again) so it also remains in the loop. I think this might become a common pattern, to distinguish negative from non-negative (or positive from non-positive) values:

                v
                "
               """>negative
non-negative <"""

At least I haven't been able to find a more compact/useful layout for this case yet.

Anyway, while A is non-negative, the loop continue, } moves A to the auxiliary stack and = swaps A and B.

Once A is negative, ? reads N and we move into the second loop:

 }:=+:
 }   !
?"({{\

We know that N is positive, so we can rely on the IP taking a left-turn (north). The loop body is now simply:

}}:=+:!\{{(

In words: moves both N and A onto the auxiliary stack. Duplicate B, swap the copy with A and add A to the other copy of B. Duplicate it again to print the current value of B. Print a newline. Move B and N back to the main stack and decrement N.

While N is positive, the IP will take a right-turn (north) continuing the loop. Once N reaches zero, the code terminates in a rather fancy way:

The IP keeps moving straight ahead (west). The ? tries to read another integer, but we've already reached EOF, so it actually pushes 0 instead. ` tries negating that, but that's still zero. So the IP still moves west, takes a turn in the corner, and then keeps moving downwards onto the @ which terminates the program.

I wonder if I could place the @ in an even cheaper position (it currently costs 3 whitespace characters) by turning the three " around the ` into compound no-ops (like )(), but I haven't been able to make that work yet.

Answer 6

C, 105 102 100 bytes

main(a,b,n,t){for(scanf("%d%d%d",&a,&b,&n);t=b-a,t>=0;a=t)b=a;for(;n--;b=t)t=a+b,printf("%d ",a=b);}

Thanks to @C0deH4cker for golfing off 2 bytes!

Try it online on Ideone.

Answer 7

Matlab / Octave, 115 125 bytes

function x=f(x,n)
while x(2)>=x(1)
x=[abs(x(1)-x(2)) x];end
x=x([2 1]);for k=1:n-1
x=[x(1)+x(2) x];end
x=x(n:-1:1);

The function should be called as f([8 13],10).

Example (Matlab):

>> f([8 13],10)
ans =
     0     1     1     2     3     5     8    13    21    34

Or try it online (Octave).

Answer 8

Haskell, 67 65 56 bytes

a#b|a>b=b:scanl(+)(a+b)(a#b)|1>0=(b-a)#a
n%a=take n.(a#)

Thanks to @nimi for suggestions

This defines a ternary infix function %, which is invoked in the format (n%a)b, for example:

> (10%8)13
[0,1,1,2,3,5,8,13,21,34]

Explanation

The binary infix function #, defined on the first line, takes in two integers a and b and returns the infinite Fibonacci-like sequence where a and b occur as consecutive elements.

a#b                                       -- Define a#b:
   |a>b=                                  -- if a>b, then a#b is
        b:                                -- the sequence that starts with b and
          scanl(+)     (a#b)              -- continues with the sums of prefixes of a#b
                  (a+b)                   -- plus the additional term a+b;
                            |1>0=(b-a)#a  -- otherwise, it's (b-a)#a.

The function % simply takes the first n elements of a#b.

Answer 9

><>, 33 31+1 for -v = 32 bytes

&:{:@(?v:}-$&
-1;!?:&<$+{oan::$&

Input must be pushed on stack using -v since parsing decimal numbers is non-trivial in ><>.

Explanation :

I will represent the stack after each (group of) operation. It starts with [F(n), F(n+1), N]

The first lines goes down the serie to its 0th term :

& removes N from the stack to put it into a register. [F(n), F(n+1)]
:{:@ move the stack and duplicate items to get [F(n+1), F(n), F(n+1), F(n)]
(?v compares the two top items of the stack and branch to the second line if F(n+1) < F(n) [F(n+1), F(n)]
:} move the stack and duplicate its top to get [F(n), F(n+1), F(n)]
- substracts the two top items and put the result on top of the stack [F(n), F(n+1) - F(n)]
$ switchs the top two values of the stack. [F(n+1) - F(n), F(n)]
& retrieve the value from the register. iteration complete, since [F(n+1) - F(n), F(n), N] can also be read as [F(n-1), F(n), N]

The second line goes up the serie until it has printed N terms :

< changes the code pointer direction to the left [F(0), F(-1)]
& retrieves the stored value back from the stack [F(0), F(-1), N]
:?!; copies N to compare it to 0, stops if it is [F(0), F(-1), N]
1- decreases it [F(0), F(-1), N-1]
& stores it back [F(0), F(-1)]
$:: makes the stack [F(-1), F(0), F(0), F(0)]
n{ prints the top of the stack then left shifts it [F(0), F(0), F(-1)]
ao displays a line feed (ascii character 0x0a) [F(0), F(0), F(-1)]
+ adds the two top values [F(0), F(-1) + F(0)]
$ switch the two top values. iteration complete since [F(-1) + F(0), F(0)] which can be read as [F(1), F(0)]

Answer 10

Java, 113 78 76 bytes

Credit goes to ETHproduction for providing the algorithm I use in this answer.

(a,b,n)->{for(;a<=b;b-=a)a=b-a;for(;n-->0;b+=a,a=b-a)System.out.println(b);}

Try here.

Explanation:

(a,b,n)->{
    for (;a<=b;b=b-a)a=b-a;  //Compute previous terms while a <= b
    for (;n-->0;b=a+b,a=b-a) //Compute and print next terms while n > 0
    System.out.println(b);   //Print term
}

Original approach, 113 93 bytes

Looks more golfy ;)

String a(int a,int b,int n){return n<0?a+" "+a(b,a+b,n+1):n>0?a>b?a(b,a+b,-n):a(b-a,a,n):"";}

Try it out here.

Explanation:

String a(int a, int b, int n){
    return 
    n < 0 ?                           //If n < 0
        a + " " + a(b, a + b, n + 1)  //Return a + next terms and increment n.
    :                                 //Else
        n > 0 ?                       //If n > 0
            a > b ?                   //If a > b
                a(b, a + b, -n)       //Negate n and return terms.
            :                         //If a <= b
                a(b - a, a, n)        //Generate previous term.
        :                             //If n == 0
            ""                        //Return nothing.
    ;
}

Answer 11

Javascript (ES6), 83 73 63 bytes

This might have been golfed to the max. We'll see.

(a,b,n)=>{while(a<=b)b-=a=b-a;for(;n--;console.log(a=b-a))b+=a}

Ungolfed:

function f(a,b,n) {
  // repeat until we find the 0th item...
  while (a <= b) {  // if a = 5, b = 8:
    a = b - a;      // a = (8 - 5) = 3
    b = b - a;      // b = (8 - 3) = 5
  }
  // repeat n times...
  while (n-- > 0) { // if a = 5, b = 8:
    b += a;         // b = (8 + 5) = 13
    a = b - a;      // a = (13 - 5) = 8
    console.log(a); // print out each item
  }
}

Answer 12

Mathematica 112

Will golf it eventually

z[a_, b_, n_] := (
  f[0] := Min[a, b];
  f[1] := Max[a, b];
  f[x_] := f[x - 1] + f[x - 2];
  f /@ Range[n]
  )

Answer 13

CJam, 40 bytes

l~:A;{_@_@)<}{_@\-\}w\{A(:A0>}{_p_@+}w\;

Baby steps. This is my first CJam program ever, so I'm proud it works at all.

It takes input in the same form as in the examples.

I've now seen I could reduce it to 33 bytes using the { ... }* construct.

l~:A;{_@_@)<}{_@-z\}w\A{_p_@+}*;;

And I could even reduce it by one more by using the ternary operator to clean the stack and produce an error.

Answer 14

Ruby, 141 bytes

def u a,b,n,z=""
n<1 ? z.chop : u(b,a+b,n-1,z+"#{a} ")
end 
def d a,b,z=0
a.abs>b ? z : d(b-a,a,[a,b]) 
end 
def f a,b,n
x,y=d a,b 
u x,y,n
end 

Execution

f function produces the desired output, argument names match the variable names from the question

f(8,13,10) # returns => "0 1 1 2 3 5 8 13 21 34"

Nothing clever:

• u (up) function computes n elements in the fibonacci sequence starting with a,b using recursion
• d (down) function finds the 0th and 1st element given two end elements using recursion
• f (fibonacci) function puts the two together

Answer 15

Mathematica, 59 bytes

If[#>#2,LinearRecurrence[{1,1},#2+{0,#},#3],#0[#2-#,#,#3]]&

Answer 16

Ruby, 81 75 73

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{b=c+a;c,a=a,b;p b}

Shortened by 6 Bytes when replacing for-loop with range.map

a,b,n=23,37,5;while(c=b-a)<a;b,a=a,c;end;p a;[*2..n].map{p b=c+a;c,a=a,b}

Saved another 2 bytes by moving print statement

Answer 17

Jelly, 14 bytes

Ḋ;_/Ɗ>/¿+⁹С/Ṗ

Try it online!

Answer 18

Common Lisp, 91 bytes

(lambda(a b n)(do((x a(- y x))(y b x))((> x y)(dotimes(k n)(print y)(psetf y(+ y x)x y)))))

Try it online!

Answer 19

Pyke, 24 bytes

DA/IDA-],X_r)QVDsRe
R]);

Try it here!