Styjun

I'm trying to write a program that "solves a circle". The Circle class contains an ArrayList of Triangle Objects and an ArrayList of Integers. The Triangle objects each have three int instance fields that represent three numbers at the vertices of each triangle. There is also a Pairs class (you can see all of the code I have in the "code" section)
Here is an example of the setup using four triangles that is not solved:

And here is the same circle after it has been "solved":

The Circle in the second picture is a solved Circle because the number on any arc of the circle is equal to the sum of the two vertex numbers next to it: 6 = 1+5, 15 = 6+9, 11 = 7+4, and 9 = 5+4. Note that this was obtained by rotating the given triangles. This is analagous in the code to simply changing the Pair that is present in the solution for each triangle (where a "Pair" is an object of two ints, where those ints are the values on the circle for each triangle)

A Circle isn't always given in a "solved" state. If this is the case, the triangles can be rotated so that the circle will be in the solved state. The precondition of any given circle is that there is a solved state, so the numbers will always line up.

A circle will always have at least two triangles and there is no (practical) maximum number. Every given circle will always be solvable, meaning there is a way to rotate each triangle so that the number on the circle is the result of the sum of the two adjacent vertices from the two different triangles.

The point of the program is not to alter any of the given instance fields; instead, I just want to create a method called solveCircle that returns an ArrayList of Pairs that represents the solution to the Circle. In the above example, the solveCircle method would return an ArrayList containing the following pairs: (4,1), (5,6), (9,7), (4,5). These pairs are in the solution because they are all pairs of numbers on a triangle, and each pair is also on the circle. Note that the solution goes counter-clockwise around the circle.

My gut is telling me that this process should involve some type of recursion, since a loop would be tricky due to the circular nature of the circle; in other words, I could loop through each pair of triangles finding the proper solution, but there could easily be more than one, and comparing each one with the solution to the next sum seems like it will be inefficient; recursion seems like a better option but I'm not sure what to apply the recursion to...what alrgorithm should I use and what is even the base case?

public class Triangle

 private int num1;
 private int num2;
 private int num3;

 public Triangle(int n1, int n2, int n3)
 
 num1 = n1;
 num2 = n2;
 num3 = n3;
 

 public ArrayList<Pair> getPairs()
 
 ArrayList<Pair> pairs = new ArrayList<Pair>();
 pairs.add(new Pair(num1, num2));
 pairs.add(new Pair(num2, num3));
 pairs.add(new Pair(num3, num1));
 return pairs;
 

class Pair

 private int p1;
 private int p2;

 public Pair(int x, int y)
 
 p1 = x;
 p2 = y;
 

public class Circle

 private ArrayList<Triangle> triangles;
 private ArrayList<Integer> sums;

 public Wheel(ArrayList<Integer> s, ArrayList<Triangle> t)
 
 triangles = t;
 sums = s;
 

 public ArrayList<Pair> solveCircle()
 
 //need help here
 

You can use a tree to separate the triangles that are solved from the ones that are unsolved. The same for the circles that are solved and that are unsolved. This way, you would make it a log n search function that would ignore the solved ones, thus avoiding unnecessary comparisons.

if (solved)
 add to left side of the tree
else 
 add to right side of the tree

The complexity as well for this could be an extreme overkill depending on the use case.

for the initial step, you call the helper three times: once for each pair, until a success is returned (boolean could be used to indicate success.)

the helper performs the recursive step.

for the recursive step, you have a sum extending behind you, an integer which you must combine with to meet that sum, and three possible ways to acheive it... however you do not return success unless your recursive call also returns success

for the terminal step, there is no rotating allowed, just a final true or false for did I complete the sum behind me.