6. Largest Color Value in a Directed Graph (Topological Sort + DP)

Notes: This problem combines topological sort with dynamic programming. Since it's a directed graph, cycles are an issue. If a cycle exists, return -1. Otherwise, use Kahn's algorithm (BFS-based topological sort). For each node, maintain a DP array $dp[node][color]$ representing the maximum count of that color on any path ending at $node$. When processing a node, update its neighbors' DP states.

import collections

class Solution:
    def largestPathValue(self, colors: str, edges: list[list[int]]) -> int:
        n = len(colors)
        adj = collections.defaultdict(list)
        in_degree = [0] * n
        
        for u, v in edges:
            adj[u].append(v)
            in_degree[v] += 1
            
        # dp[node][color_idx] stores the maximum count of color_idx
        # on any path ending at 'node'.
        # color_idx: 'a'->0, 'b'->1, ..., 'z'->25
        dp = [[0] * 26 for _ in range(n)]
        
        q = collections.deque()
        for i in range(n):
            if in_degree[i] == 0:
                q.append(i)
                dp[i][ord(colors[i]) - ord('a')] = 1
        
        nodes_visited = 0
        max_color_value = 0
        
        while q:
            u = q.popleft()
            nodes_visited += 1
            
            max_color_value = max(max_color_value, max(dp[u]))
            
            for v in adj[u]:
                # Update dp states for neighbor v
                for color_idx in range(26):
                    # For neighbor v, the count of `color_idx` on a path ending at v
                    # coming from u, is the count on path ending at u, plus 1 if v itself is that color.
                    new_val = dp[u][color_idx]
                    if color_idx == (ord(colors[v]) - ord('a')):
                        new_val += 1
                    
                    dp[v][color_idx] = max(dp[v][color_idx], new_val)
                
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    q.append(v)
                    
        if nodes_visited != n:
            return -1 # Cycle detected
        
        return max_color_value

7. Sliding Puzzle (BFS)

Notes: This is a classic shortest path problem on a state graph. Each state of the puzzle (arrangement of numbers) is a node. An edge exists between two states if one can be transformed into the other by sliding the '0' tile. Use BFS to find the minimum number of moves. The state can be represented as a tuple or string to be hashable for visited set.

import collections

class Solution:
    def slidingPuzzle(self, board: list[list[int]]) -> int:
        target_state = (1, 2, 3, 4, 5, 0)
        
        # Convert initial board to a tuple for hashability
        initial_state = tuple(board[0] + board[1])
        
        # If already solved
        if initial_state == target_state:
            return 0
        
        # BFS queue: (current_state_tuple, zero_pos_index, moves)
        # zero_pos_index: 0-5 representing the position of '0'
        # The 2D board can be flattened to a 1D array/list:
        # 0 1 2
        # 3 4 5
        
        # Possible moves for '0' at each position
        # indices: 0, 1, 2, 3, 4, 5
        # 0 <-> 1, 3
        # 1 <-> 0, 2, 4
        # 2 <-> 1, 5
        # 3 <-> 0, 4
        # 4 <-> 1, 3, 5
        # 5 <-> 2, 4
        
        moves_map = {
            0: [1, 3],
            1: [0, 2, 4],
            2: [1, 5],
            3: [0, 4],
            4: [1, 3, 5],
            5: [2, 4]
        }
        
        q = collections.deque()
        visited = set()
        
        # Find initial zero position
        zero_pos = initial_state.index(0)
        
        q.append((initial_state, zero_pos, 0))
        visited.add(initial_state)
        
        while q:
            current_state, z_pos, moves = q.popleft()
            
            for next_z_pos in moves_map[z_pos]: