From 4359caa3ca15c75c4241d869259af3be8cc8375f Mon Sep 17 00:00:00 2001 From: Aryadev Chavali Date: Mon, 29 Apr 2024 15:43:17 +0530 Subject: Moved implementations to folder --- Makefile | 10 ++-- bsearch-gen.el | 9 ---- bsearch.cpp | 57 ---------------------- btree.cpp | 109 ----------------------------------------- impls/bsearch-gen.el | 9 ++++ impls/bsearch.cpp | 57 ++++++++++++++++++++++ impls/btree.cpp | 109 +++++++++++++++++++++++++++++++++++++++++ impls/list.cpp | 134 +++++++++++++++++++++++++++++++++++++++++++++++++++ impls/powerset.rkt | 69 ++++++++++++++++++++++++++ list.cpp | 134 --------------------------------------------------- powerset.rkt | 69 -------------------------- 11 files changed, 383 insertions(+), 383 deletions(-) delete mode 100644 bsearch-gen.el delete mode 100644 bsearch.cpp delete mode 100644 btree.cpp create mode 100644 impls/bsearch-gen.el create mode 100644 impls/bsearch.cpp create mode 100644 impls/btree.cpp create mode 100644 impls/list.cpp create mode 100644 impls/powerset.rkt delete mode 100644 list.cpp delete mode 100644 powerset.rkt diff --git a/Makefile b/Makefile index afdfdbf..b7ca82b 100644 --- a/Makefile +++ b/Makefile @@ -1,15 +1,15 @@ CC=clang++ -CFLAGS=-pedantic -Wall -ggdb -fsanitize=address +CFLAGS=-pedantic -Wall -Wextra -Werror -fsanitize=address -fsanitize=undefined -ggdb -fsanitize=address VFLAGS=--show-leak-kinds=all --leak-check=full OUT= -btree.out: btree.cpp +btree.out: impls/btree.cpp $(CC) $(CFLAGS) $^ -o $@ -list.out: list.cpp +list.out: impls/list.cpp $(CC) $(CFLAGS) $^ -o $@ -bsearch.out: bsearch.cpp +bsearch.out: impls/bsearch.cpp $(CC) $(CFLAGS) $^ -o $@ .PHONY: run @@ -18,4 +18,4 @@ run: $(OUT) .PHONY: clean clean: - rm -v *.out; + rm -v *.out *.txt; diff --git a/bsearch-gen.el b/bsearch-gen.el deleted file mode 100644 index 79aac56..0000000 --- a/bsearch-gen.el +++ /dev/null @@ -1,9 +0,0 @@ -(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/bsearch.cpp b/bsearch.cpp deleted file mode 100644 index 6172b15..0000000 --- a/bsearch.cpp +++ /dev/null @@ -1,57 +0,0 @@ -/* bsearch.cpp - * Created: 2023-07-10 - * Author: Aryadev Chavali - */ - -#include -#include -#include -#include -#include -#include - -using std::cin; -using std::cout; -using std::endl; -using std::ostream; -using std::string; -using std::vector; - -vector 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/btree.cpp b/btree.cpp deleted file mode 100644 index 4067aad..0000000 --- a/btree.cpp +++ /dev/null @@ -1,109 +0,0 @@ -/* btree.cpp - * Date: 2021-11-22 - * Author: Aryadev Chavali - */ - -#include - -enum Order -{ - LT, - GT, - EQ -}; - -template -struct BinaryTree -{ - T value; - BinaryTree *left, *right; - enum Order (*compare)(T, T); - BinaryTree(T val, BinaryTree *l, BinaryTree *r, enum Order (*cmp)(T, T)) - { - value = val; - left = l; - right = r; - compare = cmp; - } - - ~BinaryTree() - { - delete left; - delete right; - } -}; - -template -BinaryTree *insert(BinaryTree *tree, T value) -{ - BinaryTree **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(value, nullptr, nullptr, tree->compare); - return tree; -} - -template -void rightRotate(BinaryTree **tree) -{ - auto left = *tree->left; - *tree->left = left->right; - left->right = *tree; - *tree = left; -} - -template -void leftRotate(BinaryTree **tree) -{ - auto right = (*tree)->right; - (*tree)->right = right->left; - right->left = *tree; - *tree = right; -} - -template -std::ostream &operator<<(std::ostream &ostream, const BinaryTree *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(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/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 +#include +#include +#include +#include +#include + +using std::cin; +using std::cout; +using std::endl; +using std::ostream; +using std::string; +using std::vector; + +vector 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 + +enum Order +{ + LT, + GT, + EQ +}; + +template +struct BinaryTree +{ + T value; + BinaryTree *left, *right; + enum Order (*compare)(T, T); + BinaryTree(T val, BinaryTree *l, BinaryTree *r, enum Order (*cmp)(T, T)) + { + value = val; + left = l; + right = r; + compare = cmp; + } + + ~BinaryTree() + { + delete left; + delete right; + } +}; + +template +BinaryTree *insert(BinaryTree *tree, T value) +{ + BinaryTree **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(value, nullptr, nullptr, tree->compare); + return tree; +} + +template +void rightRotate(BinaryTree **tree) +{ + auto left = *tree->left; + *tree->left = left->right; + left->right = *tree; + *tree = left; +} + +template +void leftRotate(BinaryTree **tree) +{ + auto right = (*tree)->right; + (*tree)->right = right->left; + right->left = *tree; + *tree = right; +} + +template +std::ostream &operator<<(std::ostream &ostream, const BinaryTree *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(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 +#include +#include + +template +struct List +{ + T value; + List *next; + + List(T val, List *n) + { + value = val; + next = n; + } + + ~List() + { + if (next == nullptr) + return; + delete next; + } +}; + +template +List *append(List *lst, T value) +{ + List *node; + if (lst == nullptr) + return new List(value, nullptr); + + for (node = lst; node->next != nullptr; node = node->next) + continue; + + node->next = new List(value, nullptr); + return lst; +} + +/** Reverse a list + */ +template +List *reverse(List *lst, List *prev = nullptr) +{ + auto next = lst->next; + lst->next = prev; + if (next == nullptr) + return lst; + return reverse(next, lst); +} + +template +List *map(List *lst, U (*f)(T)) +{ + if (!lst) + return nullptr; + return new List(f(lst->value), map(lst->next, f)); +} + +template +T reduce(List *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 +List *filter(List *lst, bool (*f)(T), List *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 +std::ostream &operator<<(std::ostream &ostream, const List *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(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(lst = reverse(lst), + [](int x) + { + return x * 2; + }); + std::cout << mapped << std::endl; + delete mapped; + printf("Sum all numbers in list: "); + std::cout << reduce( + lst, + [](int a, int b) + { + return a + b; + }, + 0) + << std::endl; + printf("Print all even numbers 1..10: "); + auto evens = filter(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))))) diff --git a/list.cpp b/list.cpp deleted file mode 100644 index b87a3e2..0000000 --- a/list.cpp +++ /dev/null @@ -1,134 +0,0 @@ -/* list.cpp - * Date: 2021-11-20 - * Author: Aryadev Chavali - */ - -#include -#include -#include - -template -struct List -{ - T value; - List *next; - - List(T val, List *n) - { - value = val; - next = n; - } - - ~List() - { - if (next == nullptr) - return; - delete next; - } -}; - -template -List *append(List *lst, T value) -{ - List *node; - if (lst == nullptr) - return new List(value, nullptr); - - for (node = lst; node->next != nullptr; node = node->next) - continue; - - node->next = new List(value, nullptr); - return lst; -} - -/** Reverse a list - */ -template -List *reverse(List *lst, List *prev = nullptr) -{ - auto next = lst->next; - lst->next = prev; - if (next == nullptr) - return lst; - return reverse(next, lst); -} - -template -List *map(List *lst, U (*f)(T)) -{ - if (!lst) - return nullptr; - return new List(f(lst->value), map(lst->next, f)); -} - -template -T reduce(List *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 -List *filter(List *lst, bool (*f)(T), List *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 -std::ostream &operator<<(std::ostream &ostream, const List *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(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(lst = reverse(lst), - [](int x) - { - return x * 2; - }); - std::cout << mapped << std::endl; - delete mapped; - printf("Sum all numbers in list: "); - std::cout << reduce( - lst, - [](int a, int b) - { - return a + b; - }, - 0) - << std::endl; - printf("Print all even numbers 1..10: "); - auto evens = filter(lst, - [](int a) - { - return a % 2 == 0; - }); - std::cout << evens << std::endl; - delete lst; - delete evens; - return 0; -} diff --git a/powerset.rkt b/powerset.rkt deleted file mode 100644 index bbece52..0000000 --- a/powerset.rkt +++ /dev/null @@ -1,69 +0,0 @@ -#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))))) -- cgit v1.2.3-13-gbd6f