diff options
| -rw-r--r-- | entries/Tarcisio-Teixeira/differential.py | 10 | ||||
| -rw-r--r-- | entries/Zhengdw/actual_fib.txt | 1 | ||||
| -rw-r--r-- | entries/dewert99/big_fib.rs | 40 | ||||
| -rw-r--r-- | entries/funemy/.gitignore | 3 | ||||
| -rw-r--r-- | entries/funemy/haskell/morphib.hs | 43 | ||||
| -rw-r--r-- | entries/funemy/koka/fib.kk | 12 | ||||
| -rw-r--r-- | entries/funemy/symbolic/phib.py | 21 | ||||
| -rwxr-xr-x | entries/funemy/z3/z3fib.sh | 2 | ||||
| -rwxr-xr-x | entries/funemy/z3/z4fib.sh | 40 | ||||
| -rw-r--r-- | entries/jlouis/README.md | 11 | ||||
| -rw-r--r-- | entries/jlouis/bin/dune | 4 | ||||
| -rw-r--r-- | entries/jlouis/bin/main.ml | 1 | ||||
| -rw-r--r-- | entries/jlouis/dune-project | 3 | ||||
| -rw-r--r-- | entries/jlouis/fib.opam | 0 | ||||
| -rw-r--r-- | entries/jlouis/lib/dune | 5 | ||||
| -rw-r--r-- | entries/jlouis/lib/fib.ml | 72 | ||||
| -rw-r--r-- | entries/jlouis/shell.nix | 11 | ||||
| -rw-r--r-- | entries/jyoo980/aspectj/Fibonacci.aj | 21 | ||||
| -rw-r--r-- | entries/kevindhir/aws/Solution.java | 21 | ||||
| -rw-r--r-- | entries/kevindhir/ts/fib.ts | 8 | ||||
| -rw-r--r-- | entries/nwoeanhinnogaehr/fib.asm | 59 | ||||
| -rw-r--r-- | people.json | 137 |
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" + } + ] } ] |