toposort

207.py

from __future__ import annotations

from collections import defaultdict, deque
from dataclasses import dataclass
from typing import Any, Dict, List, Optional, Set  # noqa

import ipdb  # type: ignore


class Node:
    def __init__(self):
        self.nexts: List[int] = []
        self.incoming_edge_count: int = 0

    def add_next(self, next: int):
        self.nexts.append(next)


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph: defaultdict[int, Node] = defaultdict(Node)
        topo_list: List[Node] = []
        for next_course, prereq in prerequisites:
            graph[prereq].add_next(next_course)
            graph[next_course].incoming_edge_count += 1

        q: deque[int] = deque()
        for course in graph.keys():
            if graph[course].incoming_edge_count == 0:
                q.append(course)

        while len(q) > 0:
            cur_course = q.pop()
            topo_list.append(graph[cur_course])
            for next_course in graph[cur_course].nexts:
                graph[next_course].incoming_edge_count -= 1
                if graph[next_course].incoming_edge_count == 0:
                    q.append(next_course)
        return len(topo_list) == len(graph)

    def canFinishDFS(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if len(prerequisites) == 0:
            return True
        courses = {i: Node(val=i) for i in range(0, numCourses)}
        for course, prereq in prerequisites:
            courses[prereq].add_next(courses[course])

        taken: Set[int] = set()
        checked: Set[int] = set()

        def _has_cycles(node: Node) -> bool:
            if node.val in checked:
                return False

            if node.val in taken:
                return True

            taken.add(node.val)
            val = False
            for next in node.nexts:
                val = _has_cycles(next)
                if val:
                    break
            checked.add(node.val)
            taken.remove(node.val)
            return val

        for node in courses.values():
            if _has_cycles(node):
                return False

        return True


@dataclass
class TestCase:
    input: List[List[int]]
    expected_output: bool
    numCourses: int


def main():
    testCases = [
        TestCase(numCourses=2, input=[[1, 0]], expected_output=True),
        TestCase(numCourses=2, input=[[1, 0], [0, 1]], expected_output=False),
        TestCase(numCourses=5, input=[[1, 4], [2, 4], [3, 1], [3, 2]], expected_output=True),
        TestCase(numCourses=5, input=[[1, 4], [2, 4], [3, 1], [3, 2]], expected_output=True),
        TestCase(
            numCourses=100,
            input=[
                [1, 0],
                [2, 0],
                [2, 1],
                [3, 1],
                [3, 2],
                [4, 2],
                [4, 3],
                [5, 3],
                [5, 4],
                [6, 4],
                [6, 5],
                [7, 5],
                [7, 6],
                [8, 6],
                [8, 7],
                [9, 7],
                [9, 8],
                [10, 8],
                [10, 9],
                [11, 9],
                [11, 10],
                [12, 10],
                [12, 11],
                [13, 11],
                [13, 12],
                [14, 12],
                [14, 13],
                [15, 13],
                [15, 14],
                [16, 14],
                [16, 15],
                [17, 15],
                [17, 16],
                [18, 16],
                [18, 17],
                [19, 17],
                [19, 18],
                [20, 18],
                [20, 19],
                [21, 19],
                [21, 20],
                [22, 20],
                [22, 21],
                [23, 21],
                [23, 22],
                [24, 22],
                [24, 23],
                [25, 23],
                [25, 24],
                [26, 24],
                [26, 25],
                [27, 25],
                [27, 26],
                [28, 26],
                [28, 27],
                [29, 27],
                [29, 28],
                [30, 28],
                [30, 29],
                [31, 29],
                [31, 30],
                [32, 30],
                [32, 31],
                [33, 31],
                [33, 32],
                [34, 32],
                [34, 33],
                [35, 33],
                [35, 34],
                [36, 34],
                [36, 35],
                [37, 35],
                [37, 36],
                [38, 36],
                [38, 37],
                [39, 37],
                [39, 38],
                [40, 38],
                [40, 39],
                [41, 39],
                [41, 40],
                [42, 40],
                [42, 41],
                [43, 41],
                [43, 42],
                [44, 42],
                [44, 43],
                [45, 43],
                [45, 44],
                [46, 44],
                [46, 45],
                [47, 45],
                [47, 46],
                [48, 46],
                [48, 47],
                [49, 47],
                [49, 48],
                [50, 48],
                [50, 49],
                [51, 49],
                [51, 50],
                [52, 50],
                [52, 51],
                [53, 51],
                [53, 52],
                [54, 52],
                [54, 53],
                [55, 53],
                [55, 54],
                [56, 54],
                [56, 55],
                [57, 55],
                [57, 56],
                [58, 56],
                [58, 57],
                [59, 57],
                [59, 58],
                [60, 58],
                [60, 59],
                [61, 59],
                [61, 60],
                [62, 60],
                [62, 61],
                [63, 61],
                [63, 62],
                [64, 62],
                [64, 63],
                [65, 63],
                [65, 64],
                [66, 64],
                [66, 65],
                [67, 65],
                [67, 66],
                [68, 66],
                [68, 67],
                [69, 67],
                [69, 68],
                [70, 68],
                [70, 69],
                [71, 69],
                [71, 70],
                [72, 70],
                [72, 71],
                [73, 71],
                [73, 72],
                [74, 72],
                [74, 73],
                [75, 73],
                [75, 74],
                [76, 74],
                [76, 75],
                [77, 75],
                [77, 76],
                [78, 76],
                [78, 77],
                [79, 77],
                [79, 78],
                [80, 78],
                [80, 79],
                [81, 79],
                [81, 80],
                [82, 80],
                [82, 81],
                [83, 81],
                [83, 82],
                [84, 82],
                [84, 83],
                [85, 83],
                [85, 84],
                [86, 84],
                [86, 85],
                [87, 85],
                [87, 86],
                [88, 86],
                [88, 87],
                [89, 87],
                [89, 88],
                [90, 88],
                [90, 89],
                [91, 89],
                [91, 90],
                [92, 90],
                [92, 91],
                [93, 91],
                [93, 92],
                [94, 92],
                [94, 93],
                [95, 93],
                [95, 94],
                [96, 94],
                [96, 95],
                [97, 95],
                [97, 96],
                [98, 96],
                [98, 97],
                [99, 97],
            ],
            expected_output=True,
        ),
    ]
    s = Solution()
    for tc in testCases:
        actual = s.canFinish(tc.numCourses, tc.input)
        assert actual == tc.expected_output, f"\nExpected\n\t{tc.expected_output}\nGot\n\t{actual}\nFrom\n\t{tc.input}"

    print("All passed!")


"""
Constraints:

Ideas:

Test Cases:
    [1,4] ,[2,4] [3,1], [3,2]


"""

alien.py

from typing import List, Dict, Set
from heapq import heappop, heappush


def build_graph(words):
    nodes = {}
    for w in words:
        for c in w:
            if c not in nodes:
                nodes[c] = list()

    prev_word = words[0]
    for i in range(1, len(words)):
        cur_word = words[i]
        j = 0
        while j < len(cur_word) and j < len(prev_word):
            if prev_word[j] != cur_word[j]:
                if not cur_word[j] in nodes[prev_word[j]]:
                    nodes[prev_word[j]].append(cur_word[j])
                break
            j += 1
        prev_word = cur_word
    return nodes


def build_counts(graph: Dict[str, Set[str]]) -> Dict[str, int]:
    counts = {n: 0 for n in graph}
    for letter, children in graph.items():
        for c in children:
            counts[c] += 1
    return counts


def topo_sort(graph: Dict[str, Set[str]]) -> List[str]:
    counts = build_counts(graph)
    q = []
    for letter, count in counts.items():
        if count == 0:
            heappush(q, letter)

    res = []
    while len(q) > 0:
        letter = heappop(q)
        res.append(letter)
        for child in graph[letter]:
            counts[child] -= 1
            if counts[child] == 0:
                heappush(q, child)
    return res if len(res) == len(graph) else []


def alien_order(words: List[str]) -> str:
    graph = build_graph(words)
    return "".join(topo_sort(graph))


from dataclasses import dataclass


@dataclass
class TestCase:
    input: List[str]
    expected_output: str


if __name__ == "__main__":
    test_cases = [
        #        TestCase(input=["wrt", "wrf", "er", "ett", "rftt"], expected_output="wertf"),
        TestCase(input=["she", "sell", "seashell", "seashore", "seahorse", "on", "a"], expected_output="lnrsheoa"),
    ]

    for tc in test_cases:
        actual = alien_order(tc.input)
        assert actual == tc.expected_output, f"Expected {tc.expected_output}, got {actual}"