Moved implementations to folder

5 files changed, 378 insertions, 0 deletions

diff --git a/impls/bsearch-gen.el b/impls/bsearch-gen.el
new file mode 100644
index 0000000..79aac56
--- /dev/null
+++ b/impls/bsearch-gen.el
@@ -0,0 +1,9 @@
+(defconst *LIST-SIZE* 128)
+(defconst *UPPER-BOUND* 1024)
+(with-current-buffer (find-file "bsearch.txt")
+  (mapcar
+   #'(lambda (res) (insert (format "%s\n" res)))
+   (cl-loop
+    for i from 0 to *LIST-SIZE*
+    collect
+    (random *UPPER-BOUND*))))
diff --git a/impls/bsearch.cpp b/impls/bsearch.cpp
new file mode 100644
index 0000000..6172b15
--- /dev/null
+++ b/impls/bsearch.cpp
@@ -0,0 +1,57 @@
+/* bsearch.cpp
+ * Created: 2023-07-10
+ * Author: Aryadev Chavali
+ */
+
+#include <algorithm>
+#include <cstdlib>
+#include <fstream>
+#include <iostream>
+#include <string>
+#include <vector>
+
+using std::cin;
+using std::cout;
+using std::endl;
+using std::ostream;
+using std::string;
+using std::vector;
+
+vector<int> arr;
+
+ostream &print_arr(ostream &os)
+{
+  os << "[";
+  for (size_t i = 0; i < arr.size(); ++i)
+    os << arr[i] << (i == arr.size() - 1 ? "" : ",");
+  return os << "]";
+}
+
+int bsearch(int n, int l = 0, int u = arr.size() - 1)
+{
+  int midpoint = ((u + l) / 2);
+  if (l >= u || u <= 0)
+    return -1;
+  int val = arr[midpoint];
+  if (val == n)
+    return midpoint;
+  else if (val > n)
+    return bsearch(n, l, midpoint - 1);
+  else
+    return bsearch(n, midpoint + 1, u);
+}
+
+int main(void)
+{
+  std::ifstream input("bsearch.txt");
+  string line;
+  while (std::getline(input, line))
+    arr.push_back(std::stoi(line));
+  std::sort(std::begin(arr), std::end(arr));
+  string inp;
+  cout << "Enter number to search: ";
+  cin >> inp;
+  int to_search = std::stoi(inp);
+  cout << bsearch(to_search) << endl;
+  return 0;
+}
diff --git a/impls/btree.cpp b/impls/btree.cpp
new file mode 100644
index 0000000..4067aad
--- /dev/null
+++ b/impls/btree.cpp
@@ -0,0 +1,109 @@
+/* btree.cpp
+ * Date: 2021-11-22
+ * Author: Aryadev Chavali
+ */
+
+#include <iostream>
+
+enum Order
+{
+  LT,
+  GT,
+  EQ
+};
+
+template <typename T>
+struct BinaryTree
+{
+  T value;
+  BinaryTree<T> *left, *right;
+  enum Order (*compare)(T, T);
+  BinaryTree(T val, BinaryTree<T> *l, BinaryTree<T> *r, enum Order (*cmp)(T, T))
+  {
+    value   = val;
+    left    = l;
+    right   = r;
+    compare = cmp;
+  }
+
+  ~BinaryTree()
+  {
+    delete left;
+    delete right;
+  }
+};
+
+template <typename T>
+BinaryTree<T> *insert(BinaryTree<T> *tree, T value)
+{
+  BinaryTree<T> **node = &tree;
+  switch (tree->compare(value, tree->value))
+  {
+  case LT:
+    node = &tree->left;
+    break;
+  case EQ:
+  case GT:
+    node = &tree->right;
+    break;
+  }
+  *node = *node ? insert(*node, value)
+                : new BinaryTree<T>(value, nullptr, nullptr, tree->compare);
+  return tree;
+}
+
+template <typename T>
+void rightRotate(BinaryTree<T> **tree)
+{
+  auto left   = *tree->left;
+  *tree->left = left->right;
+  left->right = *tree;
+  *tree       = left;
+}
+
+template <typename T>
+void leftRotate(BinaryTree<T> **tree)
+{
+  auto right     = (*tree)->right;
+  (*tree)->right = right->left;
+  right->left    = *tree;
+  *tree          = right;
+}
+
+template <typename T>
+std::ostream &operator<<(std::ostream &ostream, const BinaryTree<T> *btree)
+{
+  if (!btree)
+    return ostream;
+  ostream << btree->value << "(";
+  if (btree->left)
+    ostream << btree->left;
+  if (btree->left && btree->right)
+    ostream << ", ";
+  if (btree->right)
+    ostream << btree->right;
+  ostream << ")";
+  return ostream;
+}
+
+int main(void)
+{
+  auto cmp = [](int x, int y)
+  {
+    if (x < y)
+      return LT;
+    else if (x > y)
+      return GT;
+    else
+      return EQ;
+  };
+  auto tree = new BinaryTree<int>(5, NULL, NULL, cmp);
+  for (int i = 0; i <= 5; ++i)
+    tree = insert(tree, i * 2);
+
+  leftRotate(&tree);
+  std::cout << tree << std::endl;
+
+  delete tree;
+  return 0;
+}
diff --git a/impls/list.cpp b/impls/list.cpp
new file mode 100644
index 0000000..b87a3e2
--- /dev/null
+++ b/impls/list.cpp
@@ -0,0 +1,134 @@
+/* list.cpp
+ * Date: 2021-11-20
+ * Author: Aryadev Chavali
+ */
+
+#include <cstdio>
+#include <cstdlib>
+#include <iostream>
+
+template <typename T>
+struct List
+{
+  T value;
+  List<T> *next;
+
+  List(T val, List<T> *n)
+  {
+    value = val;
+    next  = n;
+  }
+
+  ~List()
+  {
+    if (next == nullptr)
+      return;
+    delete next;
+  }
+};
+
+template <typename T>
+List<T> *append(List<T> *lst, T value)
+{
+  List<T> *node;
+  if (lst == nullptr)
+    return new List<T>(value, nullptr);
+
+  for (node = lst; node->next != nullptr; node = node->next)
+    continue;
+
+  node->next = new List<T>(value, nullptr);
+  return lst;
+}
+
+/** Reverse a list
+ */
+template <typename T>
+List<T> *reverse(List<T> *lst, List<T> *prev = nullptr)
+{
+  auto next = lst->next;
+  lst->next = prev;
+  if (next == nullptr)
+    return lst;
+  return reverse(next, lst);
+}
+
+template <typename T, typename U>
+List<U> *map(List<T> *lst, U (*f)(T))
+{
+  if (!lst)
+    return nullptr;
+  return new List<U>(f(lst->value), map(lst->next, f));
+}
+
+template <typename T>
+T reduce(List<T> *lst, T (*reducer)(T, T), T init = 0)
+{
+  if (!lst)
+    return init;
+  else if (!init)
+    init = lst->value;
+  else
+    init = reducer(init, lst->value);
+  return reduce(lst->next, reducer, init);
+}
+
+template <typename T>
+List<T> *filter(List<T> *lst, bool (*f)(T), List<T> *new_lst = nullptr)
+{
+  if (!lst)
+    return new_lst;
+  if (f(lst->value))
+    new_lst = append(new_lst, lst->value);
+  return filter(lst->next, f, new_lst);
+}
+
+template <typename T>
+std::ostream &operator<<(std::ostream &ostream, const List<T> *lst)
+{
+  if (!lst)
+    return ostream;
+  ostream << "|" << lst->value << lst->next;
+  return ostream;
+}
+
+int main(void)
+{
+  puts("Create linked list with 1..10");
+  auto lst = append<int>(nullptr, 1);
+  for (int i = 2; i <= 10; ++i)
+    lst = append(lst, i);
+  printf("Current output for list: ");
+  std::cout << lst << std::endl;
+  lst = reverse(lst);
+  printf("Reverse list: ");
+  std::cout << lst << std::endl;
+  puts("Reverse list again...");
+  printf("Map list with f(x) = 2x: ");
+  auto mapped = map<int, int>(lst = reverse(lst),
+                              [](int x)
+                              {
+                                return x * 2;
+                              });
+  std::cout << mapped << std::endl;
+  delete mapped;
+  printf("Sum all numbers in list: ");
+  std::cout << reduce<int>(
+    lst,
+    [](int a, int b)
+    {
+      return a + b;
+    },
+                   0)
+            << std::endl;
+  printf("Print all even numbers 1..10: ");
+  auto evens = filter<int>(lst,
+                           [](int a)
+                           {
+                             return a % 2 == 0;
+                           });
+  std::cout << evens << std::endl;
+  delete lst;
+  delete evens;
+  return 0;
+}
diff --git a/impls/powerset.rkt b/impls/powerset.rkt
new file mode 100644
index 0000000..bbece52
--- /dev/null
+++ b/impls/powerset.rkt
@@ -0,0 +1,69 @@
+#lang racket
+
+(define (subsets-of lst n)
+  (cond
+    [(null? lst) null] ; 0 ways of making anything out of empty set
+    [(= n 0) (list null)] ; 1 way of making a 0 sized subset of something
+    [(= n 1) (map list lst)] ; |lst| ways of making singletons
+    [else
+     (let ([head (car lst)]
+           [tail (cdr lst)])
+       (append
+        ;; HEAD is a part of the subset, so the rest of the subset
+        ;; must be an n-1 sized subset of TAIL
+        (map (lambda (lst) (cons head lst))
+             (subsets-of tail (- n 1)))
+        ;; ... or HEAD is not part of the subset, so the subset is
+        ;; some n sized subset of TAIL
+        (subsets-of tail n)))]))
+
+(define (powerset lst)
+  (append* ; flatten list of n sized subsets to just get subsets
+   (map (lambda (n)
+          (subsets-of lst n)) ; get subset of size n
+        (range 0 (+ 1 (length lst)))))) ; n from 0 to |lst|
+
+(define (test? name expected got [equality equal?])
+  ;; Print success of test (i.e. (equality expected got)) and return a
+  ;; boolean representing if it worked.
+  (printf "[TEST ~a]: " name)
+  (if (equality expected got)
+      (begin
+        (displayln "Success")
+        #t)
+      (begin
+        (printf "Failure (expected=~a, got=~a)~n" expected got)
+        #f)))
+
+(define-syntax (perform-tests stx)
+  (with-syntax
+    ([t-clauses
+      (datum->syntax
+       stx
+       (map
+        (lambda (clause)
+          (syntax-case clause ()
+            [(name expected got)
+             #'(test? 'name expected got)]))
+        (cdr (syntax->list stx))))])
+    #'(and (~@ . t-clauses))))
+
+(let ([small (range 10)]
+      [medium (range 50)]
+      [large (range 100)])
+  (perform-tests
+   ;; Base case on lst
+   ("subsets-of->lst=null->n=0" 0 (length (subsets-of null 0)))
+   ("subsets-of->lst=null->n=1024" 0 (length (subsets-of null 1024)))
+   ;; Base case on n
+   ("subsets-of->lst=[10]->n=0" 1 (length (subsets-of small 0)))
+   ("subsets-of->lst=[50]->n=0" 1 (length (subsets-of medium 0)))
+   ("subsets-of->lst=[100]->n=0" 1 (length (subsets-of large 0)))
+   ;; Singletons
+   ("subsets-of->lst=[10]->n=1" 10 (length (subsets-of small 1)))
+   ("subsets-of->lst=[50]->n=1" 50 (length (subsets-of medium 1)))
+   ("subsets-of->lst=[100]->n=1" 100 (length (subsets-of large 1)))
+   ;; Binomial theorem tests (symmetry along the middle of Pascal's triangle)
+   ("subsets-of->lst=[10]->n=2~~n=8" (length (subsets-of small 2)) (length (subsets-of small 8)))
+   ("subsets-of->lst=[10]->n=3~~n=7" (length (subsets-of small 3)) (length (subsets-of small 7)))
+   ("subsets-of->lst=[10]->n=4~~n=6" (length (subsets-of small 4)) (length (subsets-of small 6)))))