• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 21st, 2020 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import sys
2.
3. # this is a recursive solution that creates n stacks for square_sums(n), raise the ceiling
4. sys.setrecursionlimit(10**6)
5.
6. def square_sums(n):
7.     return findHamiltonianPath(getSquareSumsGraph(n))
8.
9. # generate undirected graph of numbers in a range
10. # connect all vertices v1 and v2 that sum to a perfect square, where sqrt(v1 + v2) = an integer
11. # example: given 6 and 10, sqrt(6 + 10) = 4, therefore connect vertex(6) to vertex(10)
12. def getSquareSumsGraph(n):
13.     squares = {x for x in range(4, 2 * n) if (x ** (1 / 2)).is_integer()}  # generate perfect squares in range 2n
14.     graph = {}  # initialize an empty dictionary
15.
16.     for vertex in range(1, n + 1):  # iterate the range 1 -> n, each is a vertex (v1)
17.         subVertices = []  # this empty array will represent the vertices connected to vertex
18.         for square in squares:  # iterate the pre-calculated squares
19.             candidate = square - vertex  # since v1 + v2 (candidate) = square; v2 = square - v1
20.             if 0 < candidate <= n and candidate != vertex:  # confirm that candidate exists in the range and != v1
21.                 subVertices.append(candidate)  # keep candidate (v2)
22.         graph[vertex] = subVertices  # all vertices connected to vertex have been collected, store them in the graph
23.
24.     return graph
25.
26.
27. # return the first hamiltonian path found in the graph
28. # if no path found, return False
29. def findHamiltonianPath(graph):
30.     graphLength = len(graph)  # store the graph length for optimization
31.     subGraph = graph.copy()  # copy the graph. subGraph will be used to add and remove connections as we iterate
32.     path = []  # path will store our final result
33.
34.     # recursive child function handles searching for the path
35.     def search(options):
36.         if len(path) == graphLength:  # if path and graph are the same length, Hamiltonian Path has been found
37.             return path  # return the Hamiltonian Path
38.         options = sorted(options, key=lambda option: len(graph[option]))  # sort by shortest subVertices - optimization
39.         for option in options:  # iterate all the options. we are starting with the vertices that have the least options
40.             path.append(option)  # add the option to the path
41.             for vertex in graph[option]:  # now that option is in the path, remove it from connected subVertices
42.                 subGraph[vertex].remove(option)
43.             if search(subGraph[option]):  # recurse from the next vertex of position option
44.                 return path  # a member of the stack has found a path, return the path
45.             path.pop()  # path was not found with that option, remove it from the path
46.             for vertex in graph[option]:  # put the option back in all the subVertices it should be connected to
47.                 subGraph[vertex].append(option)
48.         return False  # no path was found, return False
49.
50.     return search([*range(1, graphLength + 1)])  # seed the search with the full range of options
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top