DCP Notebook

def return_num_lists_conseq_pos_int(n):
    count = 0  # always count the trivial case, [n]
    for i in range(1, n+1):
        total = 0
        while total < n:
            total = total + i
            i += 1
        if total == n:
            count += 1
    return count

return_num_lists_conseq_pos_int(9)

def check_list(list, k):
    # use nested list comprehension
    # add nth element to every other element, for all n
    sums = [list[n] + x for x in list for n in range(len(list))]
#     print(sums)
    if k in sums:
        return True
    else:
        return False

check_list([10, 15, 3, 7], 17)

check_list([10, 15, 3, 7], 19)

stock_prices = [10, 7, 5, 8, 11, 9]

def get_max_profit(stock_prices):
    if len(stock_prices) < 2:
        raise ValueError ('need at least 2 prices!')
     
    # greedy, O^n
    min_price = stock_prices[0]
    max_profit = stock_prices[1] - stock_prices[0]
    
    for current_time in range(1,len(stock_prices)):
        current_profit = stock_prices[current_time] - min_price
        max_profit = max(max_profit, current_profit)
        min_price = min(min_price, stock_prices[current_time])    
    return(max_profit)

get_max_profit(stock_prices)

import numpy as np
from functools import reduce

# with division and .prod()
def product_list_v1(list):
    array = np.array(list)
    product_list_v1 = [int(array.prod()/x) for x in array]
    return product_list_v1
print(product_list_v1([1, 2, 3, 4, 5]))
print(product_list_v1([3, 2, 1]))

# with division and reduce
def product_list_v2(list):
    array = np.array(list)
    product_list_v2 = [int(reduce(lambda x, y: x*y, array)/x) for x in array]
    return product_list_v2
print(product_list_v2([1, 2, 3, 4, 5]))
print(product_list_v2([3, 2, 1]))

# without division
def product_list_v3(list):
    array = np.array(list)
    product_list_v3 = [reduce(lambda x, y: x*y, array[array != x]) for x in array]
    return product_list_v3

print(product_list_v3([1, 2, 3, 4, 5]))
print(product_list_v3([3, 2, 1]))

import numpy as np
import random

unsorted_scores = [37, 89, 41, 65, 91, 53, 53, 1, 6, 8, 65, 0, 91]
HIGHEST_POSSIBLE_SCORE = 100

counts = np.zeros(HIGHEST_POSSIBLE_SCORE, dtype=int)
sorted_scores = ([])
def sort_scores(unsorted_scores, HIGHEST_POSSIBLE_SCORE):
    for score in unsorted_scores:
        counts[score] += 1
    for score in range(len(counts)):
        times = counts[score]
        for time in range(times):
            sorted_scores.append(score)
    return sorted_scores[::-1]
sort_scores(unsorted_scores, 100)

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)

a.left = b
a.right = c
c.left = d
c.right = e

def serialize(root):
    nodes = [root]
    for node in nodes:
        if not node:
            break
        nodes += [node.left, node.right]
    s = list(map(lambda x: str(x.val) if x else None, nodes))
    return s

serialize(a)

def deserialize(s):
    tree = Node(int(s[0]))
    for item in s[1:]:
        if item:
            tree.left = Node(int(item))
            tree.right = Node(int(item))
        else:
            break
    return tree
    
deserialize(serialize(a))

node = Node('root', Node('left', Node('left.left')), Node('right'))
assert deserialize(serialize(node)).left.left.val == 'left.left'

array = [3, 4, -1, 1]
# array = np.array([1, 2, 0])

def find_first_missing_positive(array):
    new_array = [array[0]]
    for i in range(1,len(array)):
        if array[i] > new_array[i-1]:
            new_array.append(array[i])
        else:
            new_array.insert(i-1, array[i])
    return(new_array)

find_first_missing_positive(array)

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

def car(pair):
    def return_first(a, b):
        return a
    return pair(return_first)
    
def cdr(pair):
    def return_last(a, b):
        return b
    return pair(return_last)

car(cons(3, 4)), cdr(cons(3, 4))

message = 111

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

a = Node(0)
b = Node(1)
c = Node(0)
d = Node(1)
e = Node(0)
f = Node(1)
g = Node(1)

a.left = b
a.right = c
c.left = d
c.right = e
d.left = f
d.right = g

# depth-first, simply due to recursion

def count_unival_subtrees(root):
    # if no root is given, return 0
    if not root:
        return 0
    # if root has no children, unival count is 1
    elif not root.left and not root.right:
        return 1
    # if root.left == None and root.right exists
    elif not root.left and root.val == root.right.val:
        return 1 + count_unival_subtrees(root.right)
    # if root.right == None and root.left exists
    elif not root.right and root.val == root.left.val:
        return 1 + count_unival_subtrees(root.left)
   
    children_counts = count_unival_subtrees(root.left) + count_unival_subtrees(root.right)
    
    # if node, node.left and node.right are all equal, that counts too:
    current_note_count = 0
    if root.val == root.left.val == root.right.val:
        current_note_count = 1
        
    return current_note_count + children_counts
    
print(count_unival_subtrees(a))

assert count_unival_subtrees(None) == 0
assert count_unival_subtrees(b) == 1
assert count_unival_subtrees(c) == 4
assert count_unival_subtrees(d) == 3
assert count_unival_subtrees(e) == 1
assert count_unival_subtrees(f) == 1
assert count_unival_subtrees(g) == 1

log = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

def record(order_id):
    log.append(order_id)
    
def get_last(i):
    return log[-i]

