Merge branch 'main' into lily

22 files changed, 493 insertions, 32 deletions

diff --git a/entries/Tarcisio-Teixeira/differential.py b/entries/Tarcisio-Teixeira/differential.py
new file mode 100644
index 0000000..8abbdae
--- /dev/null
+++ b/entries/Tarcisio-Teixeira/differential.py
@@ -0,0 +1,10 @@
+from sympy import *
+
+def fib(n):
+  x = symbols('x')
+  f = diff(1/(1-x-x**2),x,0)
+  fact = 1
+  for i in range(1,n):
+    f = diff(f,x)
+    fact *= i
+  return f.subs(x,0)/fact
diff --git a/entries/Zhengdw/actual_fib.txt b/entries/Zhengdw/actual_fib.txt
new file mode 100644
index 0000000..a48ade6
--- /dev/null
+++ b/entries/Zhengdw/actual_fib.txt
@@ -0,0 +1 @@
+A000045
diff --git a/entries/dewert99/big_fib.rs b/entries/dewert99/big_fib.rs
new file mode 100644
index 0000000..f5cddbb
--- /dev/null
+++ b/entries/dewert99/big_fib.rs
@@ -0,0 +1,40 @@
+use num_bigint::{BigUint, ToBigUint};
+
+/// Returns (fib(n-1), fib(n), fib(n+1))
+fn fib_helper(n: u64) -> [BigUint; 3] {
+    let [fm1, f0, f1] = if n == 0 {
+        [
+            1.to_biguint().unwrap(),
+            0.to_biguint().unwrap(),
+            1.to_biguint().unwrap(),
+        ]
+    } else {
+        fib_helper2(n / 2)
+    };
+    if n % 2 == 1 {
+        let [mut fm2, fm1, f0] = [fm1, f0, f1];
+        fm1.clone_into(&mut fm2);
+        let f1 = fm2 + &f0;
+        [fm1, f0, f1]
+    } else {
+        [fm1, f0, f1]
+    }
+}
+
+/// Returns (fib(2n-1), fib(2n), fib(2n+1))
+fn fib_helper2(n: u64) -> [BigUint; 3] {
+    let [fm1, fp0, fp1] = fib_helper(n);
+    // f2m1 = fm1^2 + fp0^2
+    // f2p0 = fp1*fp0 + fp0*fm1 = fp0*(fp1+fm1)
+    // f2p1 = fp1^2 + fp0^2
+    let f2p0 = (fp1.clone() + &fm1) * &fp0;
+    let fp0sqr = fp0.pow(2);
+    let f2m1 = fm1.pow(2) + &fp0sqr;
+    let f2p1 = fp1.pow(2) + fp0sqr;
+    [f2m1, f2p0, f2p1]
+}
+
+pub fn fib(n: u64) -> BigUint {
+    let [_, res, _] = fib_helper(n);
+    res
+}
diff --git a/entries/funemy/.gitignore b/entries/funemy/.gitignore
index acb903a..9211bbd 100644
--- a/entries/funemy/.gitignore
+++ b/entries/funemy/.gitignore
@@ -1,3 +1,6 @@
 .DS_Store
 *.agdai
 *.smt2
+**/.koka/*
+*.hi
+*.o
diff --git a/entries/funemy/haskell/morphib.hs b/entries/funemy/haskell/morphib.hs
new file mode 100644
index 0000000..1fae449
--- /dev/null
+++ b/entries/funemy/haskell/morphib.hs
@@ -0,0 +1,43 @@
+-- Fantastic Morphisms
+newtype Free f = Free {unFree :: f (Free f)}
+
+cata :: Functor f => (f a -> a) -> Free f -> a
+cata phi (Free x) = phi $ fmap (cata phi) x
+
+ana :: Functor f => (a -> f a) -> a -> Free f
+ana phi x = Free $ fmap (ana phi) (phi x)
+
+data FibF a =
+      Fib0
+    | Fib1
+    | FibN a a
+    deriving (Eq, Show)
+
+instance Functor FibF where
+    fmap f Fib0       = Fib0
+    fmap f Fib1       = Fib1
+    fmap f (FibN l r) = FibN (f l) (f r)
+
+type Fib a = Free FibF
+
+gen :: Int -> FibF Int
+gen 0 = Fib0
+gen 1 = Fib1
+gen n = FibN (n-1) (n-2)
+
+interp :: FibF Int -> Int
+interp Fib0       = 0
+interp Fib1       = 1
+interp (FibN l r) = l + r
+
+bif :: Int -> Fib Int
+bif = ana gen
+
+fib' :: Fib Int -> Int
+fib' = cata interp
+
+fib :: Int -> Int
+fib = fib' . bif
+
+main :: IO ()
+main = print (fib 14)
diff --git a/entries/funemy/koka/fib.kk b/entries/funemy/koka/fib.kk
new file mode 100644
index 0000000..5b7e66b
--- /dev/null
+++ b/entries/funemy/koka/fib.kk
@@ -0,0 +1,12 @@
+effect fib
+  ctl fib(n : int) : int
+
+fun doFib(inp : int) : div int
+  with ctl fib(n)
+    if n == 0 then 0
+    else if n == 1 then 1
+    else (doFib(n - 1) : int) + doFib(n - 2)
+  fib(inp)
+
+fun main()
+  print(doFib(20))
diff --git a/entries/funemy/symbolic/phib.py b/entries/funemy/symbolic/phib.py
new file mode 100644
index 0000000..c6fb23e
--- /dev/null
+++ b/entries/funemy/symbolic/phib.py
@@ -0,0 +1,21 @@
+from typing import List
+ 
+def phib(xs: List[int]) -> bool:
+    """
+    Instructions:
+        1. `pip install crosshair-tool`
+        2. modify the precondition `pre` to control the length of your fib sequence
+        3. run `crosshair check phib.py` in your terminal
+
+    pre: len(xs) >= 10
+    post: __return__ != True
+    """
+    if xs[0] != 0:
+        return False
+    if len(xs) > 1:
+        if xs[1] != 1:
+            return False
+        for i in range(2,len(xs)):
+            if xs[i] != xs[i-1] + xs[i-2]:
+                return False
+        return True
diff --git a/entries/funemy/z3/z3fib.sh b/entries/funemy/z3/z3fib.sh
index 07ab418..e96226f 100755
--- a/entries/funemy/z3/z3fib.sh
+++ b/entries/funemy/z3/z3fib.sh
@@ -15,7 +15,7 @@ else
 fi
 
 if [ "$1" -lt "0" ]; then
-  echo "Argument must be larger than 0."
+  echo "Argument must be larger or equal to 0."
   exit 1
 fi
 
diff --git a/entries/funemy/z3/z4fib.sh b/entries/funemy/z3/z4fib.sh
new file mode 100755
index 0000000..f7a1e48
--- /dev/null
+++ b/entries/funemy/z3/z4fib.sh
@@ -0,0 +1,40 @@
+#!/bin/bash
+# z3 fib, but better
+
+# Instructions:
+#  1. having z3 installed and put under your $PATH
+#  2. making sure z4fib.sh is executable, by `chmod +x z4fib.sh`
+#  3. running as `./z4fib.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 or equal to 0."
+  exit 1
+fi
+
+echo "(declare-const fib (Seq Int))" >> fib.smt2
+echo "" >> fib.smt2
+echo "(assert" >> fib.smt2
+echo "  (and" >> fib.smt2
+echo "    (= (seq.len fib) $1)" >> fib.smt2
+echo "    (= (seq.nth fib 0) 0)" >> fib.smt2
+echo "    (= (seq.nth fib 1) 1)" >> fib.smt2
+echo "    (forall ((i Int))" >> fib.smt2
+echo "      (=> (and (> i 1) (< i (seq.len fib)))" >> fib.smt2
+echo "        (= (seq.nth fib i)" >> fib.smt2
+echo "          (+ (seq.nth fib (- i 1))" >> fib.smt2
+echo "            (seq.nth fib (- i 2))))))))" >> fib.smt2
+echo "" >> fib.smt2
+
+echo "(check-sat)" >> fib.smt2
+echo "(get-model)" >> fib.smt2
+
+z3 fib.smt2
diff --git a/entries/jlouis/README.md b/entries/jlouis/README.md
new file mode 100644
index 0000000..2f14678
--- /dev/null
+++ b/entries/jlouis/README.md
@@ -0,0 +1,11 @@
+# Fib like only I would write it
+
+## Instructions
+
+Everything is in `lib/fib.ml` and the rest is just scaffolding.
+
+Use nix to get an OCaml development environment.
+
+Use dune to build: `dune build`
+Use dune to run: `dune exec fib`
+Use dune to test: `dune test`
diff --git a/entries/jlouis/bin/dune b/entries/jlouis/bin/dune
new file mode 100644
index 0000000..6d6e5f9
--- /dev/null
+++ b/entries/jlouis/bin/dune
@@ -0,0 +1,4 @@
+(executable
+ (public_name fib)
+ (name main)
+ (libraries fib))
diff --git a/entries/jlouis/bin/main.ml b/entries/jlouis/bin/main.ml
new file mode 100644
index 0000000..ca2c25e
--- /dev/null
+++ b/entries/jlouis/bin/main.ml
@@ -0,0 +1 @@
+let _ = print_endline ("Mok'ra: " ^ string_of_int (Fib.Orc.iter 10))
\ No newline at end of file
diff --git a/entries/jlouis/dune-project b/entries/jlouis/dune-project
new file mode 100644
index 0000000..ff9f42f
--- /dev/null
+++ b/entries/jlouis/dune-project
@@ -0,0 +1,3 @@
+(lang dune 3.4)
+
+(name fib)
diff --git a/entries/jlouis/fib.opam b/entries/jlouis/fib.opam
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/entries/jlouis/fib.opam
diff --git a/entries/jlouis/lib/dune b/entries/jlouis/lib/dune
new file mode 100644
index 0000000..865a6c5
--- /dev/null
+++ b/entries/jlouis/lib/dune
@@ -0,0 +1,5 @@
+(library
+ (name fib)
+ (inline_tests)
+ (preprocess
+  (pps ppx_inline_test)))
diff --git a/entries/jlouis/lib/fib.ml b/entries/jlouis/lib/fib.ml
new file mode 100644
index 0000000..9353c6a
--- /dev/null
+++ b/entries/jlouis/lib/fib.ml
@@ -0,0 +1,72 @@
+module type BASIS =
+  sig
+    type t
+    val one : t
+    val out : t -> int
+    val to_string : t -> string
+  end
+
+module type MONOIDIC =
+  sig
+    include BASIS
+    val concat : t -> t -> t
+  end
+
+(* Single Tuple, Multiple Data *)
+module STMD : MONOIDIC =
+  struct
+    type t = int * int * int * int
+
+    let one = (1, 1,
+               1, 0)
+
+    let out (_, _, _, x) = x
+
+    let to_string (a,b,c,d) = "(" ^ (string_of_int a) ^ ", "
+                                  ^ (string_of_int b) ^ ", "
+                                  ^ (string_of_int c) ^ ", "
+                                  ^ (string_of_int d) ^ ")"
+
+    let concat (a11, a12, a21, a22) (b11, b12, b21, b22) =
+      let muladd a x b y = (a*x) + (b*y) in
+      (muladd a11 b11 a12 b21,
+       muladd a11 b12 a12 b22,
+       muladd a21 b11 a22 b21,
+       muladd a21 b12 a22 b22)
+  end
+
+module MkLinear(M : MONOIDIC) =
+  struct
+    let iter n =
+      let rec loop n acc =
+        match n with
+        | 0 -> acc
+        | k -> loop (k-1) (M.concat M.one acc)
+      in
+        M.out (loop n M.one)
+
+  end
+
+module MkLog(M : MONOIDIC) =
+  struct
+    let iter n =
+      let rec loop y x k =
+        if k = 0 then y
+        else if k mod 2 = 0 then loop y (M.concat x x) (k/2)
+                            else loop (M.concat y x) (M.concat x x) ((k-1)/2)
+      in
+        M.out (loop M.one M.one n)
+  end
+
+module Kobold = MkLinear(STMD) (* You no take candle! *)
+module Orc = MkLog(STMD) (* Mok'ra *)
+
+let%test _ = Kobold.iter 10 = 55
+let%test _ = Kobold.iter 0 = 0
+let%test _ = Orc.iter 0 = 0
+let%test _ = Orc.iter 1 = 1
+let%test _ = Orc.iter 2 = 1
+let%test _ = Orc.iter 3 = 2
+let%test _ = Orc.iter 4 = 3
+let%test _ = Orc.iter 5 = 5
+let%test _ = Orc.iter 10 = 55
diff --git a/entries/jlouis/shell.nix b/entries/jlouis/shell.nix
new file mode 100644
index 0000000..d5e27a3
--- /dev/null
+++ b/entries/jlouis/shell.nix
@@ -0,0 +1,11 @@
+let
+ pkgs = import <nixpkgs> {};
+ # choose the ocaml version you want to use
+ ocamlPackages = pkgs.ocaml-ng.ocamlPackages_4_14;
+in
+pkgs.mkShell {
+  # build tools
+  nativeBuildInputs = with ocamlPackages; [ ocaml utop findlib dune_3 ocaml-lsp ppx_inline_test ];
+  # dependencies
+  buildInputs = with ocamlPackages; [ ocamlgraph ];
+}
diff --git a/entries/jyoo980/aspectj/Fibonacci.aj b/entries/jyoo980/aspectj/Fibonacci.aj
new file mode 100644
index 0000000..39dfd8a
--- /dev/null
+++ b/entries/jyoo980/aspectj/Fibonacci.aj
@@ -0,0 +1,21 @@
+public aspect Fibonnacci {
+
+    pointcut mainInvocation(): call(* Main.*(*));
+
+    void before(): mainInvocation() {
+        // Nice
+        int n = 69;
+        System.out.println("The 69th fibonacci number is: " + fibonacci(n));
+    }
+
+    public int fibonacci(int n) {
+        int prev = 0;
+        int curr = 1;
+        for (int i = 0; i < n; i++) {
+            int tmp = prev;
+            prev = curr;
+            curr = prev + tmp;
+        }
+        return prev;
+    }
+}
diff --git a/entries/kevindhir/aws/Solution.java b/entries/kevindhir/aws/Solution.java
new file mode 100644
index 0000000..602d1b1
--- /dev/null
+++ b/entries/kevindhir/aws/Solution.java
@@ -0,0 +1,21 @@
+package entries.kevindhir.aws;
+
+import java.util.Arrays;
+
+class Solution {
+    public int fib(int N) {
+        int[] storage = new int[9999];
+        Arrays.fill(storage, -1);
+        storage[0] = 0;
+        storage[1] = 1;
+        return fibMemoized(N, storage);
+    }
+
+    private int fibMemoized(int N, int[] storage){
+        if (storage[N] != -1) return storage[N];
+        int calculated = fibMemoized(N-1, storage) + fibMemoized(N-2, storage);
+        storage[N] = calculated;
+        return calculated;
+    }
+
+}
\ No newline at end of file
diff --git a/entries/kevindhir/ts/fib.ts b/entries/kevindhir/ts/fib.ts
new file mode 100644
index 0000000..f126a8b
--- /dev/null
+++ b/entries/kevindhir/ts/fib.ts
@@ -0,0 +1,8 @@
+let memo = {1: 1};
+
+function fib(n: number): number {
+    if(n <= 0) return 0;
+    if(memo[n]) return memo[n];
+    memo[n] = fib(n-1) + fib(n-2);
+    return memo[n];
+};
diff --git a/entries/nwoeanhinnogaehr/fib.asm b/entries/nwoeanhinnogaehr/fib.asm
new file mode 100644
index 0000000..26ccf11
--- /dev/null
+++ b/entries/nwoeanhinnogaehr/fib.asm
@@ -0,0 +1,59 @@
+; assembles with nasm to an 81-byte ELF binary that works on x86 Linux
+
+bits 32
+org $25430000
+    db $7F,"ELF" ; e_ident
+    dd 1 ; p_type
+    dd 0 ; p_offset
+    dd $$ ; p_vaddr
+    dw 2 ; e_type, p_paddr
+    dw 3 ; e_machine
+    dd entry ; e_version, p_filesz
+    dw (entry-$$)&0xffff ; e_entry, p_memsz
+
+entry:
+    inc ebx
+    and eax,strict dword 4 ;nop
+    inc esi ; 1
+    inc edi ; 1
+            ; 2
+            ; 3
+            ; 5
+            ; 8
+            ; ...
+
+loop:
+    mov eax,esi
+    push 10
+    pop ebp
+    push ebp
+    jmp format
+    dw $20 ; e_phentsize
+    dw 1 ; e_phnum
+
+format:
+    cdq
+    div ebp
+    inc ebx
+    dec esp
+    or edx,'0'
+    mov [esp],dl
+    test eax,eax
+    jnz format
+
+print:
+    mov al,4
+    mov ecx,esp
+    mov edx,ebx
+    mov bl,1
+    int 0x80
+
+    ;update fibbo
+    mov eax,edi
+    add edi,esi
+    xchg esi,eax
+
+    ;exit on overflow
+    jno loop
+    xchg eax,ebx
+    int 0x80
diff --git a/people.json b/people.json
index 64e5cad..f1d8014 100644
--- a/people.json
+++ b/people.json
@@ -57,6 +57,17 @@
         ]
     },
     {
+        "github": "jlouis",
+        "name": "Jesper Louis Andersen",
+        "title": "BSc, Copenhagen University",
+        "entries": [
+            {
+                "name": "ocaml",
+                "link": "./entries/jlouis/lib/fib.ml"
+            }
+        ]
+    },
+    {
         "github": "funemy",
         "name": "Yanze Li",
         "title": "PhD Student, UBC",
@@ -68,6 +79,22 @@
             {
                 "name": "z3",
                 "link": "./entries/funemy/z3/z3fib.sh"
+            },
+            {
+                "name": "z4",
+                "link": "./entries/funemy/z3/z4fib.sh"
+            },
+            {
+                "name": "symbolic",
+                "link": "./entries/funemy/symbolic/phib.py"
+            },
+            {
+                "name": "morphism",
+                "link": "./entries/funemy/haskell/morphib.hs"
+            },
+            {
+                "name": "koka",
+                "link": "./entries/funemy/koka/fib.kk"
             }
         ]
     },
@@ -83,33 +110,51 @@
             {
                 "name": "vintage-htdp",
                 "link": "./entries/jyoo980/vintage-htdp/fib.rkt"
+            },
+            {
+                "name": "aspectj",
+                "link": "./entries/jyoo980/aspectj/Fibonacci.aj"
             }
-
         ]
     },
-	{
-		"github": "rctcwyvrn",
-		"name": "Lily Lin",
-		"title": "BSc, UBC",
-		"entries": [
-			{
-				"name": "fractran",
-				"link": "./entries/lilylin/fractran/fractran.py"
-			},
-			{
-				"name": "cursed-x86",
-				"link": "./entries/lilylin/cursed-x86/"
-			},
-			{
-				"name": "mov",
-				"link": "./entries/lilylin/mov/mov.s"
-			},
+    {
+        "github": "kevindhir",
+        "name": "Kevin Dhir",
+        "title": "BCom, UBC",
+        "entries": [
+            {
+                "name": "online-assessment",
+                "link": "./entries/kevindhir/aws/Solution.java"
+            },
+            {
+                "name": "ts",
+                "link": "./entries/kevindhir/ts/fib.ts"
+            }
+        ]
+    },
+    {
+        "github": "rctcwyvrn",
+        "name": "Lily Lin",
+        "title": "BSc, UBC",
+        "entries": [
+            {
+                "name": "fractran",
+                "link": "./entries/lilylin/fractran/fractran.py"
+            },
+            {
+                "name": "cursed-x86",
+                "link": "./entries/lilylin/cursed-x86/"
+            },
+            {
+                "name": "mov",
+                "link": "./entries/lilylin/mov/mov.s"
+            },
 			{
 				"name": "desmos",
 				"link": "./entries/lilylin/desmos/readme.md"
 			}
-		]
-	},
+        ]
+    },
     {
         "github": "lizard-business",
         "name": "rhiannon morris",
@@ -243,17 +288,17 @@
             }
         ]
     },
-	{
-		"github": "StuartLiv",
-		"name": "Stuart Livingstone",
-		"title": "BSc Student, UBC",
-		"entries": [
-			{
-				"name": "ThetaFibN",
-				"link": "./entries/StuartLiv/ThetaFibN.java"
-			}
-		]
-	},
+    {
+        "github": "StuartLiv",
+        "name": "Stuart Livingstone",
+        "title": "BSc Student, UBC",
+        "entries": [
+            {
+                "name": "ThetaFibN",
+                "link": "./entries/StuartLiv/ThetaFibN.java"
+            }
+        ]
+    },
     {
         "github": "Tarcisio-Teixeira",
         "name": "Tarcísio Teixeira",
@@ -262,6 +307,10 @@
             {
                 "name": "logn?",
                 "link": "./entries/Tarcisio-Teixeira/fib.py"
+            },
+            {
+                "name": "differential",
+                "link": "./entries/Tarcisio-Teixeira/differential.py"
             }
         ]
     },
@@ -365,6 +414,21 @@
             {
                 "name": "O(1)",
                 "link": "./entries/dewert99/fib.rs"
+            },
+			{
+                "name": "efficient bigint",
+                "link": "./entries/dewert99/big_fib.rs"
+            }
+        ]
+    },
+    {
+        "github": "Zhengdw",
+        "name": "David Zheng",
+        "title": "PhD Candidate, UIUC",
+        "entries": [
+            {
+                "name": "actual_fib",
+                "link": "./entries/Zhengdw/actual_fib.txt"
             }
         ]
     },
@@ -378,5 +442,16 @@
                 "link": "./entries/markusde/collatz/collatz.png"
             }
         ]
+    },
+    {
+        "github": "nwoeanhinnogaehr",
+        "name": "Noah Weninger",
+        "title": "PhD Student, UWaterloo",
+        "entries": [
+            {
+                "name": "x86 ELF",
+                "link": "./entries/nwoeanhinnogaehr/fib.asm"
+            }
+        ]
     }
 ]