title: Finding a hamiltonian path with Javascript. How to improve efficiency?
body: <p>I'm trying to solve this kata:</p>
  
  <blockquote>
    <p>Given an integer N (&lt;1000), return an array of integers 1..N where the sum of each 2 consecutive numbers is a perfect square. If that's not possible, return <code>false</code>. </p>
  </blockquote>
  
  <p>For example, if <code>N=15</code>, the result should be this array: <code>[9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8]</code>. Below <code>N=14</code>, there's no answer, so the function should return <code>false</code>.</p>
  
  <p>I thought 'how hard can this be?' and it's been long days in the rabbit hole. I've been programming for just a few months and don't have a background of CS so I'll write what I understand so far of the problem trying to use the proper concepts but please feel free to tell me if any expression is not correct.</p>
  
  <p>Apparently, the problem is very similar to a known problem in graph theory called <a href="https://en.wikipedia.org/wiki/Travelling_salesman_problem" rel="nofollow noreferrer">TSP</a>. In this case, the vertices are connected if the sum of them is a perfect square. Also, I don't have to look for a cycle, just find one <a href="https://en.wikipedia.org/wiki/Hamiltonian_path_problem#Algorithms" rel="nofollow noreferrer">Hamiltonian Path</a>, not all.</p>
  
  <p>I understand that what I'm using is backtracking. I build an object that represents the graph and then try to find the path recursively. This is how I build the object:</p>
  
  <pre><code>function buildAdjacentsObject (limit) {
    const potentialSquares = getPotentialSquares(limit)
    const adjacents = {}
    for (let i = 0; i &lt; (limit + 1); i++) {
      adjacents[i] = {}
      for (let j = 0; j &lt; potentialSquares.length; j++) {
        if (potentialSquares[j] &gt; i) {
          const dif = potentialSquares[j] - i
          if (dif &lt;= limit) {
            adjacents[i][dif] = 1
          } else {
            break
          }
        }
      }
    }
    return adjacents
  }
  
  function getPotentialSquares (limit) {
    const maxSum = limit * 2 - 1
    let square = 4
    let i = 3
    const potentialSquares = []
    while (square &lt;= maxSum) {
      potentialSquares.push(square)
      square = i * i
      i++
    }
    return potentialSquares
  }
  </code></pre>
  
  <p>At first I was using a hash table with an array of adjacent nodes on each key. But when my algorithm had to delete vertices from the object, it had to look for elements in arrays several times, which took linear time every time. I made the adjacent vertices hashable and that improved my execution time. Then I look for the path with this function:</p>
  
  <pre><code>function findSquarePathInRange (limit) {
    // Build  the graph object
    const adjacents = buildAdjacentsObject(limit)
  
    // Deep copy the object before making any changes
    const adjacentsCopy = JSON.parse(JSON.stringify(adjacents))
  
    // Create empty path
    const solution = []
  
    // Recursively complete the path
    function getSolution (currentCandidates) {
      if (solution.length === limit) {
        return solution
      }
  
      // Sort the candidate vertices to start with the ones with less adjacent vert
      currentCandidates = currentCandidates.sort((a, b) =&gt; {
        return Object.keys(adjacentsCopy[a]).length -
          Object.keys(adjacentsCopy[b]).length
      })
  
      for (const candidate of currentCandidates) {
        // Add the candidate to the path
        solution.push(candidate)
  
        // and delete it from the object
        for (const candidateAdjacent in adjacents[candidate]) {
          delete adjacentsCopy[candidateAdjacent][candidate]
        }
        if (getSolution(Object.keys(adjacentsCopy[candidate]))) {
          return solution
        }
        // If not solution was found, delete the element from the path
        solution.pop()
  
        // and add it back to the object
        for (const candidateAdjacent in adjacents[candidate]) {
          adjacentsCopy[candidateAdjacent][candidate] = 1
        }
      }
      return false
    }
  
    const endSolution = getSolution(
      Array.from(Array(limit).keys()).slice(1)
    )
    // The elements of the path can't be strings
    return (endSolution) ? endSolution.map(x =&gt; parseInt(x, 10)) : false
  }
  </code></pre>
  
  <p>My solution works 'fast' but it's not fast enough. I need to pass more than 200 tests in less than 12 seconds and so far it's only passing 150. Probably both my algorithm and my usage of JS can be improved, so, my questions:</p>
  
  <ol>
  <li><p>Can you see a bottleneck in the code? The sorting step should be the one taking more time but it also gets me to the solution faster. Also, I'm not sure if I'm using the best data structure for this kind of problem. I tried classic looping instead of using <code>for..in</code> and <code>for..of</code> but it didn't change the performance.</p></li>
  <li><p>Do you see any place where I can save previous calculations to look for them later?</p></li>
  </ol>
  
  <p>Regarding the last question, I read that there is a dynamic solution to the problem but everywhere I found one, it looks for minimum distance, number of paths or existence of path, not the path itself. I read this everywhere but I'm unable to apply it:</p>
  
  <blockquote>
    <p>Also, a dynamic programming algorithm of Bellman, Held, and Karp can be used to solve the problem in time O(n2 2n). In this method, one determines, for each set S of vertices and each vertex v in S, whether there is a path that covers exactly the vertices in S and ends at v. For each choice of S and v, a path exists for (S,v) if and only if v has a neighbor w such that a path exists for (S − v,w), which can be looked up from already-computed information in the dynamic program.</p>
  </blockquote>
  
  <p>I just can't get the idea on how to implement that if I'm not looking for all the paths. I found <a href="https://leetcode.com/articles/number-of-squareful-arrays/" rel="nofollow noreferrer">this</a> implementation of a similar problem in python that uses a cache and some binary but again, I could translate it from py but I'm not sure how to apply those concepts to my algorithm.</p>
  
  <p>I'm currently out of ideas so any hint of something to try would be super helpful.</p>
  
  <p><strong>EDIT 1:</strong></p>
  
  <p>After Photon comment, I tried going back to using a hash table for the graph, storing adjacent vertices as arrays. Also added a separate array of bools to keep track of the remaining vertices.</p>
  
  <p>That improved my efficiency a lot. With these changes I avoided the need to convert object keys to arrays all the time, no need to copy the graph object as it was not going to be modified and no need to loop after adding one node to the path. The bad thing is that then I needed to check that separate object when sorting, to check which adjacent vertices were still available. Also, I had to filter the arrays before passing them to the next recursion. </p>
  
  <p>Yosef approach from the first answer of using an array to store the adjacent vertices and access them by index prove even more efficient. My code so far (no changes to the square finding function):</p>
  
  <pre><code>function square_sums_row (limit) {
    const adjacents = buildAdjacentsObject(limit)
    const adjacentsCopy = JSON.parse(JSON.stringify(adjacents))
    const solution = []
  
    function getSolution (currentCandidates) {
      if (solution.length === limit) {
        return solution
      }
  
      currentCandidates = currentCandidates.sort((a, b) =&gt; {
        return adjacentsCopy[a].length - adjacentsCopy[b].length
      })
      for (const candidate of currentCandidates) {
        solution.push(candidate)
        for (const candidateAdjacent of adjacents[candidate]) {
          adjacentsCopy[candidateAdjacent] = adjacentsCopy[candidateAdjacent]
            .filter(t =&gt; t !== candidate)
        }
        if (getSolution(adjacentsCopy[candidate])) {
          return solution
        }
        solution.pop()
        for (const candidateAdjacent of adjacents[candidate]) {
          adjacentsCopy[candidateAdjacent].push(candidate)
        }
      }
      return false
    }
    return getSolution(Array.from(Array(limit + 1).keys()).slice(1))
  }
  
  function buildAdjacentsObject (limit) {
    const potentialSquares = getPotentialSquares(limit)
    const squaresLength = potentialSquares.length
    const adjacents = []
    for (let i = 1; i &lt; (limit + 1); i++) {
      adjacents[i] = []
      for (let j = 0; j &lt; squaresLength; j++) {
        if (potentialSquares[j] &gt; i) {
          const dif = potentialSquares[j] - i
          if (dif &lt;= limit) {
            adjacents[i].push(dif)
          } else {
            break
          }
        }
      }
    }
    return adjacents
  }
  </code></pre>
  
  <p><strong>EDIT 2:</strong></p>
  
  <p>The code performs fine in most of the cases, but my worst case scenarios suck:</p>
  
  <pre><code>// time for 51: 30138.229ms
  // time for 77: 145214.155ms
  // time for 182: 22964.025ms
  </code></pre>
  
  <p><strong>EDIT 3:</strong></p>
  
  <p>I accepted Yosef answer as it was super useful to improve the efficiency of my JS code. Found a way to tweak the algorithm to avoid paths with dead ends using some of the restrictions from this paper <a href="https://dl.acm.org/doi/10.1145/321850.321854" rel="nofollow noreferrer">A Search Procedure for Hamilton Paths and Circuits.</a>.</p>
  
  <p>Basically, before calling another recursion, I check 2 things:</p>
  
  <ul>
  <li>If there is any node with no edges that's not part of the path till now and the path is missing more than 1 node</li>
  <li>If there were more than 2 nodes with 1 edge (one can be following node, that had 2 edges before deleting the edge to the current node, and other can be the last node)</li>
  </ul>
  
  <p>Both situations make it impossible to find a Hamiltonian path with the remaining nodes and edges (if you draw the graph it'll be clear why). Following that logic, there's another improvement if you check nodes with only 2 edges (1 way to get in and other to go out). I think you can use that to delete other edges in advance but it was not necessary at least for me.</p>
  
  <p>Now, the algorithm performs worse in most cases, where just sorting by remaining edges was good enough to predict the next node and extra work was added, but it's able to solve the worst cases in a much better time. For example, <code>limit = 77</code> it's solved in 15ms but <code>limit=1000</code> went from 30ms to 100ms.</p>
  
  <p>This is a really long post, if you have any edit suggestions, let me know. I don't think posting the final code it's the best idea taking into account that you can't check the solutions in the platform before solving the kata. But the accepted answer and this final edit should be good advice to think about this last part while still learning something. Hope it's useful. </p>