CODEWITHSUNDEEP
c#arraysalgorithmsearch
Sakamoto Kazuma
Sakamoto Kazuma

Reputation: 2579

Most Efficient Search for 2D Array of Numbers Across Multiple Cells

I have a series of 8x8 2D Arrays. Each cell in the arrays can contain a value from 0 to 9 as an int. Cells can also have the value -1, however this is to indicate a null or invalid cell. I am then given sequences in periods of time. How would I search the 2D array to find the sequence? One 2D array could contain more than one sequence, but not all sequences would be expected to be found within one 2d array. Sequences cannot change directions but can move left or right and up or down until hitting the edge of the array or an invalid cell. 

Example:
[4,6,8,1,4,5,7,-1]
[6,3,1,9,0,3,3,1]
[1,6,7,9,3,-1,7,1]
[1,6,7,-1,4,3,1,2]
[1,4,5,6,-1,8,3,1]
[8,0,1,3,5,6,2,0]
[0,6,9,8,2,6,8,2]
[2,6,9,0,4,3,5,1]

Need to find sequences: 1121021, 524, 15340962, 16793, 13309136

Code is in C#.

Should I be looking for a Path finding Algorithm, or a Search algorithm?

Upvotes: 1

Views: 227

Answers (1)

MBo
MBo

Reputation: 80187

Sequences cannot change direction, so you don't need path finding.

Instead consider using of string searching algorithms.

Here you need to look for multiple patterns, so

Aho–Corasick string matching algorithm (extension of Knuth-Morris-Pratt)
Commentz-Walter algorithm (extension of Boyer-Moore)
Set-BOM (extension of Backward Oracle Matching)
Rabin–Karp string search algorithm

are appropriate.

For reverse direction like 13309136 you can create reversed patterns.

Upvotes: 1

Related Questions