-
-
Save maxdemarzi/6fc2920296af7684cf678f386d0aba4c to your computer and use it in GitHub Desktop.
Loopy Lattice
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def lattice_size = 20 // means we have a 20 by 20 matrix. This is the number of relationships per side. | |
| def number_of_nodes = (lattice_size + 1) * (lattice_size + 1) // is equal to (20 + 1) * (20 + 1) = 441. We need to create 441 nodes in the graph | |
| def node = range[1, number_of_nodes, 1] // so let's go ahead and create 441 Vertices from 1 to 441 | |
| // We need a total of 840 edges. | |
| // There are 4 corners, each with a degree of 2, so 4 nodes x 2 degrees = 8 | |
| // There are 4 sides, each with 19 nodes (without the corners) having a degree of 3, so (19 nodes x 4 rows = 76 nodes) and 76 nodes x 3 degrees = 228 | |
| // There are 19 rows of 19 nodes each with a degree of 4, so 19 nodes x 19 rows = 361 nodes x 4 = 1444 | |
| // If we add them up, we have 8 + 228 + 1444 = 1680 total degrees. And since each edge connects 2 nodes, we divide by 2 and get 840 edges. | |
| // The node to the right is itself + 1. Node 8 connect to Node 9 and so on as long as we are not on the right side wall, | |
| // which we are if we have a zero remainder from modulo[right, n + 1] . | |
| // For example 9 % 21 = 9. We're good. But 42 % 21 = 0, which we don't want | |
| def edge(node_number, right_node) = node(node_number) and right_node = | |
| node_number + 1 and modulo[node_number, lattice_size + 1] > 0 | |
| // Same idea for down. All the nodes except the bottom row have a down relationship. | |
| // For example node 8 connects to (8 + 20 + 1) = node 29. But node 434 can't connect down since it is greater than 441. | |
| def edge(node_number, down_node) = node(node_number) and down_node = | |
| node_number + lattice_size + 1 and down_node <= number_of_nodes | |
| // from the source, there is `c=1` path of length `k=0` to itself | |
| def number_of_paths_of_length(node_number, path_length, path_count) = node_number=1, path_length=0, path_count=1 | |
| // the number of paths of length `path_length` from the source to `node_number` | |
| // is the sum over `other_node` of the number of paths to `other_node` of length `path_length-1`, | |
| // where `other_node --> node_number` is an edge | |
| def number_of_paths_of_length[node_number, path_length] = | |
| sum[other_node, paths_of_length : paths_of_length = | |
| number_of_paths_of_length[other_node, path_length - 1] and edge(other_node, node_number)] | |
| // the output is the total number of paths of length (2 * lattice_size), ending at the last node (441) | |
| def output = number_of_paths_of_length[number_of_nodes, 2 * lattice_size] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def lattice_size = 20 | |
| def number_of_nodes = (lattice_size + 1) * (lattice_size + 1) | |
| def node = range[1, number_of_nodes, 1] | |
| def edge(node_number, right_node) = node(node_number) and right_node = | |
| node_number + 1 and modulo[node_number, lattice_size + 1] > 0 | |
| def edge(node_number, down_node) = node(node_number) and down_node = | |
| node_number + lattice_size + 1 and down_node <= number_of_nodes | |
| def number_of_paths_of_length(node_number, path_length, path_count) = | |
| node_number=1, path_length=0, path_count=1 | |
| def number_of_paths_of_length[node_number, path_length] = | |
| sum[other_node, paths_of_length : paths_of_length = | |
| number_of_paths_of_length[other_node, path_length - 1] and edge(other_node, node_number)] | |
| def output = number_of_paths_of_length[number_of_nodes, 2 * lattice_size] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment