Greatest Distance between Equal Numbers in Array

Answer 1

I don't see how you can do this really any faster besides just iterating through each row, each column, and each diagonal (you can tell if something's on the same diagonal by taking the absolute value of the difference of its X and Y coordinates, of course) and keeping track of the most recent coordinates of each number you see, and the greatest observed separation.

Answer 2

Algorithm:

Simplify the problem. It is equivalent to solving the 1-dimensional version (find largest gap between equal values in a list) once per row, column and diagonal then returning the maximum.

Simplify more. The 1-dimensional version is pretty easy. You just build a Dictionary which maps values to a list of their positions, solve the trivial problem of 'what is the largest delta in this list of positions' for each value, and return the maximum.

Analysis:

The trivial problem takes linear time in the size of the position list (because the list is sorted [by the natural insertion order]). Therefore the 1-dim gap problem takes linear time in the size of the value list (because there is one position per value). Therefore the 2-dim gap problem takes linear time in the size of the matrix (because each value is included in exactly four 1-dim sub-problems).

So if the matrix is n*m, the solution will take O(n*m) time. It requires O(n+m) space (to store the value->positions dictionary during each 1-dim phase). I really doubt you'll do better (the time is clearly optimal, not so sure about the size).

Answer 3

The main idea of the following is to iterate through the array once, keeping track of the last found location in each row (hor), column (vert), and top to bottom diagonal (td) and bottom to top diagonal (dt). with this, you just find the distance to the last location for each direction and take the max.

EDIT: One other note, it looks like the question is asking for you to figure out the greatest distance between any same numbers, which i didnt understand when i wrote out the code. To fix this, you'd just need to create a dictionary or array (if you know the range of numbers that can exist), to hold collections of vert/hor/dt/td for each number and use those instead of the if yournum. It should still only require one time through the array.

int findmax(int[,] myarray, int height, int width, int yournum)
{
int diagnum = width + height - 1;

int[] vert = new int[width];
int[] hor  = new int[height];

int[] td   = new int[diagnum];
int[] dt   = new int[diagnum];

for (int x = 0; x < width; x++)
{
   vert[x] = -1;
}
for (int x = 0; x < height; x++)
{
   hor[x] = -1;
}
for (int x = 0; x < diagnum; x++)
{
   td[x] = -1;
   dt[x] = -1;
}

int maxlen = 0;

for (int x = 0; x < width; x++)
{
   for (int y = 0; y < height; y++)
   {
      if (myarray[y,x] == yournum)
      {
         if (vert[x] == -1)
         {
            vert[x] = y;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(y - vert[x] - 1));
            vert[x] = y;
         }
         if (hor[x] == -1)
         {
            hor[x] = y;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(x - hor[y] - 1));
            hor[y] = x;
         }

         int tdcol = x - y + height - 1;
         int tdloc = Math.Abs(Math.Max(0, tdcol - height + 1) - x);
         if (td[tdcol] == -1)
         {
            td[tdcol] = tdloc;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(tdloc - td[tdcol] - 1));
            td[tdcol] = tdloc;
         }
         int dtcol = y + x;
         int dtloc = Math.Abs(Math.Max(0,dtcol-height+1) - x);
         if (dt[dtcol] == -1)
         {
            dt[dtcol] = dtloc;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(dtloc - dt[dtcol] - 1));
            dt[dtcol] = dtloc;
         }
      }
   }
}
return maxlen;
}

EDIT I double checked the equations, but haven't actually tried to build/test the code, so there might be some compilation issues or logic issues, but it seems like this should work. The main part is getting the equations right, which allows you to get around having to iterate through the array multiple times (ie one per direction).

Answer 4

Since you are looking for the longest "segment," start your search with the longest possible segments and work to the shorter segments. By starting at the large end, you can stop as soon as you find a segment with matching end numbers. This assumes you only have to return a single segment that is longer OR EQUAL TO any other segment.

Answer 5

So this definitely isn't the most optimized way to accomplish your goal - but I thought it might be interesting to apply "ray-tracing" to this problem.

You have a grid of x,y coordinates and are looking to get angles and distances from one point to another and find the smallest distance on any given angle.

So with a static class something like this...

public static class RayTracing
{
    public static double GetDistance(Point a, Point b)
    {
        var x = b.X - a.X;
        var y = b.Y - a.Y;
        return Math.Sqrt(x*x + y*y);
    }

    public static double GetAngle(Point a, Point b)
    {
        var x = b.X - a.X;
        var y = b.Y - a.Y;
        var ang = Math.Atan2(y, x) * 180 / Math.PI;
        return ang < 0 ? 360 + ang : ang;
    }

