Skip to content

Instantly share code, notes, and snippets.

@hskrasek

hskrasek/train-routes.ipynb

Created November 18, 2025 16:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save hskrasek/f7806a09ccd992a694d7859f02032483 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save hskrasek/f7806a09ccd992a694d7859f02032483 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
train-routes.ipynb
{
"cells" : [ {
"cell_type" : "code",
"id" : "initial_id",
"metadata" : {
"collapsed" : true,
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:15.963115Z",
"start_time" : "2025-11-18T16:19:15.958628Z"
}
},
"source" : [ "from typing import List, Tuple, Dict\n", "\n", "type Matrix[T] = List[List[T]]\n", "\n", "train_schedules = [\n", " ['A', 'B', 'D', 'F'],\n", " ['E', 'C', 'D', 'G']\n", "]\n", "\n", "train_schedules" ],
"outputs" : [ {
"data" : {
"text/plain" : [ "[['A', 'B', 'D', 'F'], ['E', 'C', 'D', 'G']]" ]
},
"execution_count" : 66,
"metadata" : { },
"output_type" : "execute_result"
} ],
"execution_count" : 66
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:15.976500Z",
"start_time" : "2025-11-18T16:19:15.973284Z"
}
},
"cell_type" : "code",
"source" : [ "def create_directed_adjacency_matrix(data_matrix: Matrix[str]) -> Tuple[Matrix[int], Dict[int, str]]:\n", " \"\"\"\n", " Create a directed adjacency matrix from the data matrix, respecting the following\n", " movement rules:\n", "\n", " * You can ALWAYS move right.\n", " * You can ONLY move up or down when the labels match at that column.\n", " * Movement is NOT bidirectional. You can ONLY move right.\n", "\n", " The adjacency matrix encodes these rules as directed edges. Where each edge is a\n", " representation of a possible valid movement.\n", " \"\"\"\n", " rows, cols = len(data_matrix), len(data_matrix[0])\n", " total_nodes = rows * cols\n", "\n", " def pos_to_idx(row: int, col: int) -> int:\n", " return row * cols + col\n", "\n", " labels = {}\n", " for r in range(rows):\n", " for c in range(cols):\n", " labels[pos_to_idx(r, c)] = data_matrix[r][c]\n", "\n", " adjacent = [[0 for _ in range(total_nodes)] for _ in range(total_nodes)]\n", "\n", " for r in range(rows):\n", " for c in range(cols):\n", " current_idx = pos_to_idx(r, c)\n", " current_label = labels[current_idx]\n", "\n", " if c + 1 < cols:\n", " right_idx = pos_to_idx(r, c + 1)\n", " adjacent[current_idx][right_idx] = 1\n", "\n", " for other_row in range(rows):\n", " if other_row != r:\n", " other_label = data_matrix[other_row][c]\n", " if other_label == current_label:\n", " other_idx = pos_to_idx(other_row, c)\n", " adjacent[current_idx][other_idx] = 1\n", "\n", " return adjacent, labels" ],
"id" : "ba9589077a23b8f3",
"outputs" : [ ],
"execution_count" : 67
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:15.987820Z",
"start_time" : "2025-11-18T16:19:15.985814Z"
}
},
"cell_type" : "code",
"source" : [ "def matrix_multiplication(a: Matrix[int], b: Matrix[int]) -> Matrix[int]:\n", " \"\"\"\n", " Dot product of two matrices.\n", " \"\"\"\n", " rows_a = len(a)\n", " cols_a = len(a[0])\n", " cols_b = len(b[0])\n", "\n", " result = [[0 for _ in range(cols_b)] for _ in range(rows_a)]\n", "\n", " for i in range(rows_a):\n", " for j in range(cols_b):\n", " for k in range(cols_a):\n", " result[i][j] += a[i][k] * b[k][j]\n", "\n", " return result" ],
"id" : "793c6b0b89dc8e6f",
"outputs" : [ ],
"execution_count" : 68
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:15.991851Z",
"start_time" : "2025-11-18T16:19:15.989844Z"
}
},
"cell_type" : "code",
"source" : [ "def compute_reachability_matrix(adj_matrix: Matrix[int]) -> Matrix[int]:\n", " \"\"\"\n", " Compute the transitive closure of the adjacency matrix.\n", "\n", " Each power of the adjacency matrix reveals paths of increasing length.\n", " \"\"\"\n", " n = len(adj_matrix)\n", "\n", " current_power = [row[:] for row in adj_matrix]\n", " reachable = [row[:] for row in adj_matrix]\n", "\n", " for power in range(2, n):\n", " current_power = matrix_multiplication(current_power, adj_matrix)\n", " for i in range(n):\n", " for j in range(n):\n", " if current_power[i][j] > 0:\n", " reachable[i][j] = 1\n", "\n", " return reachable" ],
"id" : "ab85543251b26a82",
"outputs" : [ ],
"execution_count" : 69
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:15.995590Z",
"start_time" : "2025-11-18T16:19:15.993572Z"
}
},
"cell_type" : "code",
"source" : [ "def can_reach(start: str, end: str, adj_matrix: Matrix[int], labels: Dict[int, str]) -> bool:\n", " \"\"\"\n", " Determine if the end can be reached from the start.\n", " \"\"\"\n", " start_idx = None\n", " end_idx = None\n", "\n", " for idx, label in labels.items():\n", " if label == start and start_idx is None:\n", " start_idx = idx\n", " if label == end and end_idx is None:\n", " end_idx = idx\n", "\n", " if start_idx is None or end_idx is None:\n", " return False\n", "\n", " reachable = compute_reachability_matrix(adj_matrix)\n", "\n", " return reachable[start_idx][end_idx] > 0" ],
"id" : "308145c1b0f260be",
"outputs" : [ ],
"execution_count" : 70
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:15.998934Z",
"start_time" : "2025-11-18T16:19:15.997503Z"
}
},
"cell_type" : "code",
"source" : [ "def path_exists(schedule: Matrix[str], start: str, end: str) -> bool:\n", " \"\"\"\n", " Does a path exist in the schedule from the starting station to the ending station?\n", " \"\"\"\n", " adj_matrix, labels = create_directed_adjacency_matrix(schedule)\n", "\n", " return can_reach(start, end, adj_matrix, labels)" ],
"id" : "85160c2d727cf468",
"outputs" : [ ],
"execution_count" : 71
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:16.003217Z",
"start_time" : "2025-11-18T16:19:16.001366Z"
}
},
"cell_type" : "code",
"source" : "path_exists(train_schedules, 'A', 'F')",
"id" : "a80b23584d6cbe78",
"outputs" : [ {
"data" : {
"text/plain" : [ "True" ]
},
"execution_count" : 72,
"metadata" : { },
"output_type" : "execute_result"
} ],
"execution_count" : 72
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:16.011384Z",
"start_time" : "2025-11-18T16:19:16.009382Z"
}
},
"cell_type" : "code",
"source" : "path_exists(train_schedules, 'A', 'G')",
"id" : "7c4d2c8ac998008e",
"outputs" : [ {
"data" : {
"text/plain" : [ "True" ]
},
"execution_count" : 73,
"metadata" : { },
"output_type" : "execute_result"
} ],
"execution_count" : 73
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:16.018848Z",
"start_time" : "2025-11-18T16:19:16.016907Z"
}
},
"cell_type" : "code",
"source" : "path_exists(train_schedules, 'E', 'F')",
"id" : "c64fb886435a814a",
"outputs" : [ {
"data" : {
"text/plain" : [ "True" ]
},
"execution_count" : 74,
"metadata" : { },
"output_type" : "execute_result"
} ],
"execution_count" : 74
}, {
"metadata" : {
"ExecuteTime" : {
"end_time" : "2025-11-18T16:19:16.026016Z",
"start_time" : "2025-11-18T16:19:16.024073Z"
}
},
"cell_type" : "code",
"source" : "path_exists(train_schedules, 'F', 'A')",
"id" : "36a8eba951de6bd5",
"outputs" : [ {
"data" : {
"text/plain" : [ "False" ]
},
"execution_count" : 75,
"metadata" : { },
"output_type" : "execute_result"
} ],
"execution_count" : 75
} ],
"metadata" : {
"kernelspec" : {
"display_name" : "Python 3",
"language" : "python",
"name" : "python3"
},
"language_info" : {
"codemirror_mode" : {
"name" : "ipython",
"version" : 2
},
"file_extension" : ".py",
"mimetype" : "text/x-python",
"name" : "python",
"nbconvert_exporter" : "python",
"pygments_lexer" : "ipython2",
"version" : "2.7.6"
}
},
"nbformat" : 4,
"nbformat_minor" : 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment