Montag Minigolf: Eine Reihe von kurzen Code-Golf- 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 wird
x >= 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 13
wir 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 0
ist die 0. Nummer in dieser Reihenfolge. Darauf aufbauend drucken wir aus 0
und 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 3
kleiner 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 Code-Golf , 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!
[8, 13, 10]
)?Antworten:
Pyth, 23 bytes
Try it online: Demonstration or Test Suite
Quite unusual style of Pyth programming. Sometimes functional programming has its downsides.
Explanation:
quelle
Retina,
6554 bytesHere,
<empty>
represents an empty trailing line. Run the code as a single file with the-s
flag.The input format is
where the numbers are represented in unary. The output is a comma-separated list, also in unary. For instance:
would be
and yield
Explanation
First, we reduce
A
andB
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 capturesA
into group 1 with(1*)
, and then makes sure thatB
is at least as big asA
while capturingB-A
with\1(1*)
into group 2. This ensures that this loop terminates onceA>B
.The substitution simply turns
A,B
intoB-A,A
by setting the match to$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
fromN
. Because we already have one number we want this to happen onlyN-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 sequenceC
andD
, then the regex capturesC
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 single1
we matched inN
, thereby decrementing it.Finally, we need to get rid of -1st element of the sequence, as well the leftover
;1
fromN
, which we simply do by matching either of those and replacing it with the empty string.quelle
Python 2,
9387676160 bytesGets 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
quelle
for _ in[1]*l:
, it's a bit shorter to doexec"stuff;"*l
for _ in[1]*l:stuff
toexec"stuff;"*l
. @xnor didn't put in the stuff part in the for loop. Orfor _ in[1]*l:
toexec";"*l
j>=i
withj/i
. Just found that out! (Because You may assume that A, B, and N are always positive integers)CJam,
2623 bytesThanks to Dennis for saving 3 bytes.
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.
quelle
q~{_@\-_g)}g\@{_@+_p}*t
(N B A
) saves three bytes.B>A
it has to check forB 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.<!
instead of>
.!
in this. I simply added one to make it work ;)Labyrinth,
5854494644 bytesThanks 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 readsA
). On the"
(a no-op) it hits a dead end, so it turns around, executing the?
again (readingB
). Lastly,}
movesB
over to the auxiliary stack. The dead end saves a byte over the naiveNow 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).:
duplicatesA
,{
movesB
back to the main stack,-
computesA-B
. What we really want isB-A
though, so`
negates the value.This is now a four-way junction. For negative results, the IP takes a left-turn towards the
?
, readingN
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: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,}
movesA
to the auxiliary stack and=
swapsA
andB
.Once
A
is negative,?
readsN
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
andA
onto the auxiliary stack. DuplicateB
, swap the copy withA
and addA
to the other copy ofB
. Duplicate it again to print the current value ofB
. Print a newline. MoveB
andN
back to the main stack and decrementN
.While
N
is positive, the IP will take a right-turn (north) continuing the loop. OnceN
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 pushes0
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.quelle
C,
105102100 bytesThanks to @C0deH4cker for golfing off 2 bytes!
Try it online on Ideone.
quelle
Matlab / Octave, 115
125bytesThe function should be called as
f([8 13],10)
.Example (Matlab):
Or try it online (Octave).
quelle
f([a b],n)
should be allowed.x=f(x,n)
in the function header counts...Haskell,
67 6556 bytesThanks to @nimi for suggestions
This defines a ternary infix function
%
, which is invoked in the format(n%a)b
, for example:Explanation
The binary infix function
#
, defined on the first line, takes in two integersa
andb
and returns the infinite Fibonacci-like sequence wherea
andb
occur as consecutive elements.The function
%
simply takes the firstn
elements ofa#b
.quelle
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.><>,
3331+1 for -v = 32 bytesInput 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 :
The second line goes up the serie until it has printed N terms :
quelle
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 had00.
in the first place).!
or?
(at the end of the line) if it's on the longest line. You can try it with something like1n!
and it'll error, but if there's a line below it with something longer than it, likelorumipsum
, it won't.Java,
1137876 bytesCredit goes to ETHproduction for providing the algorithm I use in this answer.
Try here.
Explanation:
Original approach,
11393 bytesLooks more golfy ;)
Try it out here.
Explanation:
quelle
b=b-a
tob-=a
, and the same witha=b+a
. It will save 2 bytesJavascript (ES6),
837363 bytesThis might have been golfed to the max. We'll see.
Ungolfed:
quelle
Mathematica 112
Will golf it eventually
quelle
CJam, 40 bytes
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.And I could even reduce it by one more by using the ternary operator to clean the stack and produce an error.
quelle
Ruby, 141 bytes
Execution
f function produces the desired output, argument names match the variable names from the question
Nothing clever:
quelle
Mathematica, 59 bytes
quelle
Ruby,
817573Shortened by 6 Bytes when replacing for-loop with range.map
Saved another 2 bytes by moving print statement
quelle
Pyke, 24 bytes (non-competing)
Try it here!
quelle
Jelly, 14 bytes
Try it online!
quelle
Common Lisp, 91 bytes
Try it online!
quelle