148
\$\begingroup\$

The Fibonacci sequence is a sequence of numbers, where every number in the sequence is the sum of the two numbers preceding it. The first two numbers in the sequence are both 1. Here are the first few terms:

1 1 2 3 5 8 13 21 34 55 89 ...

Write the shortest code that either:

  • Generates the Fibonacci sequence without end.

  • Given n calculates the nth term of the sequence. (Either 1 or zero indexed)

You may use standard forms of input and output.

(I gave both options in case one is easier to do in your chosen language than the other.)


For the function that takes an n, a reasonably large return value (the largest Fibonacci number that fits your computer's normal word size, at a minimum) has to be supported.


Leaderboard

/* Configuration */

var QUESTION_ID = 85; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 3; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "https://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });  
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];
  
  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });
    
    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });
  
  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;
    
    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();
    
    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
body {
  text-align: left !important;
  display: block !important;
}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="https://cdn.sstatic.net/Sites/codegolf/all.css?v=ffb5d0584c5f">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>

\$\endgroup\$
4
  • 4
    \$\begingroup\$ I am sort of waiting for a response like "f", 1 byte, in my math based golf language. \$\endgroup\$ Aug 11, 2020 at 11:57
  • \$\begingroup\$ @ChrisJesterYoung can we use 1.0 are 1 only? \$\endgroup\$ May 11 at 2:45
  • \$\begingroup\$ @NumberBasher 1.0 is fine. \$\endgroup\$ May 20 at 19:10
  • \$\begingroup\$ What about 1.3? \$\endgroup\$ Aug 28 at 15:10

310 Answers 310

1
7 8 9
10
11
0
\$\begingroup\$

JAVA - 108 characters:

int[]f={0,1};System.out.println(0);for(int i=0;i<9;i+=2)System.out.printf("%d\n%d\n",f[0]+=f[1],f[1]+=f[0]);
\$\endgroup\$
5
  • \$\begingroup\$ If a space is required in the code, it should be included in the character count. \$\endgroup\$
    – Iszi
    Nov 27, 2013 at 21:53
  • \$\begingroup\$ Alright, I will update it. \$\endgroup\$
    – user10766
    Nov 27, 2013 at 21:57
  • \$\begingroup\$ Already fixed it for you - looks like someone approved my edit suggestion. \$\endgroup\$
    – Iszi
    Nov 27, 2013 at 22:05
  • \$\begingroup\$ That was me - I went to fix it, and found you had already. \$\endgroup\$
    – user10766
    Nov 27, 2013 at 22:06
  • \$\begingroup\$ Ah. All good, then. Welcome to Code Golf! \$\endgroup\$
    – Iszi
    Nov 27, 2013 at 22:10
0
\$\begingroup\$

C 64 Characters

a;main(f,n){scanf("%d",&n);while(--n)f+=a=f-a;printf("%d",f-a);}

This will print the nth Fibonacci number.

A more readable format :

a;
main(f,n){
scanf("%d",&n);
while(--n)
   f+=a=f-a;
printf("%d",f-a);
}
\$\endgroup\$
0
\$\begingroup\$

F#, 63 chars:

let rec g x y n=if n=x then x else f (n-1) y (x+y)
let f=g 0 1
\$\endgroup\$
0
\$\begingroup\$

~-~! (No Comment) - 27

'=|*>~[<'&*-~>+<'&*-~~>]*|:

Didn't think it'd be this short.

\$\endgroup\$
0
\$\begingroup\$

TI-BASIC - 18 symbols

to print fibonacci sequence starting from 0:

