# Monday Mini-Golf #1: Reverse Fibonacci Solver

Monday Mini-Golf: A series of short 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 , 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!

• I've removed the [monday-mini-golf] tag you created. I don't think we should create tags for more or less arbitrary groups of challenges. The tag doesn't really tell you anything about the challenge, and if you want to find all of these, one could just search for the phrase in search bar. Alternatively, if you include a link to this first challenge in every future instalment, they will all be linked under "Linked questions" in the sidebar. Sep 21, 2015 at 20:48
• @MartinBüttner OK, thanks; I'll keep that in mind. Sep 21, 2015 at 20:49
• Can I take the input how I want it (A python list literal [8, 13, 10])?
– Blue
Sep 21, 2015 at 20:57
• The challenge currently says write a program. Does that mean that functions are not allowed? (CC @LuisMendo) Sep 21, 2015 at 22:11
• @Dennis Sorry, slipped my mind. Functions are also allowed. Thanks for pointing that out! Sep 21, 2015 at 23:59

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


# 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.

# Python 2, 93876761 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

• Nice method. For the index-less loop for _ in*l:, it's a bit shorter to do exec"stuff;"*l
– xnor
Sep 22, 2015 at 2:54
• @xnor: It appears significantly longer to me. Sep 22, 2015 at 18:42
• Compare for _ in*l:stuff to exec"stuff;"*l. @xnor didn't put in the stuff part in the for loop. Or for _ in*l: to exec";"*l
– Blue
Sep 22, 2015 at 18:45
• You can replace j>=i with j/i. Just found that out! (Because You may assume that A, B, and N are always positive integers) Sep 22, 2015 at 21:40

# 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.

• q~{_@\-_g)}g\@{_@+_p}*t (N B A) saves three bytes. Sep 22, 2015 at 5:14
• While I was trying to solve this in CJam myself I had trouble with the input from example 1. Now I see that this solution doesn't give the expected output either. Where is the flaw here? I think instead of checking for B>A it has to check for B not smaller than A or something, but I can't figure out how to do that in CJam. EDIT: Dennis' solution prints the correct output. Sep 22, 2015 at 15:51
• Well, I solved it in my solution. Sep 22, 2015 at 16:06
• @Cabbie407 You're correct, I should have used <! instead of >. Sep 22, 2015 at 16:18
• Ah, okay. I wondered where to put that ! in this. I simply added one to make it work ;) Sep 22, 2015 at 16:35

# Labyrinth, 58544946 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.

# C, 105102 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.

# 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

• According to the rules, you can modify the input, so f([a b],n) should be allowed. Sep 21, 2015 at 22:08
• @beaker Thanks! I was going to do that... but then I read the rule "The input and output may be separated by spaces, commas, or newlines" and got confused. I'll ask for clarification Sep 21, 2015 at 22:09
• Yeah, I don't know if x=f(x,n) in the function header counts... Sep 21, 2015 at 22:10
• @AlexA. I was responding to Luis' comment about the rule "The input and output may be separated by spaces, commas, or newlines" and the OP's "A, B, and N may be taken in any order and format, as long as they are visibly separated." Because A and B would no longer visibly separated in the function header, I was questioning whether having only 2 function arguments would be permissible. Sep 22, 2015 at 14:50

# 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.

• You can create the fibonacci sequence with let f=a:scanl(+)(a+b)f in f (-> full #: a#b|a>b=let f=a:scanl(+)(a+b)f in f|1>0=(b-a)#a and save two bytes.
– nimi
Sep 22, 2015 at 21:05
• @nimi Thanks; I ran with your idea and saved a total of 9 bytes. Sep 22, 2015 at 21:25

# ><>, 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)]

• You should be able to reduce your byte count by 2 by changing 00. on the first line to &. Theoretically, ! should work but I think that ><> pads the width of lines to match the width of the longest one (edit: which is why I figure you had 00. in the first place).
– cole
Sep 27, 2015 at 2:14
• Yeah, I'm not too sure about that, I've saw people here use ! In a way that ignored spaces. I know the online interpreter at fishlanguage.com doesn't work that way, but maybe the python interpreter does. & does the trick nicely anyway, thanks ! Sep 27, 2015 at 11:31
• The online interpreter works with ! or ? (at the end of the line) if it's on the longest line. You can try it with something like 1n! and it'll error, but if there's a line below it with something longer than it, like lorumipsum, it won't.
– cole
Sep 27, 2015 at 17:55
• "The output must be separated by spaces, commas, and/or newlines." Sorry, but you'll have to use the other version. Good job, though! Sep 27, 2015 at 19:51
• Fixed it, I used \n instead of spaces to save 2 bytes Sep 28, 2015 at 8:25

# Java, 11378 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.
;
}

• What? Java is shorter than JS?!? There's gotta be something I'm doing wrong.... Sep 22, 2015 at 23:07
• @ETHproductions I actually copied your algorithm (and then golfed it) :P Sep 22, 2015 at 23:23
• That's fine with me, I took some of your improvements ;) I forgot printing each item separately was valid in JS. Sep 22, 2015 at 23:37
• You can shorten b=b-a to b-=a, and the same with a=b+a. It will save 2 bytes Sep 23, 2015 at 12:02
• +1 for making a verbose language submission so short. Usually Java submissions are the longest! Sep 23, 2015 at 22:38

# Javascript (ES6), 8373 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
}
}


## Mathematica 112

Will golf it eventually

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


# 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.

# 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

# Mathematica, 59 bytes

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


# Ruby, 8175 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

# Jelly, 14 bytes

Ḋ;_/Ɗ>/¿+⁹Ð¡/Ṗ


Try it online!

# 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!

## Pyke, 24 bytes

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


Try it here!