CODEWITHSUNDEEP
c#.netarraysmultidimensional-array
smackledorf
smackledorf

Reputation: 55

2D array index positions "touching"

I'm looking to find a way to be able to return if positions in a 2d array are both "touching" and similar values, tracing all the way around. Before I get into this there is a very similar question asked, and solved here, but it's written in python which I know nothing of. To further expand:

f f f f

f T T f

f T T f

f f f f

starting at [0][0] it would return all the falses in that array because they are the same value and chain back to [0][0].

f f f T f f f

f T f T f T f

f f f T f f f

but based on this one, starting at [0][0] would only return [0][0,1,2] , [1][0,2] , and [2][0,1,2]. however if you were to start at [0][4], it would return all the falses after [n][3] because they are the same value as the start, and touching.

Not looking for anyone to help me write code exactly but maybe point me in the right direction. Please excuse my novice level in advance, and thank you very much!

Upvotes: 2

Views: 534

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186678

It seems that you have a graph problem and you are looking for Breadth First Search or alike algorithm where

  1. Graph nodes: all valid (f) array items
  2. Graph edges: if and only if array items are neighbors

Implementation:

private static IEnumerable<Tuple<int, int>> Touching(char[,] items, 
                                                     Tuple<int, int> startAt, 
                                                     char letter = 'f') {
  if (startAt.Item1 < 0 || startAt.Item1 >= items.GetLength(0) ||
      startAt.Item2 < 0 || startAt.Item2 >= items.GetLength(1))
    yield break; // or throw ArgumentOutOfRangeException
  else if (items[startAt.Item1, startAt.Item2] != letter)
    yield break;

  Queue<Tuple<int, int>> agenda = new Queue<Tuple<int, int>>();
  HashSet<Tuple<int, int>> visited = new HashSet<Tuple<int, int>>() { startAt };

  agenda.Enqueue(startAt);

  while (agenda.Any()) {
    for (int i = agenda.Count - 1; i >= 0; --i) {
      var point = agenda.Dequeue();

      yield return point;

      // Manhattan: left, right, top, bottom neighbors only, no diagonal ones
      var validNeighbors = new Tuple<int, int>[] {
         new Tuple<int, int>(point.Item1 - 1, point.Item2),     // left
         new Tuple<int, int>(point.Item1 + 1, point.Item2),     // right
         new Tuple<int, int>(point.Item1, point.Item2 - 1),     // top
         new Tuple<int, int>(point.Item1, point.Item2 + 1),}    // bottom
      .Where(p => p.Item1 >= 0 && p.Item1 < items.GetLength(0)) // Within array
      .Where(p => p.Item2 >= 0 && p.Item2 < items.GetLength(1)) // Within array
      .Where(p => items[p.Item1, p.Item2] == letter)            // valid point
      .Where(p => visited.Add(p));                              // not visited 

      foreach (var p in validNeighbors)
        agenda.Enqueue(p);
    }
  }
}

Test:

 char[,] data = new char[,] {
    { 'f', 'f', 'f', 'T', 'f', 'f', 'f',},
    { 'f', 'f', 'f', 'T', 'f', 'f', 'f',},
    { 'f', 'f', 'f', 'T', 'f', 'f', 'f',},
  };

  string report = string.Join(Environment.NewLine, 
    Touching(data, new Tuple<int, int>(0, 0), 'f'));

  Console.WriteLine(report);

Outcome (all these items below are touching i.e. reachable from the startAt point - (0, 0)):

(0, 0)
(1, 0)
(0, 1)
(2, 0)
(1, 1)
(0, 2)
(2, 1)
(1, 2)
(2, 2)

With a help of Linq you can organize the report in different way (like in the question):

var report = string.Join(Environment.NewLine, 
  Touching(data, new Tuple<int, int>(0, 0), 'f')
    .GroupBy(item => item.Item1, item => item.Item2)
    .OrderBy(chunk => chunk.Key)
    .Select(chunk => $"[{chunk.Key}][{string.Join(", ", chunk.OrderBy(x => x))}]"));

And have the response below:

[0][0, 1, 2]
[1][0, 1, 2]
[2][0, 1, 2]

Upvotes: 2

Related Questions