diff options
Diffstat (limited to 'users/wpcarro/scratch/data_structures_and_algorithms')
53 files changed, 3797 insertions, 0 deletions
diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/array-traversals.py b/users/wpcarro/scratch/data_structures_and_algorithms/array-traversals.py new file mode 100644 index 0000000000..35cb439281 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/array-traversals.py @@ -0,0 +1,87 @@ +# This is practice for various types of list traversals that turn up. + +xs = range(10) +n = len(xs) + +print('---') +# pythonic left-to-right traversal +result = '' +for x in xs: + result += str(x) +print(result) + +print('---') +# left-to-right traversal +result = '' +for i in range(n): + result += str(xs[i]) +print(result) + +print('---') +# right-to-left traversal +result = '' +for i in range(n): + result += str(xs[n - 1 - i]) +print(result) + +print('---') +# 2x left-to-right traversal +result = '' +for i in range(2 * n): + result += str(xs[i % n]) +print(result) + +print('---') +# 2x right-to-left traversal +result = '' +for i in range(2 * n): + result += str(xs[(n - 1 - i) % n]) +print(result) + +################################################################################ +# Table traversals +################################################################################ + +table = [[row * 10 + i for i in range(10)] for row in range(3)] +row_ct = len(table) +col_ct = len(table[0]) + +print('---') +# 3x10 table traversal +result = '' +for row in table: + r = '' + for col in row: + r += '{:3d}'.format(col) + result += r + '\n' +print(result[0:-1]) + +print('---') +# 3x10 table traversal +result = '' +for row in range(row_ct): + r = '' + for col in range(col_ct): + r += '{:3d}'.format(table[row][col]) + result += r + '\n' +print(result[0:-1]) + +print('---') +# 3x10 table traversal (reverse) +result = '' +for row in range(row_ct): + r = '' + for col in range(col_ct): + r += '{:3d}'.format(table[row_ct - 1 - row][col_ct - 1 - col]) + result += r + '\n' +print(result) + +print('---') +# 3x10 column-row traversal +result = '' +for col in range(col_ct): + r = '' + for row in range(row_ct): + r += '{:3d}'.format(table[row][col]) + result += r + '\n' +print(result) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/balanced-binary-tree.py b/users/wpcarro/scratch/data_structures_and_algorithms/balanced-binary-tree.py new file mode 100644 index 0000000000..01fd965fd5 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/balanced-binary-tree.py @@ -0,0 +1,145 @@ +import unittest +from itertools import combinations + + +def balanced(xs): + """Return True if `xs` contains no two values that differ by more than + one.""" + if len(xs) == 0 or len(xs) == 1: + return True + if len(xs) == 2: + return math.abs(xs[0] - xs[1]) <= 1 + else: + pass + + +def is_leaf(node): + return node.left is None and node.right is None + + +def is_balanced(tree_root): + """Returns True if the difference between the depths of any two leaf nodes + does not exceed 1.""" + depths = set() + populate_depths(tree_root, 0, depths) + + # cartesian product - only the top half + for diff in set(abs(a - b) for a, b in combinations(depths, 2)): + if diff > 1: + return False + + return True + + +def populate_depths(node, depth, depths): + if is_leaf(node): + depths.add(depth) + else: + if node.left is not None: + populate_depths(node.left, depth + 1, depths) + if node.right is not None: + populate_depths(node.right, depth + 1, depths) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class BinaryTreeNode(object): + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def insert_left(self, value): + self.left = Test.BinaryTreeNode(value) + return self.left + + def insert_right(self, value): + self.right = Test.BinaryTreeNode(value) + return self.right + + def test_full_tree(self): + tree = Test.BinaryTreeNode(5) + left = tree.insert_left(8) + right = tree.insert_right(6) + left.insert_left(1) + left.insert_right(2) + right.insert_left(3) + right.insert_right(4) + result = is_balanced(tree) + self.assertTrue(result) + + def test_both_leaves_at_the_same_depth(self): + tree = Test.BinaryTreeNode(3) + left = tree.insert_left(4) + right = tree.insert_right(2) + left.insert_left(1) + right.insert_right(9) + result = is_balanced(tree) + self.assertTrue(result) + + def test_leaf_heights_differ_by_one(self): + tree = Test.BinaryTreeNode(6) + left = tree.insert_left(1) + right = tree.insert_right(0) + right.insert_right(7) + result = is_balanced(tree) + self.assertTrue(result) + + def test_leaf_heights_differ_by_two(self): + tree = Test.BinaryTreeNode(6) + left = tree.insert_left(1) + right = tree.insert_right(0) + right_right = right.insert_right(7) + right_right.insert_right(8) + result = is_balanced(tree) + self.assertFalse(result) + + def test_three_leaves_total(self): + tree = Test.BinaryTreeNode(1) + left = tree.insert_left(5) + right = tree.insert_right(9) + right.insert_left(8) + right.insert_right(5) + result = is_balanced(tree) + self.assertTrue(result) + + def test_both_subtrees_superbalanced(self): + tree = Test.BinaryTreeNode(1) + left = tree.insert_left(5) + right = tree.insert_right(9) + right_left = right.insert_left(8) + right.insert_right(5) + right_left.insert_left(7) + result = is_balanced(tree) + self.assertFalse(result) + + def test_both_subtrees_superbalanced_two(self): + tree = Test.BinaryTreeNode(1) + left = tree.insert_left(2) + right = tree.insert_right(4) + left.insert_left(3) + left_right = left.insert_right(7) + left_right.insert_right(8) + right_right = right.insert_right(5) + right_right_right = right_right.insert_right(6) + right_right_right.insert_right(9) + result = is_balanced(tree) + self.assertFalse(result) + + def test_only_one_node(self): + tree = Test.BinaryTreeNode(1) + result = is_balanced(tree) + self.assertTrue(result) + + def test_linked_list_tree(self): + tree = Test.BinaryTreeNode(1) + right = tree.insert_right(2) + right_right = right.insert_right(3) + right_right.insert_right(4) + result = is_balanced(tree) + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/bit-manipulation.py b/users/wpcarro/scratch/data_structures_and_algorithms/bit-manipulation.py new file mode 100644 index 0000000000..dc30bb5088 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/bit-manipulation.py @@ -0,0 +1,32 @@ +def test(x, i): + return x & (1 << i) != 0 + + +def set(x, i): + return x | (1 << i) + + +def clear(x, i): + return x & ~(1 << i) + + +def toggle(x, i): + if test(x, i): + return clear(x, i) + else: + return set(x, i) + + +def test_single(x): + if x == 0: + return False + else: + return x & (x - 1) == 0 + + +print(test(0b1010, 3)) +print('{0:b}'.format(set(0b1010, 1))) +print('{0:b}'.format(clear(0b1010, 1))) +print('{0:b}'.format(toggle(0b1010, 2))) +print(test_single(0b1010)) +print(test_single(0b1000)) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/bracket-validator.py b/users/wpcarro/scratch/data_structures_and_algorithms/bracket-validator.py new file mode 100644 index 0000000000..a50f8b074e --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/bracket-validator.py @@ -0,0 +1,63 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# is_valid :: String -> Boolean +def is_valid(xs): + s = [] + seeking = { + '}': '{', + ']': '[', + ')': '(', + } + openers = seeking.values() + closers = seeking.keys() + for c in xs: + if c in openers: + s.append(c) + elif c in closers: + if not s: + return False + elif s[-1] != seeking.get(c): + return False + else: + s.pop() + return len(s) == 0 + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_valid_short_code(self): + result = is_valid('()') + self.assertTrue(result) + + def test_valid_longer_code(self): + result = is_valid('([]{[]})[]{{}()}') + self.assertTrue(result) + + def test_interleaved_openers_and_closers(self): + result = is_valid('([)]') + self.assertFalse(result) + + def test_mismatched_opener_and_closer(self): + result = is_valid('([][]}') + self.assertFalse(result) + + def test_missing_closer(self): + result = is_valid('[[]()') + self.assertFalse(result) + + def test_extra_closer(self): + result = is_valid('[[]]())') + self.assertFalse(result) + + def test_empty_string(self): + result = is_valid('') + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/bst-checker.py b/users/wpcarro/scratch/data_structures_and_algorithms/bst-checker.py new file mode 100644 index 0000000000..689be97a85 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/bst-checker.py @@ -0,0 +1,121 @@ +import unittest + + +################################################################################ +# Implementation +################################################################################ +# is_leaf :: Node(a) -> Boolean +def is_leaf(node): + return not node.left and not node.right + + +# is_binary_search_tree :: Node(Integer) -> Set(Int) -> Set(Int) -> Boolean +def is_binary_search_tree_a(node, la=set(), ra=set()): + """My first solution for this problem.""" + for x in la: + if not node.value < x: + return False + for x in ra: + if not node.value > x: + return False + if is_leaf(node): + return True + elif not node.left: + return is_binary_search_tree( + node.right, + la=la, + ra=ra ^ {node.value}, + ) + elif not node.right: + return is_binary_search_tree(node.left, la=la ^ {node.value}, ra=ra) + else: + return all([ + is_binary_search_tree(node.left, la=la ^ {node.value}, ra=ra), + is_binary_search_tree(node.right, la=la, ra=ra ^ {node.value}) + ]) + + +# is_binary_search_tree :: Node(Int) -> Maybe(Int) -> Maybe(Int) -> Boolean +def is_binary_search_tree(node, lb=None, ub=None): + if lb: + if node.value < lb: + return False + if ub: + if node.value > ub: + return False + if is_leaf(node): + return True + elif not node.right: + return is_binary_search_tree(node.left, lb=lb, ub=node.value) + elif not node.left: + return is_binary_search_tree(node.right, lb=node.value, ub=ub) + else: + return is_binary_search_tree( + node.left, lb=lb, ub=node.value) and is_binary_search_tree( + node.right, lb=node.value, ub=ub) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class BinaryTreeNode(object): + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def insert_left(self, value): + self.left = Test.BinaryTreeNode(value) + return self.left + + def insert_right(self, value): + self.right = Test.BinaryTreeNode(value) + return self.right + + def test_valid_full_tree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + right.insert_right(80) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + def test_both_subtrees_valid(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(80) + left.insert_left(20) + left.insert_right(60) + right.insert_left(70) + right.insert_right(90) + result = is_binary_search_tree(tree) + self.assertFalse(result) + + def test_descending_linked_list(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(40) + left_left = left.insert_left(30) + left_left_left = left_left.insert_left(20) + left_left_left.insert_left(10) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + def test_out_of_order_linked_list(self): + tree = Test.BinaryTreeNode(50) + right = tree.insert_right(70) + right_right = right.insert_right(60) + right_right.insert_right(80) + result = is_binary_search_tree(tree) + self.assertFalse(result) + + def test_one_node_tree(self): + tree = Test.BinaryTreeNode(50) + result = is_binary_search_tree(tree) + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py b/users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py new file mode 100644 index 0000000000..e34a2b136a --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/cafe-order-checker.py @@ -0,0 +1,91 @@ +import unittest + + +################################################################################ +# Implementation +################################################################################ +def is_first_come_first_served(to, di, xs): + # All the guards, assertions we should need. + if to == di == xs == []: + return True + elif to == di == []: + return False + elif to == []: + return di == xs + elif to == []: + return di == xs + elif di == []: + return to == xs + elif xs == []: + return False + elif len(xs) != (len(to) + len(di)): + return False + + fst, snd = to, di + + if xs[0] == to[0]: + fst, snd = to, di + elif xs[0] == di[0]: + fst, snd = di, to + else: + return False + + fst_done, snd_done = False, False + fi, si = 1, 0 + + for i in range(1, len(xs)): + # Short-circuit and avoid index-out-of-bounds without introducing overly + # defensive, sloppy code. + if fst_done: + return snd[si:] == xs[i:] + elif snd_done: + return fst[fi:] == xs[i:] + + if fst[fi] == xs[i]: + fi += 1 + elif snd[si] == xs[i]: + si += 1 + else: + return False + + fst_done, snd_done = fi == len(fst), si == len(snd) + + return True + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_both_registers_have_same_number_of_orders(self): + result = is_first_come_first_served([1, 4, 5], [2, 3, 6], + [1, 2, 3, 4, 5, 6]) + self.assertTrue(result) + + def test_registers_have_different_lengths(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], [1, 2, 6, 3, 5]) + self.assertFalse(result) + + def test_one_register_is_empty(self): + result = is_first_come_first_served([], [2, 3, 6], [2, 3, 6]) + self.assertTrue(result) + + def test_served_orders_is_missing_orders(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], [1, 6, 3, 5]) + self.assertFalse(result) + + def test_served_orders_has_extra_orders(self): + result = is_first_come_first_served([1, 5], [2, 3, 6], + [1, 2, 3, 5, 6, 8]) + self.assertFalse(result) + + def test_one_register_has_extra_orders(self): + result = is_first_come_first_served([1, 9], [7, 8], [1, 7, 8]) + self.assertFalse(result) + + def test_one_register_has_unserved_orders(self): + result = is_first_come_first_served([55, 9], [7, 8], [1, 7, 8, 9]) + self.assertFalse(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/cake-thief.py b/users/wpcarro/scratch/data_structures_and_algorithms/cake-thief.py new file mode 100644 index 0000000000..9eddb34b2d --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/cake-thief.py @@ -0,0 +1,71 @@ +import unittest +from math import floor + + +################################################################################ +# Solution +################################################################################ +def max_duffel_bag_value(xs, cap): + ct = (cap + 1) + maxes = [0] * ct + for c in range(cap + 1): + for w, v in xs: + if w == 0 and v > 0: + return float('inf') + if w == c: + maxes[c:] = [max(maxes[c], v)] * (ct - c) + elif w < c: + d = c - w + maxes[c:] = [max(maxes[c], v + maxes[d])] * (ct - c) + else: + continue + return maxes[cap] + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_one_cake(self): + actual = max_duffel_bag_value([(2, 1)], 9) + expected = 4 + self.assertEqual(actual, expected) + + def test_two_cakes(self): + actual = max_duffel_bag_value([(4, 4), (5, 5)], 9) + expected = 9 + self.assertEqual(actual, expected) + + def test_only_take_less_valuable_cake(self): + actual = max_duffel_bag_value([(4, 4), (5, 5)], 12) + expected = 12 + self.assertEqual(actual, expected) + + def test_lots_of_cakes(self): + actual = max_duffel_bag_value([(2, 3), (3, 6), (5, 1), (6, 1), (7, 1), + (8, 1)], 7) + expected = 12 + self.assertEqual(actual, expected) + + def test_value_to_weight_ratio_is_not_optimal(self): + actual = max_duffel_bag_value([(51, 52), (50, 50)], 100) + expected = 100 + self.assertEqual(actual, expected) + + def test_zero_capacity(self): + actual = max_duffel_bag_value([(1, 2)], 0) + expected = 0 + self.assertEqual(actual, expected) + + def test_cake_with_zero_value_and_weight(self): + actual = max_duffel_bag_value([(0, 0), (2, 1)], 7) + expected = 3 + self.assertEqual(actual, expected) + + def test_cake_with_non_zero_value_and_zero_weight(self): + actual = max_duffel_bag_value([(0, 5)], 5) + expected = float('inf') + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/coins.py b/users/wpcarro/scratch/data_structures_and_algorithms/coins.py new file mode 100644 index 0000000000..eb5754f982 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/coins.py @@ -0,0 +1,57 @@ +import unittest +from math import floor + +################################################################################ +# Solution +################################################################################ + +# change_possibilities :: Int -> [Int] -> Int +def change_possibilities(n, xs): + combinations = [0] * (n + 1) + combinations[0] = 1 + + for x in xs: + for i in range(len(combinations)): + if i >= x: + combinations[i] += combinations[i - x] + + return combinations[n] + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + + def test_sample_input(self): + actual = change_possibilities(4, (1, 2, 3)) + expected = 4 + self.assertEqual(actual, expected) + + def test_one_way_to_make_zero_cents(self): + actual = change_possibilities(0, (1, 2)) + expected = 1 + self.assertEqual(actual, expected) + + def test_no_ways_if_no_coins(self): + actual = change_possibilities(1, ()) + expected = 0 + self.assertEqual(actual, expected) + + def test_big_coin_value(self): + actual = change_possibilities(5, (25, 50)) + expected = 0 + self.assertEqual(actual, expected) + + def test_big_target_amount(self): + actual = change_possibilities(50, (5, 10)) + expected = 6 + self.assertEqual(actual, expected) + + def test_change_for_one_dollar(self): + actual = change_possibilities(100, (1, 5, 10, 25, 50)) + expected = 292 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/conways-game-of-life.py b/users/wpcarro/scratch/data_structures_and_algorithms/conways-game-of-life.py new file mode 100644 index 0000000000..3836bcd0c6 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/conways-game-of-life.py @@ -0,0 +1,78 @@ +from itertools import product +from random import choice +from time import sleep +from os import system +from math import floor +from colorama import Back, Fore, Style + +################################################################################ +# Simulation of Conway's Game of Life. The goal here was to write this with a +# small amount of code as a proof-of-concept that could be run in the terminal. +# +# If you'd like to tinker with the rules, see the conditionals defined in the +# `advance/1` function. For other parameters, like the board size and refresh +# rate, refer to the while-loop defined at the bottom of this file. +################################################################################ + + +def init_board(n, init_alive_percentage): + """Initialize a board of size `n` by `n`. Supply a percentage, + `init_alive_percentage`, representing the number of cells in the board that + should be alive from the start.""" + alive_count = floor(n * init_alive_percentage) + distribution = [True] * alive_count + [False] * (n - alive_count) + return [[choice(distribution) for _ in range(n)] for _ in range(n)] + + +def neighbors(coord, board): + """Return the neighbors for a given `coord` on a `board`.""" + n = len(board) + row, col = coord + return [ + board[(row + row_d) % n][(col + col_d) % n] + for row_d, col_d in product([-1, 0, 1], [-1, 0, 1]) + if (row_d, col_d) != (0, 0) + ] + + +def advance(board): + """Advance the state of the `board` from T[n] to T[n+1].""" + n = len(board) + new_board = [[False for _ in range(n)] for _ in range(n)] + for row in range(n): + for col in range(n): + alive_count = len([x for x in neighbors((row, col), board) if x]) + # Loneliness + if alive_count == 0: + new_board[row][col] = False + # Status Quo + elif alive_count == 1: + new_board[row][col] = board[row][col] + # Cooperation + elif alive_count == 2: + new_board[row][col] = True + # Resource starvation + elif alive_count >= 3: + new_board[row][col] = False + return new_board + + +def print_board(board): + """Print the game `board` in a human-readable way.""" + result = '' + for row in board: + for col in row: + if col: + result += Back.GREEN + '1 ' + Style.RESET_ALL + else: + result += Back.RED + '0 ' + Style.RESET_ALL + result += '\n' + print(result) + + +board = init_board(100, 0.50) +while True: + system('clear') + print_board(board) + sleep(0.15) + board = advance(board) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/delete-node.py b/users/wpcarro/scratch/data_structures_and_algorithms/delete-node.py new file mode 100644 index 0000000000..7e431e2249 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/delete-node.py @@ -0,0 +1,60 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def delete_node(x): + if not x.next: + raise Exception('Cannot delete the last node in a linked list.') + else: + x.value = x.next.value + x.next = x.next.next + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class LinkedListNode(object): + def __init__(self, value, next=None): + self.value = value + self.next = next + + def get_values(self): + node = self + values = [] + while node is not None: + values.append(node.value) + node = node.next + return values + + def setUp(self): + self.fourth = Test.LinkedListNode(4) + self.third = Test.LinkedListNode(3, self.fourth) + self.second = Test.LinkedListNode(2, self.third) + self.first = Test.LinkedListNode(1, self.second) + + def test_node_at_beginning(self): + delete_node(self.first) + actual = self.first.get_values() + expected = [2, 3, 4] + self.assertEqual(actual, expected) + + def test_node_in_middle(self): + delete_node(self.second) + actual = self.first.get_values() + expected = [1, 3, 4] + self.assertEqual(actual, expected) + + def test_node_at_end(self): + with self.assertRaises(Exception): + delete_node(self.fourth) + + def test_one_node_in_list(self): + unique = Test.LinkedListNode(1) + with self.assertRaises(Exception): + delete_node(unique) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/dft.py b/users/wpcarro/scratch/data_structures_and_algorithms/dft.py new file mode 100644 index 0000000000..127d48c186 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/dft.py @@ -0,0 +1,65 @@ +from random import choice + + +class Node(object): + def __init__(self, value=None, left=None, right=None): + self.value = value + self.left = left + self.right = left + + +def p(node, indent=0): + print(indent * ' ' + '|-' + str(node.value)) + if node.left is not None: + p(node.left, indent=indent + 2) + if node.right is not None: + p(node.right, indent=indent + 2) + + +# read trees (i.e. traversing, parsing) +# write trees (i.e. generating, printing) +def random(d=0): + left = None + right = None + + if choice([True, False]): + left = random(d + 1) + + if choice([True, False]): + right = random(d + 1) + + return Node( + value=d, + left=left, + right=right, + ) + + +################################################################################ +# DFTs can be: +# - imperative (mutable) +# - functional (immutable) +# - iterative +# - recursive +################################################################################ + + +# Iterative +def traverse(node, f): + stack = [(node, 0)] + + while len(stack): + node, depth = stack.pop() + f(node, depth) + print(depth) + + if node.left is not None: + stack.append((node.left, depth + 1)) + if node.right is not None: + stack.append((node.right, depth + 1)) + + +print('----------------------------------------------------------------------') +for _ in range(10): + traverse(random(), lambda _, d: print(d)) +print() diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py b/users/wpcarro/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py new file mode 100644 index 0000000000..03907f6040 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/dijkstra-shortest-path.py @@ -0,0 +1,48 @@ +from collections import deque +from heapq import heappush, heappop +from fixtures import weighted_graph + + +def put(t, x, xs): + if t == 'stack': + return xs.append(x) + if t == 'queue': + return xs.append(x) + if t == 'priority': + return heappush(xs, x) + + +def pop(t, xs): + if t == 'stack': + return xs.pop() + if t == 'queue': + return xs.popleft() + if t == 'priority': + return heappop(xs) + + +# shortest_path :: Vertex -> Vertex -> Graph -> [Vertex] +def shortest_path(a, b, g): + """Returns the shortest path from vertex a to vertex b in graph g.""" + t = 'priority' + xs = [] + seen = set() + # Map(Weight, [Vertex]) + m = {} + + put(t, (0, [a], a), xs) + + while xs: + w0, path, v = pop(t, xs) + + seen.add(v) + if v == b: + m[w0] = path + for w1, x in g.get(v): + if x not in seen: + put(t, (w0 + w1, path + [x], x), xs) + + return m + + +print(shortest_path('a', 'f', graph_a)) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space-beast.py b/users/wpcarro/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space-beast.py new file mode 100644 index 0000000000..93fdd9eed2 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space-beast.py @@ -0,0 +1,56 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def find_duplicate(xs): + self_ref_count = 0 + for i in range(len(xs)): + if xs[i] == i + 1: + self_ref_count += 1 + hops = len(xs) - 1 - self_ref_count + current = xs[-1] + while hops > 0: + current = xs[current - 1] + hops -= 1 + return current + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + # TODO: Debug why this fails. + def test_darren_from_interview_cake(self): + actual = find_duplicate([4, 1, 8, 3, 2, 7, 6, 5, 4]) + expected = 4 + self.assertEqual(actual, expected) + + def test_just_the_repeated_number(self): + actual = find_duplicate([1, 1]) + expected = 1 + self.assertEqual(actual, expected) + + def test_short_list(self): + actual = find_duplicate([1, 2, 3, 2]) + expected = 2 + self.assertEqual(actual, expected) + + def test_last_cycle(self): + actual = find_duplicate([3, 4, 2, 3, 1, 5]) + expected = 3 + self.assertEqual(actual, expected) + + def test_medium_list(self): + actual = find_duplicate([1, 2, 5, 5, 5, 5]) + expected = 5 + self.assertEqual(actual, expected) + + def test_long_list(self): + actual = find_duplicate([4, 1, 4, 8, 3, 2, 7, 6, 5]) + expected = 4 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space.py b/users/wpcarro/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space.py new file mode 100644 index 0000000000..e2739f0f60 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/find-duplicate-optimize-for-space.py @@ -0,0 +1,61 @@ +from math import floor +import unittest + + +################################################################################ +# Solution +################################################################################ +def bounds(r): + ct = len(r) + if ct % 2 == 0: + h = int(ct / 2) + return ct, h + else: + h = floor(ct / 2) + return ct, h + + +def find_repeat(xs): + ct, h = bounds(xs) + rl = range(1, h + 1) + rr = range(h + 1, ct) + while True: + nl = len([None for x in xs if x in rl]) + nr = len([None for x in xs if x in rr]) + branch = rl if nl > nr else rr + if len(branch) == 1: + return branch[0] + ct, h = bounds(branch) + rl = range(branch[0], branch[0]) + rr = range(branch[0] + h, branch[-1] + 1) + raise Exception( + 'We could not find any duplicates in xs. Perhaps xs did not adhere to the usage contract.' + ) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_just_the_repeated_number(self): + actual = find_repeat([1, 1]) + expected = 1 + self.assertEqual(actual, expected) + + def test_short_list(self): + actual = find_repeat([1, 2, 3, 2]) + expected = 2 + self.assertEqual(actual, expected) + + def test_medium_list(self): + actual = find_repeat([1, 2, 5, 5, 5, 5]) + expected = 5 + self.assertEqual(actual, expected) + + def test_long_list(self): + actual = find_repeat([4, 1, 4, 8, 3, 2, 7, 6, 5]) + expected = 4 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/find-rotation-point.py b/users/wpcarro/scratch/data_structures_and_algorithms/find-rotation-point.py new file mode 100644 index 0000000000..2103a5b84f --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/find-rotation-point.py @@ -0,0 +1,59 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def find_rotation_point(xs): + """Usage of `visited` here is a hack, but works for the test cases + (gulp).""" + i = 0 + j = round(len(xs) / 2) + result = None + visited = set() + while not result: + if i in visited: + i += 1 + if j in visited: + j -= 1 + visited.add(i) + visited.add(j) + if xs[j - 1] > xs[j]: + result = j + elif xs[i] < xs[j]: + i = j + j += round((len(xs) - j) / 2) + elif xs[i] >= xs[j]: + i = j + j -= round((j - i) / 2) + return result + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_small_list(self): + actual = find_rotation_point(['cape', 'cake']) + expected = 1 + self.assertEqual(actual, expected) + + def test_medium_list(self): + actual = find_rotation_point( + ['grape', 'orange', 'plum', 'radish', 'apple']) + expected = 4 + self.assertEqual(actual, expected) + + def test_large_list(self): + actual = find_rotation_point([ + 'ptolemaic', 'retrograde', 'supplant', 'undulate', 'xenoepist', + 'asymptote', 'babka', 'banoffee', 'engender', 'karpatka', + 'othellolagkage' + ]) + expected = 5 + self.assertEqual(actual, expected) + + # Are we missing any edge cases? + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/find-unique-int-among-duplicates.py b/users/wpcarro/scratch/data_structures_and_algorithms/find-unique-int-among-duplicates.py new file mode 100644 index 0000000000..dfa5de42cc --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/find-unique-int-among-duplicates.py @@ -0,0 +1,45 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def find_unique_delivery_id(xs): + a = 0 + for x in xs: + a ^= x + return a + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_one_drone(self): + actual = find_unique_delivery_id([1]) + expected = 1 + self.assertEqual(actual, expected) + + def test_unique_id_comes_first(self): + actual = find_unique_delivery_id([1, 2, 2]) + expected = 1 + self.assertEqual(actual, expected) + + def test_unique_id_comes_last(self): + actual = find_unique_delivery_id([3, 3, 2, 2, 1]) + expected = 1 + self.assertEqual(actual, expected) + + def test_unique_id_in_middle(self): + actual = find_unique_delivery_id([3, 2, 1, 2, 3]) + expected = 1 + self.assertEqual(actual, expected) + + def test_many_drones(self): + actual = find_unique_delivery_id( + [2, 5, 4, 8, 6, 3, 1, 4, 2, 3, 6, 5, 1]) + expected = 8 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/fixtures.py b/users/wpcarro/scratch/data_structures_and_algorithms/fixtures.py new file mode 100644 index 0000000000..27689ca76d --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/fixtures.py @@ -0,0 +1,110 @@ +# Using this module to store commonly used, but annoying to create, data +# structures for my test inputs. +# +# Use like: +# from fixtures import graph_a + +################################################################################ +# Constants +################################################################################ + +edge_list = [ + ('a', 'b'), + ('a', 'c'), + ('a', 'e'), + ('b', 'c'), + ('b', 'd'), + ('c', 'e'), + ('d', 'f'), + ('e', 'd'), + ('e', 'f'), +] + +unweighted_graph = { + 'a': {'b', 'c', 'e'}, + 'b': {'c', 'd'}, + 'c': {'e'}, + 'd': {'f'}, + 'e': {'d', 'f'}, + 'f': set(), +} + +adjacencies = { + 'a': { + 'a': False, + 'b': False + }, + 'a': [], + 'a': [], + 'a': [], + 'a': [], + 'a': [], + 'a': [], +} + +weighted_graph = { + 'a': {(4, 'b'), (2, 'c'), (4, 'e')}, + 'b': {(5, 'c'), (10, 'd')}, + 'c': {(3, 'e')}, + 'd': {(11, 'f')}, + 'e': {(4, 'd'), (5, 'f')}, + 'f': set(), +} + +# This is `weighted_graph` with each of its weighted edges "expanded". +expanded_weights_graph = { + 'a': ['b-1', 'c-1', 'e-1'], + 'b-1': ['b-2'], + 'b-2': ['b-3'], + 'b-3': ['b'], + 'c-1': ['c'], + 'e-1': ['e-2'], + 'e-2': ['e-3'], + 'e-3': ['e'], + # and so on... +} + +unweighted_digraph = { + '5': {'2', '0'}, + '4': {'0', '1'}, + '3': {'1'}, + '2': {'3'}, + '1': set(), + '0': set(), +} + +################################################################################ +# Functions +################################################################################ + + +def vertices(xs): + result = set() + for a, b in xs: + result.add(a) + result.add(b) + return result + + +def edges_to_neighbors(xs): + result = {v: set() for v in vertices(xs)} + for a, b in xs: + result[a].add(b) + return result + + +def neighbors_to_edges(xs): + result = [] + for k, ys in xs.items(): + for y in ys: + result.append((k, y)) + return result + + +def edges_to_adjacencies(xs): + return xs + + +# Skipping handling adjacencies because I cannot think of a reasonable use-case +# for it when the vertex labels are items other than integers. I can think of +# ways of handling this, but none excite me. diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/graph-coloring.py b/users/wpcarro/scratch/data_structures_and_algorithms/graph-coloring.py new file mode 100644 index 0000000000..bc7f7ceea5 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/graph-coloring.py @@ -0,0 +1,180 @@ +import unittest +from collections import deque + + +################################################################################ +# Solution +################################################################################ +class GraphNode: + def __init__(self, label): + self.label = label + self.neighbors = set() + self.color = None + + +# color_graph :: G(V, E) -> Set(Color) -> IO () +def color_graph(graph, colors): + q = deque() + seen = set() + q.append(graph[0]) + + while q: + node = q.popleft() + + illegal = {n.color for n in node.neighbors} + for x in colors: + if x not in illegal: + node.color = x + + seen.add(node) + + for x in node.neighbors: + if x not in seen: + q.append(x) + + # TODO: Is this the best way to traverse separate graphs? + for x in graph: + if x not in seen: + q.append(x) + + return 0 + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def setUp(self): + self.colors = frozenset([ + 'red', + 'green', + 'blue', + 'orange', + 'yellow', + 'white', + ]) + + def assertGraphColoring(self, graph, colors): + self.assertGraphHasColors(graph, colors) + self.assertGraphColorLimit(graph) + for node in graph: + self.assertNodeUniqueColor(node) + + def assertGraphHasColors(self, graph, colors): + for node in graph: + msg = 'Node %r color %r not in %r' % (node.label, node.color, + colors) + self.assertIn(node.color, colors, msg=msg) + + def assertGraphColorLimit(self, graph): + max_degree = 0 + colors_found = set() + for node in graph: + degree = len(node.neighbors) + max_degree = max(degree, max_degree) + colors_found.add(node.color) + max_colors = max_degree + 1 + used_colors = len(colors_found) + msg = 'Used %d colors and expected %d at most' % (used_colors, + max_colors) + self.assertLessEqual(used_colors, max_colors, msg=msg) + + def assertNodeUniqueColor(self, node): + for adjacent in node.neighbors: + msg = 'Adjacent nodes %r and %r have the same color %r' % ( + node.label, + adjacent.label, + node.color, + ) + self.assertNotEqual(node.color, adjacent.color, msg=msg) + + def test_line_graph(self): + node_a = GraphNode('a') + node_b = GraphNode('b') + node_c = GraphNode('c') + node_d = GraphNode('d') + + node_a.neighbors.add(node_b) + node_b.neighbors.add(node_a) + node_b.neighbors.add(node_c) + node_c.neighbors.add(node_b) + node_c.neighbors.add(node_d) + node_d.neighbors.add(node_c) + + graph = [node_a, node_b, node_c, node_d] + tampered_colors = list(self.colors) + color_graph(graph, tampered_colors) + self.assertGraphColoring(graph, self.colors) + + def test_separate_graph(self): + node_a = GraphNode('a') + node_b = GraphNode('b') + node_c = GraphNode('c') + node_d = GraphNode('d') + + node_a.neighbors.add(node_b) + node_b.neighbors.add(node_a) + node_c.neighbors.add(node_d) + node_d.neighbors.add(node_c) + + graph = [node_a, node_b, node_c, node_d] + tampered_colors = list(self.colors) + color_graph(graph, tampered_colors) + self.assertGraphColoring(graph, self.colors) + + def test_triangle_graph(self): + node_a = GraphNode('a') + node_b = GraphNode('b') + node_c = GraphNode('c') + + node_a.neighbors.add(node_b) + node_a.neighbors.add(node_c) + node_b.neighbors.add(node_a) + node_b.neighbors.add(node_c) + node_c.neighbors.add(node_a) + node_c.neighbors.add(node_b) + + graph = [node_a, node_b, node_c] + tampered_colors = list(self.colors) + color_graph(graph, tampered_colors) + self.assertGraphColoring(graph, self.colors) + + def test_envelope_graph(self): + node_a = GraphNode('a') + node_b = GraphNode('b') + node_c = GraphNode('c') + node_d = GraphNode('d') + node_e = GraphNode('e') + + node_a.neighbors.add(node_b) + node_a.neighbors.add(node_c) + node_b.neighbors.add(node_a) + node_b.neighbors.add(node_c) + node_b.neighbors.add(node_d) + node_b.neighbors.add(node_e) + node_c.neighbors.add(node_a) + node_c.neighbors.add(node_b) + node_c.neighbors.add(node_d) + node_c.neighbors.add(node_e) + node_d.neighbors.add(node_b) + node_d.neighbors.add(node_c) + node_d.neighbors.add(node_e) + node_e.neighbors.add(node_b) + node_e.neighbors.add(node_c) + node_e.neighbors.add(node_d) + + graph = [node_a, node_b, node_c, node_d, node_e] + tampered_colors = list(self.colors) + color_graph(graph, tampered_colors) + self.assertGraphColoring(graph, self.colors) + + def test_loop_graph(self): + node_a = GraphNode('a') + node_a.neighbors.add(node_a) + graph = [node_a] + tampered_colors = list(self.colors) + with self.assertRaises(Exception): + color_graph(graph, tampered_colors) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/graph-to-graphviz.py b/users/wpcarro/scratch/data_structures_and_algorithms/graph-to-graphviz.py new file mode 100644 index 0000000000..0e7e97a20c --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/graph-to-graphviz.py @@ -0,0 +1,39 @@ +from graphviz import Digraph +from collections import deque +from fixtures import weighted_graph + +# There are three ways to model a graph: +# 1. Edge list: [(Vertex, Vertex)] +# 2. Neighbors table: Map(Vertex, [Vertex]) +# 3. Adjacency matrix: [[Boolean]] +# +# The following graph is a neighbors table. + + +# to_graphviz :: Vertex -> Map(Vertex, [(Vertex, Weight)]) -> String +def to_graphviz(start, g): + """Compiles the graph into GraphViz.""" + d = Digraph() + q = deque() + seen = set() + + q.append(start) + + while q: + v = q.popleft() + if v in seen: + continue + d.node(v, label=v) + + for w, x in g[v]: + d.edge(v, x, label=str(w)) + q.append(x) + seen.add(v) + + return d.source + + +with open('/tmp/test.gv', 'w') as f: + src = to_graphviz('a', weighted_graph) + f.write(src) + print('/tmp/test.gv created!') diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py b/users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py new file mode 100644 index 0000000000..889663e058 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/highest-product-of-3.py @@ -0,0 +1,89 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# f :: [Int] -> Int +def highest_product_of_3(xs): + """Here we're greedily storing: + - current max + - largest product of two + - largest positive number + - second largest positive number + - largest negative number + """ + if len(xs) < 3: + raise Exception + + cm = None + ld = xs[0] * xs[1] + l2 = min(xs[0], xs[1]) + if xs[0] < 0 or xs[1] < 0: + ln = min(xs[0], xs[1]) + else: + ln = 1 + l = max(xs[0], xs[1]) + + for x in xs[2:]: + if not cm: + cm = max(x * ln * l, ld * x, x * l * l2) # beware + ld = max(ld, x * ln, x * l) + ln = min(ln, x) + l = max(l, x) + if x < l: + l2 = max(l2, x) + else: + cm = max(cm, x * ln * l, x * ld, x * l * l2) + ld = max(ld, x * ln, x * l) + ln = min(ln, x) + l = max(l, x) + if x < l: + l2 = max(l2, x) + + return cm + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_short_list(self): + actual = highest_product_of_3([1, 2, 3, 4]) + expected = 24 + self.assertEqual(actual, expected) + + def test_longer_list(self): + actual = highest_product_of_3([6, 1, 3, 5, 7, 8, 2]) + expected = 336 + self.assertEqual(actual, expected) + + def test_list_has_one_negative(self): + actual = highest_product_of_3([-5, 4, 8, 2, 3]) + expected = 96 + self.assertEqual(actual, expected) + + def test_list_has_two_negatives(self): + actual = highest_product_of_3([-10, 1, 3, 2, -10]) + expected = 300 + self.assertEqual(actual, expected) + + def test_list_is_all_negatives(self): + actual = highest_product_of_3([-5, -1, -3, -2]) + expected = -6 + self.assertEqual(actual, expected) + + def test_error_with_empty_list(self): + with self.assertRaises(Exception): + highest_product_of_3([]) + + def test_error_with_one_number(self): + with self.assertRaises(Exception): + highest_product_of_3([1]) + + def test_error_with_two_numbers(self): + with self.assertRaises(Exception): + highest_product_of_3([1, 1]) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/inflight-entertainment.py b/users/wpcarro/scratch/data_structures_and_algorithms/inflight-entertainment.py new file mode 100644 index 0000000000..6e17baef37 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/inflight-entertainment.py @@ -0,0 +1,35 @@ +# possible :: Int -> [Int] -> Bool +def possible(flight_duration, film_durations): + seeking = set() + + for x in film_durations: + if x in seeking: + return True + else: + seeking.add(flight_duration - x) + + return False + + +should = [ + (10, [1, 9, 8, 8, 8]), + (10, [1, 9]), + (10, [1, 9, 5, 5, 6]), + (1, [0.5, 0.5]), + (1, [0.5, 0.5]), +] + +for a, b in should: + print("Testing: %s %s" % (a, b)) + assert possible(a, b) + +shouldnt = [ + (10, [1, 10, 1, 2, 1, 12]), + (1, [0.25, 0.25, 0.25, 0.25]), + (5, [1, 2, 2]), +] +for a, b in shouldnt: + print("Testing: %s %s" % (a, b)) + assert not possible(a, b) + +print("Tests pass") diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/knapsack-0-1.py b/users/wpcarro/scratch/data_structures_and_algorithms/knapsack-0-1.py new file mode 100644 index 0000000000..c72d19d4ed --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/knapsack-0-1.py @@ -0,0 +1,38 @@ +import unittest +from math import floor + + +def knapify(xs, capacity=None): + assert capacity is not None + n = len(xs) + # For 0/1 Knapsack, we must use a table, since this will encode which values + # work for which items. This is cleaner than including a separate data + # structure to capture it. + maxes = [[0 for x in range(capacity + 1)] for x in range(n + 1)] + + # Build table maxes[][] in bottom up manner + for row in range(n + 1): + for col in range(capacity + 1): + if row == 0 or col == 0: + maxes[row][col] = 0 + elif xs[row - 1][0] <= col: + maxes[row][col] = max( + xs[row - 1][1] + maxes[row - 1][col - xs[row - 1][0]], + maxes[row - 1][col]) + else: + maxes[row][col] = maxes[row - 1][col] + + return maxes[-1][capacity] + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_one_cake(self): + actual = knapify([(3, 10), (2, 15), (7, 2), (12, 20)], capacity=12) + expected = None + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/kth-to-last.py b/users/wpcarro/scratch/data_structures_and_algorithms/kth-to-last.py new file mode 100644 index 0000000000..8291e54533 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/kth-to-last.py @@ -0,0 +1,82 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def length(x): + if not x: + return 0 + else: + count = 1 + while x: + x = x.next + count += 1 + return count + + +def kth_to_last_node(k, x): + hops = length(x) - 1 + dest = hops - k + + if k == 0: + raise Exception("Our God doesn't support this kind of behavior.") + + if dest < 0: + raise Exception('Value k to high for list.') + + while dest > 0: + x = x.next + dest -= 1 + + return x + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class LinkedListNode(object): + def __init__(self, value, next=None): + self.value = value + self.next = next + + def get_values(self): + node = self + values = [] + while node is not None: + values.append(node.value) + node = node.next + return values + + def setUp(self): + self.fourth = Test.LinkedListNode(4) + self.third = Test.LinkedListNode(3, self.fourth) + self.second = Test.LinkedListNode(2, self.third) + self.first = Test.LinkedListNode(1, self.second) + + def test_first_to_last_node(self): + actual = kth_to_last_node(1, self.first) + expected = self.fourth + self.assertEqual(actual, expected) + + def test_second_to_last_node(self): + actual = kth_to_last_node(2, self.first) + expected = self.third + self.assertEqual(actual, expected) + + def test_first_node(self): + actual = kth_to_last_node(4, self.first) + expected = self.first + self.assertEqual(actual, expected) + + def test_k_greater_than_linked_list_length(self): + with self.assertRaises(Exception): + kth_to_last_node(5, self.first) + + def test_k_is_zero(self): + with self.assertRaises(Exception): + kth_to_last_node(0, self.first) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/largest-stack.py b/users/wpcarro/scratch/data_structures_and_algorithms/largest-stack.py new file mode 100644 index 0000000000..aab9671eb6 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/largest-stack.py @@ -0,0 +1,107 @@ +import unittest + + +class Stack(object): + def __init__(self): + """Initialize an empty stack""" + self.items = [] + + def push(self, item): + """Push a new item onto the stack""" + self.items.append(item) + + def pop(self): + """Remove and return the last item""" + # If the stack is empty, return None + # (it would also be reasonable to throw an exception) + if not self.items: + return None + + return self.items.pop() + + def peek(self): + """Return the last item without removing it""" + if not self.items: + return None + return self.items[-1] + + +class MaxStack(object): + # Implement the push, pop, and get_max methods + def __init__(self): + self.m = Stack() + self.stack = Stack() + + def push(self, item): + if self.m.peek() is None: + self.m.push(item) + elif item >= self.m.peek(): + self.m.push(item) + self.stack.push(item) + + def pop(self): + x = self.stack.pop() + if x == self.m.peek(): + self.m.pop() + return x + + def get_max(self): + return self.m.peek() + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_stack_usage(self): + max_stack = MaxStack() + + max_stack.push(5) + + actual = max_stack.get_max() + expected = 5 + self.assertEqual(actual, expected) + + max_stack.push(4) + max_stack.push(7) + max_stack.push(7) + max_stack.push(8) + + actual = max_stack.get_max() + expected = 8 + self.assertEqual(actual, expected) + + actual = max_stack.pop() + expected = 8 + self.assertEqual(actual, expected) + + actual = max_stack.get_max() + expected = 7 + self.assertEqual(actual, expected) + + actual = max_stack.pop() + expected = 7 + self.assertEqual(actual, expected) + + actual = max_stack.get_max() + expected = 7 + self.assertEqual(actual, expected) + + actual = max_stack.pop() + expected = 7 + self.assertEqual(actual, expected) + + actual = max_stack.get_max() + expected = 5 + self.assertEqual(actual, expected) + + actual = max_stack.pop() + expected = 4 + self.assertEqual(actual, expected) + + actual = max_stack.get_max() + expected = 5 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/linked-list-cycles.py b/users/wpcarro/scratch/data_structures_and_algorithms/linked-list-cycles.py new file mode 100644 index 0000000000..75a4b99394 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/linked-list-cycles.py @@ -0,0 +1,88 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def contains_cycle(x): + if not x: + return False + elif not x.next: + return False + + a = x + b = x.next + + while b.next: + if a == b: + return True + + a = a.next + b = b.next.next + + return False + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class LinkedListNode(object): + def __init__(self, value, next=None): + self.value = value + self.next = next + + def test_linked_list_with_no_cycle(self): + fourth = Test.LinkedListNode(4) + third = Test.LinkedListNode(3, fourth) + second = Test.LinkedListNode(2, third) + first = Test.LinkedListNode(1, second) + result = contains_cycle(first) + self.assertFalse(result) + + def test_cycle_loops_to_beginning(self): + fourth = Test.LinkedListNode(4) + third = Test.LinkedListNode(3, fourth) + second = Test.LinkedListNode(2, third) + first = Test.LinkedListNode(1, second) + fourth.next = first + result = contains_cycle(first) + self.assertTrue(result) + + def test_cycle_loops_to_middle(self): + fifth = Test.LinkedListNode(5) + fourth = Test.LinkedListNode(4, fifth) + third = Test.LinkedListNode(3, fourth) + second = Test.LinkedListNode(2, third) + first = Test.LinkedListNode(1, second) + fifth.next = third + result = contains_cycle(first) + self.assertTrue(result) + + def test_two_node_cycle_at_end(self): + fifth = Test.LinkedListNode(5) + fourth = Test.LinkedListNode(4, fifth) + third = Test.LinkedListNode(3, fourth) + second = Test.LinkedListNode(2, third) + first = Test.LinkedListNode(1, second) + fifth.next = fourth + result = contains_cycle(first) + self.assertTrue(result) + + def test_empty_list(self): + result = contains_cycle(None) + self.assertFalse(result) + + def test_one_element_linked_list_no_cycle(self): + first = Test.LinkedListNode(1) + result = contains_cycle(first) + self.assertFalse(result) + + def test_one_element_linked_list_cycle(self): + first = Test.LinkedListNode(1) + first.next = first + result = contains_cycle(first) + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/memo.py b/users/wpcarro/scratch/data_structures_and_algorithms/memo.py new file mode 100644 index 0000000000..44ea93e1bd --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/memo.py @@ -0,0 +1,60 @@ +import time +import random +from heapq import heappush, heappop + + +class Memo(object): + def __init__(self, size=1): + """ + Create a key-value data-structure that will never exceed `size` + members. Memo evicts the least-recently-accessed elements from itself + before adding inserting new key-value pairs. + """ + if size <= 0: + raise Exception("We do not support an empty memo") + self.xs = {} + self.heap = [(0, None)] * size + + def contains(self, k): + """ + Return true if key `k` exists in the Memo. + """ + return k in self.xs + + def get(self, k): + """ + Return the memoized item at key `k`. + """ + # "touch" the element in the heap + return self.xs[k] + + def set(self, k, v): + """ + Memoize value `v` at key `k`. + """ + _, to_evict = heappop(self.heap) + if to_evict != None: + del self.xs[to_evict] + heappush(self.heap, (time.time(), k)) + self.xs[k] = v + + +memo = Memo(size=10) + + +def f(x): + """ + Compute some mysterious, expensive function. + """ + if memo.contains(x): + print("Hit.\t\tf({})".format(x)) + return memo.get(x) + else: + print("Computing...\tf({})".format(x)) + time.sleep(0.25) + res = random.randint(0, 10) + memo.set(x, res) + return res + + +[f(random.randint(0, 10)) for _ in range(10)] diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/merge-sort.py b/users/wpcarro/scratch/data_structures_and_algorithms/merge-sort.py new file mode 100644 index 0000000000..6dbe0fa0f3 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/merge-sort.py @@ -0,0 +1,28 @@ + + + +# merge :: [a] -> [a] -> [a] +# merge([], []): [] +# merge(xs, []): xs +# merge([], ys): ys +# merge(xs@[x|xs'], ys@[y|ys']) +# when y =< x: cons(y, merge(xs, ys')) +# when x < y: cons(x, merge(xs', ys)) +def merge(xs, ys): + if xs == [] and ys == []: + return [] + elif ys == []: + return xs + elif xs == []: + return ys + else: + x = xs[0] + y = ys[0] + + if y <= x: + return [y] + merge(xs, ys[1:]) + else: + return [x] + merge(xs[1:], ys) + +print(merge([3, 4, 6, 10, 11, 15], + [1, 5, 8, 12, 14, 19])) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/merging-ranges.py b/users/wpcarro/scratch/data_structures_and_algorithms/merging-ranges.py new file mode 100644 index 0000000000..4e3604d5bc --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/merging-ranges.py @@ -0,0 +1,94 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# do_merge_ranges :: [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)] +def do_merge_ranges(prev, xs): + if len(xs) == 0: + return prev + elif len(xs) == 1: + return prev + xs + else: + a1, a2 = xs[0] + b1, b2 = xs[1] + rest = xs[2:] + if b1 <= a2: + return do_merge_ranges(prev, [(a1, max(a2, b2))] + rest) + else: + return do_merge_ranges(prev + [(a1, a2)], [(b1, b2)] + rest) + + +# merge_ranges :: [(Int, Int)] -> [(Int, Int)] +def merge_ranges(xs): + xs = xs[:] + xs.sort() + return do_merge_ranges([], xs) + + +# merge_ranges_b :: [(Int, Int)] -> [(Int, Int)] +def merge_ranges_b(xs): + fi = 0 + ci = 1 + result = [] + xs = xs[:] + xs.sort() + while ci < len(xs): + while ci < len(xs) and xs[ci][0] <= xs[fi][1]: + xs[fi] = xs[fi][0], max(xs[ci][1], xs[fi][1]) + ci += 1 + result.append(xs[fi]) + fi = ci + ci += 1 + if fi < len(xs): + result.append(xs[fi]) + return result + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_meetings_overlap(self): + actual = merge_ranges([(1, 3), (2, 4)]) + expected = [(1, 4)] + self.assertEqual(actual, expected) + + def test_meetings_touch(self): + actual = merge_ranges([(5, 6), (6, 8)]) + expected = [(5, 8)] + self.assertEqual(actual, expected) + + def test_meeting_contains_other_meeting(self): + actual = merge_ranges([(1, 8), (2, 5)]) + expected = [(1, 8)] + self.assertEqual(actual, expected) + + def test_meetings_stay_separate(self): + actual = merge_ranges([(1, 3), (4, 8)]) + expected = [(1, 3), (4, 8)] + self.assertEqual(actual, expected) + + def test_multiple_merged_meetings(self): + actual = merge_ranges([(1, 4), (2, 5), (5, 8)]) + expected = [(1, 8)] + self.assertEqual(actual, expected) + + def test_meetings_not_sorted(self): + actual = merge_ranges([(5, 8), (1, 4), (6, 8)]) + expected = [(1, 4), (5, 8)] + self.assertEqual(actual, expected) + + def test_one_long_meeting_contains_smaller_meetings(self): + actual = merge_ranges([(1, 10), (2, 5), (6, 8), (9, 10), (10, 12)]) + expected = [(1, 12)] + self.assertEqual(actual, expected) + + def test_sample_input(self): + actual = merge_ranges([(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]) + expected = [(0, 1), (3, 8), (9, 12)] + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.gv b/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.gv new file mode 100644 index 0000000000..1e67c3954f --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.gv @@ -0,0 +1,11 @@ +strict graph { + Min -- {William, Jayden, Omar} + William -- {Min, Noam} + Jayden -- {Min, Amelia, Ren, Noam} + Adam -- {Amelia, Miguel, Sofia, Lucas} + Ren -- {Jayden, Omar} + Amelia -- {Jayden, Adam, Miguel} + Miguel -- {Amelia, Adam, Liam, Nathan} + Noam -- {Nathan, Jayden, William} + Omar -- {Ren, Min, Scott} +} diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py b/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py new file mode 100644 index 0000000000..c9d7d9d741 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/mesh-message.py @@ -0,0 +1,97 @@ +import unittest +from collections import deque + + +################################################################################ +# Solution +################################################################################ +# get_path :: G(V, E) -> V -> V -> Maybe([V]) +def get_path(g, src, dst): + q = deque() + result = None + seen = set() + q.append(([], src)) + + if src not in g or dst not in g: + raise Exception + + while q: + p, node = q.popleft() + + seen.add(node) + + if node == dst: + if not result: + result = p + [node] + elif len(p + [node]) < len(result): + result = p + [node] + else: + if node not in g: + raise Exception + for x in g.get(node): + if not x in seen: + q.append((p + [node], x)) + + return result + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def setUp(self): + self.graph = { + 'a': ['b', 'c', 'd'], + 'b': ['a', 'd'], + 'c': ['a', 'e'], + 'd': ['a', 'b'], + 'e': ['c'], + 'f': ['g'], + 'g': ['f'], + } + + def test_two_hop_path_1(self): + actual = get_path(self.graph, 'a', 'e') + expected = ['a', 'c', 'e'] + self.assertEqual(actual, expected) + + def test_two_hop_path_2(self): + actual = get_path(self.graph, 'd', 'c') + expected = ['d', 'a', 'c'] + self.assertEqual(actual, expected) + + def test_one_hop_path_1(self): + actual = get_path(self.graph, 'a', 'c') + expected = ['a', 'c'] + self.assertEqual(actual, expected) + + def test_one_hop_path_2(self): + actual = get_path(self.graph, 'f', 'g') + expected = ['f', 'g'] + self.assertEqual(actual, expected) + + def test_one_hop_path_3(self): + actual = get_path(self.graph, 'g', 'f') + expected = ['g', 'f'] + self.assertEqual(actual, expected) + + def test_zero_hop_path(self): + actual = get_path(self.graph, 'a', 'a') + expected = ['a'] + self.assertEqual(actual, expected) + + def test_no_path(self): + actual = get_path(self.graph, 'a', 'f') + expected = None + self.assertEqual(actual, expected) + + def test_start_node_not_present(self): + with self.assertRaises(Exception): + get_path(self.graph, 'h', 'a') + + def test_end_node_not_present(self): + with self.assertRaises(Exception): + get_path(self.graph, 'a', 'h') + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/norman.py b/users/wpcarro/scratch/data_structures_and_algorithms/norman.py new file mode 100644 index 0000000000..379ba92abb --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/norman.py @@ -0,0 +1,78 @@ + + + +# Write a function with the following type signature:L +# equal? :: String -> String -> Bool +# +# Determine equality between two inputs with backspace characters encoded as +# "<". + +################################################################################ +# Solution 1 +################################################################################ + +# from collections import deque + +# def equal(a, b): +# sa = deque() +# sb = deque() + +# for c in a: +# if c == '<': +# sa.pop() +# else: +# sa.append(c) + +# for c in b: +# if c == '<': +# sb.pop() +# else: +# sb.append(c) + +# return sa == sb + +################################################################################ +# Solution 2 +################################################################################ + +def handle_dels(num_dels, i, xs): + if i < 0: + return -1 + + while xs[i] == '<': + num_dels += 1 + i -= 1 + + while num_dels > 0 and xs[i] != '<': + num_dels -= 1 + i -= 1 + + if xs[i] == '<': + return handle_dels(num_dels, i, xs) + else: + return i + +def update_index(i, xs): + # TODO: Indexing into non-available parts of a string. + if xs[i] != '<' and xs[i - 1] != '<': + return i - 1 + + elif xs[i - 1] == '<': + return handle_dels(0, i - 1, xs) + +def equal(a, b): + ia = len(a) - 1 + ib = len(b) - 1 + + while ia >= 0 and ib >= 0: + if a[ia] != b[ib]: + return False + ia = update_index(ia, a) + ib = update_index(ib, b) + + if ia != 0: + return update_index(ia, a) <= -1 + if ib != 0: + return update_index(ib, b) <= -1 + + return True diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/nth-fibonacci.py b/users/wpcarro/scratch/data_structures_and_algorithms/nth-fibonacci.py new file mode 100644 index 0000000000..cdb2846ea3 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/nth-fibonacci.py @@ -0,0 +1,59 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +def fib(n): + """This should be accomplishable in O(1) space.""" + if n in {0, 1}: + return n + a = 0 # i = 0 + b = 1 # i = 1 + for x in range(2, n + 1): + result = a + b + a = b + b = result + return result + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_zeroth_fibonacci(self): + actual = fib(0) + expected = 0 + self.assertEqual(actual, expected) + + def test_first_fibonacci(self): + actual = fib(1) + expected = 1 + self.assertEqual(actual, expected) + + def test_second_fibonacci(self): + actual = fib(2) + expected = 1 + self.assertEqual(actual, expected) + + def test_third_fibonacci(self): + actual = fib(3) + expected = 2 + self.assertEqual(actual, expected) + + def test_fifth_fibonacci(self): + actual = fib(5) + expected = 5 + self.assertEqual(actual, expected) + + def test_tenth_fibonacci(self): + actual = fib(10) + expected = 55 + self.assertEqual(actual, expected) + + def test_negative_fibonacci(self): + with self.assertRaises(Exception): + fib(-1) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/optimal-stopping.py b/users/wpcarro/scratch/data_structures_and_algorithms/optimal-stopping.py new file mode 100644 index 0000000000..af13239941 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/optimal-stopping.py @@ -0,0 +1,49 @@ +from random import choice +from math import floor + +# Applying Chapter 1 from "Algorithms to Live By", which describes optimal +# stopping problems. Technically this simulation is invalid because the +# `candidates` function takes a lower bound and an upper bound, which allows us +# to know the cardinal number of an individual candidates. The "look then leap" +# algorithm is ideal for no-information games - i.e. games when upper and lower +# bounds aren't known. The `look_then_leap/1` function is ignorant of this +# information, so it behaves as if in a no-information game. Strangely enough, +# this algorithm will pick the best candidate 37% of the time. +# +# Chapter 1 describes two algorithms: +# 1. Look-then-leap: ordinal numbers - i.e. no-information games. Look-then-leap +# finds the best candidate 37% of the time. +# 2. Threshold: cardinal numbers - i.e. where upper and lower bounds are +# known. The Threshold algorithm finds the best candidate ~55% of the time. +# +# All of this and more can be studied as "optimal stopping theory". This applies +# to finding a spouse, parking a car, picking an apartment in a city, and more. + + +# candidates :: Int -> Int -> Int -> [Int] +def candidates(lb, ub, ct): + xs = list(range(lb, ub + 1)) + return [choice(xs) for _ in range(ct)] + + +# look_then_leap :: [Integer] -> Integer +def look_then_leap(candidates): + best = candidates[0] + seen_ct = 1 + ignore_ct = floor(len(candidates) * 0.37) + for x in candidates[1:]: + if ignore_ct > 0: + ignore_ct -= 1 + best = max(best, x) + else: + if x > best: + print('Choosing the {} candidate.'.format(seen_ct)) + return x + seen_ct += 1 + print('You may have waited too long.') + return candidates[-1] + + +candidates = candidates(1, 100, 100) +print(candidates) +print(look_then_leap(candidates)) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/perm-tree.py b/users/wpcarro/scratch/data_structures_and_algorithms/perm-tree.py new file mode 100644 index 0000000000..0eb389c26b --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/perm-tree.py @@ -0,0 +1,83 @@ +import unittest + + +################################################################################ +# Answer +################################################################################ +class Node(object): + def __init__(self, value, children=set()): + self.value = value + self.children = children + + +# treeify :: Char -> Set(Char) -> Node(Char) +def treeify(x, xs): + return Node(x, [treeify(c, xs - {c}) for c in xs]) + + +# dft :: Node(Char) -> [String] +def dft(node): + result = [] + s = [] + + s.append(('', node)) + + while s: + p, n = s.pop() + p += str(n.value) + + if not n.children: + result.append(p) + else: + for c in n.children: + s.append((p, c)) + + return result + + +# main :: String -> Set(String) +def get_permutations(xs): + if xs == '': + return set(['']) + + ys = set(xs) + trees = [] + + for y in ys: + trees.append(treeify(y, ys - {y})) + + result = set() + + for t in trees: + for d in dft(t): + result.add(d) + + return result + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_empty_string(self): + actual = get_permutations('') + expected = set(['']) + self.assertEqual(actual, expected) + + def test_one_character_string(self): + actual = get_permutations('a') + expected = set(['a']) + self.assertEqual(actual, expected) + + def test_two_character_string(self): + actual = get_permutations('ab') + expected = set(['ab', 'ba']) + self.assertEqual(actual, expected) + + def test_three_character_string(self): + actual = get_permutations('abc') + expected = set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']) + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/permutation-palindrome.py b/users/wpcarro/scratch/data_structures_and_algorithms/permutation-palindrome.py new file mode 100644 index 0000000000..0a2136a408 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/permutation-palindrome.py @@ -0,0 +1,49 @@ +from collections import Counter +import unittest + + +################################################################################ +# Impl +################################################################################ +# palindromifiable :: String -> Boolean +def has_palindrome_permutation(x): + bag = Counter(x) + odd_entries_ct = 0 + + for _, y in bag.items(): + if y % 2 != 0: + odd_entries_ct += 1 + + return odd_entries_ct in {0, 1} + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_permutation_with_odd_number_of_chars(self): + result = has_palindrome_permutation('aabcbcd') + self.assertTrue(result) + + def test_permutation_with_even_number_of_chars(self): + result = has_palindrome_permutation('aabccbdd') + self.assertTrue(result) + + def test_no_permutation_with_odd_number_of_chars(self): + result = has_palindrome_permutation('aabcd') + self.assertFalse(result) + + def test_no_permutation_with_even_number_of_chars(self): + result = has_palindrome_permutation('aabbcd') + self.assertFalse(result) + + def test_empty_string(self): + result = has_palindrome_permutation('') + self.assertTrue(result) + + def test_one_character_string(self): + result = has_palindrome_permutation('a') + self.assertTrue(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/permutations.py b/users/wpcarro/scratch/data_structures_and_algorithms/permutations.py new file mode 100644 index 0000000000..fc2c1ef7ee --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/permutations.py @@ -0,0 +1,55 @@ +class Node(object): + # ctor :: a -> [a] -> Node(a) + def __init__(self, value, children=[]): + self.value = value + self.children = children + + +# is_leaf :: Node(a) -> Boolean +def is_leaf(node): + return len(node.children) == 0 + + +# enumerate :: Node(a) -> Set(List(a)) +def enumerate(node): + current = [] + result = [] + q = [] + + q.append(node) + + while q: + x = q.pop() + print(x.value) + + for c in x.children: + q.append(c) + + current.append(x.value) + print(current) + + if is_leaf(x): + result.append(current) + print("Reseting current") + current = [] + + return result + + +node = Node('root', [ + Node('a', [ + Node('b', [Node('c')]), + Node('c', [Node('b')]), + ]), + Node('b', [ + Node('a', [Node('c')]), + Node('c', [Node('a')]), + ]), + Node('c', [ + Node('a', [Node('b')]), + Node('b', [Node('a')]), + ]) +]) + +print('----------') +print(enumerate(node)) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/plot.py b/users/wpcarro/scratch/data_structures_and_algorithms/plot.py new file mode 100644 index 0000000000..5601891a0d --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/plot.py @@ -0,0 +1,9 @@ +import numpy as np +import matplotlib.pyplot as plt + +rng = np.random.RandomState(10) # deterministic random data +a = np.hstack((rng.normal(size=1000), rng.normal(loc=5, scale=2, size=1000))) +_ = plt.hist(a, bins='auto') # arguments are passed to np.histogram +plt.title("Histogram with 'auto' bins") +Text(0.5, 1.0, "Histogram with 'auto' bins") +plt.show() diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/product-of-other-numbers.py b/users/wpcarro/scratch/data_structures_and_algorithms/product-of-other-numbers.py new file mode 100644 index 0000000000..d05e82d42b --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/product-of-other-numbers.py @@ -0,0 +1,68 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# f :: [Int] -> [Int] +def get_products_of_all_ints_except_at_index(xs): + if len(xs) in {0, 1}: + raise Exception + + ct = len(xs) + lefts = [1] * ct + rights = [1] * ct + result = [] + + for i in range(1, ct): + lefts[i] = lefts[i - 1] * xs[i - 1] + for i in range(ct - 2, -1, -1): + rights[i] = rights[i + 1] * xs[i + 1] + + return [lefts[i] * rights[i] for i in range(ct)] + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_small_list(self): + actual = get_products_of_all_ints_except_at_index([1, 2, 3]) + expected = [6, 3, 2] + self.assertEqual(actual, expected) + + def test_longer_list(self): + actual = get_products_of_all_ints_except_at_index([8, 2, 4, 3, 1, 5]) + expected = [120, 480, 240, 320, 960, 192] + self.assertEqual(actual, expected) + + def test_list_has_one_zero(self): + actual = get_products_of_all_ints_except_at_index([6, 2, 0, 3]) + expected = [0, 0, 36, 0] + self.assertEqual(actual, expected) + + def test_list_has_two_zeros(self): + actual = get_products_of_all_ints_except_at_index([4, 0, 9, 1, 0]) + expected = [0, 0, 0, 0, 0] + self.assertEqual(actual, expected) + + def test_one_negative_number(self): + actual = get_products_of_all_ints_except_at_index([-3, 8, 4]) + expected = [32, -12, -24] + self.assertEqual(actual, expected) + + def test_all_negative_numbers(self): + actual = get_products_of_all_ints_except_at_index([-7, -1, -4, -2]) + expected = [-8, -56, -14, -28] + self.assertEqual(actual, expected) + + def test_error_with_empty_list(self): + with self.assertRaises(Exception): + get_products_of_all_ints_except_at_index([]) + + def test_error_with_one_number(self): + with self.assertRaises(Exception): + get_products_of_all_ints_except_at_index([1]) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/queue-two-stacks.py b/users/wpcarro/scratch/data_structures_and_algorithms/queue-two-stacks.py new file mode 100644 index 0000000000..63da08ebf7 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/queue-two-stacks.py @@ -0,0 +1,66 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +class QueueTwoStacks(object): + def __init__(self): + self.a = [] + self.b = [] + + def enqueue(self, x): + self.a.append(x) + + def dequeue(self): + if self.b: + return self.b.pop() + else: + while self.a: + self.b.append(self.a.pop()) + return self.dequeue() + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_basic_queue_operations(self): + queue = QueueTwoStacks() + queue.enqueue(1) + queue.enqueue(2) + queue.enqueue(3) + actual = queue.dequeue() + expected = 1 + self.assertEqual(actual, expected) + actual = queue.dequeue() + expected = 2 + self.assertEqual(actual, expected) + queue.enqueue(4) + actual = queue.dequeue() + expected = 3 + self.assertEqual(actual, expected) + actual = queue.dequeue() + expected = 4 + self.assertEqual(actual, expected) + + def test_error_when_dequeue_from_new_queue(self): + queue = QueueTwoStacks() + with self.assertRaises(Exception): + queue.dequeue() + + def test_error_when_dequeue_from_empty_queue(self): + queue = QueueTwoStacks() + queue.enqueue(1) + queue.enqueue(2) + actual = queue.dequeue() + expected = 1 + self.assertEqual(actual, expected) + actual = queue.dequeue() + expected = 2 + self.assertEqual(actual, expected) + with self.assertRaises(Exception): + queue.dequeue() + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/rectangular-love.py b/users/wpcarro/scratch/data_structures_and_algorithms/rectangular-love.py new file mode 100644 index 0000000000..47c0f53979 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/rectangular-love.py @@ -0,0 +1,246 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# bottom :: Rectangle -> Int +def bottom(x): + return x.get('bottom_y') + + +# top :: Rectangle -> Int +def top(x): + return bottom(x) + x.get('height') + + +# left :: Rectangle -> Int +def left(x): + return x.get('left_x') + + +# right :: Rectangle -> Int +def right(x): + return left(x) + x.get('width') + + +# sort_highest :: Rectangle -> Rectangle -> (Rectangle, Rectangle) +def sort_highest(x, y): + if top(x) >= top(y): + return x, y + else: + return y, x + + +# sort_leftmost :: Rectangle -> Rectangle -> (Rectangle, Rectangle) +def sort_leftmost(x, y): + if left(x) <= left(y): + return x, y + else: + return y, x + + +# rectify :: Int -> Int -> Int -> Int -> Rectify +def rectify(top=None, bottom=None, left=None, right=None): + assert top >= bottom + assert left <= right + return { + 'left_x': left, + 'bottom_y': bottom, + 'width': right - left, + 'height': top - bottom, + } + + +# empty_rect :: Rectangle +def empty_rect(): + return { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + + +# find_rectangular_overlap :: Rectangle -> Rectangle -> Maybe(Rectangle) +def find_rectangular_overlap(x, y): + ha, hb = sort_highest(x, y) + la, lb = sort_leftmost(x, y) + + if bottom(hb) <= top(hb) <= bottom(ha) <= top(ha): + return empty_rect() + + if left(la) <= right(la) <= left(lb) <= right(lb): + return empty_rect() + + # We should have an intersection here. + verts = [bottom(ha), top(ha), bottom(hb), top(hb)] + verts.sort() + horzs = [left(la), right(la), left(lb), right(lb)] + horzs.sort() + return rectify(top=verts[2], + bottom=verts[1], + left=horzs[1], + right=horzs[2]) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_overlap_along_both_axes(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 6, + 'height': 3, + } + rect2 = { + 'left_x': 5, + 'bottom_y': 2, + 'width': 3, + 'height': 6, + } + expected = { + 'left_x': 5, + 'bottom_y': 2, + 'width': 2, + 'height': 2, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_one_rectangle_inside_another(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 6, + 'height': 6, + } + rect2 = { + 'left_x': 3, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': 3, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_both_rectangles_the_same(self): + rect1 = { + 'left_x': 2, + 'bottom_y': 2, + 'width': 4, + 'height': 4, + } + rect2 = { + 'left_x': 2, + 'bottom_y': 2, + 'width': 4, + 'height': 4, + } + expected = { + 'left_x': 2, + 'bottom_y': 2, + 'width': 4, + 'height': 4, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_touch_on_horizontal_edge(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 2, + 'width': 3, + 'height': 4, + } + rect2 = { + 'left_x': 2, + 'bottom_y': 6, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_touch_on_vertical_edge(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 2, + 'width': 3, + 'height': 4, + } + rect2 = { + 'left_x': 4, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_touch_at_a_corner(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 2, + 'height': 2, + } + rect2 = { + 'left_x': 3, + 'bottom_y': 3, + 'width': 2, + 'height': 2, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + def test_no_overlap(self): + rect1 = { + 'left_x': 1, + 'bottom_y': 1, + 'width': 2, + 'height': 2, + } + rect2 = { + 'left_x': 4, + 'bottom_y': 6, + 'width': 3, + 'height': 6, + } + expected = { + 'left_x': None, + 'bottom_y': None, + 'width': None, + 'height': None, + } + actual = find_rectangular_overlap(rect1, rect2) + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/recursive-string-permutations.py b/users/wpcarro/scratch/data_structures_and_algorithms/recursive-string-permutations.py new file mode 100644 index 0000000000..70461ddf5d --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/recursive-string-permutations.py @@ -0,0 +1,37 @@ +import unittest + + +################################################################################ +# Implementation +################################################################################ +# get_permutations :: String -> Set(String) +def get_permutations(string): + pass + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_empty_string(self): + actual = get_permutations('') + expected = set(['']) + self.assertEqual(actual, expected) + + def test_one_character_string(self): + actual = get_permutations('a') + expected = set(['a']) + self.assertEqual(actual, expected) + + def test_two_character_string(self): + actual = get_permutations('ab') + expected = set(['ab', 'ba']) + self.assertEqual(actual, expected) + + def test_three_character_string(self): + actual = get_permutations('abc') + expected = set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']) + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/reverse-linked-list.py b/users/wpcarro/scratch/data_structures_and_algorithms/reverse-linked-list.py new file mode 100644 index 0000000000..b7396b20ce --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/reverse-linked-list.py @@ -0,0 +1,79 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# reverse :: List(a) -> List(a) +def reverse(node): + curr = node + prev = None + while curr: + nxt = curr.next + curr.next = prev + prev = curr + curr = nxt + # Make sure to understand the spec! Debugging takes time. Rewriting takes + # time. + return prev + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class LinkedListNode(object): + def __init__(self, value, next=None): + self.value = value + self.next = next + + def get_values(self): + node = self + values = [] + while node is not None: + values.append(node.value) + node = node.next + return values + + def test_short_linked_list(self): + second = Test.LinkedListNode(2) + first = Test.LinkedListNode(1, second) + + result = reverse(first) + self.assertIsNotNone(result) + + actual = result.get_values() + expected = [2, 1] + self.assertEqual(actual, expected) + + def test_long_linked_list(self): + sixth = Test.LinkedListNode(6) + fifth = Test.LinkedListNode(5, sixth) + fourth = Test.LinkedListNode(4, fifth) + third = Test.LinkedListNode(3, fourth) + second = Test.LinkedListNode(2, third) + first = Test.LinkedListNode(1, second) + + result = reverse(first) + self.assertIsNotNone(result) + + actual = result.get_values() + expected = [6, 5, 4, 3, 2, 1] + self.assertEqual(actual, expected) + + def test_one_element_linked_list(self): + first = Test.LinkedListNode(1) + + result = reverse(first) + self.assertIsNotNone(result) + + actual = result.get_values() + expected = [1] + self.assertEqual(actual, expected) + + def test_empty_linked_list(self): + result = reverse(None) + self.assertIsNone(result) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py b/users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py new file mode 100644 index 0000000000..5df12ebabd --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/reverse-words.py @@ -0,0 +1,181 @@ +from collections import deque +import unittest + +################################################################################ +# Solution +################################################################################ + + +def rev(xs, i, j): + """Reverse xs in place from [i, j]""" + while i < j: + xs[i], xs[j] = xs[j], xs[i] + i += 1 + j -= 1 + + +def rotate(xs, n, i=None, j=None): + """Mutably rotates list, xs, n times. Positive n values rotate right while + negative n values rotate left. Rotate within window [i, j].""" + i = i or 0 + j = j or len(xs) - 1 + ct = j - i + + if n < 0: + n = abs(n) + p = i + n - 1 + rev(xs, i, p) + rev(xs, p + 1, j) + rev(xs, i, j) + else: + p = j - (n - 1) + rev(xs, p, j) + rev(xs, i, p - 1) + rev(xs, i, j) + return xs + + +def rev_words(xs, i, j): + if j + 1 == len(xs): + return 0 + + while j + 1 < len(xs): + while j + 1 < len(xs) and xs[j + 1] != ' ': + j += 1 + + rev(xs, i, j) + j += 2 + i = j + + return 0 + + +def reverse_words(xs): + # first reverse everything + rev(xs, 0, len(xs) - 1) + return rev_words(xs, 0, 0) + + +def reverse_words_bak(xs, i=None, j=None): + i = i or 0 + j = j or len(xs) - 1 + w0, w1 = [], [] + + if i >= j: + return 0 + + pi = i + while pi < len(xs) and xs[pi] != ' ': + w0.append(xs[pi]) + pi += 1 + + if pi == len(xs): + return 0 + + pj = j + while xs[pj] != ' ': + w1.append(xs[pj]) + pj -= 1 + + d = len(w0) - len(w1) + + rotate(xs, -1 * d, i, j) + + for k in range(len(w1)): + xs[i + k] = w1[len(w1) - 1 - k] + + for k in range(len(w0)): + xs[j - k] = w0[len(w0) - 1 - k] + + while i != j and xs[i] != ' ' and xs[j] != ' ': + i += 1 + j -= 1 + + if i == j: + return 0 + + elif xs[i] == ' ': + while j > 0 and xs[j] != ' ': + j -= 1 + if j == 0: + return 0 + elif xs[j] == ' ': + while i < len(xs) and xs[i] != ' ': + i += 1 + if i == len(xs): + return 0 + return reverse_words(xs, i + 1, j - 1) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_rev(self): + xs = [1, 2, 3, 4, 5] + rev(xs, 0, len(xs) - 1) + self.assertEqual(xs, [5, 4, 3, 2, 1]) + + def test_rotate(self): + ys = [1, 2, 3, 4, 5] + xs = ys[:] + self.assertEqual(rotate(xs, 1, 1, 3), [1, 4, 2, 3, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, -1, 1, 3), [1, 3, 4, 2, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, 1), [5, 1, 2, 3, 4]) + xs = ys[:] + self.assertEqual(rotate(xs, -1), [2, 3, 4, 5, 1]) + xs = ys[:] + self.assertEqual(rotate(xs, -2), [3, 4, 5, 1, 2]) + xs = ys[:] + self.assertEqual(rotate(xs, -5), [1, 2, 3, 4, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, 5), [1, 2, 3, 4, 5]) + xs = ys[:] + self.assertEqual(rotate(xs, 3), [3, 4, 5, 1, 2]) + + def test_one_word(self): + message = list('vault') + reverse_words(message) + expected = list('vault') + self.assertEqual(message, expected) + + def test_two_words(self): + message = list('thief cake') + reverse_words(message) + expected = list('cake thief') + self.assertEqual(message, expected) + + def test_three_words(self): + message = list('one another get') + reverse_words(message) + expected = list('get another one') + self.assertEqual(message, expected) + + def test_multiple_words_same_length(self): + message = list('rat the ate cat the') + reverse_words(message) + expected = list('the cat ate the rat') + self.assertEqual(message, expected) + + def test_multiple_words_different_lengths(self): + message = list('at rat house') + reverse_words(message) + expected = list('house rat at') + self.assertEqual(message, expected) + + def test_multiple_words_different_lengths(self): + message = list('yummy is cake bundt chocolate') + reverse_words(message) + expected = list('chocolate bundt cake is yummy') + self.assertEqual(message, expected) + + def test_empty_string(self): + message = list('') + reverse_words(message) + expected = list('') + self.assertEqual(message, expected) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/second-largest-item-bst.py b/users/wpcarro/scratch/data_structures_and_algorithms/second-largest-item-bst.py new file mode 100644 index 0000000000..bc167d975a --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/second-largest-item-bst.py @@ -0,0 +1,179 @@ +import unittest +from collections import deque + + +################################################################################ +# Implementation +################################################################################ +def is_leaf(node): + return node.left is None and node.right is None + + +def find_largest(node): + current = node + while current.right is not None: + current = current.right + return current.value + + +def find_second_largest(node): + history = deque() + current = node + + while current.right: + history.append(current) + current = current.right + + if current.left: + return find_largest(current.left) + elif history: + return history.pop().value + else: + raise TypeError + + +def find_second_largest_backup(node): + history = deque() + current = node + + # traverse -> largest + while current.right: + history.append(current) + current = current.right + + if current.left: + return find_largest(current.left) + elif history: + return history.pop().value + else: + raise ArgumentError + + +# Write a iterative version to avoid consuming memory with the call stack. +# Commenting out the recursive code for now. +def find_second_largest_backup(node): + if node.left is None and node.right is None: + raise ArgumentError + + elif node.right is None and is_leaf(node.left): + return node.left.value + + # recursion + # elif node.right is None: + # return find_largest(node.left) + + # iterative version + elif node.right is None: + current = node.left + while current.right is not None: + current = current.right + return current.value + + # recursion + # TODO: Remove recursion from here. + elif not is_leaf(node.right): + return find_second_largest(node.right) + + # could do an else here, but let's be more assertive. + elif is_leaf(node.right): + return node.value + + else: + raise ArgumentError + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + class BinaryTreeNode(object): + def __init__(self, value): + self.value = value + self.left = None + self.right = None + + def insert_left(self, value): + self.left = Test.BinaryTreeNode(value) + return self.left + + def insert_right(self, value): + self.right = Test.BinaryTreeNode(value) + return self.right + + def test_full_tree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + right.insert_right(80) + actual = find_second_largest(tree) + expected = 70 + self.assertEqual(actual, expected) + + def test_largest_has_a_left_child(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right.insert_left(60) + actual = find_second_largest(tree) + expected = 60 + self.assertEqual(actual, expected) + + def test_largest_has_a_left_subtree(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + right = tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + right_left = right.insert_left(60) + right_left_left = right_left.insert_left(55) + right_left.insert_right(65) + right_left_left.insert_right(58) + actual = find_second_largest(tree) + expected = 65 + self.assertEqual(actual, expected) + + def test_second_largest_is_root_node(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(30) + tree.insert_right(70) + left.insert_left(10) + left.insert_right(40) + actual = find_second_largest(tree) + expected = 50 + self.assertEqual(actual, expected) + + def test_descending_linked_list(self): + tree = Test.BinaryTreeNode(50) + left = tree.insert_left(40) + left_left = left.insert_left(30) + left_left_left = left_left.insert_left(20) + left_left_left.insert_left(10) + actual = find_second_largest(tree) + expected = 40 + self.assertEqual(actual, expected) + + def test_ascending_linked_list(self): + tree = Test.BinaryTreeNode(50) + right = tree.insert_right(60) + right_right = right.insert_right(70) + right_right.insert_right(80) + actual = find_second_largest(tree) + expected = 70 + self.assertEqual(actual, expected) + + def test_error_when_tree_has_one_node(self): + tree = Test.BinaryTreeNode(50) + with self.assertRaises(Exception): + find_second_largest(tree) + + def test_error_when_tree_is_empty(self): + with self.assertRaises(Exception): + find_second_largest(None) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/shortest-path-inject-vertices.py b/users/wpcarro/scratch/data_structures_and_algorithms/shortest-path-inject-vertices.py new file mode 100644 index 0000000000..e08ea66b8f --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/shortest-path-inject-vertices.py @@ -0,0 +1,94 @@ +from heapq import heappush, heappop +from collections import deque +from fixtures import weighted_graph, expanded_weights_graph + +# UnweightedGraph(a) :: Map(a, Set(a)) +# WeightedGraph(a) :: Map(a, Set(a)) + + +# shortest_path_dijkstra :: Vertex -> Vertex -> WeightedGraph(Vertex) +def shortest_path_dijkstra(a, b, g): + q = [] + seen = set() + + heappush(q, (0, a, [a])) + + while q: + w0, v0, path = heappop(q) + if v0 in seen: + continue + elif v0 == b: + return w0, path + for w1, v1 in g.get(v0): + heappush(q, (w0 + w1, v1, path + [v1])) + seen.add(v0) + return 'weighted', 'pizza' + + +# expand_edge :: Vertex -> (Weight, Vertex) -> Map(Vertex, [Vertex]) +def expand_edge(v0, wv): + w, v1 = wv + assert w > 1 + + result = {v0: ['{}-{}'.format(v1, 1)]} + for x in range(w - 2): + result['{}-{}'.format(v1, x + 1)] = ['{}-{}'.format(v1, x + 2)] + result['{}-{}'.format(v1, w - 1)] = [v1] + + return result + + +# expand_weights :: Vertex -> WeightedGraph(Vertex) -> UnweightedGraph(Vertex) +def expand_weights(v, g): + result = {} + q = deque() + seen = set() + + q.append(v) + while q: + v = d.popleft() + if v in seen: + continue + x = expand_edge(v, g.get) + for w, v1 in g.get(v): + if w > 1: + ws = expand_edge(v, (w, v1)) + result = {**result, **ws} + q.append(v) + pass + + +# shortest_path_inject :: Vertex -> Vertex -> WeightedGraph(Vertex) +def shortest_path_inject(a, b, g): + q = deque() + seen = set() + + q.append((a, [a])) + + while q: + v0, path = q.popleft() + if v0 == 'dummy': + continue + elif v0 in seen: + continue + elif v0 == b: + return len(path), path + for _, v1 in g.get(v0): + q.append((v1, path + [v1])) + seen.add(v0) + continue + + return None, None + + +print(expand_edge('a', (4, 'b'))) +print(expand_edge('a', (5, 'e'))) +assert expand_weights('a', weighted_graph) == expanded_weights_graph +# a = 'a' +# b = 'd' +# w, x = shortest_path_dijkstra(a, b, weighted_graph) +# w1, x1 = shortest_path_inject(a, b, weighted_graph) +# print("[dijkstra] Shortest path from {} to {} is {} with weight {}".format( +# a, b, x, w)) +# print("[injection] Shortest path from {} to {} is {} with weight {}".format( +# a, b, x1, w1)) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/shuffle.py b/users/wpcarro/scratch/data_structures_and_algorithms/shuffle.py new file mode 100644 index 0000000000..bdfbad2426 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/shuffle.py @@ -0,0 +1,34 @@ +import random + + +def get_random(floor, ceiling): + return random.randrange(floor, ceiling + 1) + + +# shuffle_in_place :: [a] -> IO () +def shuffle_in_place(xs): + """Fisher-Yates algorithm. Notice that shuffling here is the same as + selecting a random permutation of the input set, `xs`.""" + n = len(xs) - 1 + for i in range(len(xs)): + r = get_random(i, n) + xs[i], xs[r] = xs[r], xs[i] + return xs + + +# shuffle :: [a] -> [a] +def shuffle_not_in_place(xs): + result = [] + + while xs: + i = get_random(0, len(xs) - 1) + x = xs.pop(i) + result.append(x) + + return result + + +xs = [x for x in range(9)] +print(xs) +# print(shuffle_not_in_place(xs)) +print(shuffle_in_place(xs[:])) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/string-reverse.py b/users/wpcarro/scratch/data_structures_and_algorithms/string-reverse.py new file mode 100644 index 0000000000..8b4cdac1c2 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/string-reverse.py @@ -0,0 +1,22 @@ + +# swap :: Int -> Int -> [Char] -> IO () +def swap(ia, iz, xs): + # handle swap when ia == iz + assert ia <= iz + xs[ia], xs[iz] = xs[iz], xs[ia] + + +# reverse :: [Char] -> IO () +def reverse(xs): + ia = 0 + iz = len(xs) - 1 + + while ia <= iz: + swap(ia, iz, xs) + ia += 1 + iz -= 1 + +x = list("superduperpooper") +reverse(x) +print(x) +print("Tests pass") diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/temperature-tracker.py b/users/wpcarro/scratch/data_structures_and_algorithms/temperature-tracker.py new file mode 100644 index 0000000000..6b042182f0 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/temperature-tracker.py @@ -0,0 +1,84 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +class TempTracker(object): + def __init__(self): + # min / max + self.min = None + self.max = None + # mean + self.sum = 0 + self.num = 0 + # mode + self.nums = [0] * 111 + self.mode_num = 0 + self.mode = None + + def insert(self, x): + # min / max + if not self.min or x < self.min: + self.min = x + if not self.max or x > self.max: + self.max = x + # mean + self.sum += x + self.num += 1 + # mode + self.nums[x] += 1 + if self.nums[x] >= self.mode_num: + self.mode_num = self.nums[x] + self.mode = x + + def get_max(self): + return self.max + + def get_min(self): + return self.min + + def get_mean(self): + return self.sum / self.num + + def get_mode(self): + return self.mode + + +# Tests + + +class Test(unittest.TestCase): + def test_tracker_usage(self): + tracker = TempTracker() + + tracker.insert(50) + msg = 'failed on first temp recorded' + self.assertEqual(tracker.get_max(), 50, msg='max ' + msg) + self.assertEqual(tracker.get_min(), 50, msg='min ' + msg) + self.assertEqual(tracker.get_mean(), 50.0, msg='mean ' + msg) + self.assertEqual(tracker.get_mode(), 50, msg='mode ' + msg) + + tracker.insert(80) + msg = 'failed on higher temp recorded' + self.assertEqual(tracker.get_max(), 80, msg='max ' + msg) + self.assertEqual(tracker.get_min(), 50, msg='min ' + msg) + self.assertEqual(tracker.get_mean(), 65.0, msg='mean ' + msg) + self.assertIn(tracker.get_mode(), [50, 80], msg='mode ' + msg) + + tracker.insert(80) + msg = 'failed on third temp recorded' + self.assertEqual(tracker.get_max(), 80, msg='max ' + msg) + self.assertEqual(tracker.get_min(), 50, msg='min ' + msg) + self.assertEqual(tracker.get_mean(), 70.0, msg='mean ' + msg) + self.assertEqual(tracker.get_mode(), 80, msg='mode ' + msg) + + tracker.insert(30) + msg = 'failed on lower temp recorded' + self.assertEqual(tracker.get_max(), 80, msg='max ' + msg) + self.assertEqual(tracker.get_min(), 30, msg='min ' + msg) + self.assertEqual(tracker.get_mean(), 60.0, msg='mean ' + msg) + self.assertEqual(tracker.get_mode(), 80, msg='mode ' + msg) + + +unittest.main(verbosity=2) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/test.txt b/users/wpcarro/scratch/data_structures_and_algorithms/test.txt new file mode 100644 index 0000000000..ce01362503 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/test.txt @@ -0,0 +1 @@ +hello diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/top-scores.py b/users/wpcarro/scratch/data_structures_and_algorithms/top-scores.py new file mode 100644 index 0000000000..8e7b073dd8 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/top-scores.py @@ -0,0 +1,25 @@ +from collections import deque + +# list: +# array: +# vector: +# bit-{array,vector}: + + +def sort(xs, highest): + v = [0] * (highest + 1) + result = deque() + + for x in xs: + v[x] += 1 + + for i, x in enumerate(v): + if x > 0: + result.appendleft(i) + + return list(result) + + +assert sort([37, 89, 41, 100, 65, 91, 53], + 100) == [100, 91, 89, 65, 53, 41, 37] +print("Tests pass!") diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/topo-sort.py b/users/wpcarro/scratch/data_structures_and_algorithms/topo-sort.py new file mode 100644 index 0000000000..fe295b0279 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/topo-sort.py @@ -0,0 +1,31 @@ +from fixtures import unweighted_digraph +from collections import deque + +# vertices_no_in_edges :: UnweightedDigraph -> Set(Vertex) +def vertices_no_in_edges(g): + """Return the vertices in graph `g` with no in-edges.""" + result = set() + vertices = set(g.keys()) + for neighbors in g.values(): + result = result.union(neighbors) + return vertices ^ result + +# topo_sort :: UnweightedDigraph -> List(Vertex) +def topo_sort(g): + q = deque() + seen = set() + result = [] + for x in vertices_no_in_edges(g): + q.append(x) + while q: + vertex = q.popleft() + if vertex in seen: + continue + result.append(vertex) + neighbors = g.get(vertex) + for x in g.get(vertex): + q.append(x) + seen.add(vertex) + return result + +print(topo_sort(unweighted_digraph)) diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/trickling-water.py b/users/wpcarro/scratch/data_structures_and_algorithms/trickling-water.py new file mode 100644 index 0000000000..45621990ec --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/trickling-water.py @@ -0,0 +1,38 @@ +class Node(object): + def __init__(self, value, children=[]): + self.value = value + self.children = children + + +################################################################################ +# Solution +################################################################################ +def trip_time(node): + s = [] + result = 0 + s.append((node.value, node)) + while s: + p, node = s.pop() + if not node.children: + result = max(result, p) + for x in node.children: + s.append((p + x.value, x)) + return result + + +################################################################################ +# Tests +################################################################################ +tree = Node( + 0, + children=[ + Node(5, children=[Node(6)]), + Node(2, children=[ + Node(6), + Node(10), + ]), + Node(3, children=[Node(2, children=[Node(11)])]), + ]) + +assert trip_time(tree) == 16 +print("Tests pass!") diff --git a/users/wpcarro/scratch/data_structures_and_algorithms/which-appears-twice.py b/users/wpcarro/scratch/data_structures_and_algorithms/which-appears-twice.py new file mode 100644 index 0000000000..e9a4f0eb24 --- /dev/null +++ b/users/wpcarro/scratch/data_structures_and_algorithms/which-appears-twice.py @@ -0,0 +1,33 @@ +import unittest + + +################################################################################ +# Solution +################################################################################ +# find_repeat :: [Int] -> Int +def find_repeat(xs): + n = len(xs) - 1 + return sum(xs) - ((n**2 + n) / 2) + + +################################################################################ +# Tests +################################################################################ +class Test(unittest.TestCase): + def test_short_list(self): + actual = find_repeat([1, 2, 1]) + expected = 1 + self.assertEqual(actual, expected) + + def test_medium_list(self): + actual = find_repeat([4, 1, 3, 4, 2]) + expected = 4 + self.assertEqual(actual, expected) + + def test_long_list(self): + actual = find_repeat([1, 5, 9, 7, 2, 6, 3, 8, 2, 4]) + expected = 2 + self.assertEqual(actual, expected) + + +unittest.main(verbosity=2) |