From 9d6f7b9b5123c6e6d8d5a13ee3f4b5f63a0cf663 Mon Sep 17 00:00:00 2001 From: James Yoo Date: Sun, 23 Oct 2022 14:36:19 -0700 Subject: Adding return type to fib function --- entries/jyoo980/scala/Fib.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'entries') 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 { -- cgit v1.2.3-70-g09d2 From 0cf22c94832a4ae44536b25ec5d5c0e2132b1069 Mon Sep 17 00:00:00 2001 From: Christopher Powroznik Date: Sun, 23 Oct 2022 14:37:15 -0700 Subject: fixed duplicated calculation --- entries/Metroxe/index.html | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'entries') 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"); -- cgit v1.2.3-70-g09d2 From 72c87a2aafa2bd98952494463353b2a48c1a06f5 Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 15:30:17 -0700 Subject: boring one --- entries/funemy/.gitignore | 1 + entries/funemy/agda/fib1.agda | 36 ++++++++++++++++++++++++++++++++++++ 2 files changed, 37 insertions(+) create mode 100644 entries/funemy/.gitignore create mode 100644 entries/funemy/agda/fib1.agda (limited to 'entries') diff --git a/entries/funemy/.gitignore b/entries/funemy/.gitignore new file mode 100644 index 0000000..171a389 --- /dev/null +++ b/entries/funemy/.gitignore @@ -0,0 +1 @@ +*.agdai diff --git a/entries/funemy/agda/fib1.agda b/entries/funemy/agda/fib1.agda new file mode 100644 index 0000000..9e7f82a --- /dev/null +++ b/entries/funemy/agda/fib1.agda @@ -0,0 +1,36 @@ +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 + + -- cgit v1.2.3-70-g09d2 From bbde9e43c3503e6d4ae2e180a6ac01305744ae68 Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Sun, 23 Oct 2022 16:01:40 -0700 Subject: rename to `.s` --- entries/adirar111/y86/fib.s | 56 ++++++++++++++++++++++++++++++++++++++++++++ entries/adirar111/y86/fib.ys | 56 -------------------------------------------- 2 files changed, 56 insertions(+), 56 deletions(-) create mode 100644 entries/adirar111/y86/fib.s delete mode 100644 entries/adirar111/y86/fib.ys (limited to 'entries') diff --git a/entries/adirar111/y86/fib.s b/entries/adirar111/y86/fib.s new file mode 100644 index 0000000..156c1ae --- /dev/null +++ b/entries/adirar111/y86/fib.s @@ -0,0 +1,56 @@ +# y86 implementation of +# def fibonacci(n): +# if n <= 1: +# return n +# return fibonacci(n-1) + fibonacci(n-2) + +.pos 0 +main: +irmovq stack, %rsp # initialize stack pointer +irmovq $13, %rdi # %rdi = n +call fib # fib(n) +halt + + +fib: +irmovq $2, %rsi +irmovq $1, %rdx +rrmovq %rdi, %rcx +rrmovq %rdi, %r8 + +subq %rsi, %rcx # %rcx = n-2 +subq %rdx, %r8 # %r8 = n-1 +jle base # goto base if n <= 1 + +recursed: +# save to stack +pushq %r8 # %r8 = n-1 + +# recurse +rrmovq %rcx, %rdi # %rdi = n-2 +call fib # fib(n-2) + +# restore from stack +popq %r8 # %r8 = n-1 + +# save to stack +pushq %rax # %rax = fib(n-2) + +# recurse +rrmovq %r8, %rdi # %rdi = n-1 +call fib # fib(n-1) + +# restore from stack +popq %r10 # r10 = fib(n-2) + +addq %r10, %rax # %rax = fib(n-2) + fib(n-1) +jmp end + +base: +rrmovq %rdi, %rax # return n + +end: +ret + +.pos 0x1000 +stack: diff --git a/entries/adirar111/y86/fib.ys b/entries/adirar111/y86/fib.ys deleted file mode 100644 index 156c1ae..0000000 --- a/entries/adirar111/y86/fib.ys +++ /dev/null @@ -1,56 +0,0 @@ -# y86 implementation of -# def fibonacci(n): -# if n <= 1: -# return n -# return fibonacci(n-1) + fibonacci(n-2) - -.pos 0 -main: -irmovq stack, %rsp # initialize stack pointer -irmovq $13, %rdi # %rdi = n -call fib # fib(n) -halt - - -fib: -irmovq $2, %rsi -irmovq $1, %rdx -rrmovq %rdi, %rcx -rrmovq %rdi, %r8 - -subq %rsi, %rcx # %rcx = n-2 -subq %rdx, %r8 # %r8 = n-1 -jle base # goto base if n <= 1 - -recursed: -# save to stack -pushq %r8 # %r8 = n-1 - -# recurse -rrmovq %rcx, %rdi # %rdi = n-2 -call fib # fib(n-2) - -# restore from stack -popq %r8 # %r8 = n-1 - -# save to stack -pushq %rax # %rax = fib(n-2) - -# recurse -rrmovq %r8, %rdi # %rdi = n-1 -call fib # fib(n-1) - -# restore from stack -popq %r10 # r10 = fib(n-2) - -addq %r10, %rax # %rax = fib(n-2) + fib(n-1) -jmp end - -base: -rrmovq %rdi, %rax # return n - -end: -ret - -.pos 0x1000 -stack: -- cgit v1.2.3-70-g09d2 From bdd284352a0cff33cff2fdc88b154301b63b2306 Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Sun, 23 Oct 2022 16:04:16 -0700 Subject: links to try --- entries/adirar111/y86/fib.s | 3 +++ 1 file changed, 3 insertions(+) (limited to 'entries') diff --git a/entries/adirar111/y86/fib.s b/entries/adirar111/y86/fib.s index 156c1ae..eae74fe 100644 --- a/entries/adirar111/y86/fib.s +++ b/entries/adirar111/y86/fib.s @@ -3,6 +3,9 @@ # 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: -- cgit v1.2.3-70-g09d2 From 7e1694ced1cfce43f79cb4641781d91ebcc15e90 Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Sun, 23 Oct 2022 16:07:58 -0700 Subject: indent comment --- entries/adirar111/y86/fib.s | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'entries') diff --git a/entries/adirar111/y86/fib.s b/entries/adirar111/y86/fib.s index eae74fe..8aa62d2 100644 --- a/entries/adirar111/y86/fib.s +++ b/entries/adirar111/y86/fib.s @@ -1,8 +1,10 @@ # 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 -- cgit v1.2.3-70-g09d2 From 679ee8faf561b6e53f582edef2d93b65615bcea7 Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 16:14:40 -0700 Subject: z3 fib impl --- entries/funemy/.gitignore | 2 ++ entries/funemy/agda/fib1.agda | 2 -- entries/funemy/z3/z3fib.sh | 48 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 50 insertions(+), 2 deletions(-) create mode 100755 entries/funemy/z3/z3fib.sh (limited to 'entries') diff --git a/entries/funemy/.gitignore b/entries/funemy/.gitignore index 171a389..acb903a 100644 --- a/entries/funemy/.gitignore +++ b/entries/funemy/.gitignore @@ -1 +1,3 @@ +.DS_Store *.agdai +*.smt2 diff --git a/entries/funemy/agda/fib1.agda b/entries/funemy/agda/fib1.agda index 9e7f82a..d8931a0 100644 --- a/entries/funemy/agda/fib1.agda +++ b/entries/funemy/agda/fib1.agda @@ -32,5 +32,3 @@ 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..fdc8937 --- /dev/null +++ b/entries/funemy/z3/z3fib.sh @@ -0,0 +1,48 @@ +#!/bin/bash + +# Instruction: +# 1. having z3 installed and under you $PATH +# 2. making sure z3fib.sh is executable, by `chmod +x z3fib.sh` +# 3. run 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 + +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 +echo " (= x1 1)" >> fib.smt2 + +for i in $(seq 2 $1); +do + echo " (= x$i (+ x$(($i - 2)) x$(($i - 1))))" >> fib.smt2 +done + +echo " )" >> fib.smt2 +echo ")" >> fib.smt2 + +echo "" >> fib.smt2 + +echo "(check-sat)" >> fib.smt2 +echo "(get-model)" >> fib.smt2 + +z3 fib.smt2 -- cgit v1.2.3-70-g09d2 From a89c7847195a7b20e307b042fbc821e741ccdaa4 Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 16:16:41 -0700 Subject: minor --- entries/funemy/z3/z3fib.sh | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'entries') diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh index fdc8937..9faa228 100755 --- a/entries/funemy/z3/z3fib.sh +++ b/entries/funemy/z3/z3fib.sh @@ -3,7 +3,7 @@ # Instruction: # 1. having z3 installed and under you $PATH # 2. making sure z3fib.sh is executable, by `chmod +x z3fib.sh` -# 3. run as `./z3fib.sh [length of the fib sequence]` +# 3. running as `./z3fib.sh [length of the fib sequence]` # 4. having fun :) if [ -e fib.smt2 ] -- cgit v1.2.3-70-g09d2 From 760fb3275b2af023d099a8c1e2a143cab41c5c6b Mon Sep 17 00:00:00 2001 From: Jonathan Chan Date: Sun, 23 Oct 2022 16:17:39 -0700 Subject: Create Fib.agda --- entries/ionchy/agda/Fib.agda | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) create mode 100644 entries/ionchy/agda/Fib.agda (limited to 'entries') diff --git a/entries/ionchy/agda/Fib.agda b/entries/ionchy/agda/Fib.agda new file mode 100644 index 0000000..a12b0a5 --- /dev/null +++ b/entries/ionchy/agda/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]`. -} -- cgit v1.2.3-70-g09d2 From 8c3619fcb5e01b14eeab69bfa8c88cd75ed16ac9 Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Sun, 23 Oct 2022 16:28:11 -0700 Subject: Make Jon's work/description consistent with everyone else --- README.md | 3 +++ entries/ionathanch/agda/Fib.agda | 19 +++++++++++++++++++ entries/ionchy/agda/Fib.agda | 19 ------------------- 3 files changed, 22 insertions(+), 19 deletions(-) create mode 100644 entries/ionathanch/agda/Fib.agda delete mode 100644 entries/ionchy/agda/Fib.agda (limited to 'entries') diff --git a/README.md b/README.md index e2c309e..d126e3b 100644 --- a/README.md +++ b/README.md @@ -15,6 +15,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G +### [`ionathanch`](https://github.com/ionathanch) +- [`agda`](./entries/ionathanch/agda/Fib.agda) + ### [`funemy`](https://github.com/funemy) - [`agda`](./entries/funemy/agda/fib1.agda) - [`z3`](./entries/funemy/z3/z3fib.sh) diff --git a/entries/ionathanch/agda/Fib.agda b/entries/ionathanch/agda/Fib.agda new file mode 100644 index 0000000..a12b0a5 --- /dev/null +++ b/entries/ionathanch/agda/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/ionchy/agda/Fib.agda b/entries/ionchy/agda/Fib.agda deleted file mode 100644 index a12b0a5..0000000 --- a/entries/ionchy/agda/Fib.agda +++ /dev/null @@ -1,19 +0,0 @@ - -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]`. -} -- cgit v1.2.3-70-g09d2 From 2927387ace15b664d80e2335084e50d478581733 Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Sun, 23 Oct 2022 16:42:08 -0700 Subject: Add Margo's fibs --- README.md | 3 +++ entries/margoseltzer/efficiency.c | 23 +++++++++++++++++++++++ 2 files changed, 26 insertions(+) create mode 100644 entries/margoseltzer/efficiency.c (limited to 'entries') diff --git a/README.md b/README.md index d126e3b..d43be80 100644 --- a/README.md +++ b/README.md @@ -25,6 +25,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G ### [`jyoo980`](https://github.com/jyoo980) - [`scala`](./entries/jyoo980/scala/Fib.scala) +## [`margoseltzer`](https://github.com/margoseltzer) +- [`efficiency`](./entries/margoseltzer/efficiency.c) + ### [`Metroxe`](https://github.com/Metroxe) - [`html`](./entries/Metroxe/index.html) 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 -- cgit v1.2.3-70-g09d2 From 97d0bca7470bef068b5852a94c5e51c103b0400c Mon Sep 17 00:00:00 2001 From: Tarcisio-Teixeira Date: Sun, 23 Oct 2022 16:48:02 -0700 Subject: Create fib.py --- entries/Tarcisio-Teixeira/fib.py | 5 +++++ 1 file changed, 5 insertions(+) create mode 100644 entries/Tarcisio-Teixeira/fib.py (limited to 'entries') diff --git a/entries/Tarcisio-Teixeira/fib.py b/entries/Tarcisio-Teixeira/fib.py new file mode 100644 index 0000000..1246517 --- /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, (3*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)) -- cgit v1.2.3-70-g09d2 From d0513187789505955e41441973c63848ec247cbc Mon Sep 17 00:00:00 2001 From: Tarcisio-Teixeira Date: Sun, 23 Oct 2022 17:02:58 -0700 Subject: Update fib.py --- entries/Tarcisio-Teixeira/fib.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'entries') diff --git a/entries/Tarcisio-Teixeira/fib.py b/entries/Tarcisio-Teixeira/fib.py index 1246517..a73cdd2 100644 --- a/entries/Tarcisio-Teixeira/fib.py +++ b/entries/Tarcisio-Teixeira/fib.py @@ -2,4 +2,4 @@ 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, (3*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)) + 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)) -- cgit v1.2.3-70-g09d2 From e5de46c67d3edeb6e4bc96889a6594ab77f07265 Mon Sep 17 00:00:00 2001 From: Shayan Hosseini Date: Sun, 23 Oct 2022 17:25:21 -0700 Subject: added shayanh's entry --- README.md | 3 +++ entries/shayanh/matrix.go | 40 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 43 insertions(+) create mode 100644 entries/shayanh/matrix.go (limited to 'entries') diff --git a/README.md b/README.md index efc713a..be6323b 100644 --- a/README.md +++ b/README.md @@ -34,6 +34,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G ### [`Tarcisio-Teixeira`](https://github.com/Tarcisio-Teixeira) - [`logn?`](./entries/Tarcisio-Teixeira/fib.py) +### [`shayanh`](https://github.com/shayanh) +- [`matrix`](./entries/shayanh/matrix.go) + ## Contributing To contribute just make a PR into the `main` branch! 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] +} -- cgit v1.2.3-70-g09d2 From 48902c10c743feac836d2c51a3bf1824e8db378a Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Sun, 23 Oct 2022 17:30:17 -0700 Subject: Add fib-lang --- .gitmodules | 3 +++ README.md | 3 +++ entries/wilbowma/fib-lang | 1 + 3 files changed, 7 insertions(+) create mode 100644 .gitmodules create mode 160000 entries/wilbowma/fib-lang (limited to 'entries') diff --git a/.gitmodules b/.gitmodules new file mode 100644 index 0000000..1088a73 --- /dev/null +++ b/.gitmodules @@ -0,0 +1,3 @@ +[submodule "entries/wilbowma/fib-lang"] + path = entries/wilbowma/fib-lang + url = git@github.com:wilbowma/fib-lang.git diff --git a/README.md b/README.md index efc713a..986aac9 100644 --- a/README.md +++ b/README.md @@ -34,6 +34,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G ### [`Tarcisio-Teixeira`](https://github.com/Tarcisio-Teixeira) - [`logn?`](./entries/Tarcisio-Teixeira/fib.py) +### [`wilbowma`](https://github.com/wilbowma) +- [`fib-lang`](./entries/wilbowma/fib-lang) + ## Contributing To contribute just make a PR into the `main` branch! diff --git a/entries/wilbowma/fib-lang b/entries/wilbowma/fib-lang new file mode 160000 index 0000000..2ec2d1d --- /dev/null +++ b/entries/wilbowma/fib-lang @@ -0,0 +1 @@ +Subproject commit 2ec2d1dfd141220882d824cf3dac5b374ed291f3 -- cgit v1.2.3-70-g09d2 From 46a659c983911b87b38b20cd4b28ab9176e4fdb3 Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Sun, 23 Oct 2022 19:13:46 -0700 Subject: Add fib-java --- README.md | 3 +++ entries/nritschel/fib-java/fib.iml | 13 +++++++++++++ .../fib-java/src/CachedFibonacciNumberFactory.java | 13 +++++++++++++ .../nritschel/fib-java/src/FibonacciCalculator.java | 3 +++ .../fib-java/src/FibonacciCalculatorImpl.java | 17 +++++++++++++++++ entries/nritschel/fib-java/src/FibonacciNumber.java | 19 +++++++++++++++++++ .../fib-java/src/FibonacciNumberFactory.java | 3 +++ entries/nritschel/fib-java/src/Main.java | 21 +++++++++++++++++++++ .../fib-java/src/NaiveFibonacciNumberFactory.java | 6 ++++++ 9 files changed, 98 insertions(+) create mode 100644 entries/nritschel/fib-java/fib.iml create mode 100644 entries/nritschel/fib-java/src/CachedFibonacciNumberFactory.java create mode 100644 entries/nritschel/fib-java/src/FibonacciCalculator.java create mode 100644 entries/nritschel/fib-java/src/FibonacciCalculatorImpl.java create mode 100644 entries/nritschel/fib-java/src/FibonacciNumber.java create mode 100644 entries/nritschel/fib-java/src/FibonacciNumberFactory.java create mode 100644 entries/nritschel/fib-java/src/Main.java create mode 100644 entries/nritschel/fib-java/src/NaiveFibonacciNumberFactory.java (limited to 'entries') diff --git a/README.md b/README.md index 3944068..4eb6fa1 100644 --- a/README.md +++ b/README.md @@ -31,6 +31,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G ### [`Metroxe`](https://github.com/Metroxe) - [`html`](./entries/Metroxe/index.html) +### [`nritschel`](https://github.com/nritschel) +- [`fib-java`](./entries/nritschel/fib-java/src) + ### [`shayanh`](https://github.com/shayanh) - [`matrix`](./entries/shayanh/matrix.go) 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 @@ + + + + + + + + + + + + + \ 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 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); + } +} -- cgit v1.2.3-70-g09d2 From 201f9e290b59838ed249b7d1be03e5b8230bef3e Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 19:21:33 -0700 Subject: add proper bound check --- entries/funemy/z3/z3fib.sh | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'entries') diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh index 9faa228..03a7209 100755 --- a/entries/funemy/z3/z3fib.sh +++ b/entries/funemy/z3/z3fib.sh @@ -14,6 +14,11 @@ 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 @@ -32,10 +37,13 @@ done echo " (= x0 0)" >> fib.smt2 echo " (= x1 1)" >> fib.smt2 -for i in $(seq 2 $1); -do - echo " (= x$i (+ x$(($i - 2)) x$(($i - 1))))" >> fib.smt2 -done +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 -- cgit v1.2.3-70-g09d2 From 31aa5baf3cc0935b579ac41b194f46e771443583 Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 19:24:26 -0700 Subject: minor --- entries/funemy/z3/z3fib.sh | 1 - 1 file changed, 1 deletion(-) (limited to 'entries') diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh index 03a7209..d3a93c2 100755 --- a/entries/funemy/z3/z3fib.sh +++ b/entries/funemy/z3/z3fib.sh @@ -44,7 +44,6 @@ if [ "$1" -ge "2" ]; then done fi - echo " )" >> fib.smt2 echo ")" >> fib.smt2 -- cgit v1.2.3-70-g09d2 From 08986a7a748a8ae747e076a3807e367f479b3ece Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 19:26:05 -0700 Subject: fix --- entries/funemy/z3/z3fib.sh | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'entries') diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh index d3a93c2..ecf42b4 100755 --- a/entries/funemy/z3/z3fib.sh +++ b/entries/funemy/z3/z3fib.sh @@ -35,7 +35,9 @@ do done echo " (= x0 0)" >> fib.smt2 -echo " (= x1 1)" >> fib.smt2 +if [ "$1" -ge "1" ]; then + echo " (= x1 1)" >> fib.smt2 +fi if [ "$1" -ge "2" ]; then for i in $(seq 2 $1); -- cgit v1.2.3-70-g09d2 From dffabc78b6c1e4e01b2618f5ba274b375b5c7cc4 Mon Sep 17 00:00:00 2001 From: funemy Date: Sun, 23 Oct 2022 19:27:25 -0700 Subject: minor --- entries/funemy/z3/z3fib.sh | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'entries') diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh index ecf42b4..07ab418 100755 --- a/entries/funemy/z3/z3fib.sh +++ b/entries/funemy/z3/z3fib.sh @@ -1,7 +1,7 @@ #!/bin/bash -# Instruction: -# 1. having z3 installed and under you $PATH +# 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 :) -- cgit v1.2.3-70-g09d2 From 77a33a73cc11e2a4a66db549f43ec5f0e0c6eb56 Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Sun, 23 Oct 2022 19:29:26 -0700 Subject: Add Reid's contribution --- README.md | 3 +++ .../Fibonacci series in JavaScript - Stack Overflow.webloc | 8 ++++++++ 2 files changed, 11 insertions(+) create mode 100644 entries/rtholmes/Fibonacci series in JavaScript - Stack Overflow.webloc (limited to 'entries') diff --git a/README.md b/README.md index 4eb6fa1..51ade8f 100644 --- a/README.md +++ b/README.md @@ -34,6 +34,9 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G ### [`nritschel`](https://github.com/nritschel) - [`fib-java`](./entries/nritschel/fib-java/src) +### [`rtholmes`](https://github.com/rtholmes) +- [`stack-overflow`](./entries/rtholmes/Fibonacci%20series%20in%20JavaScript%20-%20Stack%20Overflow.webloc) + ### [`shayanh`](https://github.com/shayanh) - [`matrix`](./entries/shayanh/matrix.go) 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 @@ + + + + + URL + https://stackoverflow.com/a/55764043 + + -- cgit v1.2.3-70-g09d2 From 4c717196fd630c5c207e114ffa9ca9c301eb1198 Mon Sep 17 00:00:00 2001 From: Jonathan Chan Date: Sun, 23 Oct 2022 23:07:43 -0400 Subject: Fortran :) (also moved my Agda file up a dir) --- README.md | 3 ++- entries/ionathanch/Fib.agda | 19 +++++++++++++++++++ entries/ionathanch/agda/Fib.agda | 19 ------------------- entries/ionathanch/fib.f90 | 21 +++++++++++++++++++++ 4 files changed, 42 insertions(+), 20 deletions(-) create mode 100644 entries/ionathanch/Fib.agda delete mode 100644 entries/ionathanch/agda/Fib.agda create mode 100644 entries/ionathanch/fib.f90 (limited to 'entries') diff --git a/README.md b/README.md index 51ade8f..0fcbc53 100644 --- a/README.md +++ b/README.md @@ -16,7 +16,8 @@ For a submission to the upcoming "Reclaim your space" exhibition at [Hatch Art G ### [`ionathanch`](https://github.com/ionathanch) -- [`agda`](./entries/ionathanch/agda/Fib.agda) +- [`agda`](./entries/ionathanch/Fib.agda) +- [`fortran`](./entries/ionathanch/fib.f90) ### [`funemy`](https://github.com/funemy) - [`agda`](./entries/funemy/agda/fib1.agda) 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/agda/Fib.agda b/entries/ionathanch/agda/Fib.agda deleted file mode 100644 index a12b0a5..0000000 --- a/entries/ionathanch/agda/Fib.agda +++ /dev/null @@ -1,19 +0,0 @@ - -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 -- cgit v1.2.3-70-g09d2 From 5a918f5a59e0e3b3af1ef75b5251b9f7ae7a15e8 Mon Sep 17 00:00:00 2001 From: Perry Liao Date: Sun, 23 Oct 2022 20:17:53 -0700 Subject: Create Jenkins groovy pipeline for fib --- entries/perryliao/fib.groovy | 48 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) create mode 100644 entries/perryliao/fib.groovy (limited to 'entries') diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy new file mode 100644 index 0000000..af1c4df --- /dev/null +++ b/entries/perryliao/fib.groovy @@ -0,0 +1,48 @@ +pipeline { + agent any + + parameters { + string defaultValue: '2', description: 'Number to compute in the Fibonacci Sequence', name: 'num', trim: true + } + + stages { + stage('Create Cache') { + steps { + script { + if (!fileExists("fibbonacciCache")) { + sh 'echo "0\n1" > fibbonacciCache' + } + } + } + } + stage('Validate Parameter') { + steps { + script { + assert params.num.isInteger() + } + } + } + stage('Get Fibbonacci') { + steps { + script { + result = fib(params.num.toInteger()) + println("The result is F(${params.num}) = ${result}") + } + } + } + } +} + +int fib(int n, cache = 'fibbonacciCache') { + nComputed = sh(returnStdout: true, script: "wc -l < ${cache}").trim().toInteger() + if (n >= nComputed) { + // Need to do more recursion + result = fib(n - 2, cache) + fib(n - 1, cache) + 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}").trim().toInteger() + } +} + -- cgit v1.2.3-70-g09d2 From f426d8a9b0b17336838b8840a4e5374f34949383 Mon Sep 17 00:00:00 2001 From: Megha Singhania Date: Sun, 23 Oct 2022 20:29:52 -0700 Subject: bash: add fib function --- entries/meghasinghania22/bash/script.sh | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 entries/meghasinghania22/bash/script.sh (limited to 'entries') 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 -- cgit v1.2.3-70-g09d2 From 1df988400399d3147514cf42a132141b7f5d8194 Mon Sep 17 00:00:00 2001 From: Perry Liao Date: Sun, 23 Oct 2022 20:46:17 -0700 Subject: make only 1 wc call --- entries/perryliao/fib.groovy | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) (limited to 'entries') diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy index af1c4df..168913f 100644 --- a/entries/perryliao/fib.groovy +++ b/entries/perryliao/fib.groovy @@ -9,8 +9,8 @@ pipeline { stage('Create Cache') { steps { script { - if (!fileExists("fibbonacciCache")) { - sh 'echo "0\n1" > fibbonacciCache' + if (!fileExists("fibCache")) { + sh 'echo "0\n1" > fibCache' } } } @@ -25,6 +25,7 @@ pipeline { 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}") } @@ -33,16 +34,17 @@ pipeline { } } -int fib(int n, cache = 'fibbonacciCache') { - nComputed = sh(returnStdout: true, script: "wc -l < ${cache}").trim().toInteger() +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}").trim().toInteger() + return sh(returnStdout: true, script: "sed -n '${n + 1}p' ${cache}").toInteger() } } - -- cgit v1.2.3-70-g09d2 From 2f4fab9864a91d69d2b705430f6633bdfe7f5dd5 Mon Sep 17 00:00:00 2001 From: Perry Liao Date: Sun, 23 Oct 2022 20:56:25 -0700 Subject: validation should probably come first lol --- entries/perryliao/fib.groovy | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'entries') diff --git a/entries/perryliao/fib.groovy b/entries/perryliao/fib.groovy index 168913f..d625d68 100644 --- a/entries/perryliao/fib.groovy +++ b/entries/perryliao/fib.groovy @@ -6,19 +6,19 @@ pipeline { } stages { - stage('Create Cache') { + stage('Validate Parameter') { steps { script { - if (!fileExists("fibCache")) { - sh 'echo "0\n1" > fibCache' - } + assert params.num.isInteger() } } } - stage('Validate Parameter') { + stage('Create Cache') { steps { script { - assert params.num.isInteger() + if (!fileExists("fibCache")) { + sh 'echo "0\n1" > fibCache' + } } } } -- cgit v1.2.3-70-g09d2 From 81fdbeb7fa4d8a80d028a988c353c3fa16d4953b Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Sun, 23 Oct 2022 23:06:51 -0700 Subject: wasm lol --- entries/adirar111/wasm/fib.wasm | Bin 0 -> 144 bytes entries/adirar111/wasm/fib.wat | 46 ++++++++++++++++++++++++++++++++++++++ entries/adirar111/wasm/index.html | 21 +++++++++++++++++ entries/adirar111/wasm/index.js | 21 +++++++++++++++++ entries/adirar111/wasm/style.css | 27 ++++++++++++++++++++++ 5 files changed, 115 insertions(+) create mode 100644 entries/adirar111/wasm/fib.wasm create mode 100644 entries/adirar111/wasm/fib.wat create mode 100644 entries/adirar111/wasm/index.html create mode 100644 entries/adirar111/wasm/index.js create mode 100644 entries/adirar111/wasm/style.css (limited to 'entries') diff --git a/entries/adirar111/wasm/fib.wasm b/entries/adirar111/wasm/fib.wasm new file mode 100644 index 0000000..6a93250 Binary files /dev/null and b/entries/adirar111/wasm/fib.wasm differ diff --git a/entries/adirar111/wasm/fib.wat b/entries/adirar111/wasm/fib.wat new file mode 100644 index 0000000..b9eba78 --- /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 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 @@ + + + + wasm fib + + + + +

go ahead, type a number

+
+ + +
+

fib.wasm says:

+ + + + diff --git a/entries/adirar111/wasm/index.js b/entries/adirar111/wasm/index.js new file mode 100644 index 0000000..43ee9a6 --- /dev/null +++ b/entries/adirar111/wasm/index.js @@ -0,0 +1,21 @@ +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)) { + result.textContent = "that's not a number..." + return + } + 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 +} -- cgit v1.2.3-70-g09d2 From 51ebb554063aa504668e939c766236967829b94b Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Sun, 23 Oct 2022 23:16:59 -0700 Subject: comment --- entries/adirar111/wasm/fib.wat | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'entries') diff --git a/entries/adirar111/wasm/fib.wat b/entries/adirar111/wasm/fib.wat index b9eba78..255fa12 100644 --- a/entries/adirar111/wasm/fib.wat +++ b/entries/adirar111/wasm/fib.wat @@ -1,5 +1,5 @@ ;; iterative fib(n) in web assembly text format (wat) -;; this gets compiled to fib.wasm binary +;; this gets compiled to the fib.wasm binary ;; and gets fetched via a data URL in index.js (module (export "fib" (func $fib)) -- cgit v1.2.3-70-g09d2 From 5e2b3d53917bb6a39dbffd0db6888bacaa283536 Mon Sep 17 00:00:00 2001 From: Aymen Dirar Date: Sun, 23 Oct 2022 23:29:34 -0700 Subject: handle negative --- entries/adirar111/wasm/index.js | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'entries') diff --git a/entries/adirar111/wasm/index.js b/entries/adirar111/wasm/index.js index 43ee9a6..667ff82 100644 --- a/entries/adirar111/wasm/index.js +++ b/entries/adirar111/wasm/index.js @@ -10,8 +10,10 @@ WebAssembly.instantiateStreaming(fetch(wasmBinaryDataURL)).then( const result = document.getElementById("result") const n = parseInt(input.value) if (isNaN(n)) { - result.textContent = "that's not a number..." - return + 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) } -- cgit v1.2.3-70-g09d2 From dcf99fd7ebf54474ea6d81ced6e00c28fba614fa Mon Sep 17 00:00:00 2001 From: rhiannon morris Date: Mon, 24 Oct 2022 08:48:36 +0200 Subject: add maude & ATS --- entries/lizard-business/fib.dats | 25 +++++++++++++++++++++++++ entries/lizard-business/fib.maude | 27 +++++++++++++++++++++++++++ people.json | 15 +++++++++++++++ 3 files changed, 67 insertions(+) create mode 100644 entries/lizard-business/fib.dats create mode 100644 entries/lizard-business/fib.maude (limited to 'entries') 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} .. + (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/people.json b/people.json index cc5e8e3..526da06 100644 --- a/people.json +++ b/people.json @@ -70,6 +70,21 @@ } ] }, + { + "github": "lizard-business", + "name": "rhiannon morris", + "title": "amateur type system liker", + "entries": [ + { + "name": "maude", + "link": "./entries/lizard-business/fib.maude" + }, + { + "name": "ats", + "link": "./entries/lizard-business/fib.dats" + } + ] + }, { "github": "margoseltzer", "name": "Margo Seltzer", -- cgit v1.2.3-70-g09d2 From b42ea5e994de56ffc7d4ec0e723261a147179b15 Mon Sep 17 00:00:00 2001 From: Felipe Bañados Schwerter Date: Mon, 24 Oct 2022 10:46:18 -0600 Subject: Specified implementation in coq --- entries/fbanados/fib.v | 90 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 90 insertions(+) create mode 100644 entries/fbanados/fib.v (limited to 'entries') 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. + -- cgit v1.2.3-70-g09d2 From b0644202ce201774445a09f103908498f3838820 Mon Sep 17 00:00:00 2001 From: Felipe Bañados Schwerter Date: Mon, 24 Oct 2022 11:27:43 -0600 Subject: Base smalltalk export --- entries/fbanados/fib.st | 1 + 1 file changed, 1 insertion(+) create mode 100644 entries/fbanados/fib.st (limited to 'entries') diff --git a/entries/fbanados/fib.st b/entries/fbanados/fib.st new file mode 100644 index 0000000..8431a09 --- /dev/null +++ b/entries/fbanados/fib.st @@ -0,0 +1 @@ +'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.! ! \ No newline at end of file -- cgit v1.2.3-70-g09d2 From ac7935ad693adac61f7fe0a6c9ec1344f3297c48 Mon Sep 17 00:00:00 2001 From: Felipe Bañados Schwerter Date: Mon, 24 Oct 2022 11:33:02 -0600 Subject: Ok made it readable --- entries/fbanados/fib.st | 9 ++++++++- 1 file changed, 8 insertions(+), 1 deletion(-) (limited to 'entries') diff --git a/entries/fbanados/fib.st b/entries/fbanados/fib.st index 8431a09..099407c 100644 --- a/entries/fbanados/fib.st +++ b/entries/fbanados/fib.st @@ -1 +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.! ! \ No newline at end of file +'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. + +! ! -- cgit v1.2.3-70-g09d2 From f540b8058f8ed83c9230662f9d02fad898da008e Mon Sep 17 00:00:00 2001 From: Justin Frank Date: Mon, 24 Oct 2022 14:12:11 -0400 Subject: Added fib in befunge --- entries/laelath/fib.bf | 3 +++ people.json | 11 +++++++++++ 2 files changed, 14 insertions(+) create mode 100644 entries/laelath/fib.bf (limited to 'entries') 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/people.json b/people.json index 2543c07..26dc1db 100644 --- a/people.json +++ b/people.json @@ -202,5 +202,16 @@ "link": "./entries/fbanados/fib.st" } ] + }, + { + "github": "laelath", + "name": "Justin Frank", + "title": "PhD Student, UMD", + "entries": [ + { + "name": "befunge", + "link": "./entries/laelath/fib.bf" + } + ] } ] -- cgit v1.2.3-70-g09d2 From 7972ad88012a56f6afd54ada46cd45206418682a Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Mon, 24 Oct 2022 12:03:21 -0700 Subject: Add Nico's new fibs --- entries/nritschel/assets/scratch.png | Bin 0 -> 752302 bytes entries/nritschel/scratch/README.md | 1 + entries/nritschel/scratch/fib.sb3 | Bin 0 -> 43364 bytes entries/nritschel/xlsx/fib.xlsx | Bin 0 -> 11704 bytes people.json | 8 ++++++++ 5 files changed, 9 insertions(+) create mode 100644 entries/nritschel/assets/scratch.png create mode 100644 entries/nritschel/scratch/README.md create mode 100644 entries/nritschel/scratch/fib.sb3 create mode 100644 entries/nritschel/xlsx/fib.xlsx (limited to 'entries') diff --git a/entries/nritschel/assets/scratch.png b/entries/nritschel/assets/scratch.png new file mode 100644 index 0000000..5883245 Binary files /dev/null and b/entries/nritschel/assets/scratch.png differ 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 @@ +scratch preview \ No newline at end of file diff --git a/entries/nritschel/scratch/fib.sb3 b/entries/nritschel/scratch/fib.sb3 new file mode 100644 index 0000000..a3cf2cc Binary files /dev/null and b/entries/nritschel/scratch/fib.sb3 differ diff --git a/entries/nritschel/xlsx/fib.xlsx b/entries/nritschel/xlsx/fib.xlsx new file mode 100644 index 0000000..e1b662d Binary files /dev/null and b/entries/nritschel/xlsx/fib.xlsx differ diff --git a/people.json b/people.json index 26dc1db..fa3f624 100644 --- a/people.json +++ b/people.json @@ -130,6 +130,14 @@ { "name": "fib-java", "link": "./entries/nritschel/fib-java/src" + }, + { + "name": "xlsx", + "link": "./entries/nritschel/xlsx/fib.xlsx" + }, + { + "name": "scratch", + "link": "./entries/nritschel/scratch" } ] }, -- cgit v1.2.3-70-g09d2 From 06ad8853e86b5c270f31f6d7b99081323f2f677a Mon Sep 17 00:00:00 2001 From: Zack Grannan Date: Mon, 24 Oct 2022 12:02:15 -0700 Subject: Add submission for zgrannan --- entries/zgrannan/Fib.hs | 18 ++++++++++++++++++ people.json | 11 +++++++++++ 2 files changed, 29 insertions(+) create mode 100644 entries/zgrannan/Fib.hs (limited to 'entries') 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] diff --git a/people.json b/people.json index 26dc1db..a9d5fa0 100644 --- a/people.json +++ b/people.json @@ -213,5 +213,16 @@ "link": "./entries/laelath/fib.bf" } ] + }, + { + "github": "zgrannan", + "name": "Zack Grannan", + "title": "MS Student, UBC", + "entries": [ + { + "name": "haskell", + "link": "./entries/zgrannan/Fib.hs" + } + ] } ] -- cgit v1.2.3-70-g09d2 From 0aa0d695f8fef33b02cbf04fbd6825bd2cbc6de1 Mon Sep 17 00:00:00 2001 From: Xu, Junfeng Date: Mon, 24 Oct 2022 12:24:50 -0700 Subject: add haskell entry --- entries/nxjfxu/fib.hs | 5 +++++ people.json | 11 +++++++++++ 2 files changed, 16 insertions(+) create mode 100644 entries/nxjfxu/fib.hs (limited to 'entries') 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/people.json b/people.json index 26dc1db..e63fc4d 100644 --- a/people.json +++ b/people.json @@ -213,5 +213,16 @@ "link": "./entries/laelath/fib.bf" } ] + }, + { + "github": "nxjfxu", + "name": "Junfeng Xu", + "title": "MSc Student, UBC", + "entries": [ + { + "name": "ouroboros", + "link": "./entries/nxjfxu/fib.hs" + } + ] } ] -- cgit v1.2.3-70-g09d2 From db535e5c3035030bc1089528ad5fc12b9eef14ad Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Mon, 24 Oct 2022 12:34:39 -0700 Subject: Add Paulette --- entries/pkoronkevich/tex/README.md | 1 + entries/pkoronkevich/tex/fib.tex | 28 ++++++++++++++++++++++++++++ entries/pkoronkevich/tex/render.pdf | Bin 0 -> 21761 bytes entries/pkoronkevich/tex/render.png | Bin 0 -> 297404 bytes people.json | 11 +++++++++++ 5 files changed, 40 insertions(+) create mode 100644 entries/pkoronkevich/tex/README.md create mode 100644 entries/pkoronkevich/tex/fib.tex create mode 100644 entries/pkoronkevich/tex/render.pdf create mode 100644 entries/pkoronkevich/tex/render.png (limited to 'entries') 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 @@ +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..22781d1 --- /dev/null +++ b/entries/pkoronkevich/tex/fib.tex @@ -0,0 +1,28 @@ +\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{\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 \ \appo{(\isz)}{n} \\ % is n zero + \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 new file mode 100644 index 0000000..b69f747 Binary files /dev/null and b/entries/pkoronkevich/tex/render.pdf differ diff --git a/entries/pkoronkevich/tex/render.png b/entries/pkoronkevich/tex/render.png new file mode 100644 index 0000000..2e172cc Binary files /dev/null and b/entries/pkoronkevich/tex/render.png differ diff --git a/people.json b/people.json index b957009..ef2cbd2 100644 --- a/people.json +++ b/people.json @@ -232,5 +232,16 @@ "link": "./entries/zgrannan/Fib.hs" } ] + }, + { + "github": "pkoronkevich", + "name": "Paulette Koronkevich", + "title": "PhD Student, UBC", + "entries": [ + { + "name": "tex", + "link": "./entries/pkoronkevich/tex" + } + ] } ] -- cgit v1.2.3-70-g09d2 From d6cab23a8b6879a58eadac239001acc40372cbb6 Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Mon, 24 Oct 2022 13:04:02 -0700 Subject: Update Paulette's fib --- entries/pkoronkevich/tex/fib.tex | 3 ++- entries/pkoronkevich/tex/render.pdf | Bin 21761 -> 21807 bytes entries/pkoronkevich/tex/render.png | Bin 297404 -> 387387 bytes 3 files changed, 2 insertions(+), 1 deletion(-) (limited to 'entries') diff --git a/entries/pkoronkevich/tex/fib.tex b/entries/pkoronkevich/tex/fib.tex index 22781d1..cef9138 100644 --- a/entries/pkoronkevich/tex/fib.tex +++ b/entries/pkoronkevich/tex/fib.tex @@ -11,6 +11,7 @@ \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} @@ -19,7 +20,7 @@ \begin{gather*} \fix \\ % recursive function application \quad \lambda r . \lambda n . (\ife) \\ % of fib, which takes itself and n, if expression - \quad \ \appo{(\isz)}{n} \\ % is n zero + \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 diff --git a/entries/pkoronkevich/tex/render.pdf b/entries/pkoronkevich/tex/render.pdf index b69f747..8ee60c7 100644 Binary files a/entries/pkoronkevich/tex/render.pdf and b/entries/pkoronkevich/tex/render.pdf differ diff --git a/entries/pkoronkevich/tex/render.png b/entries/pkoronkevich/tex/render.png index 2e172cc..a1896a2 100644 Binary files a/entries/pkoronkevich/tex/render.png and b/entries/pkoronkevich/tex/render.png differ -- cgit v1.2.3-70-g09d2 From 2db6cb57d86bfa3616e9f8ede8ac73b30dfe75e1 Mon Sep 17 00:00:00 2001 From: StuartLiv Date: Mon, 24 Oct 2022 14:26:31 -0700 Subject: Added ThetaFibN --- entries/StuartLiv/ThetaFibN.java | 13 +++++++++++++ people.json | 11 +++++++++++ 2 files changed, 24 insertions(+) create mode 100644 entries/StuartLiv/ThetaFibN.java (limited to 'entries') 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/people.json b/people.json index 248c644..bb44dde 100644 --- a/people.json +++ b/people.json @@ -166,6 +166,17 @@ } ] }, + { + "github": "StuartLiv", + "name": "Stuart Livingstone", + "title": "BSc Student, UBC", + "entries": [ + { + "name": "ThetaFibN", + "link": "./entries/StuartLiv/ThetaFibN.java" + } + ] + }, { "github": "Tarcisio-Teixeira", "name": "Tarcísio Teixeira", -- cgit v1.2.3-70-g09d2 From 8ffac10bf733f5f75bf85750562710c1cd60cf0a Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Mon, 24 Oct 2022 15:14:18 -0700 Subject: Add Ron --- entries/rxg/fib.rkt | 132 ++++++++++++++++++++++++++++++++++++++++++++++++++++ people.json | 11 +++++ 2 files changed, 143 insertions(+) create mode 100644 entries/rxg/fib.rkt (limited to 'entries') 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/people.json b/people.json index b84c8d8..1ff8fa0 100644 --- a/people.json +++ b/people.json @@ -163,6 +163,17 @@ } ] }, + { + "github": "rxg", + "name": "Ronald Garcia", + "title": "Associate Professor of Computer Science, UBC", + "entries": [ + { + "name": "fib-iter*", + "link": "./entries/rxg/fib.rkt" + } + ] + }, { "github": "shayanh", "name": "Shayan Hosseini", -- cgit v1.2.3-70-g09d2 From d8809640625ff7113b3e534a0ddc84d970674570 Mon Sep 17 00:00:00 2001 From: braxtonhall Date: Mon, 24 Oct 2022 15:21:37 -0700 Subject: Add Marie --- entries/MarieSal0/FibonacciWorkplace/.gitignore | 133 +++++++++++++++++++++ .../FibonacciWorkplace/FibonacciWorkplace.csproj | 10 ++ entries/MarieSal0/FibonacciWorkplace/Program.cs | 41 +++++++ people.json | 11 ++ 4 files changed, 195 insertions(+) create mode 100644 entries/MarieSal0/FibonacciWorkplace/.gitignore create mode 100644 entries/MarieSal0/FibonacciWorkplace/FibonacciWorkplace.csproj create mode 100644 entries/MarieSal0/FibonacciWorkplace/Program.cs (limited to 'entries') 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 @@ + + + + Exe + net6.0 + enable + enable + + + 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/people.json b/people.json index b84c8d8..60654a5 100644 --- a/people.json +++ b/people.json @@ -100,6 +100,17 @@ } ] }, + { + "github": "MarieSal0", + "name": "Marie Salomon", + "title": "MSc Student, UBC", + "entries": [ + { + "name": "c#", + "link": "./entries/MarieSal0/FibonacciWorkplace/Program.cs" + } + ] + }, { "github": "meghasinghania22", "name": "Megha Singhania", -- cgit v1.2.3-70-g09d2