def last_N_order_ids(N):
    return [get_last(i) for i in range(1,N+1)]

assert last_N_order_ids(3) == [10, 9, 8], 'fail'

last_N_order_ids(3)

class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next

A = Node(3, Node(7, Node(8, Node(10))))
B = Node(99, Node(1, Node(8, Node(10))))

def find_intersection(A, B):
    # enumerate A first, turn it into a list
    list_a = [A.val]
    while A.next:
        list_a.append(A.next.val)
        A = A.next
    
    # go through B, searching for matches
    while B.next:
        if B.val in list_a:
            return B.val
        else:
            B = B.next

## test
assert find_intersection(A, B) == 8

class Rocket():
    # simulate a rocket, for a game
    
    def __init__(self):   
        self.x = 0   #stores attributes of Rocket
        self.y = 0
        
    def move_up(self):  #do something to one of the attributes
        self.y += 1

#Now, make a Rocket:

#variable = name of the class
rocket = Rocket()
print(rocket)

rocket.x

rocket.y

rocket.move_up()

rocket.y

# Create a fleet of 5 rockets, and store them in a list.
my_rockets = []
for x in range(0,5):
    new_rocket = Rocket()
    my_rockets.append(new_rocket)
    
for rocket in my_rockets:
    print(rocket)

# with list comprehension:
my_rockets_list = [Rocket() for x in range(0,5)]
print(my_rockets_list)

my_rockets_list[4].move_up()
for rockets in my_rockets_list:
    print('altitude:', rockets.y)

# accept parameters for init method
class Rocket():
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
    
    def move_up(self):
        self.y += 1

a = Rocket(5,10)
a.move_up()
a.y

# accept parameters for move_up method
class Rocket():
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
    
    def move_rocket(self, x_increment=0, y_increment=0):
        self.x += x_increment
        self.y += y_increment

b = Rocket(0,0)
b.move_rocket(1,2)
print(b.x, b.y)

from math import sqrt
# add "distance to other rocket" method
class Rocket():
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y
    
    def move_rocket(self, x_increment=0, y_increment=0):
        self.x += x_increment
        self.y += y_increment
        
    def get_distance(self, other_rocket):
        x_diff = self.x-other_rocket.x
        y_diff = self.y-other_rocket.y
        distance = sqrt(x_diff**2 + y_diff**2)
        return distance

Rocket(0,0).get_distance(Rocket(1,1))

class NewClass(ParentClass):
    
    def __init__(self, arguments_new_class, arguments_parent_class):
        super().__init__(arguments_parent_class)  # Code for initializing an object of the new class.

class Shuttle(Rocket):
    # Shuttle simulates a space shuttle, which is really
    #  just a reusable rocket.
    def __init__(self, x=0, y=0, flights_completed=0):
        super().__init__(x, y)
        self.flights_completed = flights_completed

# Save as rocket.py
from math import sqrt

class Rocket():
    # Rocket simulates a rocket ship for a game,
    #  or a physics simulation.
    
    def __init__(self, x=0, y=0):
        # Each rocket has an (x,y) position.
        self.x = x
        self.y = y
        
    def move_rocket(self, x_increment=0, y_increment=1):
        # Move the rocket according to the paremeters given.
        #  Default behavior is to move the rocket up one unit.
        self.x += x_increment
        self.y += y_increment
        
    def get_distance(self, other_rocket):
        # Calculates the distance from this rocket to another rocket,
        #  and returns that value.
        distance = sqrt((self.x-other_rocket.x)**2+(self.y-other_rocket.y)**2)
        return distance

class Shuttle(Rocket):
    # Shuttle simulates a space shuttle, which is really
    #  just a reusable rocket.
    def __init__(self, x=0, y=0, flights_completed=0):
        super().__init__(x, y)
        self.flights_completed = flights_completed

# inside rocket_simulation.py, do..

# from (module) import (Class)

from rocket import Rocket, Shuttle

rocket = Rocket(5, 16)
print("The rocket is at (%d, %d)." % (rocket.x, rocket.y))

shuttle = Shuttle(0, 0, 7)
print("The shuttle is at (%d, %d) and has flown %d times." % (shuttle.x, shuttle.y, shuttle.flights_completed))

a = list(range(0,5))

a

a.pop()

a

a.pop()

a

a.pop(0)

a

a

a.append(3)
a

a

a = a.append(4)

a

a = list(range(0,5))
a

a.append(5)
a

a.pop()

a

a.extend([7, 8])
a

graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

# goal: visit all nodes, depth first
def dfs(graph, start):
    visited, queue = [], [start]
    while queue:
        vertex = queue.pop()  # <--- popping off the left (.pop(0)) or right (.pop()) changes the behavior between breadth and depth, respectively.
        print("current: ", vertex)
        print("queue: ", queue)
        if vertex not in visited:
            visited.append(vertex)
            print("visited: ", visited)
            queue.extend(graph[vertex] - set(visited))
            print("queue:", queue)
            print(" ")
    return visited

dfs(graph,'A')

# goal: visit all nodes, breadth first
def bfs(graph, start):
    visited, queue = [], [start]
    while queue:
        vertex = queue.pop(0)   # <--- popping off the left (.pop(0)) or right (.pop()) changes the behavior between breadth and depth, respectively.
        print("current: ", vertex)
        print("queue: ", queue)
        if vertex not in visited:
            visited.append(vertex)
            print("visited: ", visited)
            queue.extend(graph[vertex] - set(visited))
            print("queue:", queue)
            print(" ")
    return visited

bfs(graph,'A')