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. OK, I Understand
Top