<jupyter_start><jupyter_text>HackerRank Questions - Graph Traversal- categories: [hacker-rank] I recently did a few hacker rank questions. No promises that these are ideal solutions, but this is my work below.  Problems<jupyter_code>import big_o
import random
from typing import List, Tuple, Dict, Optional<jupyter_output><empty_output><jupyter_text>Q1Given the number of rows and columns for a grid, find the number of different paths when you can only move down or right assuming you start at the top left and finish at the bottom right.**Example:** (7, 3) -> 28; (3,3) -> 6<jupyter_code>def calc_matrix_paths(rows:int, columns:Optional[int]=None) -> int:
    if columns is None: columns = rows
    first_row, first_column = 0, 0
    count_matrix = [[0 for column in range(columns)] for row in range(rows)] 
    
    # r
    for row in range(rows): 
        count_matrix[row][first_column] = 1
    
    # c
    for column in range(columns): 
        count_matrix[first_row][column] = 1 
    
    # r*c
    for row in range(1, rows): 
        for column in range(1, columns):  
            count_matrix[row][column] = count_matrix[row-1][column] + count_matrix[row][column-1] 
            
    return count_matrix[rows-1][columns-1]   

cases = [
    (3, 3), # square matrix
    (7, 3), # non square matrix
]   
    
for rows, columns in cases:
    print(f"rows: {rows} | columns: {columns}")
    result = calc_matrix_paths(rows, columns)
    print(f"number of paths: {result}")
big_o.complexities.ALL_CLASSES
gen = lambda n: n
best, others = big_o.big_o(calc_matrix_paths, gen, min_n=2, max_n=5_000, n_measures=10, n_repeats=2)
print(f"predicted: {best}")
print()
for class_, residual in sorted(others.items(), key=lambda t: t[1], reverse=False):
    print(f"{class_} | {residual}")<jupyter_output>predicted: Exponential: time = -3.2 * 0.002^n (sec)

Exponential: time = -3.2 * 0.002^n (sec) | 9.055977664509317
Polynomial: time = -7.5 * x^1.3 (sec) | 22.531114726371193
Cubic: time = -49 + 4.3E-09*n^3 (sec) | 56631.68144191306
Quadratic: time = -72 + 2E-05*n^2 (sec) | 101322.81044136792
Linearithmic: time = -1.1E+02 + 0.01*n*log(n) (sec) | 165159.6456644176
Linear: time = -1.1E+02 + 0.086*n (sec) | 176698.92796259583
Logarithmic: time = -1E+02 + 29*log(n) (sec) | 324034.55046488193
Constant: time = 1E+02 (sec) | 364452.09251446975<jupyter_text>I wonder if the looping is that bad in python... Unless I'm missing something it looks like O(r*c) so should be polynomial time  Q2Given an r x c grid, print all cells in spiral order**Example:**[[1,2,3],[4,5,6],[7,8,9]] -> 1,2,3,6,9,8,7,4,5<jupyter_code>def get_spiral_order(inp_matrix:List[List[int]]) -> List[int]:
    start_row = 0
    start_col = 0
    end_row = len(inp_matrix)
    end_col = len(inp_matrix[0])
    result = []

    while end_row > start_row and end_col > start_col:

        for item in inp_matrix[start_row][start_col: end_col]:
            result.append(item)

        for row in range(start_row+1, end_row):
            result.append(inp_matrix[row][end_col-1])
            
        for col in reversed(list(range(start_col, end_col-1))):
            result.append(inp_matrix[end_row-1][col])
            
        for i in reversed(list(range(start_row+1, end_row-1))):
            result.append(inp_matrix[i][start_col])
        
        start_col += 1
        start_row += 1
        end_col -= 1
        end_row -= 1
            
    return result
        
cases = [
    [[1,2,3],[4,5,6],[7,8,9]],
    [[1,2,3,4,5],[6,7,8,9,10],[11,12,13,14,15],[16,17,18,19,20]],
]

for case in cases:
    print(f"input matrix: {case}")
    spiral_order = get_spiral_order(case)
    print(f"spiral order: {spiral_order}")<jupyter_output>input matrix: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
spiral order: [1, 2, 3, 6, 9, 8, 7, 4, 5]
input matrix: [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20]]
spiral order: [1, 2, 3, 4, 5, 10, 15, 20, 19, 18, 17, 16, 11, 6, 7, 8, 9, 14, 13, 12]<jupyter_text>Q3**Scheduling Problem**You are tasked with creating an algorithm to determine the execution order of a set of tasks.  This algorithm will beprovided with a list of task labels and a list of task dependencies.  Your algorithm should determine a valid executionorder of the provided tasks.  If there is no valid execution order your algorithm should return None.**Example 1:**labels = ['a', 'b', 'c', 'd', 'e']where each element in "labels" represents a task labeldependencies = [('b', 'a'), ('c', 'a'), ('d', 'c')]where each element tuple represents a task dependency in which the first element depends on the secondi.e. 'b' depends on 'a', 'c' depends on 'a', and 'd' depends on 'c'In this case a valid execution order would be ['a', 'b', 'c', 'd']another valid execution order could be ['a', 'c', 'b', 'd']**Example 2:**labels = ['a', 'b']dependencies = [('b', 'a'), ('a', 'b')]In this case there is no valid execution order so your algorithm should return None<jupyter_code>from collections import defaultdict, deque

def make_dependency_graph(labels: List[str], dependencies: List[Tuple[str]]) -> Dict[str, List[str]]:
    graph = {}
    for l in labels:
        graph[l] = []
    for k, v in dependencies:
        deps = graph[k]
        deps.append(v)
    
    return graph


def get_execution_plan(nodes: List[str], graph: Dict[str, List[str]]) -> Optional[List[str]]:   
    to_visit, visited, checked = deque(labels), [], defaultdict(int)
    while to_visit:
        cur_place = to_visit.pop()
        checked[cur_place] += 1
        for dep_place in graph.get(cur_place): # dependencies
            if dep_place not in visited: 
                to_visit.append(cur_place)
                break
        else:
            visited.append(cur_place)
        if checked[cur_place] > 2:
            return None
            
    return visited
    
            
for labels, dependencies in [
    [['a', 'b', 'c', 'd', 'e'],
     [('a', 'e'), ('a', 'b'), ('b', 'c'), ('c', 'd')]],
    [['a', 'b'],
    [('b', 'a'), ('a', 'b')]],]:
    graph = make_dependency_graph(labels, dependencies)
    print(f"Dependency Graph: {graph}")

    visited = get_execution_plan(labels, graph) 
    print(f"Suggested Execution Plan: {visited}")<jupyter_output>Dependency Graph: {'a': ['e', 'b'], 'b': ['c'], 'c': ['d'], 'd': [], 'e': []}
Suggested Execution Plan: ['e', 'd', 'c', 'b', 'a']
Dependency Graph: {'a': ['b'], 'b': ['a']}
Suggested Execution Plan: None
{'fraction_non_alphanumeric': 0.15669205658324264, 'fraction_numerical': 0.05813772734338567, 'mean_word_length': 3.418956043956044, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '455248', 'license': 'Apache-2.0', 'n_tokens_mistral': 2523, 'n_tokens_neox': 2274, 'n_words': 680, 'path': '_notebooks/2021-02-13-hackerrank-questions.ipynb', 'repo_name': 'kslader8/kslader8-thoughts', 'size': '6433'}