Merge branch 'main' into feat/octave

davevad93 · Dec 10, 2024 · b0075b9 · b0075b9
2 parents 9107173 + 7292907
commit b0075b9
Show file tree

Hide file tree

Showing 24 changed files with 595 additions and 76 deletions.
diff --git a/.gitignore b/.gitignore
@@ -3,5 +3,6 @@ code
 .idea/
 *.user
 *.o
+*.ali
 .aider*
-.env
+.env
diff --git a/README.md b/README.md
@@ -1,4 +1,3 @@
-https://benjdd.com/languages/ and https://benjdd.com/languages2/
 
 # Languages
 
@@ -40,7 +39,7 @@ To run one of the benchmarks:
 
 4. For good measure, execute `$ ../clean.sh` when finished.
 
-`bash ../run.sh` runs each program three times using the `runOnce` function and `awk` captures the real execution time.
+Hyperfine is used to warm, execute, and time the runs of the programs.
 
 ## Adding
 
@@ -56,10 +55,16 @@ You are also welcome to add new top-level benchmarks dirs
 
 # Available Benchmarks
 
-## loops
+### [loops](./loops/README.md)
 
-Emphasizes loop, conditional, and basic math performance.
+### [fibonacci](./fibonacci/README.md)
 
-## fibonacci
+### [levenshtein](./levenshtein/README.md)
 
-Emphasizes function call overhead and recursion.
+# Corresponding visuals
+
+Several visuals have been published based on the work here.
+More will likely be added in the future, as this repository improves:
+
+- https://benjdd.com/languages
+- https://benjdd.com/languages2
diff --git a/compile.sh b/compile.sh
@@ -1,3 +1,4 @@
+
 clang -O3 c/code.c -o c/code
 clang++ -std=c++23 -march=native -O3 -Ofast -o cpp/code cpp/code.cpp
 go build -ldflags "-s -w" -o go/code go/code.go
@@ -15,7 +16,6 @@ nim -d:release --threads:off --stackTrace:off --lineTrace:off --opt:speed -x:off
 sbcl --noinform --non-interactive --load "common-lisp/code.lisp" --build
 fpc -O3 fpc/code.pas
 crystal build -o crystal/code --release crystal/code.cr
-#gnatmake -O3 -gnat2022 -gnatp -flto ada/code.adb -D ada -o ada/code
 scala-cli --power package scala/code.scala -f -o scala/code
 ldc2 -O3 -release -boundscheck=off -mcpu=native flto=thin d/code.d
 odin build odin/code.odin -o:speed -file -out:odin/code
@@ -24,14 +24,16 @@ gfortran -O3 fortran/code.f90 -o fortran/code
 zig build-exe -O ReleaseFast -femit-bin=zig/code zig/code.zig
 luajit -b lua/code.lua lua/code
 swiftc -O -parse-as-library -Xcc -funroll-loops -Xcc -march=native -Xcc -ftree-vectorize -Xcc -ffast-math swift/code.swift -o swift/code
-# haxe --class-path haxe -main Code --jvm haxe/code.jar # was getting errors running `haxelib install hxjava`
-#dotnet publish csharp -o csharp/code-aot /p:PublishAot=true /p:OptimizationPreference=Speed
 dotnet publish csharp -o csharp/code
-#dotnet publish fsharp -o fsharp/code-aot /p:PublishAot=true /p:OptimizationPreference=Speed
 dotnet publish fsharp -o fsharp/code
 ghc -O2 -fllvm haskell/code.hs -o haskell/code || { echo "ghc: cannot compile with llvm backend; fallback to use default backend"; ghc -O2 haskell/code.hs -o haskell/code; }
 v -prod -cc clang -d no_backtrace -gc none -o v/code v/code.v
 emojicodec emojicode/code.emojic
 echo '(compile-program "chez/code.ss")' | chez --optimize-level 3 -q
 (cd clojure && mkdir -p classes && clojure -Sdeps '{:paths ["."]}' -M -e "(compile 'code)")
 cobc -I /opt/homebrew/include/ -O -O2 -O3 -Os -x -o cobol/main cobol/main.cbl
