Montag Minigolf Nr. 1: Reverse Fibonacci Solver

28

Montag Minigolf: Eine Reihe von kurzen Herausforderungen, die (hoffentlich!) Jeden Montag veröffentlicht werden.

Eine Fibonacci-ähnliche Sequenz wird unter Verwendung der gleichen Methode wie die berühmte Fibonacci-Sequenz erhalten ; Das heißt, jede Zahl F (n) wird durch Addition der vorherigen beiden Zahlen in der Folge ( F (n) = F (n-1) + F (n-2) ) oder durch Subtrahieren der nächsten beiden Zahlen ( F) gefunden (n) = F (n + 2) - F (n + 1) ). Der Hauptunterschied besteht darin, dass diese Sequenzen mit zwei beliebigen Zahlen beginnen können. Die Null-Indizierung dieser Sequenzen ist umstritten, aber im Moment werden wir diese Regel anwenden:

  • Die 0. Ziffer in einer Fibonacci-ähnlichen Folge ist die letzte Ziffer, die kleiner ist als die vorherige Ziffer.

Als Beispiel könnte die Fibonacci-Sequenz so geschrieben werden 1, 0, 1, 1, 2, 3, 5..., dass die 0-te Zahl in der Sequenz die einzige ist 0.

Herausforderung

Das Ziel der Herausforderung besteht darin, ein Programm oder eine Funktion zu schreiben, die drei ganze Zahlen in einem beliebigen Format enthält:

  • A und B sind die beiden Zahlen, mit denen eine Sequenz generiert werden soll.
  • N ist die Länge der resultierenden Sequenz, die ausgegeben werden soll.

Und gibt die ersten N Zahlen der Sequenz aus, beginnend mit der 0.

Einzelheiten

  • A , B und N können in beliebiger Reihenfolge und in beliebigem Format angegeben werden, sofern sie sichtbar voneinander getrennt sind. Wenn Sie eine andere Bestellung / ein anderes Format verwenden, geben Sie bitte an, um was es sich handelt.
  • Sie können annehmen, dass A , B und N immer positive ganze Zahlen sind.
  • Sie können davon ausgehen, dass N nicht mehr als 100 ist und die resultierende Sequenz nicht enthalten wirdx >= 2^31 .
  • Wenn A größer als B ist , ist B die 0. Zahl in der Folge.
  • Die Ausgabe muss durch Leerzeichen, Kommas und / oder Zeilenumbrüche getrennt sein.
  • Ein nachgestelltes Leerzeichen oder eine neue Zeile ist zulässig, jedoch kein nachgestelltes Komma.

Testfälle

Beispiel 1:

8 13 10

Wenn 8 13wir rückwärts arbeiten, bis wir eine größere Zahl als die vorherige finden, erhalten wir 13 8 5 3 2 1 1 0 1. Somit 0ist die 0. Nummer in dieser Reihenfolge. Darauf aufbauend drucken wir aus 0und die nächsten 9 Mitglieder:

0 1 1 2 3 5 8 13 21 34

Beispiel 2:

23 37 5

Wieder rückwärts arbeiten, um die 0. Zahl zu finden, finden wir 37 23 14 9 5 4 1 3. Die 0. Zahl ist diesmal 1, also drucken wir sie zusammen mit den nächsten 4 Mitgliedern aus:

1 4 5 9 14

Beispiel 3:

4 3 8

Mit diesem müssen wir nicht rückwärts arbeiten, um die 0. Zahl zu finden, da sie 3kleiner ist als 4:

3 7 10 17 27 44 71 115

Beispiel 4:

29 47 11

Ergebnis:

1 3 4 7 11 18 29 47 76 123 199

Wertung

Das ist , also gewinnt der kürzeste gültige Code in Bytes. Tiebreaker geht zu einem früher geposteten Beitrag. Der Gewinner wird am kommenden Montag, 28. September, ermittelt. Viel Glück!

Bearbeiten: Herzlichen Glückwunsch an Ihren Gewinner, @Jakube, mit Pyth für erstaunliche 23 Bytes!

ETHproductions
quelle
10
Ich habe das von Ihnen erstellte [Montag-Minigolf] -Tag entfernt. Ich denke nicht, dass wir Tags für mehr oder weniger willkürliche Gruppen von Herausforderungen erstellen sollten. Das Tag sagt Ihnen eigentlich nichts über die Herausforderung aus, und wenn Sie all diese finden möchten, können Sie einfach in der Suchleiste nach der Phrase suchen. Wenn Sie alternativ in jeder zukünftigen Ausgabe einen Link zu dieser ersten Herausforderung einfügen, werden diese in der Seitenleiste unter "Verknüpfte Fragen" verlinkt.
Martin Ender
@ MartinBüttner OK, danke; Ich werde mir das merken.
ETHproductions
Can I take the input how I want it (A python list literal [8, 13, 10])?
Blue
3
The challenge currently says write a program. Does that mean that functions are not allowed? (CC @LuisMendo)
Dennis
3
@Dennis Sorry, slipped my mind. Functions are also allowed. Thanks for pointing that out!
ETHproductions

Antworten:

12

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]
Jakube
quelle
12

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.

Martin Ender
quelle
7

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

Blue
quelle
1
Nice method. For the index-less loop for _ in[1]*l:, it's a bit shorter to do exec"stuff;"*l
xnor
@xnor: It appears significantly longer to me.
recursive
Compare for _ in[1]*l:stuff to exec"stuff;"*l. @xnor didn't put in the stuff part in the for loop. Or for _ in[1]*l: to exec";"*l
Blue
2
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)
mbomb007
6

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.
Martin Ender
quelle
q~{_@\-_g)}g\@{_@+_p}*t (N B A) saves three bytes.
Dennis
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.
Cabbie407
Well, I solved it in my solution.
Cabbie407
@Cabbie407 You're correct, I should have used <! instead of >.
Martin Ender
Ah, okay. I wondered where to put that ! in this. I simply added one to make it work ;)
Cabbie407
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.

Martin Ender
quelle
5

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.

Dennis
quelle
4

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

Luis Mendo
quelle
According to the rules, you can modify the input, so f([a b],n) should be allowed.
beaker
@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
Luis Mendo
Yeah, I don't know if x=f(x,n) in the function header counts...
beaker
@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.
beaker
3

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.

Zgarb
quelle
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
@nimi Thanks; I ran with your idea and saved a total of 9 bytes.
Zgarb
3

><>, 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)]
Aaron
quelle
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
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 !
Aaron
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
"The output must be separated by spaces, commas, and/or newlines." Sorry, but you'll have to use the other version. Good job, though!
ETHproductions
Fixed it, I used \n instead of spaces to save 2 bytes
Aaron
2

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.
    ;
}
TheNumberOne
quelle
3
What? Java is shorter than JS?!? There's gotta be something I'm doing wrong....
ETHproductions
@ETHproductions I actually copied your algorithm (and then golfed it) :P
TheNumberOne
That's fine with me, I took some of your improvements ;) I forgot printing each item separately was valid in JS.
ETHproductions
You can shorten b=b-a to b-=a, and the same with a=b+a. It will save 2 bytes
Javier Diaz
+1 for making a verbose language submission so short. Usually Java submissions are the longest!
DankMemes
2

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
  }
}
ETHproductions
quelle
1

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]
  )
WizardOfMenlo
quelle
1

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.

Cabbie407
quelle
1

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
alexanderbird
quelle
1

Mathematica, 59 bytes

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

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

Yuri Kazakov
quelle
0

Jelly, 14 bytes

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

Try it online!

Erik the Outgolfer
quelle
0

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!

Renzo
quelle