Skip to main content
additional thoughts
Source Link
JimmyJames
  • 28.9k
  • 3
  • 55
  • 105

If I understand properly, the way this problem is structured allows it to be solved by building a directed graph and determining whether there is any path that includes all nodes without repeating any node. I've gone ahead and drawn an (ugly) drawing of the friend graph:

enter image description here

I haven't checked but I think there probably is at least one such path. Given that, you there shouldn't be any need to consider the 'enemies' data because any path through this graph would be one where only 'friends' are adjacent.

Now if you were to try to maximize the distance between 'enemies' or add more rows, this would be a far more complex problem but as stated it's fairly well-known. This is equivalent in structure to the Seven Bridges of Königsberg problem. I believe You could use a variant of Dijkstra's algorithm to come up with shortest path solutions that touch all nodes where all vertexes have a distance of 1.

On looking at the graph again, it was thinking about the fact that some friend relationships are on-directional. This could be modeled by adding a weight (distance) to each vertex based on whether they are bi-directional e.g. 1 for a 1-directional and 0.5 for a bi-directional relationship. This would allow the shortest path algorithm to optimize such that you get answers where plants have friends on both sides as much as possible.

If I understand properly, the way this problem is structured allows it to be solved by building a directed graph and determining whether there is any path that includes all nodes without repeating any node. I've gone ahead and drawn an (ugly) drawing of the friend graph:

enter image description here

I haven't checked but I think there probably is at least one such path. Given that, you there shouldn't be any need to consider the 'enemies' data because any path through this graph would be one where only 'friends' are adjacent.

Now if you were to try to maximize the distance between 'enemies' or add more rows, this would be a far more complex problem but as stated it's fairly well-known. This is equivalent in structure to the Seven Bridges of Königsberg problem. I believe You could use a variant of Dijkstra's algorithm to come up with shortest path solutions that touch all nodes where all vertexes have a distance of 1.

If I understand properly, the way this problem is structured allows it to be solved by building a directed graph and determining whether there is any path that includes all nodes without repeating any node. I've gone ahead and drawn an (ugly) drawing of the friend graph:

enter image description here

I haven't checked but I think there probably is at least one such path. Given that, you there shouldn't be any need to consider the 'enemies' data because any path through this graph would be one where only 'friends' are adjacent.

Now if you were to try to maximize the distance between 'enemies' or add more rows, this would be a far more complex problem but as stated it's fairly well-known. This is equivalent in structure to the Seven Bridges of Königsberg problem. I believe You could use a variant of Dijkstra's algorithm to come up with shortest path solutions that touch all nodes where all vertexes have a distance of 1.

On looking at the graph again, it was thinking about the fact that some friend relationships are on-directional. This could be modeled by adding a weight (distance) to each vertex based on whether they are bi-directional e.g. 1 for a 1-directional and 0.5 for a bi-directional relationship. This would allow the shortest path algorithm to optimize such that you get answers where plants have friends on both sides as much as possible.

Source Link
JimmyJames
  • 28.9k
  • 3
  • 55
  • 105

If I understand properly, the way this problem is structured allows it to be solved by building a directed graph and determining whether there is any path that includes all nodes without repeating any node. I've gone ahead and drawn an (ugly) drawing of the friend graph:

enter image description here

I haven't checked but I think there probably is at least one such path. Given that, you there shouldn't be any need to consider the 'enemies' data because any path through this graph would be one where only 'friends' are adjacent.

Now if you were to try to maximize the distance between 'enemies' or add more rows, this would be a far more complex problem but as stated it's fairly well-known. This is equivalent in structure to the Seven Bridges of Königsberg problem. I believe You could use a variant of Dijkstra's algorithm to come up with shortest path solutions that touch all nodes where all vertexes have a distance of 1.