;i
;While 1
;Disp real(Ans
;real(Ans)+imag(Ans)+ireal(Ans
;End

to print fibonacci sequence starting from 1:

;1
;While 1
;Disp real(Ans
;real(Ans)+imag(Ans)+ireal(Ans
;End
\$\endgroup\$
1
  • \$\begingroup\$ real(Ans)-conj(iAns is shorter. \$\endgroup\$
    – lirtosiast
    Aug 8, 2015 at 4:23
0
\$\begingroup\$

Ruby - 49 characters

Nobody has done a Ruby solution for the second problem so I thought I'd give that a go:

p Hash.new{|h,k|k<2?k:(h[k-2]+h[k-1])}[gets.to_i]
\$\endgroup\$
0
\$\begingroup\$

Javascript, 53 bytes

a=[1,1];setInterval('a.push(a[b=a.length-1]+a[b-1])')

I decided to use a new approach to create an infinite stream. Works anywhere else but Firefox.

To get the array of integers, simply do a from the console.

\$\endgroup\$
0
\$\begingroup\$

CoffeeScript, 63 bytes

j=0;k=1;a=[];a=((i=j+k;k=j;j=i) for i in [0..prompt()]);alert a
\$\endgroup\$
0
\$\begingroup\$

C, 45 bytes

Simple, iterative approach. Exits when signed integer overflows.

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

Try it here.

\$\endgroup\$
1
  • \$\begingroup\$ I seems to me you can remove b>0 condition. \$\endgroup\$
    – sergiol
    Jul 8, 2017 at 22:32
0
\$\begingroup\$

Julia, 20 bytes

!n=n>1?!~-n+!~-~-n:n

Straightforward implementation of the recursive definition. No match for the matrix approach, but a lovely opportunity to abuse Julia's ability to redefine operators.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

C, 33 bytes

Recursively calculates the nth fibbonacci number.

f(n){return n>1?f(n-1)+f(n-2):n;}
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 32 26 bytes

-6 bytes thanks to @MartinEnder!

±1=±2=1;±n_:=±(n-1)+±(n-2)

Recursive function, returns nth value in sequence.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can golf this with prefix notation: f@1=f@2=1;f@n_:=f[n-1]+f[n-2]. And even further by defining an operator instead: ±1=±2=1;±n_:=±(n-1)+±(n-2). \$\endgroup\$ Mar 24, 2017 at 9:57
  • \$\begingroup\$ Oh yeah, forgot about prefix notation here. Didn't know about the operator, thanks! \$\endgroup\$ Mar 24, 2017 at 11:06
0
\$\begingroup\$

JavaScript (ES6)

A couple of different ES6 implementations. The first two return the nth Fibonacci number and the third returns an array of the first n Fibonacci numbers. Non-competing, obviously.

30 bytes

f=

(n,x=1,y=0)=>!n?y:f(n-1,x+y,x)

console.log(f(10))

46 bytes

f=

n=>(x=1,y=0,eval("while(n--)[x,y]=[x+y,x]"),y)

console.log(f(10))

46 bytes

f=

n=>(a=[],(f=x=>a[x]=x<2?x:f(--x)+f(--x))(n),a)

console.log(f(10))

\$\endgroup\$
0
\$\begingroup\$

Pylons, 13 bytes

Takes the number of iterations as a command line argument to the interpreter.

11fA..+@{A,i}

How it works:

11  # Pushes 1, 1 to the stack.
fA#.##.#+@  # Creates a function "A" that takes the top two elements of the stack and adds them.
{A,i}  # Calls A sys.argv[1] times.
\$\endgroup\$
0
0
\$\begingroup\$

Pug, 30 bytes

Without input (infinite)

-a=b=1
while 1
 =a
 -b=a+(a=b)

Will produce an output:

1123581321345589144233377610...

With an output delimiter: 34 bytes

-a=b=1
while 1
 =a+" "
 -b=a+(a=b)

Will produce an output:

1 1 2 3 5 8 13 21 34 55 89...

With HTML as an output delimiter: 31 bytes

-a=b=1
while 1
 p=a
 -b=a+(a=b)

Although I doubt this is compliant to the challenge's rules, this will produce:

<p>1</p>
<p>1</p>
<p>2</p>
<p>3</p>
<p>5</p>
<p>8</p>
<p>13</p>
<p>21</p>
<p>34</p>
<p>55</p>
...


With input (as a funcion; finite)

Without an output delimiter, 47 bytes

mixin f(n)
 -a=b=1
 while n--
  =a
  -b=a+(a=b)

For an input n=10, for example, it produces:

11235813213455


Just as it is with the infinite series versions:

  • +4 bytes (+" ") = 51 bytes for a space delimiter
  • +1 byte (p) = 48 bytes for an HTML <p> tag delimiter
\$\endgroup\$
0
\$\begingroup\$

Implicit, 12 11 bytes

]3.(,[+%:]ß

Try it online!

10 bytes (knock off the ß) if we don't need delimiters. It's not specified in the challenge... TIO

This is my own (rather simple) method of computing the sequence. Explanation:

#::.(,[+%:]ß
#::.            push 0, 0, 1 (push stack length, duplicate twice, increment last one)
    (.......    forever (implicit ¶ at end of program)
     ,           swap top two stack values
      [          pop stack into memory
       +         add top two stack values
        %        print
         :       duplicate top of stack
          ]      push memory to stack
           ß     print a space

In a normal language, say, C, it would look like this:

int x, y, z;
x = 0; y = 0; z = 1;

do {
    swap(&y, &z);
    x += y;
    y = x;
    printf("%d ",x);
} while (1);

Equivalence:

int x = 0, y = 0, z = 1;   // #::.
do {                       // (
    swap(&y,&z);           // ,
                           // [ (z is ignored below)
    x += y;                // +
    y = x;                 // :
    printf("%d ",x);       // %ß
                           // ] (z is ignored above)
} while (1);               // ¶

Here's how the stack looks after each operation that modifies it:

#  0
:  0 0
:  0 0 0
.  0 0 1

,  0 1 0
[  0 1
+  1
%  1
:  1 1
]  1 1 0

,  1 0 1
[  1 0
+  1
%  1
:  1 1
]  1 1 1

,  1 1 1
[  1 1
+  2
%  2
:  2 2
]  2 2 1

,  2 1 2
[  2 1
+  3
%  3
:  3 3
]  3 3 2

,  3 2 3
[  3 2
+  5
%  5
:  5 5
]  5 5 3

,  5 3 5
[  5 3
+  8
%  8
:  8 8
]  8 8 5

,  8 5 8
[  8 5
+  13
%  13
:  13 13
]  13 13 8

,  13 8 13
[  13 8
+  21
%  21
:  21 21
]  21 21 13

,  21 13 21
[  21 13
+  34
%  34
:  34 34
]  34 34 21

Golf notes:

  • ]3. is shorter than #::. which is shorter than :0::1 which is shorter than :0:0:1.
  • ß is shorter than @32.
  • (... is shorter than :1(;...:1).

(ß, , and implicit added during the writing of this program.)

\$\endgroup\$
0
\$\begingroup\$

Momema, 28 bytes

1 1z0-8*01+*1*00+*1-*0-9 9z1

Try it online! Outputs infinitely with a tab between numbers.

If no separator between numbers is required, you can save four bytes:

1 1z0-8*01+*1*00+*1-*0z1

Explanation

                                                     #  a = 0
1   1       #            [1] = 1                     #  b = 1
z   0       #  label z0: jump past label z0 (no-op)  #  while true {
-8  *0      #            output num [0]              #    print a
1   +*1*0   #            [1] = [1] + [0]             #    b = a + b
0   +*1-*0  #            [0] = [1] - [0]             #    a = b - a
-9  9       #            output chr 9                #    print '\t'
z1          #  label z1: jump past label z0          #  }
\$\endgroup\$
0
\$\begingroup\$

Reflections, 93 bytes

     \
/*\/#  (0:0\
* 0\_*;(0\/ :(0\
  \     v/#@/_ /
\  (1/ 1)0)*
        : \\/
        \(1/

Test it!

Explanation:

Initialisation

Executing \*/(1\*/*\0\.

  • * at (5|2) pushes 5×2=10 (\n)
  • (1 moves the newline to stack 1
  • * at (0|2) pushes 0×2=0 (F(-1))
  • * at (1|1) pushes 1×1=1 (F(0))
  • 0 moves these two values to stack 0

Loop

Executing v1):\(1/\\0)#/:(0\/_//\*@\0:(0#/\_*;(0\/.

  • 1) pulls the newline from stack 1
  • : duplicates it
  • (1 moves the duplicate to stack 1
  • 0) pulls the last result from stack 0
  • # redefines (0|0)
  • : duplicates the last result
  • (0 moves the duplicate back to stack 0
  • _ at (3|0) converts the last result to a list of digits
  • * at (1|1) pushes 1×1=1
  • @ prints the last result and a newline
  • 0 pulls both values from stack 0
  • : duplicates the top one (newer one)
  • (0 pushes the duplicate back to stack 0
  • # redefines (0|0)
  • _ at (0|1) adds the two values together
  • * at (1|1) pushes 1×1=1
  • ; pops that again
  • (0 pushes the new result to stack 0
\$\endgroup\$
0
\$\begingroup\$

Stax, 2 bytes

|5

Run and debug online!

Added for completeness. An internal that returns 0-indexed Fibonacci number.

Infinite sequence generator without using the internal:

ò¶AÄ∟

The ASCII equivalent is

01WQb+
\$\endgroup\$
0
\$\begingroup\$

SmileBASIC, 28 bytes

F.,1DEF F X,Y?Y
F Y,X+Y
END

Ungolfed:

F 0,1
DEF F X,Y
 PRINT Y
 F Y,X+Y
END
\$\endgroup\$
0
\$\begingroup\$

Elixir, 49 bytes

Defines a function to get the nth fibonacci number. 1-indexed (starts at 0).

Simple recursive formula. Slow.

def f(n)when n<2,do: n
def f(n),do: f(n-1)+f(n-2)

Try it online!

Elixir, 50 bytes

Returns an infinite stream of fibonacci numbers. 1-indexed (starts at 0).

Fast, carries over an accumulator with the sum of the previous two numbers.

fn->Stream.unfold{0,1},fn{a,b}->{a,{b,a+b}}end end

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Javascript, 57 bytes

_=1;i=0;for(z=10;z--;)alert((a=>!(o=_+i)+(i=_)+!(_=o))())

\$\endgroup\$
0
\$\begingroup\$

Python 2, 33 31 bytes

i=j=1
while 1:print j;i,j=j+i,i

Try it online!

Uses a loop to infinitely print the sequence. Will eventually error out due to integer overflow. It has been pointed out to me that Python uses arbitrary precision integers. Learn something new every day!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Python uses arbitrary precision integers so an integer overflow will not occur. \$\endgroup\$ Aug 3, 2018 at 14:48
  • 1
    \$\begingroup\$ i,j=1,1 can be i=j=1. \$\endgroup\$ Aug 3, 2018 at 14:48
0
\$\begingroup\$

Julia 0.6, 19 bytes

!a=round(φ^a/√5)

Try it online!

This is 16 chars and 19 bytes, a goof way to abuse Julia beats the existing Julia answers which were 20 bytes. by 1 bytes and 3 chars

\$\endgroup\$
0
0
\$\begingroup\$

Tcl, 71 bytes (function implementation=43, Enter=1, call=27)

proc F x {expr $x>1?\[F $x-1]+\[F $x-2]:$x}
while 1 {puts [F [incr i]]}

Try it online!

Serves both purposes: Has a function F that allows calculate the x'th Fibonacci number. then it is called to show on stdout F applied to the whole range of positive integers.

\$\endgroup\$
4
  • \$\begingroup\$ tcl,89: Different approach — iterative. demo — but it does not have a function and fails to represent the first one. \$\endgroup\$
    – sergiol
    Jul 8, 2017 at 22:17
  • \$\begingroup\$ Failed outgolf; tcl,91 (function implementation=56, Enter=1, call=34): tio.run/##K0nO@f@/oCg/WaEkOcfKKjexJCOtNC/… \$\endgroup\$
    – sergiol
    Nov 5, 2017 at 17:08
  • \$\begingroup\$ You can use less expr as there's a leading one, in escaping evaluation of each 1st brackets code 45B \$\endgroup\$
    – david
    Dec 16, 2018 at 20:00
  • \$\begingroup\$ Thanks @david . I did not know I could do it by escaping [ with `\`. I bet I have some more answers I can golf them the way you described. \$\endgroup\$
    – sergiol
    Dec 16, 2018 at 20:52
0
\$\begingroup\$

C# (.NET Core), 68, 56 bytes

Lambda using decimal size for single n.

EDIT: Ty Jo King for pointing out better ways to assign the maths to the vars!

p=>{decimal a=0,b=1,j=0;for(;j++<p;b=a-b)a+=b;return a;}

Try it online!

\$\endgroup\$
2
0
\$\begingroup\$

Ouroboros, 10 bytes

Outputs an infinite Fibonacci sequence, starting at 0, separated by newlines.

.!+.@.nao+

Explanation

Each line of an Ouroboros program represents a snake eating its own tail. When execution reaches the end of the line, it loops back to the beginning. Each snake has a stack to store values.

If this is the first pass through the code, we need to initialize the stack by turning the top into a 1. (The empty stack is treated as containing infinite zeros.) .! dups and logically negates (1 if the value was 0, otherwise 0), and + adds that result to the top value. This has the effect of pushing a 1 if the stack was empty, and doing nothing if the stack contained a nonzero value.

Now, call the two numbers on the stack x and y, where x is smaller and y is on the top of the stack. .@.n copies y, rotates x to the top, and outputs a copy of it. a pushes 10 and o outputs it as a character (printing a newline). Finally, + adds x to a copy of y. The stack now contains y and x+y, and we proceed to the next iteration.

Try it out

// Define Stack class
function Stack() {
  this.stack = [];
  this.length = 0;
}
Stack.prototype.push = function(item) {
  this.stack.push(item);
  this.length++;
}
Stack.prototype.pop = function() {
  var result = 0;
  if (this.length > 0) {
    result = this.stack.pop();
    this.length--;
  }
  return result;
}
Stack.prototype.top = function() {
  var result = 0;
  if (this.length > 0) {
    result = this.stack[this.length - 1];
  }
  return result;
}
Stack.prototype.toString = function() {
  return "" + this.stack;
}

// Define Snake class
function Snake(code) {
  this.code = code;
  this.length = this.code.length;
  this.ip = 0;
  this.ownStack = new Stack();
  this.currStack = this.ownStack;
  this.alive = true;
  this.wait = 0;
  this.partialString = this.partialNumber = null;
}
Snake.prototype.step = function() {
  if (!this.alive) {
    return null;
  }
  if (this.wait > 0) {
    this.wait--;
    return null;
  }
  var instruction = this.code.charAt(this.ip);
  var output = null;
  console.log("Executing instruction " + instruction);
  if (this.partialString !== null) {
    // We're in the middle of a double-quoted string
    if (instruction == '"') {
      // Close the string and push its character codes in reverse order
      for (var i = this.partialString.length - 1; i >= 0; i--) {
        this.currStack.push(this.partialString.charCodeAt(i));
      }
      this.partialString = null;
    } else {
      this.partialString += instruction;
    }
  } else if (instruction == '"') {
    this.partialString = "";
  } else if ("0" <= instruction && instruction <= "9") {
    if (this.partialNumber !== null) {
      this.partialNumber = this.partialNumber + instruction;  // NB: concatenation!
    } else {
      this.partialNumber = instruction;
    }
    next = this.code.charAt((this.ip + 1) % this.length);
    if (next < "0" || "9" < next) {
      // Next instruction is non-numeric, so end number and push it
      this.currStack.push(+this.partialNumber);
      this.partialNumber = null;
    }
  } else if ("a" <= instruction && instruction <= "f") {
    // a-f push numbers 10 through 15
    var value = instruction.charCodeAt(0) - 87;
    this.currStack.push(value);
  } else if (instruction == "$") {
    // Toggle the current stack
    if (this.currStack === this.ownStack) {
      this.currStack = this.program.sharedStack;
    } else {
      this.currStack = this.ownStack;
    }
  } else if (instruction == "s") {
    this.currStack = this.ownStack;
  } else if (instruction == "S") {
    this.currStack = this.program.sharedStack;
  } else if (instruction == "l") {
    this.currStack.push(this.ownStack.length);
  } else if (instruction == "L") {
    this.currStack.push(this.program.sharedStack.length);
  } else if (instruction == ".") {
    var item = this.currStack.pop();
    this.currStack.push(item);
    this.currStack.push(item);
  } else if (instruction == "m") {
    var item = this.ownStack.pop();
    this.program.sharedStack.push(item);
  } else if (instruction == "M") {
    var item = this.program.sharedStack.pop();
    this.ownStack.push(item);
  } else if (instruction == "y") {
    var item = this.ownStack.top();
    this.program.sharedStack.push(item);
  } else if (instruction == "Y") {
    var item = this.program.sharedStack.top();
    this.ownStack.push(item);
  } else if (instruction == "\\") {
    var top = this.currStack.pop();
    var next = this.currStack.pop()
    this.currStack.push(top);
    this.currStack.push(next);
  } else if (instruction == "@") {
    var c = this.currStack.pop();
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(b);
    this.currStack.push(c);
    this.currStack.push(a);
  } else if (instruction == ";") {
    this.currStack.pop();
  } else if (instruction == "+") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a + b);
  } else if (instruction == "-") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a - b);
  } else if (instruction == "*") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a * b);
  } else if (instruction == "/") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a / b);
  } else if (instruction == "%") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(a % b);
  } else if (instruction == "_") {
    this.currStack.push(-this.currStack.pop());
  } else if (instruction == "I") {
    var value = this.currStack.pop();
    if (value < 0) {
      this.currStack.push(Math.ceil(value));
    } else {
      this.currStack.push(Math.floor(value));
    }
  } else if (instruction == ">") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(+(a > b));
  } else if (instruction == "<") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(+(a < b));
  } else if (instruction == "=") {
    var b = this.currStack.pop();
    var a = this.currStack.pop();
    this.currStack.push(+(a == b));
  } else if (instruction == "!") {
    this.currStack.push(+ !this.currStack.pop());
  } else if (instruction == "?") {
    this.currStack.push(Math.random());
  } else if (instruction == "n") {
    output = "" + this.currStack.pop();
  } else if (instruction == "o") {
    output = String.fromCharCode(this.currStack.pop());
  } else if (instruction == "r") {
    var input = this.program.io.getNumber();
    this.currStack.push(input);
  } else if (instruction == "i") {
    var input = this.program.io.getChar();
    this.currStack.push(input);
  } else if (instruction == "(") {
    this.length -= Math.floor(this.currStack.pop());
    this.length = Math.max(this.length, 0);
  } else if (instruction == ")") {
    this.length += Math.floor(this.currStack.pop());
    this.length = Math.min(this.length, this.code.length);
  } else if (instruction == "w") {
    this.wait = this.currStack.pop();
  }
  // Any unrecognized character is a no-op
  if (this.ip >= this.length) {
    // We've swallowed the IP, so this snake dies
    this.alive = false;
    this.program.snakesLiving--;
  } else {
    // Increment IP and loop if appropriate
    this.ip = (this.ip + 1) % this.length;
  }
  return output;
}
Snake.prototype.getHighlightedCode = function() {
  var result = "";
  for (var i = 0; i < this.code.length; i++) {
    if (i == this.length) {
      result += '<span class="swallowedCode">';
    }
    if (i == this.ip) {
      if (this.wait > 0) {
        result += '<span class="nextActiveToken">';
      } else {
        result += '<span class="activeToken">';
      }
      result += escapeEntities(this.code.charAt(i)) + '</span>';
    } else {
      result += escapeEntities(this.code.charAt(i));
    }
  }
  if (this.length < this.code.length) {
    result += '</span>';
  }
  return result;
}

// Define Program class
function Program(source, speed, io) {
  this.sharedStack = new Stack();
  this.snakes = source.split(/\r?\n/).map(function(snakeCode) {
    var snake = new Snake(snakeCode);
    snake.program = this;
    snake.sharedStack = this.sharedStack;
    return snake;
  }.bind(this));
  this.snakesLiving = this.snakes.length;
  this.io = io;
  this.speed = speed || 10;
  this.halting = false;
}
Program.prototype.run = function() {
  this.step();
  if (this.snakesLiving) {
    this.timeout = window.setTimeout(this.run.bind(this), 1000 / this.speed);
  }
}
Program.prototype.step = function() {
   for (var s = 0; s < this.snakes.length; s++) {
    var output = this.snakes[s].step();
    if (output) {
      this.io.print(output);
    }
  }
  this.io.displaySource(this.snakes.map(function (snake) {
      return snake.getHighlightedCode();
    }).join("<br>"));
 }
Program.prototype.halt = function() {
  window.clearTimeout(this.timeout);
}

var ioFunctions = {
  print: function (item) {
    var stdout = document.getElementById('stdout');
    stdout.value += "" + item;
  },
  getChar: function () {
    if (inputData) {
      var inputChar = inputData[0];
      inputData = inputData.slice(1);
      result = inputChar.charCodeAt(0);
    } else {
      result = -1;
    }
    var stdinDisplay = document.getElementById('stdin-display');
    stdinDisplay.innerHTML = escapeEntities(inputData);
    return result;
  },
  getNumber: function () {
    while (inputData && (inputData[0] < "0" || "9" < inputData[0])) {
      inputData = inputData.slice(1);
    }
    if (inputData) {
      var inputNumber = inputData.match(/\d+/)[0];
      inputData = inputData.slice(inputNumber.length);
      result = +inputNumber;
    } else {
      result = -1;
    }
    var stdinDisplay = document.getElementById('stdin-display');
    stdinDisplay.innerHTML = escapeEntities(inputData);
    return result;
  },
  displaySource: function (formattedCode) {
    var sourceDisplay = document.getElementById('source-display');
    sourceDisplay.innerHTML = formattedCode;
  }
};
var program = null;
var inputData = null;
function showEditor() {
  var source = document.getElementById('source'),
    sourceDisplayWrapper = document.getElementById('source-display-wrapper'),
    stdin = document.getElementById('stdin'),
    stdinDisplayWrapper = document.getElementById('stdin-display-wrapper');
  
  source.style.display = "block";
  stdin.style.display = "block";
  sourceDisplayWrapper.style.display = "none";
  stdinDisplayWrapper.style.display = "none";
  
  source.focus();
}
function hideEditor() {
  var source = document.getElementById('source'),
    sourceDisplay = document.getElementById('source-display'),
    sourceDisplayWrapper = document.getElementById('source-display-wrapper'),
    stdin = document.getElementById('stdin'),
    stdinDisplay = document.getElementById('stdin-display'),
    stdinDisplayWrapper = document.getElementById('stdin-display-wrapper');
  
  source.style.display = "none";
  stdin.style.display = "none";
  sourceDisplayWrapper.style.display = "block";
  stdinDisplayWrapper.style.display = "block";
  
  var sourceHeight = getComputedStyle(source).height,
    stdinHeight = getComputedStyle(stdin).height;
  sourceDisplayWrapper.style.minHeight = sourceHeight;
  sourceDisplayWrapper.style.maxHeight = sourceHeight;
  stdinDisplayWrapper.style.minHeight = stdinHeight;
  stdinDisplayWrapper.style.maxHeight = stdinHeight;
  sourceDisplay.textContent = source.value;
  stdinDisplay.textContent = stdin.value;
}
function escapeEntities(input) {
  return input.replace(/&/g, '&amp;').replace(/</g, '&lt;').replace(/>/g, '&gt;');
}
function resetProgram() {
  var stdout = document.getElementById('stdout');
  stdout.value = null;
  if (program !== null) {
    program.halt();
  }
  program = null;
  inputData = null;
  showEditor();
}
function initProgram() {
  var source = document.getElementById('source'),
    stepsPerSecond = document.getElementById('steps-per-second'),
    stdin = document.getElementById('stdin');
  program = new Program(source.value, +stepsPerSecond.innerHTML, ioFunctions);
  hideEditor();
  inputData = stdin.value;
}
function runBtnClick() {
  if (program === null || program.snakesLiving == 0) {
    resetProgram();
    initProgram();
  } else {
    program.halt();
    var stepsPerSecond = document.getElementById('steps-per-second');
    program.speed = +stepsPerSecond.innerHTML;
  }
  program.run();
}
function stepBtnClick() {
  if (program === null) {
    initProgram();
  } else {
    program.halt();
  }
  program.step();
}
function sourceDisplayClick() {
  resetProgram();
}
.container {
    width: 100%;
}
.so-box {
    font-family:'Helvetica Neue', Arial, sans-serif;
    font-weight: bold;
    color: #fff;
    text-align: center;
    padding: .3em .7em;
    font-size: 1em;
    line-height: 1.1;
    border: 1px solid #c47b07;
    -webkit-box-shadow: 0 2px 2px rgba(0, 0, 0, 0.3), 0 2px 0 rgba(255, 255, 255, 0.15) inset;
    text-shadow: 0 0 2px rgba(0, 0, 0, 0.5);
    background: #f88912;
    box-shadow: 0 2px 2px rgba(0, 0, 0, 0.3), 0 2px 0 rgba(255, 255, 255, 0.15) inset;
}
.control {
    display: inline-block;
    border-radius: 6px;
    float: left;
    margin-right: 25px;
    cursor: pointer;
}
.option {
    padding: 10px 20px;
    margin-right: 25px;
    float: left;
}
h1 {
    text-align: center;
    font-family: Georgia, 'Times New Roman', serif;
}
a {
    text-decoration: none;
}
input, textarea {
    box-sizing: border-box;
}
textarea {
    display: block;
    white-space: pre;
    overflow: auto;
    height: 100px;
    width: 100%;
    max-width: 100%;
    min-height: 25px;
}
span[contenteditable] {
    padding: 2px 6px;
    background: #cc7801;
    color: #fff;
}
#stdout-container, #stdin-container {
    height: auto;
    padding: 6px 0;
}
#reset {
    float: right;
}
#source-display-wrapper , #stdin-display-wrapper{
    display: none;
    width: 100%;
    height: 100%;
    overflow: auto;
    border: 1px solid black;
    box-sizing: border-box;
}
#source-display , #stdin-display{
    font-family: monospace;
    white-space: pre;
    padding: 2px;
}
.activeToken {
    background: #f93;
}
.nextActiveToken {
    background: #bbb;
}
.swallowedCode{
    color: #999;
}
.clearfix:after {
    content:".";
    display: block;
    height: 0;
    clear: both;
    visibility: hidden;
}
.clearfix {
    display: inline-block;
}
* html .clearfix {
    height: 1%;
}
.clearfix {
    display: block;
}
<!--
Designed and written 2015 by D. Loscutoff
Much of the HTML and CSS was taken from this Befunge interpreter by Ingo Bürk: http://codegolf.stackexchange.com/a/40331/16766
-->
<div class="container">
<textarea id="source" placeholder="Enter your program here" wrap="off">.!+.@.nao+</textarea>
<div id="source-display-wrapper" onclick="sourceDisplayClick()"><div id="source-display"></div></div></div><div id="stdin-container" class="container">
<textarea id="stdin" placeholder="Input" wrap="off"></textarea>
<div id="stdin-display-wrapper" onclick="stdinDisplayClick()"><div id="stdin-display"></div></div></div><div id="controls-container" class="container clearfix"><input type="button" id="run" class="control so-box" value="Run" onclick="runBtnClick()" /><input type="button" id="pause" class="control so-box" value="Pause" onclick="program.halt()" /><input type="button" id="step" class="control so-box" value="Step" onclick="stepBtnClick()" /><input type="button" id="reset" class="control so-box" value="Reset" onclick="resetProgram()" /></div><div id="stdout-container" class="container"><textarea id="stdout" placeholder="Output" wrap="off" readonly></textarea></div><div id="options-container" class="container"><div class="option so-box">Steps per Second:
<span id="steps-per-second" contenteditable>20</span></div></div>

\$\endgroup\$
0
\$\begingroup\$

33, 7 bytes

1c[oca]

Not a Fibonacci number, I'm afraid.

\$\endgroup\$
0
\$\begingroup\$

Golfscript 42 bytes

~:n;2 -1?:h;5h?:f;1f+2/:p;p n?-1p*n~)?-f/

I origionally solved this in python with 64chars because i didn't think golfscript supported floats. I did some more digging and it actually does if you raise a number to -1.

Back in my graph theory/combinitorics class we went over creating an O(1) form of recurance eqautions, the fibonacci sequence is one example we used. I don't remeber the method for converting a recurance equation to constant time because the class was a few years ago, but I found the solution for the fibonacci equation online

constant time fibonacci sequence

phi

This allows you to compute the nth fibbonacci number without computing the previous terms

\$\endgroup\$
1
  • \$\begingroup\$ You're correct, hardcoing phi is a bit messy, see my updated answer using golfscript and not hardcoding any values \$\endgroup\$
    – wade king
    Aug 28, 2019 at 23:53
0
\$\begingroup\$

C (gcc), 57 bytes

x=0,y=1,s;main(){for(;;){s=x+y;printf("%d,",s);x=y;y=s;}}

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Shouldn't you be starting at 1,1,2,3...? Also, you can omit the =0, and instead of for(;;), you can call main() again. Try it online! \$\endgroup\$
    – Jo King
    Oct 21, 2019 at 4:41
  • 1
    \$\begingroup\$ @ceilingcat And even further (assuming no arguments) 45 bytes \$\endgroup\$
    – Jo King
    Oct 21, 2019 at 20:31
  • 1
    \$\begingroup\$ or 41 bytes with a different interpreter \$\endgroup\$
    – Jo King
    Oct 21, 2019 at 21:31
1
7 8 9
10
11

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.