# List and Array
# List and Array are both dynamic/auto-resizable.
# List holds mixed types and array static/single type for performance.
from array import array
robotIndices = array("i", [0,1,2,3])
len(arr) # returns 5
#cant do array of strings, use lists or sets for that
robotsList = ["R2", "HAL", "Bender", "Johnny5"]
benderCharArray = list("Bender") # create list of chars
arr = array("u", benderCharArray)
someList = list()
someList.append()
someList.pop() # can also specfix pop(index)
del someList[len(someList)-1] # deletes last element in list
someList[:-1] # slice; O(n) copy minus last element
# note also SortedList from sortedcontainers; balanced b-tree

# HashSet - unordered collection of unique elements.
# Resizes on collisions and constant time addition and retrieval.
robots = set() # optional since python is duck typed
robots = set(robotsList) # equivalent to below
robots = {"R2", "HAL", "Bender", "Johnny5"}
robots.add("AgentSmith")
robots.remove("AgentSmith")
robots.update({"HAL"}) #add if not exist otherwise no-op

# Hash table / HashMap / dictionary and sets
# Constant time addition and retrieval.
robotStatuses = dict() # again optional.
robotStatuses = {"R2": "On", "HAL": "Unknown", "Bender": "On", "Johnny5": "Off"}
robotStatuses["R2"] # returns "On" 
# you can also use get("R2")
robotStatuses.keys() # returns {"R2","HAL","Bender","Johnny5"}
robots = set(robotStatuses.keys()) # cast either to set if needed
robotStatuses.values() # returns {"On","Unknown","On","Off"}
robotStatuses["HAL"] = "On" # yikes
del robotStatuses["HAL"] # Delete an entry. 
# You can use pop on dictionaries but I avoid for DS&Algo purity. 
# Yes Python is amorphous.
from sortedcontainers import SortedDict # equivalent of TreeMap
from sortedcontainers import SortedSet # equivalent of TreeSet
for key, value in robotStatuses.items(): # note you can iterate with tuple
letterCounts = Counter("R2") #from collections import Counter, gives {"R":1, "2":1}

# Queue - from collections import deque.
# deque supports both FIFO queue and LIFO stack with O(1) append/pop.
# list also has append and pop but keep in mind is O(n).
robotsToUpgrade = deque(["R2","Johnny5"]) # optional init values
robotsToUpgrade.append("Bender") # adds to the right/end
robotsToUpgrade.pop() # returns Bender, LIFO stack by default
robotsToUpgrade.popleft() # returns R2, works as FIFO
robotsToUpgrade.appendleft("R2") # adds to the left/beginning
# there is also queue.Queue and LifoQueue with less operations.
# they use put/get but I usually avoid multi-threading in python.

# Common string manipulations.
introduction = "Hello World"
introduction.replace("World", "Neo") # doesn't mutate original
"Neo" in introduction # returns False
# use the 'in' operator or alternatively count
introduction.count("Neo") # returns 0
# there are other approaches such as .___contains__ but less readable
introduction.lower() or str.lower(introduction) # to lowercase
introduction.startswith("Hello") # returns True
introduction.endswith("Neo") # returns False
introduction.split(" ") # returns ["Hello", "World"]
print(str1 + str(int1) + str2) # concatenate strings with +

# String formatting.
# I avoid mix and matching positionals.
"{greeting} {noun}".format(greeting="Hello", noun="World")
"{0} {1}".format("Hello", "World")
f"{robots}" # f strings in python>3.6.

# Equality comparison
"hello world" == "Hello World" # False since case sensitive
"hello world" != "Hello World" # expectedly returns True
<=, >=, <, > # for strings these operators are lexicographical/alphabetical
"robots" < "terminators" # true because robots come before terminators, alphabetically...
7 > 6 # noncontroversially true
return X if (condition) #e.g. 1==1
x = 1 if (condition) else 2 # similar to ternary in java/c#

