aboutsummaryrefslogtreecommitdiff
path: root/impls
diff options
context:
space:
mode:
Diffstat (limited to 'impls')
-rw-r--r--impls/bsearch-gen.el9
-rw-r--r--impls/bsearch.cpp57
-rw-r--r--impls/btree.cpp109
-rw-r--r--impls/list.cpp134
-rw-r--r--impls/powerset.rkt69
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)))))
generated by cgit v1.2.3-13-gbd6f (git 2.30.0) at 2024-12-25 02:07:57 +0000