+lake build --dir lean4 
+#dotnet publish fsharp -o fsharp/code-aot /p:PublishAot=true /p:OptimizationPreference=Speed
+# haxe --class-path haxe -main Code --jvm haxe/code.jar # was getting errors running `haxelib install hxjava`
+#dotnet publish csharp -o csharp/code-aot /p:PublishAot=true /p:OptimizationPreference=Speed
+#gnatmake -O3 -gnat2022 -gnatp -flto ada/code.adb -D ada -o ada/code
diff --git a/fibonacci/README.md b/fibonacci/README.md
@@ -0,0 +1,30 @@
+# Fibonacci
+
+This program computes the sum of the first N fibonacci numbers.
+Each fibonacci number is computed using a naive recursive solution.
+Submissions using faster tail-recursion or iterative solutions will not not be accepted.
+Emphasizes function call overhead, stack pushing / popping, and recursion.
+
+Below is the reference C program.
+All languages must do the equivalent amount of work and meet these requirements:
+
+```C
+#include "stdio.h"
+#include "stdlib.h"
+#include "stdint.h"
+                                           // ALL IMPLEMENTAITONS MUST...
+int32_t fibonacci(int32_t n) {             // Have a function that recursively compute a fibonacci number with this naive algorithm
+  if (n == 0) return 0;                    // Base case for input 0
+  if (n == 1) return 1;                    // Base case for input 1
+  return fibonacci(n-1) + fibonacci(n-2);  // Must make two recursive calls for each non-base invocation
+}                                          // No result caching, conversion to tail recursion, or iterative solutions.
+
+int main (int argc, char** argv) {
+  int32_t u = atoi(argv[1]);               // Get exactly one numberic value from the command line
+  int32_t r = 0;                           // Create variable to store sum
+  for (int32_t i = 1; i < u; i++) {        // Loop 1...u times
+    r += fibonacci(i);                     // Sum all fibonacci numbers 1...u
+  }
+  printf("%d\n", r);                       // Print out the single, numeric sum
+}
+```
diff --git a/fibonacci/ada/.gitignore b/fibonacci/ada/.gitignore
diff --git a/fibonacci/kotlin/code.kt b/fibonacci/kotlin/code.kt
@@ -1,7 +1,7 @@
 fun fibonacci(n: Int): Int {
     if (n == 0) return 0
     if (n == 1) return 1
-    return fibonacci(n-1) + fibonacci(n-2)
+    return fibonacci(n - 1) + fibonacci(n - 2)
 }
 
 fun main(args: Array<String>) {

diff --git a/fibonacci/lean4/Main.lean b/fibonacci/lean4/Main.lean
@@ -0,0 +1,14 @@
+import Std
+
+partial def fibonacci (n : UInt32): UInt32 :=
+  match n with
+  | 0 => 0
+  | 1 => 1
+  | _ => fibonacci (n-2) + fibonacci (n-1)
+
+def main (args : List String) : IO Unit := do
+  let u : Nat := args[0]!.toNat!
+  let mut r : UInt32 := 0
+  for i in [1:u] do
+    r := r + fibonacci i.toUInt32
+  IO.println r
diff --git a/fibonacci/lean4/lake-manifest.json b/fibonacci/lean4/lake-manifest.json
@@ -0,0 +1,5 @@
+{"version": "1.1.0",
+ "packagesDir": ".lake/packages",
+ "packages": [],
+ "name": "lean4",
+ "lakeDir": ".lake"}
diff --git a/fibonacci/lean4/lakefile.toml b/fibonacci/lean4/lakefile.toml
@@ -0,0 +1,10 @@
+name = "lean4"
+version = "0.1.0"
+defaultTargets = ["lean4"]
+
+[[lean_lib]]
+name = "Lean4"
+
+[[lean_exe]]
+name = "lean4"
+root = "Main"
diff --git a/fibonacci/lean4/lean-toolchain b/fibonacci/lean4/lean-toolchain
@@ -0,0 +1 @@
+leanprover/lean4:stable
diff --git a/levenshtein/README.md b/levenshtein/README.md
@@ -0,0 +1,71 @@
+# Levenshtein
+
+This program computes the [levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance) between all of the strings provided on the command line.
+It prints out the total number of strings compared for distance, and the lowest distance score of all comparisons.
+This program emphasizes array/string access and basic looping and conditionals.
+
+Below is the reference C program.
+All languages must do the equivalent amount of work and meet these requirements:
+
+```C
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+                                // ALL IMPLEMENTATIONS MUST...
+int min(int a, int b, int c) {  // Have a function for calculating min
+  int min = a;                  // If the language has a builtin or standard library min that supports 3+ inputs, that may be used as an alternative.
+  if (b < min) min = b;
+  if (c < min) min = c;
+  return min;
+}
+
+int levenshtein(const char *str1, const char *str2) {  // A function that takes two string inputs, returns levenshtein distance
+  int m = strlen(str1);                                // The lengths of the two strings must be ascertained somehow
+  int n = strlen(str2);
+
+  int matrix[m+1][n+1];                                // A MxN matrix must be allocated. Either stack or heap is acceptable.
+
+  for (int i = 0; i <= m; i++) {                       // Matrix initialization step to generate first row and column.
+    matrix[i][0] = i;
+  }
+  for (int j = 0; j <= n; j++) {
+    matrix[0][j] = j;
+  }
+
+  for (int i = 1; i <= m; i++) {                       // Entire levenshtein matrix must be populated
+    for (int j = 1; j <= n; j++) {                     // Using standard / naive levenshtein algorithm
+      int cost = (str1[i-1] == str2[j-1]) ? 0 : 1;
+      matrix[i][j] = min(matrix[i-1][j] + 1,
+                         matrix[i][j-1] + 1,
+                         matrix[i-1][j-1] + cost);
+    }
+  }
+
+  // The matrix must be cleaned up.
+  // For a heap allocation this means some form of cleanup
+  // For example, in C, call(s) to free()
+  // If stack was used, should just clean up when returning
+  return matrix[m][n];
+}
+
+int main(int argc, char *argv[]) {                     // Program accepts any number of string inputs on the command line
+  int min_distance = -1;
+  int times = 0;
+  for (int i = 0; i < argc-1; i++) {                   // Compute levenshtein distance for all combinations of input strings
+    for (int j = 0; j < argc-1; j++) {
+      if (i != j) {                                    // Not including comparing a string with itself
+        int distance = levenshtein(argv[i+1], argv[j+1]);
+        if (min_distance == -1 || min_distance > distance) {
+          min_distance = distance;                     // Keep track of the minimum distance
+        }
+        times++;                                       // Keep track of number of distance calls performed
+      }
+    }
+  }
+
+  printf("times: %d\n", times);                        // Print out count of distance calls performed
+  printf("min_distance: %d\n", min_distance);          // Print out minimum distance
+
+  return 0;
+}
+```
diff --git a/levenshtein/ada/code.adb b/levenshtein/ada/code.adb
@@ -0,0 +1,96 @@
+with Ada.Text_IO;         use Ada.Text_IO;
+with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
+with Ada.Command_Line;    use Ada.Command_Line;
+
+procedure Code is
+   type Matrix_Type is array (Natural range <>, Natural range <>) of Integer;
+
+   Min_Distance : Integer := -1;
+   Times        : Natural := 0;
+   Distance     : Integer := 0;
+
+   ---------
+   -- Min --
+   ---------
+
+   function Min (A, B, C : Natural) return Natural is
+      Min : Natural := A;
+   begin
+      if B < Min then
+         Min := B;
+      end if;
+
+      if C < Min then
+         Min := C;
+      end if;
+
+      return Min;
+   end Min;
+
+   -----------------
+   -- Levenshtein --
+   -----------------
+
+   function Levenshtein_Distance
+     (Str1 : in String; Str2 : in String) return Natural
+   is
+      M : Natural := Str1'Length;
+      N : Natural := Str2'Length;
+
+      Matrix : Matrix_Type (0 .. M + 1, 0 .. N + 1) :=
+        (others => (others => 0));
+
+      Cost : Natural := 0;
+   begin
+      for I in Matrix'Range(1) loop
+         Matrix (I, 0) := I;
+      end loop;
+
+      for J in Matrix'Range(2) loop
+         Matrix (0, J) := J;
+      end loop;
+
+      for I in 1 .. M loop
+         for J in 1 .. N loop
+
+            if Str1 (I) = Str2 (J) then
+               Cost := 0;
+            else
+               Cost := 1;
+            end if;
+
+            Matrix (I, J) :=
+              Min
+                (Matrix (I - 1, J) + 1,
+                 Matrix (I, J - 1) + 1,
+                 Matrix (I - 1, J - 1) + Cost);
+         end loop;
+      end loop;
+
+      return Matrix (M, N);
+   end Levenshtein_Distance;
+
+begin
+   for I in 1 .. Argument_Count loop
+      for J in 1 .. Argument_Count loop
+
+         if I /= J then
+            Distance := Levenshtein_Distance (Argument (I), Argument (J));
+
+            if (Min_Distance = -1) or (Min_Distance > Distance) then
+               Min_Distance := Distance;
+            end if;
+            Times := Times + 1;
+         end if;
+
+      end loop;
+   end loop;
+
+   Put ("times: ");
+   Put (Item => Times, Width => 1);
+   New_Line;
+   Put ("min_distance: ");
+   Put (Item => Min_Distance, Width => 1);
+   New_Line;
+
+end Code;
diff --git a/levenshtein/c/code.c b/levenshtein/c/code.c
@@ -0,0 +1,65 @@
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+int min(int a, int b, int c) {
+  int min = a;
+  if (b < min) min = b;
+  if (c < min) min = c;
+  return min;
+}
+
+// Compute Levenshtein distance between two strings
+int levenshtein_distance(const char *str1, const char *str2) {
+  int m = strlen(str1);
+  int n = strlen(str2);
+
+  // Create a matrix to store distances
+  int matrix[m+1][n+1];
+
+  // Initialize first row and column
+  for (int i = 0; i <= m; i++) {
+    matrix[i][0] = i;
+  }
+  for (int j = 0; j <= n; j++) {
+    matrix[0][j] = j;
+  }
+
+  // Compute Levenshtein distance
+  for (int i = 1; i <= m; i++) {
+    for (int j = 1; j <= n; j++) {
+      int cost = (str1[i-1] == str2[j-1]) ? 0 : 1;
+      matrix[i][j] = min(
+        matrix[i-1][j] + 1,      // Deletion
+        matrix[i][j-1] + 1,      // Insertion
+        matrix[i-1][j-1] + cost  // Substitution
+      );
+    }
+  }
+
+  return matrix[m][n];
+}
+
+int main(int argc, char *argv[]) {
+  int min_distance = -1;
+  int times = 0;
+  for (int i = 0; i < argc-1; i++) {
+    for (int j = 0; j < argc-1; j++) {
+      if (i != j) {
+        int distance = levenshtein_distance(argv[i+1], argv[j+1]);
+        if (min_distance == -1 || min_distance > distance) {
+          min_distance = distance;
+        }
+        times++;
+      }
+    }
+  }
+
+  // The only output from the program should be the times (number of comparisons) 
+  // and min distance calculated of all comparisons. Two total lines of output, 
+  // formatted exactly like this.
+  printf("times: %d\n", times);
+  printf("min_distance: %d\n", min_distance);
+
+  return 0;
+}
diff --git a/levenshtein/input.txt b/levenshtein/input.txt
@@ -0,0 +1 @@
+aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cccccccccccccccccccccccccccccccccccccccccccccccccccc ddddddddddddddd eeeeeeeeeeeeeeeee ffffffffffffff ggggggggggg hhhhhhhhhhhhhhhhhhhhhhhhhhhhh iiiiiiiiiiiiiiiiiiiiiiiiiiiii jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk llllllllllllllllllllllllllllllllllllllllllllll mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn ooooooooooooooooooooooooooooooooo pppppppppppppppppppppppppppppppppppppppppp qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq rrrrrrrrrrrrrrrrrrrrrrrrrrrrr ssssssssssssssssssssssssssssss tttttttttttttttttttttttttt uuuuuuuuuuuuuuuuuuuuuuuuu vvvvvvvvvvvvvvvvvvvvvvvvvvvvv wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm 1234567890 QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890 mnxbckfjquwhduywetdftfqrcfgzbxmcsdlsppweuouhftvjcsmnbsdvuqtfvcjbxmcnbkaoqwerpweiurigjhdfjbmsbjgqiuyeiruyoisbnsvuyfguweygrhoaiosjdkjhfbsjhdvfkqjnoi gaywgeudgaewytfvajsdvfjahsdvfjhsdfjhgsfjhqowiueryiuweytruiyytfyqvhgvzxncbsidfjdflsdfpwoeiriuwheuyfvydtvqyuygbhskdjfbkajbuywgduywegfvsnmwehriygwuerygwerdfjhsdfsdkfhbsjdhfjuavufywefhuwlihfoqwehqrwheiruyuyqgruwieqrhsdjhfbjwhvdfisdufhikquhweifgbwfisdhfksjdhfiwuh ASDFHWERFIWSHHSDFJWERPWFOAHDSDFXMCVNWMERKJQEOQIWRUQIHJSBFSDFKJSDFOWIERIOU werkjhiauwryisydgcfkjsdfkjsjdhfguiyqgtfsdfSDGFDSFGwsrhqwigdeyiwefDFBdkqedfgdFHGHKJiFHTYRGFsefjhwhsgdfjhhjsdfDWEfsdfWEFfbgFGjYuioIOpvbnVBNSDFadfsSDFwegsdgfAWFDFGDFghjTyIGHJREGFsddqwdsdfweaWQAZZSDGgnlpHmHJMgkOYUTDFGSFSDFSDFDHGDFGSDFDGRFjhbjshdgfjhgsdfSDGDFG kjsdfkhgwieyfguwsyefgsdfSDFGJSDAKFDSAFIRFYUDSFHSBVXCVBNMSDKFJWOYSDFHKADSDnfsdfjbjshdbfkwjbfksdbfhwbkyguygyfshbcdmnxbvcmnsdkfsdfsdflspflwoekorwueiruygwuygjshbvnbvzcjsuhfdiuhsdfghkwjhdfiwegfjdhsgfbksjhfksdhgfhsdhfghfgfgfsjdjfhkwjehoueuq abcdefghijklmnopqrstuvwxyz qwerty elephant lolipop candycrush emojicode python java dart zig hellothere superb transistor caliber caliper caterpillar conglomerate starched startled
-Original file line number
+Diff line change
@@ Expand Up / @@ -3,5 +3,6 @@ code @@
     .idea/
     *.user
     *.o
+    *.ali
     .aider*
-    .env
+    .env
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb cccccccccccccccccccccccccccccccccccccccccccccccccccc ddddddddddddddd eeeeeeeeeeeeeeeee ffffffffffffff ggggggggggg hhhhhhhhhhhhhhhhhhhhhhhhhhhhh iiiiiiiiiiiiiiiiiiiiiiiiiiiii jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk llllllllllllllllllllllllllllllllllllllllllllll mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn ooooooooooooooooooooooooooooooooo pppppppppppppppppppppppppppppppppppppppppp qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq rrrrrrrrrrrrrrrrrrrrrrrrrrrrr ssssssssssssssssssssssssssssss tttttttttttttttttttttttttt uuuuuuuuuuuuuuuuuuuuuuuuu vvvvvvvvvvvvvvvvvvvvvvvvvvvvv wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm 1234567890 QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890 mnxbckfjquwhduywetdftfqrcfgzbxmcsdlsppweuouhftvjcsmnbsdvuqtfvcjbxmcnbkaoqwerpweiurigjhdfjbmsbjgqiuyeiruyoisbnsvuyfguweygrhoaiosjdkjhfbsjhdvfkqjnoi gaywgeudgaewytfvajsdvfjahsdvfjhsdfjhgsfjhqowiueryiuweytruiyytfyqvhgvzxncbsidfjdflsdfpwoeiriuwheuyfvydtvqyuygbhskdjfbkajbuywgduywegfvsnmwehriygwuerygwerdfjhsdfsdkfhbsjdhfjuavufywefhuwlihfoqwehqrwheiruyuyqgruwieqrhsdjhfbjwhvdfisdufhikquhweifgbwfisdhfksjdhfiwuh ASDFHWERFIWSHHSDFJWERPWFOAHDSDFXMCVNWMERKJQEOQIWRUQIHJSBFSDFKJSDFOWIERIOU werkjhiauwryisydgcfkjsdfkjsjdhfguiyqgtfsdfSDGFDSFGwsrhqwigdeyiwefDFBdkqedfgdFHGHKJiFHTYRGFsefjhwhsgdfjhhjsdfDWEfsdfWEFfbgFGjYuioIOpvbnVBNSDFadfsSDFwegsdgfAWFDFGDFghjTyIGHJREGFsddqwdsdfweaWQAZZSDGgnlpHmHJMgkOYUTDFGSFSDFSDFDHGDFGSDFDGRFjhbjshdgfjhgsdfSDGDFG kjsdfkhgwieyfguwsyefgsdfSDFGJSDAKFDSAFIRFYUDSFHSBVXCVBNMSDKFJWOYSDFHKADSDnfsdfjbjshdbfkwjbfksdbfhwbkyguygyfshbcdmnxbvcmnsdkfsdfsdflspflwoekorwueiruygwuygjshbvnbvzcjsuhfdiuhsdfghkwjhdfiwegfjdhsgfbksjhfksdhgfhsdhfghfgfgfsjdjfhkwjehoueuq abcdefghijklmnopqrstuvwxyz qwerty elephant lolipop candycrush emojicode python java dart zig hellothere superb transistor caliber caliper caterpillar conglomerate starched startled