CODEWITHSUNDEEP
objective-cloopsrecursioncocos2d-iphonensmutablearray
cbros2008
cbros2008

Reputation: 353

Dynamic way of looping through X number of nested arrays in Objective-C

I'm creating an iPhone game and have created Line objects each with their own properties such as their (x,y) coordinates and a 'connected' array which details all other lines which are currently touching 'this' line.

What I want to do is from a starting line (Line1), iterate through its array of other connected lines and from there, choose another line at random (say Line2). I then want to repeat this logic and look at all of Line2s connected lines array and choose another Line that's connected except the line it just came from (i.e. not Line1). In short, I want to find out if a set of lines complete a 'circuit', that is, the last line == the first so in

Pseudo Code:

Line1->Line1Array->Line2->Line2Array->Line3->Line3Array->Line4->Line4Array->Line1->Stop!

Visual representation:

lines

I've managed to get it working by hard coding this particular visual representation which I've shown below. The problem is, a circuit might not always be made up of 4 sides and this solution doesn't seem particularly robust nor elegant. It'd be great if I had a method which could iterate through X number of arrays and simply return whether a circuit is detected or not. I came across using recursion but got confused by how I could apply it to this particular problem.

Actual Code:

for(Line* line1 in allLines) {

   // contains all lines connected to this line
   NSMutableArray* connectedTo = [line1 getConnectedTo];

// lets loop through all lines connected to our line1
for(Line* line2 in connectedTo) {

      // contains all lines connected to line2
      NSMutableArray* secondConnectedTo = [line2 getConnectedTo];

// lets loop through all lines connected to line2
for(Line* line3 in secondConnectedTo) {

 // don't look back at line1 from line2
 if([line3 getLineCreationNumber] != [line1 getLineCreationNumber]) {

     // contains all lines connected to the 3rd line
     NSMutableArray* thirdConnectTo = [line3 getConnectedTo];

// lets loop through all lines connected to our 3rd line
for(Line* line4 in thirdConnectTo) {

      // contains all lines connected to the 4th line
      NSMutableArray* fourthConnectTo = [line4 getConnectedTo];

// 'line5' here is actually the same as line1 so check to confirm for circuit
for(Line* line5 in fourthConnectTo) {                   
      if([line5 getLineCreationNumber] == [line1 getLineCreationNumber]) {
       CCLOG(@"CIRCUIT FOUND");
}}}}}}}

Updated Code:

hi @dasblinkenlight thanks for the answer, it's been useful. I feel I'm very close to cracking this but am still coming up against an issue. Here's the code thus far (note I'm passing an empty array initially as per instruction):

-(bool) findCircuit:(NSMutableArray*) circuit {

for(Line* l in [self getConnectedTo]) {

// ensure line isn't in circuit found so far
if(![circuit containsObject: self]) {
    // add connected line to end of circuit
    [circuit addObject: l];
    // call find circuit on the latest connected line
    if([l findCircuit: circuit])
    return YES;
} else {
    [circuit removeLastObject];
    continue;
}}}

I'm still geting confused at the latter parts i.e. when to return YES/NO and how this ties up. I can see by outputting line IDs that when there are 3 lines, the lines are being trawled through as expected. Here's the flow with 3 lines:

Line1->Line2->Line1->Line2->line3->Line2

Unfortunately, when 4 lines are linked, the program goes extremely slow (I can see many threads created) and I get the following loop instead:

Line1->Line2->Line1->Line4->Line3->Line4->Line1

Upvotes: 1

Views: 210

Answers (1)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

Recursion is a step in the right direction. The trick to applying it right is to think that you work with one line at a time, and pretend that your recursive method is already completed. By the time you are done, the method will be completed, and so your code would work (it's OK for this to sound a little like magic at first).

To start, add this method to your Line class:

-(BOOL)findCircuit:(NSMutableArray*)circuit {
    ...
}

The circuit array would contain the list of lines that you've found so far; the caller would pass an initially empty NSMutableArray to your function. The Line object itself would supply the connected lines that you need to try. There will be a loop over the connected lines. On each iteration, your code will

  • Check that the connected line is not on the circuit that you found so far
  • If it is not, add the connected line to the end of the circuit, and call findCircuit on it. This is where the magic happens: you have not finished writing your method, yet you can call it!
  • If findCircuit returns YES, your function returns YES too
  • If NO is returned, your loop removes the last line that you added to the circuit, and move on to the next one
  • Once all connected lines in the loop are exhausted without returning YES, the method returns NO to its caller.

That's it, really! Call this method on the line from which you would like to create a circuit, pass it an empty NSMutableArray, and see if the method returns YES. If it does, the array that you passed would contain your circuit.

Upvotes: 4

Related Questions