Find longest path of 1s through an array of 0s

[dropkickweasel]

I posted a similar question a couple of days ago and am still struggling to come up with a solution to my problem.
I'm hoping if I rephrase it here someone might be able to help.

I have a 21x21 array in cells B2:V22.
Each cell in the array contains either a 0 or a 1. (If it makes any difference to potential help, these can easily be changed to blanks, letters, or whatever works for the most efficient solution).

I would like to calculate the length of the longest contiguous run of orthogonally adjacent 1s.

The longest run of contiguous 1s in the picture below is highlighted in green.
In light green is an alternate route that would still result in the longest run.
In blue are cells that are adjacent to the longest run, but not contributing to it.
In orange are other runs that are not the longest.

Using the formula:

=MAX(IF(SUM(A2,B2)>1,A24+1,B2),IF(SUM(B1,B2)>1,B23+1,B2))

In cell B24, I am able to produce the following result:

This formula checks to the left and above of the target cell, looking for 1s, and where there is a 1 in both the target cell and either the cell above or to the left, it adds 1 to the highest value found so far.
This allows me to run a cumulative total from the top left down towards the bottom right.

However, if I add a new IF to the formula to check to the right as well, then I get a circular reference error:

I understand why I get the circular reference error - the 5 to the right is generated from the 4 on the left, so adding the 5 to the 4 making a 9 on the left (which is what I want) would produce a 10 on the right (which I don't want), which would produce a 19 on the left etc. I just can't figure out a way to get around it.

So, can anyone offer any help with a solution for the longest run of orthogonally adjacent 1s?

I have looked into using a Lambda function as I believe they are able to deal with recursive situations like this, but I can't figure out how to write it with an appropriate way to exit the loop.

I'm open to all suggestions - helper cells, formulae and VBA - that would help me calculate a solution to this problem.

Additional considerations:
The area will always be a 21x21 array.
The longest path could have multiple changes of direction.
The longest path could start and end anywhere within the array.
I don't need to know where the longest path is, just how many cells it is.

Thanks in advance to anyone who is able to offer advice or a full-blown solution to this :]

 

[mikerickson]

So this would be length 9?

011100
010110
011100

 

[dropkickweasel]

So this would be length 9?

011100
010110
011100

It would.

The path should not be able to cross itself and can't count a cell more than once.

 

[dropkickweasel]

Slight modification to the path rules:

There is a chance that a path may cross itself once only.

Example:

000010000
000010000
000010000
000010000
111111110
000010010
000010010
000011110
000000000

This path would have a length of 21, crossing the italicised 1 twice.

There would never be the opportunity for two such 'crossroads' to exist.
It would be possible to change the crossroads 1 to a 2 (or any other character) if it helps with the formulae/code.

Any thoughts?

My current (and very inelegant) plan is to have additional 'helper grids'.
On my own I think I can assess the paths once horizontally and once vertically in each helper grid.
This first one assesses left to right and top to bottom.
I would then use this grid as the input for a second grid assessing right to left and bottom to top.
Given that a path may have many changes of direction, and in any order, I would then repeat these two steps several times over (maybe mixing up the left-right and top-bottom combinations each time), until I believe I have covered the most likely possible inputs.
I find this 'solution' to be very inelegant and unsatisfactory though, so I'm hoping a lambda function or a vba user defined function might be able to perform the same analysis more efficiently and with 100% success.

Again, thank you in advance to anyone who can offer any help :]

 

[mikerickson]

That new rule just blew up my solution.

I'm trying to figure out the crossing requirement, would this result in 11?

0000100100
0011111110
0000100100

 

[dropkickweasel]

Ah, sorry.

The crossing the path is something of an edge case so it didn't occur to me immediately.

In the example you gave, the result should be 7.

0000100100
0011111110
0000100100

The bold path through the centre and any one of the 3 bold/italics 1s at the end of that node would result in a length of 7.
Even though there are two opportunities to cross in this example, there is no full path linking through, so the other 1s on each 'crossroads' are ignored as 'dead ends'.

Does that make sense?

And thank you so much for dedicating any amount of time to trying to help me find a solution to this, it is appreciated :]

 

[dropkickweasel]

Apologies for initially posting this as a new thread - thank you to Fluff for making me aware of the rules violation - won't happen again :].

Recap:

I have a 21x21 grid of 1s and 0s. (These can be changed if you have a solution that works with blanks/letters/whatever).
The 1s and 0s will be distributed in different cells at different times, though the size of the grid will remain the constant.
I would like to be able to run a macro that will count the longest contiguous run of 1s, allowing for orthogonal changes in direction.
Each cell may only be used once with the exception of a 'crossroads' which may be passed through both vertically and horizontally.

In the image below, I have highlighted in orange the longest run of 1s, which would lead to a count/sum of 52.
In yellow are contiguous runs which are not the longest, or 'offshoots' of the longest run which should not be counted as they are not on the 'path' that I'm trying to trace.

Update:

With help from people on this forum I have been using the following code to count cells in each direction, but this doesn't work for the crossroads, or offshoots.
Equally, there is no way to know which order to run the directional codes for the correct solution to any given path.
As a result of this, running the FromLeft and equivalent FromRight code consecutively produces a value twice the length of a single horizontal run of 1s.

Code:
Sub FromLeft()

Dim rng As Range
Set rng = Range("Input")

Dim r As Long
Dim c As Long

For r = 1 To 21 Step 1
For c = 1 To 21 Step 1

'If the cell, or the cell directly left is 0, then leave the cell value as it is
If rng.Cells(r, c).Value = 0 Or rng.Cells(r, c - 1).Value = 0 Then
rng.Cells(r, c).Value = rng.Cells(r, c).Value
'otherwise, if the cell plus the cell left is > 1, then the cell value becomes the value of the cell left + 1
ElseIf rng.Cells(r, c - 1).Value + rng.Cells(r, c).Value > 1 Then
rng.Cells(r, c).Value = rng.Cells(r, c - 1).Value + 1
rng.Cells(r, c - 1).Value = 0
'otherwise, leave the cell value as it was
Else: rng.Cells(r, c).Value = rng.Cells(r, c).Value
End If

Next c
Next r

End Sub

Any suggestions or advice before I give up on this project?

 

[yrpsoa]

I really like this one! Did you find a solution?

 

[bebo021999]

I really like this one! Did you find a solution?

Do you want macros?
I saw your newest thread about name chain, but macros is not an option.
I dont believe formula can do this.

 

[dropkickweasel]

I really like this one! Did you find a solution?

I did not, sadly. I gave up on it, but if you have a suggestion for a solution, I’d love to hear it :]

Do you want macros?
I saw your newest thread about name chain, but macros is not an option.
I dont believe formula can do this.

I would be happy to use any combination of macros And formulae that can accurately produce a count of the longest orthogonal contiguous group of 1s from a 21x21 grid of 0s and 1s. Any suggestions on how this might be achieved?