# Functions/Methods, Conditional logic and null checking
# Type declarations on params and return type is optional.
# The Types are useful for catching errors as your codebase grows.
# Check your interviewer preference but likely your choice.
def removeBadRobots(robots: set[str]) -> set[str]:
    if robots is None or len(robots) == 0:
        print("robots are missing!")
    elif "HAL" in robots:
        print("HAL detected! removing")
        robots.remove("HAL") # note! value mutated!
        return getCoolRobots(robots)
    elif "Johnny5" in robots:
        print("Johnny5 is alive!")
    else:
        print("all good") # python>3.10 also has switch statements
    return robots # for void/no return indicate 'pass'

# Loops
for i in range(5):
    print(i) # prints 0-4
    # note i continues to exist in function context
    # you can also do things like range(len(someList))

j=0
while j < 5:
    print(j) # prints 0-4
    j += 1
    # use break and continue for short circuits

# Common Functions and Shorthand
max(num1, num2) # returns the largest of the two; see also 'min'
var1 = var2 = 0 # initializes two variables with 0
sum
mean # import statistics, but this is also only few lines

# Lambda. Optional. Basically inline functions for simple operations. 
# Cool if you're comfortable with it but optional.
robotIsSentient = lambda robotName: True if robotName in {"R2", "HAL", "Bender", "Johnny5"} else False
robotIsSentient("T-1000") # returns False
sentientRobots = set(filter(robotIsSentient, robots)) # no change since they all match

# List comprehensions. Also optional. 
# Can pair with lambda for more complex filters.
valuesToSquare = [0, 1, 2, 3]
valuesSquared = [val ** 2 for val in valuesToSquare] # 0,1,4,9
positiveValues = [val for val in valuesSquared if val % 2 == 0]
coordinates = [(x, y) for x in range(3) for y in range(3)] # list of tuples
matrix = [[i for i in range(2)] for i in range(2)] # creates [[0,1],[0,1]]
flatMatrix = [val for sublist in matrix for val in sublist] #flatten; basically nested loops

# recursive
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()

    visited.add(node)
    print(node)  # do something with node

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# Ex (adjacency list); you'll encounter these or matrixes
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
}

dfs(graph, 'A') # note many problems start with 'root'

# using stack LIFO (dfs) or queue FIFO
from queue import deque
def bfs_or_dfs_template(root):
    visited = set()
    stack = deque(root)
    while stack:
        node = stack.pop() # use popleft for FIFO queue
        if node not in visited:
            print(node)
            visited.add(node)
            for node in reversed(node.adjacentNodes):
                if node not in visited:
                    stack.append(n)

# dfs of tree
def dfs_tree(node):
    if not node:
        return
    print(node.value)  # do something with node
    for child in node.children:
        dfs_tree(child)  # No need for visited set
   

import heapq

heap = [] # defaults to min heap in python
heapq.heappush(heap, 2) # log(n) insertion
heapq.heappush(heap, 1) # each is log(n) so overall is nlogn
# print(heap) shows 1,2
heapq.heappop(heap) # output 1; smallest/root element

# use negative values to simulate max heap in python
heapq.heappush(heap,-1)
heapq.heappush(heap,-2)
# print(heap) shows -1,-2
# then can negate output, note this breaks if you have neg nums
largest = -heapq.heappop(max_heap)

heapq.heapify(somelist) # Floyd construction is O(n) vs nlogn
# note heapify is faster than individual insertion
# note there is no simple heapify maxheap 
# if you do [-x for x in nums] keep in mind extra O(n)
# or make your own maxheap, or use java

[(a, b) for a in iterable_a for b in iterable_b]

# or more readable

result = []
for a in iterable_a:
    for b in iterable_b:
        result.append((a, b))

def transpose(matrix):
    rows, cols = len(matrix), len(matrix[0])
    transposed = [[0] * rows for x in range(cols)]  # initialize empty matrix

    for i in range(rows):
        for j in range(cols):
            transposed[j][i] = matrix[i][j]  # Swap rows and columns

    return transposed

# Example Matrix
matrix = [
    [1, 2, 3],
    [4, 5, 6]
]

result = transpose(matrix)
for row in result:
    print(row)

"""
output:
[1, 4]
[2, 5]
[3, 6]
"""