    public static Dictionary<double, double> GetDistByAngles(int[][] matrix, Point target)
    {
        var result = new Dictionary<double, double>();

        var tvalue = matrix[target.Y][target.X];
        for (int y = 0; y < matrix.Length; y++)
            for (int x = 0; x < matrix[y].Length; x++)
                if (!(x == target.X && y == target.Y) && matrix[y][x] == tvalue)
                {
                    var ang = GetAngle(target, new Point(x, y));
                    var dist = GetDistance(target, new Point(x, y));
                    if (!result.ContainsKey(ang))
                        result.Add(ang, dist);
                    else if (result[ang] > dist)
                        result[ang] = dist;
                }
        return result;
    }
}

You could actually take any point in your matrix and out of every angle that has a matching value (not just horizontal, vertical, and diagonal) you could find the closest distance.

        var m = new List<int[]>();
        m.Add(new[] { 0, 0, 5, 0, 3, 6, 6, 4, 0, 3, 0, 8, 0, 1, 1 });
        m.Add(new[] { 9, 4, 0, 6, 0, 0, 0, 4, 1, 0, 6, 0, 7, 0, 0 });
        m.Add(new[] { 3, 1, 6, 1, 5, 0, 8, 0, 8, 0, 3, 2, 6, 4, 8 });
        m.Add(new[] { 1, 0, 2, 2, 8, 5, 8, 1, 8, 7, 4, 1, 0, 3, 0 });
        m.Add(new[] { 6, 3, 8, 1, 0, 0, 4, 0, 0, 3, 1, 5, 2, 0, 0 });
        m.Add(new[] { 0, 0, 5, 0, 3, 6, 6, 4, 0, 3, 0, 8, 0, 1, 1 });
        m.Add(new[] { 9, 4, 0, 6, 0, 0, 0, 4, 1, 0, 6, 0, 7, 0, 0 });
        m.Add(new[] { 3, 1, 6, 1, 5, 0, 8, 0, 8, 0, 3, 2, 6, 4, 8 });
        m.Add(new[] { 1, 0, 2, 2, 8, 5, 8, 1, 8, 7, 4, 1, 0, 3, 0 });
        m.Add(new[] { 6, 3, 8, 1, 0, 0, 4, 0, 0, 3, 1, 5, 2, 0, 0 });

        var results = RayTracing.GetDistByAngles(m.ToArray(), new Point(8, 5));

        foreach (var item in results)
            Console.WriteLine("Angle: {0},  \tDistance: {1}", item.Key, item.Value);

        Console.ReadKey();

Just thought it would be an interesting approach

I think in this example that 0 degrees is actually pointing to the right, and the distance for diagonal matches will be a little over the integer value since a grid is square and not elliptical.

Answer 6

assuming that the distance must be a direct path between the two identical number (ie no roundabouts or infinite loops).

1. create an array of 10 (for the digitsthat appear in the problem)
   • DIGIT_STRUCT[10]
2. create an array for each digit for each position of that digit. ie sample the whole grid and arrange it by number.
   • DIGIT_STRUCT[n].POSTITIONS[]
3. pick out a combo of those positions that are the maximum distance
   • this is the tricky part. but since diagonal moves are allowed, and the table is square, i believe that you can actually rank each postition by its distance from the origin (0,0). you would just have to pick out the first and last occurence (by rank). its a sort, for each digit list
   • DIGIT_STRUCT[n].MAX_DIST {POSITION a, POSITION b}
4. make sure that at least one minimal path for each MAX_DIST exists without hitting another position number. the path would only be blocked if a whole row or column was filled with that number. in your 6 example a whole column is blocked out on the subgrid by another 6.
5. compare each digits maximum distance.

not all the work needs to be done here, you do not need to validate paths that are obviously going to be shorter. if a path is invalidated you do not need to search for a different position combo (right away), if another digit contains the same distance path.

if you find a potential path of grid size (16 in your example) you should just try and validate that one since no others are going to be longer.

validating a path should require two arrays of subgrid size, hor and vert, add a number to each vert[x], and hor[y] for each POSTITION(x,y) in DIGIT_STRUCT that is within the subgrid. if there doesnt exist a vert[n] or hor[m] that equals the subgrid size you know that the shortest path there will not be blocked.

EDIT

forgot that a path may be suboptimal. if there exists a situation like

0 0 1 1
1 0 1 1
1 0 0 0
1 1 1 0

the answer here would be 0, path = 6, from (0, 0) to (3, 3)

in this case you would have to validate a path for every number, and that validation should return a distance. because the distance of a path may increase you would have to validate a lot more paths for each number (the distance may at most double).

Q. are you forced to take the most direct path? in this case (square sub grid) there is only one direct path and its blocked. if you are you are forced to do that then i think you can gain some performance back by knowing the path wont increase during the validation.