diff options
Diffstat (limited to 'entries')
48 files changed, 1045 insertions, 5 deletions
diff --git a/entries/MarieSal0/FibonacciWorkplace/.gitignore b/entries/MarieSal0/FibonacciWorkplace/.gitignore new file mode 100644 index 0000000..9b956f9 --- /dev/null +++ b/entries/MarieSal0/FibonacciWorkplace/.gitignore @@ -0,0 +1,133 @@ +## Ignore Visual Studio temporary files, build results, and +## files generated by popular Visual Studio add-ons. + +# User-specific files +*.suo +*.user +*.sln.docstates + +# Build results + +[Dd]ebug/ +[Rr]elease/ +x64/ +[Bb]in/ +[Oo]bj/ + +# MSTest test Results +[Tt]est[Rr]esult*/ +[Bb]uild[Ll]og.* + +*_i.c +*_p.c +*_i.h +*.ilk +*.meta +*.obj +*.pch +*.pdb +*.pgc +*.pgd +*.rsp +*.sbr +*.tlb +*.tli +*.tlh +*.tmp +*.tmp_proj +*.log +*.vspscc +*.vssscc +.builds +*.pidb +*.log +*.svclog +*.scc + +# Visual C++ cache files +ipch/ +*.aps +*.ncb +*.opensdf +*.sdf +*.cachefile + +# Visual Studio profiler +*.psess +*.vsp +*.vspx + +# Guidance Automation Toolkit +*.gpState + +# ReSharper is a .NET coding add-in +_ReSharper*/ +*.[Rr]e[Ss]harper +*.DotSettings.user + +# Click-Once directory +publish/ + +# Publish Web Output +*.Publish.xml +*.pubxml +*.azurePubxml + +# NuGet Packages Directory +## TODO: If you have NuGet Package Restore enabled, uncomment the next line +packages/ +## TODO: If the tool you use requires repositories.config, also uncomment the next line +!packages/repositories.config + +# Windows Azure Build Output +csx/ +*.build.csdef + +# Windows Store app package directory +AppPackages/ + +# Others +sql/ +*.Cache +ClientBin/ +[Ss]tyle[Cc]op.* +![Ss]tyle[Cc]op.targets +~$* +*~ +*.dbmdl +*.[Pp]ublish.xml + +*.publishsettings + +# RIA/Silverlight projects +Generated_Code/ + +# Backup & report files from converting an old project file to a newer +# Visual Studio version. Backup files are not needed, because we have git ;-) +_UpgradeReport_Files/ +Backup*/ +UpgradeLog*.XML +UpgradeLog*.htm + +# SQL Server files +App_Data/*.mdf +App_Data/*.ldf + +# ========================= +# Windows detritus +# ========================= + +# Windows image file caches +Thumbs.db +ehthumbs.db + +# Folder config file +Desktop.ini + +# Recycle Bin used on file shares +$RECYCLE.BIN/ + +# Mac desktop service store files +.DS_Store + +_NCrunch*
\ No newline at end of file diff --git a/entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj b/entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj new file mode 100644 index 0000000..40c60dd --- /dev/null +++ b/entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj @@ -0,0 +1,10 @@ +<Project Sdk="Microsoft.NET.Sdk">
+
+ <PropertyGroup>
+ <OutputType>Exe</OutputType>
+ <TargetFramework>net6.0</TargetFramework>
+ <ImplicitUsings>enable</ImplicitUsings>
+ <Nullable>enable</Nullable>
+ </PropertyGroup>
+
+</Project>
diff --git a/entries/MarieSal0/FibonacciWorkplace/Program.cs b/entries/MarieSal0/FibonacciWorkplace/Program.cs new file mode 100644 index 0000000..bac5688 --- /dev/null +++ b/entries/MarieSal0/FibonacciWorkplace/Program.cs @@ -0,0 +1,41 @@ +using System;
+namespace FibonacciWorkplace
+{
+ public class Program
+ {
+ static void Main(string[] args)
+ {
+ Console.Write("How long should the Fibonacci Series be?? ");
+ int lengthOfSeries = Convert.ToInt32(Console.ReadLine());
+ if (lengthOfSeries<=2)
+ {
+ LengthCheck(lengthOfSeries);
+ }
+ FibonacciSeries(0, 1, 1, lengthOfSeries);
+ Console.ReadKey();
+ }
+ public static void LengthCheck(int lengthOfSeries)
+ {
+ if (lengthOfSeries<=1)
+ {
+ Console.Write("The Fibonacci Series needs to be greater than 2");
+ lengthOfSeries = Convert.ToInt32(Console.ReadLine());
+ LengthCheck(lengthOfSeries);
+ }
+
+ }
+
+ public static void FibonacciSeries(int firstNumber, int secondNumber, int counter, int lengthOfSeries)
+ {
+ Console.Write(firstNumber + " ");
+ if (counter < lengthOfSeries)
+ {
+ int sum = firstNumber + secondNumber;
+ counter++;
+ FibonacciSeries(secondNumber, sum, counter, lengthOfSeries);
+ }
+ }
+
+
+ }
+}
\ No newline at end of file diff --git a/entries/Metroxe/index.html b/entries/Metroxe/index.html index 98ac5b9..cb85a24 100644 --- a/entries/Metroxe/index.html +++ b/entries/Metroxe/index.html @@ -23,7 +23,7 @@ const n1 = s.substring(i1 + 1); const n2 = i2 === -1 ? s.substring(0, i1 - 1) : s.substring(i2 + 1, i1); const v = Number(n1) + Number(n2); - const output = `${s},${Number(n1) + Number(n2)}`; + const output = `${s},${v}`; document.getElementById("sequence").innerText = output; const next = document.getElementById("next"); diff --git a/entries/StuartLiv/ThetaFibN.java b/entries/StuartLiv/ThetaFibN.java new file mode 100644 index 0000000..1e4f431 --- /dev/null +++ b/entries/StuartLiv/ThetaFibN.java @@ -0,0 +1,13 @@ +public class ThetaFibN { + + //Fibonacci(n) is asymptotically in ϴ(Fibonacci(n)) + public int Fibonacci(int n) { + String reference = "0"; + int fib = 1; + for(int i = 1; i <= n; i++) { + fib = reference.length(); + reference = reference.replace("0", "").replace("1", "0") + "1".repeat(fib); + } + return fib; + } +} diff --git a/entries/Tarcisio-Teixeira/fib.py b/entries/Tarcisio-Teixeira/fib.py new file mode 100644 index 0000000..a73cdd2 --- /dev/null +++ b/entries/Tarcisio-Teixeira/fib.py @@ -0,0 +1,5 @@ +def fib(n,arr={},v =-1): + if v>=0: + arr[n]=v + return v + return arr[n] if n in arr.keys() else fib(n, arr, (2*n*n*n - 9*n*n+13*n)//6 if n <= 3 else fib(n//2-1,arr)*fib(n-n//2,arr) + fib(n//2,arr)*fib(n-n//2+1,arr)) diff --git a/entries/adirar111/wasm/fib.wasm b/entries/adirar111/wasm/fib.wasm Binary files differnew file mode 100644 index 0000000..6a93250 --- /dev/null +++ b/entries/adirar111/wasm/fib.wasm diff --git a/entries/adirar111/wasm/fib.wat b/entries/adirar111/wasm/fib.wat new file mode 100644 index 0000000..255fa12 --- /dev/null +++ b/entries/adirar111/wasm/fib.wat @@ -0,0 +1,46 @@ +;; iterative fib(n) in web assembly text format (wat) +;; this gets compiled to the fib.wasm binary +;; and gets fetched via a data URL in index.js +(module + (export "fib" (func $fib)) + (func $fib (param $n i32) (result i32) + (local $last i32) + (local $sum i32) + (local $i i32) + (local $tmp i32) + (if + (i32.lt_s + (local.get $n) + (i32.const 2) + ) + (return (local.get $n)) + ) + (local.set $last (i32.const 0)) + (local.set $sum (i32.const 1)) + (local.set $i (i32.const 2)) + (local.set $n (i32.add (local.get $n) (i32.const 1))) + (loop $loop + (local.set $tmp (local.get $sum)) + (local.set $sum + (i32.add + (local.get $sum) + (local.get $last) + ) + ) + (local.set $last (local.get $tmp)) + (local.set $i + (i32.add + (local.get $i) + (i32.const 1) + ) + ) + (br_if $loop + (i32.lt_s + (local.get $i) + (local.get $n) + ) + ) + ) + (return (local.get $sum)) + ) +) diff --git a/entries/adirar111/wasm/index.html b/entries/adirar111/wasm/index.html new file mode 100644 index 0000000..8357a55 --- /dev/null +++ b/entries/adirar111/wasm/index.html @@ -0,0 +1,21 @@ +<!DOCTYPE html> +<html> + <head> + <title>wasm fib</title> + <link + href="https://fonts.googleapis.com/css2?family=Source+Code+Pro:wght@600;700&display=swap" + rel="stylesheet" + /> + <link rel="stylesheet" href="style.css" /> + </head> + <body> + <p>go ahead, type a number</p> + <div id="input-area"> + <input id="input" type="text" autocomplete="off" /> + <button id="compute">compute!</button> + </div> + <p>fib.wasm says:</p> + <span id="result"></span> + <script src="index.js"></script> + </body> +</html> diff --git a/entries/adirar111/wasm/index.js b/entries/adirar111/wasm/index.js new file mode 100644 index 0000000..667ff82 --- /dev/null +++ b/entries/adirar111/wasm/index.js @@ -0,0 +1,23 @@ +const wasmBinaryBase64 = "AGFzbQEAAAABBgFgAX8BfwMCAQAHBwEDZmliAAAKRwFFAQR/IABBAkgEQCAADwtBACEBQQEhAkECIQMgAEEBaiEAA0AgAiEEIAIgAWohAiAEIQEgA0EBaiEDIAMgAEgNAAsgAg8LACgEbmFtZQEGAQADZmliAhkBAAUAAW4BBGxhc3QCA3N1bQMBaQQDdG1w" +const wasmBinaryDataURL = `data:application/wasm;base64,${wasmBinaryBase64}`; + +WebAssembly.instantiateStreaming(fetch(wasmBinaryDataURL)).then( + (wasmObj) => { + const {fib: fibWasm} = wasmObj.instance.exports + const fib = (event) => { + event.preventDefault() + const input = document.getElementById("input") + const result = document.getElementById("result") + const n = parseInt(input.value) + if (isNaN(n)) { + return result.textContent = "that wasn't very wasm of you" + } + if (n < 0) { + return result.textContent = "why are you being so negative" + } + result.textContent = fibWasm(n) + } + const button = document.getElementById("compute") + button.onclick = fib + } +); diff --git a/entries/adirar111/wasm/style.css b/entries/adirar111/wasm/style.css new file mode 100644 index 0000000..8ab403f --- /dev/null +++ b/entries/adirar111/wasm/style.css @@ -0,0 +1,27 @@ +html { + background: #5a46ee; + color: #fff; + font-family: "Source Code Pro" +} + +body { + display: flex; + flex-direction: column; + justify-content: center; + align-items: center; +} + +#input-area { + display: flex; + flex-direction: row; + justify-content: space-between; +} + +#input { + height: 40px; + font-size: 30px +} + +#result { + font-size: 50px +} diff --git a/entries/adirar111/y86/fib.ys b/entries/adirar111/y86/fib.s index 156c1ae..8aa62d2 100644 --- a/entries/adirar111/y86/fib.ys +++ b/entries/adirar111/y86/fib.s @@ -1,8 +1,13 @@ # y86 implementation of +# # def fibonacci(n): -# if n <= 1: -# return n -# return fibonacci(n-1) + fibonacci(n-2) +# if n <= 1: +# return n +# return fibonacci(n-1) + fibonacci(n-2) +# +# run it: +# * https://www.students.cs.ubc.ca/~cs-313/simulator/?arch=y86&impl=seq +# * https://www.eecs.yorku.ca/~jonatan/simulator/?arch=y86&impl=seq .pos 0 main: diff --git a/entries/fbanados/fib.st b/entries/fbanados/fib.st new file mode 100644 index 0000000..099407c --- /dev/null +++ b/entries/fbanados/fib.st @@ -0,0 +1,8 @@ +'From Pharo10.0.0 of 15 June 2022 [Build information: Pharo-10.0.0+build.521.sha.14f541319d443f4261f84f4fa19fbb34460a5edb (64 Bit)] on 24 October 2022 at 11:26:20.436554 am'! + +!Integer methodsFor: '*Fibonacci' stamp: 'FelipeBanados 10/24/2022 11:13'! +fibonacciNumber + self <= 2 ifTrue: [ ^ 1 ]. + ^ (self - 1) fibonacciNumber + (self - 2) fibonacciNumber. + +! ! diff --git a/entries/fbanados/fib.v b/entries/fbanados/fib.v new file mode 100644 index 0000000..e9fe796 --- /dev/null +++ b/entries/fbanados/fib.v @@ -0,0 +1,90 @@ +Require Import Coq.Arith.Wf_nat. (* import strong induction on naturals *) +Require Import Lia. (* Linear Integer Arithmetic solver *) + +(* First, simple specification *) + +Fixpoint fib_simpl (n : nat) {struct n} : nat := + match n with + | 0 => 1 + | S n => match n with + | 0 => 1 + | S m => fib_simpl n + fib_simpl m + end + end. + +Example fib_3 : (fib_simpl 2 = 2). reflexivity. Qed. +Example fib_4 : (fib_simpl 3 = 3). reflexivity. Qed. +Example fib_5 : (fib_simpl 4 = 5). reflexivity. Qed. + +Lemma fib_simpl_spec : forall n, (* useful lemma for rewriting *) + fib_simpl (S (S n)) = fib_simpl (S n) + fib_simpl n. +Proof. + destruct n. + - (* case n := 0 *) + reflexivity. + - (* case n := (S n) *) + destruct n; reflexivity. +Qed. + +(* For a (slightly) faster version *) + +Fixpoint fib_acc_aux (n : nat) (acc : nat) (prev : nat) {struct n} : nat := + match n with + | 0 => acc + prev + | S n => fib_acc_aux n (acc + prev) acc + end. + +Definition fib_faster (n : nat) : nat := + match n with + | 0 => 1 + | S n => match n with + | 0 => 1 + | S m => (fib_acc_aux m 1 1) + end + end. + +Example fib_faster_3 : (fib_faster 2 = 2). reflexivity. Qed. +Example fib_faster_4 : (fib_faster 3 = 3). reflexivity. Qed. +Example fib_faster_5 : (fib_faster 4 = 5). reflexivity. Qed. + +Lemma fib_acc_aux_rewrite : forall n a b c d, + fib_acc_aux n a c + fib_acc_aux n b d = fib_acc_aux n (a + b) (c + d). +Proof. + induction n; intros. + - (* case n := 0 *) + simpl; lia. + - (* case n := (S n) *) + simpl. + rewrite IHn. + f_equal. + lia. +Qed. + +Theorem fib_faster_spec: forall n, fib_simpl n = fib_faster n. +Proof. + induction n using lt_wf_ind. (* use strong induction *) + rename H into strong_induction_hypothesis. + destruct n. (* lt_wf_ind does not deal immediately with cases *) + - (* case n := 0 *) + reflexivity. + - (* case n := (S n) *) + destruct n. + + (* case n := 1 *) + reflexivity. + + (* case n := (S (S n)) *) + rewrite ?fib_simpl_spec. + do 2 rewrite strong_induction_hypothesis by lia. + enough (forall n, fib_faster (S n) + fib_faster n = fib_faster (S (S n))) as lemma by apply lemma. + clear. + destruct n. + * (* for lemma, case n := 0 *) + reflexivity. + * (* for lemma, case n := S n *) + destruct n. + -- (* for lemma, case n := 1 *) + reflexivity. + -- (* for lemma, case n := S (S n) *) + simpl. + apply fib_acc_aux_rewrite. +Qed. + diff --git a/entries/funemy/.gitignore b/entries/funemy/.gitignore new file mode 100644 index 0000000..acb903a --- /dev/null +++ b/entries/funemy/.gitignore @@ -0,0 +1,3 @@ +.DS_Store +*.agdai +*.smt2 diff --git a/entries/funemy/agda/fib1.agda b/entries/funemy/agda/fib1.agda new file mode 100644 index 0000000..d8931a0 --- /dev/null +++ b/entries/funemy/agda/fib1.agda @@ -0,0 +1,34 @@ +open import Agda.Builtin.Equality + +data Nat : Set where + zero : Nat + suc : Nat -> Nat + +{-# BUILTIN NATURAL Nat #-} + +z : Nat +z = zero + +one : Nat +one = suc zero + +add : Nat → Nat → Nat +add zero y = y +add (suc x) y = suc (add x y) + +fib : Nat → Nat +fib zero = zero +fib (suc zero) = suc zero +fib (suc (suc x)) = add (fib x) (fib (suc x)) + +fib0 : fib 0 ≡ 0 +fib0 = refl + +fib1 : fib 1 ≡ 1 +fib1 = refl + +fib2 : fib 2 ≡ 1 +fib2 = refl + +fib8 : fib 8 ≡ 21 +fib8 = refl diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh new file mode 100755 index 0000000..07ab418 --- /dev/null +++ b/entries/funemy/z3/z3fib.sh @@ -0,0 +1,57 @@ +#!/bin/bash + +# Instructions: +# 1. having z3 installed and put under your $PATH +# 2. making sure z3fib.sh is executable, by `chmod +x z3fib.sh` +# 3. running as `./z3fib.sh [length of the fib sequence]` +# 4. having fun :) + +if [ -e fib.smt2 ] +then + rm -f fib.smt2 + touch fib.smt2 +else + touch fib.smt2 +fi + +if [ "$1" -lt "0" ]; then + echo "Argument must be larger than 0." + exit 1 +fi + +for i in $(seq 0 $1); +do + echo "(declare-const x$i Int)" >> fib.smt2 +done + +echo "" >> fib.smt2 + +echo "(assert" >> fib.smt2 +echo " (and" >> fib.smt2 + +for i in $(seq 0 $1); +do + echo " (>= x$i 0)" >> fib.smt2 +done + +echo " (= x0 0)" >> fib.smt2 +if [ "$1" -ge "1" ]; then + echo " (= x1 1)" >> fib.smt2 +fi + +if [ "$1" -ge "2" ]; then + for i in $(seq 2 $1); + do + echo " (= x$i (+ x$(($i - 2)) x$(($i - 1))))" >> fib.smt2 + done +fi + +echo " )" >> fib.smt2 +echo ")" >> fib.smt2 + +echo "" >> fib.smt2 + +echo "(check-sat)" >> fib.smt2 +echo "(get-model)" >> fib.smt2 + +z3 fib.smt2 diff --git a/entries/ionathanch/Fib.agda b/entries/ionathanch/Fib.agda new file mode 100644 index 0000000..a12b0a5 --- /dev/null +++ b/entries/ionathanch/Fib.agda @@ -0,0 +1,19 @@ + +open import Agda.Builtin.Nat +open import Agda.Builtin.List +open import Agda.Builtin.Reflection + +data Fib : Nat → Nat → Set where + instance F0 : Fib 0 0 + instance F1 : Fib 1 1 + instance Fk : ∀ {k n m} → ⦃ Fib k n ⦄ → ⦃ Fib (suc k) m ⦄ → Fib (suc (suc k)) (n + m) + +fib' : ∀ k {n} → ⦃ Fib k n ⦄ → Nat +fib' k {n} ⦃ fib ⦄ = n + +macro + fib : Term → Term → TC _ + fib t hole = unify hole (def (quote fib') (arg i t ∷ [])) + where i = arg-info visible (modality relevant quantity-ω) + +{- Get the [n]th Fibonacci number by normalization via C-n `fib [n]`. -} diff --git a/entries/ionathanch/fib.f90 b/entries/ionathanch/fib.f90 new file mode 100644 index 0000000..3cf1850 --- /dev/null +++ b/entries/ionathanch/fib.f90 @@ -0,0 +1,21 @@ +PROGRAM main + ! The 93rd Fibonacci number is the largest that fits in 64 bits anyway + CHARACTER(3) :: kth + INTEGER :: k + CALL get_command_argument(1, kth) + READ(kth, *) k + WRITE(*, *) fib(k) +CONTAINS + +PURE RECURSIVE INTEGER*8 FUNCTION fib(k) RESULT(n) + INTEGER, INTENT (IN) :: k + IF (k == 0) THEN + n = 0 + ELSE IF (k == 1) THEN + n = 1 + ELSE + n = fib(k - 1) + fib(k - 2) + END IF +END FUNCTION fib + +END PROGRAM diff --git a/entries/jyoo980/scala/Fib.scala b/entries/jyoo980/scala/Fib.scala index 05bdd1e..f9107b0 100644 --- a/entries/jyoo980/scala/Fib.scala +++ b/entries/jyoo980/scala/Fib.scala @@ -1,4 +1,4 @@ -def fib(n: Int) = +def fib(n: Int): Int = (0 until n).foldLeft((0, 1)) { case ((prev, curr), _) => (curr, prev + curr) } match { diff --git a/entries/laelath/fib.bf b/entries/laelath/fib.bf new file mode 100644 index 0000000..ff7d67a --- /dev/null +++ b/entries/laelath/fib.bf @@ -0,0 +1,3 @@ +>101p011p&:v:-1 < + v+g11g10_11g.@ + >11g01p11p ^ diff --git a/entries/lizard-business/fib.dats b/entries/lizard-business/fib.dats new file mode 100644 index 0000000..f6bd5a1 --- /dev/null +++ b/entries/lizard-business/fib.dats @@ -0,0 +1,25 @@ +#include "share/atspre_define.hats" +#include "share/atspre_staload.hats" + +dataprop is_fib(int, int) = +| F0(0, 0) | F1(1, 1) +| {i, m, n : nat} Fplus(i + 2, m + n) of (is_fib(i, m), is_fib(i + 1, n)) + +typedef fib(i : int) = [n : nat] (is_fib(i, n) | int(n)) + + +fun fib {t : nat} .<>. (t : int(t)) :<> fib(t) = +let + fun go {m, n, i : nat | i <= t} .<t - i>. + (M : is_fib(i, m), N : is_fib(i + 1, n) | + m : int(m), n : int(n), i : int(i)) :<> + fib(t) = + if i = t then (M | m) + else go(N, Fplus(M, N) | n, m + n, i + 1) +in + go(F0, F1 | 0, 1, 0) +end + +fun fib_(i : Nat) : Nat = let val (_ | res) = fib(i) in res end + +implement main0 () = println!("fib(15) = ", fib_(15)) diff --git a/entries/lizard-business/fib.maude b/entries/lizard-business/fib.maude new file mode 100644 index 0000000..20bc428 --- /dev/null +++ b/entries/lizard-business/fib.maude @@ -0,0 +1,27 @@ +smod FIB is + pr LIST{Nat} . + + vars M N : Nat . + var Ns : List{Nat} . + + rl [start]: nil => 0 1 . + rl [next]: Ns M N => Ns M N (M + N) . + rl [drop] : Ns N => N . + + strats fib fibgo : Nat @ List{Nat} . + sd fib(N) := start ; fibgo(N) . + sd fibgo(0) := top(drop) . + sd fibgo(s(N)) := top(next) ; fibgo(N) . +endsm + +***( + Maude> srew nil using fib(10) . + srewrite in FIB : nil using fib(10) . + + Solution 1 + rewrites: 8330 in 12ms cpu (12ms real) (694166 rewrites/second) + result NzNat: 89 + + No more solutions. + rewrites: 8469 in 12ms cpu (13ms real) (705750 rewrites/second) +) diff --git a/entries/margoseltzer/efficiency.c b/entries/margoseltzer/efficiency.c new file mode 100644 index 0000000..6e017f3 --- /dev/null +++ b/entries/margoseltzer/efficiency.c @@ -0,0 +1,23 @@ +unsigned long foo(unsigned long n) { + if (n < 2) return (n); + return(foo(n - 1) + foo(n - 2)); +} + +// Efficiency of expression + +unsigned long bar(unsigned long n) { + unsigned long i, last; + unsigned long sum, tmp; + + if (n < 2) return (n); + last = 0; + sum = 1; + for (i = 2; i <= n; i++) { + tmp = sum; + sum += last; + last = tmp; + } + return (sum); +} + +// Efficiency in resource utilization diff --git a/entries/meghasinghania22/bash/script.sh b/entries/meghasinghania22/bash/script.sh new file mode 100644 index 0000000..0cbba4d --- /dev/null +++ b/entries/meghasinghania22/bash/script.sh @@ -0,0 +1,27 @@ +#!/bin/bash +int_regex='^[0-9]+$' +function fib(){ + if [ "$1" -le 1 ]; then + echo $1 + else + echo $[`fib $[$1 - 1]` + `fib $[$1 - 2]` ] + fi +} + +function main(){ + echo -n "Enter a whole number: " + read num + + if [ -z "$num" ]; then + echo "Uh oh! Argument required!" + elif ! [[ "$num" =~ $int_regex ]]; then + echo "Uh oh! Argument must be a number :|" + elif [ "$num" -lt 0 ]; then + echo "Uh oh! Argument must be a whole number :|" + else + fib $num + fi + +} + +main
\ No newline at end of file diff --git a/entries/nritschel/assets/scratch.png b/entries/nritschel/assets/scratch.png Binary files differnew file mode 100644 index 0000000..5883245 --- /dev/null +++ b/entries/nritschel/assets/scratch.png diff --git a/entries/nritschel/fib-java/fib.iml b/entries/nritschel/fib-java/fib.iml new file mode 100644 index 0000000..815e958 --- /dev/null +++ b/entries/nritschel/fib-java/fib.iml @@ -0,0 +1,13 @@ +<?xml version="1.0" encoding="UTF-8"?> +<module type="JAVA_MODULE" version="4"> + <component name="NewModuleRootManager" inherit-compiler-output="true"> + <exclude-output /> + <content url="file://$MODULE_DIR$"> + <sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" /> + </content> + <orderEntry type="inheritedJdk" /> + <orderEntry type="sourceFolder" forTests="false" /> + <orderEntry type="module-library"> + </orderEntry> + </component> +</module>
\ No newline at end of file diff --git a/entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java b/entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java new file mode 100644 index 0000000..5c404e8 --- /dev/null +++ b/entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java @@ -0,0 +1,13 @@ +import java.util.HashMap; + +public class CachedFibonacciNumberFactory implements FibonacciNumberFactory { + private final HashMap<Integer, FibonacciNumber> cachedNumbers = new HashMap<>(); + + @Override + public FibonacciNumber getFibonacciNumber(int num) { + if (!cachedNumbers.containsKey(num)) { + cachedNumbers.put(num, new FibonacciNumber(num)); + } + return cachedNumbers.get(num); + } +} diff --git a/entries/nritschel/fib-java/src/FibonacciCalculator.java b/entries/nritschel/fib-java/src/FibonacciCalculator.java new file mode 100644 index 0000000..8806c20 --- /dev/null +++ b/entries/nritschel/fib-java/src/FibonacciCalculator.java @@ -0,0 +1,3 @@ +public interface FibonacciCalculator { + public int calculateFibonacci(FibonacciNumber fib); +} diff --git a/entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java b/entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java new file mode 100644 index 0000000..7bb5ee9 --- /dev/null +++ b/entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java @@ -0,0 +1,17 @@ +public class FibonacciCalculatorImpl implements FibonacciCalculator { + private final FibonacciNumberFactory factory; + + public FibonacciCalculatorImpl(FibonacciNumberFactory factory) { + this.factory = factory; + } + + @Override + public int calculateFibonacci(FibonacciNumber fib) { + if (fib.getNumber() <= 2) { + return 1; + } + else { + return factory.getFibonacciNumber(fib.getNumber() - 1).calculate(this) + factory.getFibonacciNumber(fib.getNumber() - 2).calculate(this); + } + } +} diff --git a/entries/nritschel/fib-java/src/FibonacciNumber.java b/entries/nritschel/fib-java/src/FibonacciNumber.java new file mode 100644 index 0000000..fc9381f --- /dev/null +++ b/entries/nritschel/fib-java/src/FibonacciNumber.java @@ -0,0 +1,19 @@ +public class FibonacciNumber { + private final int number; + private Integer result; + + public FibonacciNumber(int number) { + this.number = number; + } + + public int getNumber() { + return number; + } + + public int calculate(FibonacciCalculator calculator) { + if (result == null) { + result = calculator.calculateFibonacci(this); + } + return result; + } +} diff --git a/entries/nritschel/fib-java/src/FibonacciNumberFactory.java b/entries/nritschel/fib-java/src/FibonacciNumberFactory.java new file mode 100644 index 0000000..42ef6c2 --- /dev/null +++ b/entries/nritschel/fib-java/src/FibonacciNumberFactory.java @@ -0,0 +1,3 @@ +public interface FibonacciNumberFactory { + public FibonacciNumber getFibonacciNumber(int num); +} diff --git a/entries/nritschel/fib-java/src/Main.java b/entries/nritschel/fib-java/src/Main.java new file mode 100644 index 0000000..8ae46f1 --- /dev/null +++ b/entries/nritschel/fib-java/src/Main.java @@ -0,0 +1,21 @@ +public class Main { + public static void main(String[] args) { + if (args.length < 1) { + System.out.println(""" + Please provide: + 1. fibonacci number to compute, and + 2. (optional) the calculation method (naive or cached)."""); + } + else { + FibonacciNumberFactory factory; + if (args.length >= 2 && args[1].equals("naive")) { + factory = new NaiveFibonacciNumberFactory(); + } + else { + factory = new CachedFibonacciNumberFactory(); + } + FibonacciCalculator calculator = new FibonacciCalculatorImpl(factory); + System.out.println(factory.getFibonacciNumber(Integer.parseInt(args[0])).calculate(calculator)); + } + } +} diff --git a/entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java b/entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java new file mode 100644 index 0000000..5185a8b --- /dev/null +++ b/entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java @@ -0,0 +1,6 @@ +public class NaiveFibonacciNumberFactory implements FibonacciNumberFactory { + @Override + public FibonacciNumber getFibonacciNumber(int num) { + return new FibonacciNumber(num); + } +} diff --git a/entries/nritschel/scratch/README.md b/entries/nritschel/scratch/README.md new file mode 100644 index 0000000..e059267 --- /dev/null +++ b/entries/nritschel/scratch/README.md @@ -0,0 +1 @@ +<img src="../assets/scratch.png" alt="scratch preview">
\ No newline at end of file diff --git a/entries/nritschel/scratch/fib.sb3 b/entries/nritschel/scratch/fib.sb3 Binary files differnew file mode 100644 index 0000000..a3cf2cc --- /dev/null +++ b/entries/nritschel/scratch/fib.sb3 diff --git a/entries/nritschel/xlsx/fib.xlsx b/entries/nritschel/xlsx/fib.xlsx Binary files differnew file mode 100644 index 0000000..e1b662d --- /dev/null +++ b/entries/nritschel/xlsx/fib.xlsx diff --git a/entries/nxjfxu/fib.hs b/entries/nxjfxu/fib.hs new file mode 100644 index 0000000..0f0d871 --- /dev/null +++ b/entries/nxjfxu/fib.hs @@ -0,0 +1,5 @@ +fib :: Int -> Int +fib = (fibs !!) + where + fibs = 0 : 1 : [fibs !! (i - 2) + fibs !! (i - 1) | i <- [2..]] + diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy new file mode 100644 index 0000000..d625d68 --- /dev/null +++ b/entries/perryliao/fib.groovy @@ -0,0 +1,50 @@ +pipeline { + agent any + + parameters { + string defaultValue: '2', description: 'Number to compute in the Fibonacci Sequence', name: 'num', trim: true + } + + stages { + stage('Validate Parameter') { + steps { + script { + assert params.num.isInteger() + } + } + } + stage('Create Cache') { + steps { + script { + if (!fileExists("fibCache")) { + sh 'echo "0\n1" > fibCache' + } + } + } + } + stage('Get Fibbonacci') { + steps { + script { + nComputed = sh(returnStdout: true, script: "wc -l < fibCache").trim().toInteger() + result = fib(params.num.toInteger()) + println("The result is F(${params.num}) = ${result}") + } + } + } + } +} + +def nComputed + +int fib(int n, cache = 'fibCache') { + if (n >= nComputed) { + // Need to do more recursion + result = fib(n - 2, cache) + fib(n - 1, cache) + nComputed++ + sh "echo '${result}' >> ${cache}" + return result + } else { + // Already have what we need, so read from cache + return sh(returnStdout: true, script: "sed -n '${n + 1}p' ${cache}").toInteger() + } +} diff --git a/entries/pkoronkevich/tex/README.md b/entries/pkoronkevich/tex/README.md new file mode 100644 index 0000000..225773b --- /dev/null +++ b/entries/pkoronkevich/tex/README.md @@ -0,0 +1 @@ +<img src="./render.png" alt="fib.tex preview">
\ No newline at end of file diff --git a/entries/pkoronkevich/tex/fib.tex b/entries/pkoronkevich/tex/fib.tex new file mode 100644 index 0000000..cef9138 --- /dev/null +++ b/entries/pkoronkevich/tex/fib.tex @@ -0,0 +1,29 @@ +\documentclass[11pt]{article} +\usepackage[fleqn]{amsmath} + +\newcommand{\one}{\lambda f . \lambda x . f \ x} +\newcommand{\two}{\lambda f . \lambda x . f \ (f \ x)} +\newcommand{\tru}{\lambda x . \lambda y . x} +\newcommand{\flse}{\lambda x . \lambda y . y} +\newcommand{\isz}{\lambda n . n \ (\lambda c . \flse) \ \tru} +\newcommand{\ife}{\lambda p . \lambda a . \lambda b . p \ a \ b} +\newcommand{\suc}{\lambda n . \lambda f . \lambda x . f \ (n \ f \ x)} +\newcommand{\plus}{\lambda m . \lambda n . m \ (\suc) \ n} +\newcommand{\pred}{\lambda n . \lambda f . \lambda x . n \ (\lambda g . \lambda h . h \ (g \ f)) \ (\lambda u . x) \ (\lambda u . u)} +\newcommand{\sub}{\lambda m . \lambda n . n \ (\pred) \ m} +\newcommand{\lleq}{\lambda m . \lambda n . \\ \qquad \isz \ ((\sub) \\ \qquad \ m \ n)} +\newcommand{\fix}{\lambda g . (\lambda x . g \ (x \ x)) \ (\lambda x . g \ (x \ x))} +\newcommand{\appo}[2]{#1 \ #2} +\newcommand{\appt}[3]{#1 \ #2 \ #3} + +\begin{document} +\begin{gather*} + \fix \\ % recursive function application + \quad \lambda r . \lambda n . (\ife) \\ % of fib, which takes itself and n, if expression + \quad \ \appt{(\lleq)}{n}{\one} \\ % if n less than or equal to one + \quad \ (\one) \\ % if so, return 1 + \quad \ (\plus) \\ % if not, add + \qquad \appo{r}{(\appo{(\pred)}{n})} \\ % the first recursive call, n - 1, to + \qquad \appo{r}{(\appt{(\sub)}{n}{\two})} % the second recursive call, n - 2 +\end{gather*} +\end{document} diff --git a/entries/pkoronkevich/tex/render.pdf b/entries/pkoronkevich/tex/render.pdf Binary files differnew file mode 100644 index 0000000..8ee60c7 --- /dev/null +++ b/entries/pkoronkevich/tex/render.pdf diff --git a/entries/pkoronkevich/tex/render.png b/entries/pkoronkevich/tex/render.png Binary files differnew file mode 100644 index 0000000..a1896a2 --- /dev/null +++ b/entries/pkoronkevich/tex/render.png diff --git a/entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc b/entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc new file mode 100644 index 0000000..939529d --- /dev/null +++ b/entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc @@ -0,0 +1,8 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> +<plist version="1.0"> +<dict> + <key>URL</key> + <string>https://stackoverflow.com/a/55764043</string> +</dict> +</plist> diff --git a/entries/rxg/fib.rkt b/entries/rxg/fib.rkt new file mode 100644 index 0000000..61373cd --- /dev/null +++ b/entries/rxg/fib.rkt @@ -0,0 +1,132 @@ +#lang racket + +;; fib.rkt - A variety of iterative implementations of the Fibonacci Sequence +;; All are based on accumulators + +;; Natural -> Natural +;; produce the n'th Fibonacci number +(define (fib-iter n) + (cond + [(= n 0) 1] + [(= n 1) 1] + [else + (let-values ([(n-2 n-1) + ;; i-2 = fib (i-2) + ;; i-1 = fib (i-1) + (for/fold ([i-2 1] [i-1 1]) + ([i (in-range 2 n)]) + (values i-1 (+ i-2 i-1)))]) + (+ n-2 n-1))])) + + +(define (fib-iter2 n) + (cond + [(= n 0) 1] + [(= n 1) 1] + [else + ;; i-2 = fib (i-2) + ;; i-1 = fib (i-1) + (let loop ([i-2 1] [i-1 1] [i 2]) + (if (= i n) + (+ i-2 i-1) + (loop i-1 (+ i-2 i-1) (add1 i))))])) + +(define (fib-iter3 n) + (cond + [(= n 0) 1] + [(= n 1) 1] + [else + ;; i-2 = fib (i-2) + ;; i-1 = fib (i-1) + (do ([i-2 1 i-1] + [i-1 1 (+ i-2 i-1)] + [i 2 (add1 i)]) + [(= i n) + (+ i-2 i-1)])])) + +;; New variant of for with accumulators and a final expression in terms of +;; the accumulators +(define-syntax (for/acc stx) + (syntax-case stx () + [(_ ([id* init*] ...) + (clauses ...) + body + result) + (with-syntax ([original stx]) + #'(let-values ([(id* ...) + (for/fold/derived original + ([id* init*] ...) + (clauses ...) + body)]) + result))])) + +(define (fib-iter4 n) + (cond + [(= n 0) 1] + [(= n 1) 1] + [else + ;; i-2 = fib (i-2) + ;; i-1 = fib (i-1) + (for/acc ([i-2 1] [i-1 1]) + ([i (in-range 2 n)]) + (values i-1 (+ i-2 i-1)) + (+ i-2 i-1))])) + +;; New variant of for with accumulators and a final expression in terms of +;; the accumulators +(define-syntax (for/do stx) + (syntax-case stx () + [(_ ([id* init* step*] ...) + (clauses ...) + result) + (with-syntax ([original stx]) + #'(let-values ([(id* ...) + (for/fold/derived original + ([id* init*] ...) + (clauses ...) + (values step* ...))]) + result))])) + +(define (fib-iter5 n) + (cond + [(= n 0) 1] + [(= n 1) 1] + [else + ;; i-2 = fib (i-2) + ;; i-1 = fib (i-1) + (for/do ([i-2 1 i-1] [i-1 1 (+ i-2 i-1)]) + ([i (in-range 2 n)]) + (+ i-2 i-1))])) + + +;; Fibonacci's problem, as described by Greg Rawlins in "Compared to What": +;; Suppose you have a pair of rabbits and suppose every month each pair +;; bears a new pair that from the second month on becomes productive. +;; how many pairs of rabbits will you have in a year? + +;; Analysis: +;; - At time 0 you have 1 unproductive pair: 1 pair, 0 productive pairs +;; - Each month, each productive pair produces an unproductive pair +;; - Each month, last months unproductive pairs transition to productive +;; - how many pairs are there at time step 12? + +;; The following function solves the problem *directly* as a +;; structural recursion over natural numbers with two +;; accumulators (for lost context (fertile) and result-so-far (total)) + +;; Natural -> Natural +;; produce the solution to Fibonacci's problem after n months +(define (fib-rabbit n0) + ;; Accumulator: total is Natural + ;; Invariant: total pairs of rabbits after (- n0 n) months + ;; Accumulator: fertile is Natural + ;; Invariant: productive pairs of rabbits after (- n0 n) months + (local [(define (fib-acc fertile total n) + (cond [(zero? n) total] + [else + (fib-acc total ;; next month, all will be productive + (+ ;; next months pairs include: + total ;; - this months pairs plus + fertile) ;; - offspring from productive pairs + (sub1 n))]))] + (fib-acc 0 1 n0))) diff --git a/entries/shayanh/matrix.go b/entries/shayanh/matrix.go new file mode 100644 index 0000000..3f374cb --- /dev/null +++ b/entries/shayanh/matrix.go @@ -0,0 +1,40 @@ +package main + +type fibmat [2][2]int + +func matmul(m1 fibmat, m2 fibmat) (m3 fibmat) { + for i := 0; i < 2; i++ { + for j := 0; j < 2; j++ { + for k := 0; k < 2; k++ { + m3[i][j] += m1[i][k] * m2[k][j] + } + } + } + return +} + +func matpow(m fibmat, n int) fibmat { + if n == 0 { + return [2][2]int{ + {1, 0}, + {0, 1}, + } + } else if n%2 == 0 { + t := matpow(m, n/2) + return matmul(t, t) + } else { + t := matpow(m, n-1) + return matmul(t, m) + } +} + +func fib(n int) int { + m := matpow( + [2][2]int{ + {1, 1}, + {1, 0}, + }, + n, + ) + return m[0][1] +} diff --git a/entries/wilbowma/fib-lang b/entries/wilbowma/fib-lang new file mode 160000 +Subproject 2ec2d1dfd141220882d824cf3dac5b374ed291f diff --git a/entries/zgrannan/Fib.hs b/entries/zgrannan/Fib.hs new file mode 100644 index 0000000..1918fc8 --- /dev/null +++ b/entries/zgrannan/Fib.hs @@ -0,0 +1,18 @@ +-- Point-less fibonacci +fib :: Int -> Int +fib = fix fib' + where + fib' = + ap (when 0 . (0 ==)) . + ap (when 1 . (1 ==)) . + ap (ap . ((+) .) . (. subtract 1)) (. subtract 2) + + when t c e = if c then t else e + + ap mf m = mf >>= (\f -> m >>= return . f) + + fix f = f (fix f) + + +main :: IO () +main = mapM_ (print . fib) [0 .. 10] |
