none
How do I check for consecutive repeating integers in a 2d array?

    Question

  • As my per my title, how would i go about finding if a number repeats itself N times in a row? For example if I have in my array 10101101111, how would I go about checking if the number 1 repeated itself 4 times in a row? I have searched for an answer but I can't seem to find an answer specific to this situation. Also I know I have in the title a 2d array and I gave an example of a 1d array but I just need to know how to do it horizontally then I can figure out how to do it vertically and diagonally.

    Thanks in advance


    Thursday, March 30, 2017 5:50 PM

Answers

  • @Wyck Ideally since it is a connect N game, I would just need to find the first time there was N in a row so just the first occurence, and yea efficiency would definitely would be a plus for this algorithm. Thanks for the response

    I disagree that efficiency would be a plus.  You wouldn't even notice the time it takes for even a Vic 20 to locate 4 in a row on a 7 x 6 grid.

    Shoot for the most obvious code.  In fact, I've actually included a counterexample to prove my point.  Look at my implementation for DirToDxDy.  Too complicated?  You decide.  Just write what's logical and optimize later.

    namespace ConnectFour
    {
        public class Win
        {
            public int row;
            public int col;
            public int dir;
        }
    
        public class Board
        {
            const int numCols = 7;
            const int numRows = 6;
            const int n = 4;
            int[,] grid = new int[numRows, numCols];
    
            public int[,] Grid
            {
                get
                {
                    return grid;
                }
            }
    
            public int NumRows
            {
                get
                {
                    return numRows;
                }
            }
            public int NumCols
            {
                get
                {
                    return numCols;
                }
            }
    
            public static void DirToDxDy( int dir, out int dx, out int dy )
            {
                // 0: SW: (-1, 1)
                // 1: S:  ( 0, 1)
                // 2: SE: ( 1, 1)
                // 3: E:  ( 1, 0)
                dx = dir - 1;
                if( dx > 1 ) dx = 1;
                dy = 1 - (dir / 3);
            }
    
            public Win CheckWin( int player )
            {
                for( int row = 0; row < numRows; ++row ) {
                    for( int col = 0; col < numCols; ++col ) {
                        if( grid[row, col] == player ) {
                            for( int dir = 0; dir < 4; ++dir ) {
                                int dx, dy;
                                DirToDxDy( dir, out dx, out dy );
                                int lastRow = row + dy * (n - 1);
                                int lastCol = col + dx * (n - 1);
                                if( lastRow >= 0 && lastRow < numRows && lastCol >= 0 && lastCol < numCols ) {
                                    for( int i = 1; i < n; ++i ) {
                                        if( grid[row + dy * i, col + dx * i] != player ) {
                                            goto nextDir;
                                        }
                                    }
                                    // Found!
                                    return new Win() { row = row, col = col, dir = dir };
                                }
                            nextDir:;
                            }
                        }
                    }
                }
                return null;
            }
        }
    }
    

    Friday, March 31, 2017 1:59 PM

All replies

  • In your example, are you talking about bits or bytes? Does each byte contain a "1" or a "0"?

    Also, step back a bit and describe your project. Ultimately, what are you trying to accomplish by locating these repetitive patterns?

    Thursday, March 30, 2017 7:37 PM
  • My project is basically a connect 4 game except instead of 4 pieces in a row, the user specifies how many pieces in a row are needed to win. I am representing each player with a player id  which is an integer variable, so player one will be denoted with the integer 0 and player 2 will be denoted by the integer 1. Essentially i'm trying to create a method that will detect whether or not one player's pieces have N in a row either horizontally, vertically, or diagonally. Hope that helps clear up the problem a bit. If you need more clarity don't hesitate to ask.
    Thursday, March 30, 2017 7:43 PM
  • Do you need to find any or all occurrences?  And does it need to be perfectly efficient?

    The straightforward logical approach is:

    for each cell in the grid {
       for each direction in (E, SE, S, and SW) {
          if the cell N-1 steps in the direction exists {
             for each index in (0 to N-1) {
                 if the cell at offset index in the direction of direction doesn't match the value you're looking for. {
                    next direction
                 }
             }
             //found!
          }
       }
    }

    Obviously there are ways to optimize it, but that's the basic idea.

    Thursday, March 30, 2017 8:03 PM
  • how would i go about finding if a number repeats itself N times in a row? For example if I have in my array 10101101111, how would I go about checking if the number 1 repeated itself 4 times in a row?

    There must be countless (no pun intended) ways to do this task.

    One simple approach - which may not be the most efficient - is to convert
    the array to a string and use the Contains method:

    Simplified example:

    int[] ia = new int[11] {1,0,1,0,1,1,0,1,1,1,1};
    foreach (int n in ia)
    {
        str += (char)(n + '0');
    }
    Console.WriteLine(str);
    if (str.Contains("1111"))
    {
        Console.WriteLine("The number 1 repeats 4 times in succession!");            
    }
    if (str.Contains("0000"))
    {
        Console.WriteLine("The number 0 repeats 4 times in succession!");
    }           
    

    - Wayne

    Thursday, March 30, 2017 8:38 PM
  • @WayneAKing  Although this may work well with a 1d array, i'm using a 2d array for my project so it'd be a hassle to convert it in addition it would conflict with all my other methods using my 2d array as an integer type. Do you have any other suggestions?
    • Edited by Ishiii101 Friday, March 31, 2017 1:14 AM put who the reply was addressed to
    Friday, March 31, 2017 1:13 AM
  • @Wyck Ideally since it is a connect N game, I would just need to find the first time there was N in a row so just the first occurence, and yea efficiency would definitely would be a plus for this algorithm. Thanks for the response
    Friday, March 31, 2017 1:18 AM
  •       static void Main()
          {
             int[] row = new int[] { 1,0,1,0,1,1,0,1,1,1,1 };
    
             int numberLookingFor = 4;
             int numberFound = 0;
             int startingAt = -1;
             int lastNumber = -1;
    
             for (int i = 0; i < row.Length; i++)
             {
                if (lastNumber != row[i])
                {
                   lastNumber = row[i];
                   numberFound = 1;
                   startingAt = i;
                }
                else
                {
                   numberFound++;
                   if (numberFound == numberLookingFor)
                   {
                      break;
                   }
                }
             }
    
             if (numberFound == numberLookingFor)
                Console.WriteLine("Found {0} {1}s starting at position {2}", numberLookingFor, lastNumber, startingAt);
             else
                Console.WriteLine("{0} consecutive numbers not found.", numberLookingFor);
    
          }
    

    Friday, March 31, 2017 1:38 AM
  • @Wyck Ideally since it is a connect N game, I would just need to find the first time there was N in a row so just the first occurence, and yea efficiency would definitely would be a plus for this algorithm. Thanks for the response

    I disagree that efficiency would be a plus.  You wouldn't even notice the time it takes for even a Vic 20 to locate 4 in a row on a 7 x 6 grid.

    Shoot for the most obvious code.  In fact, I've actually included a counterexample to prove my point.  Look at my implementation for DirToDxDy.  Too complicated?  You decide.  Just write what's logical and optimize later.

    namespace ConnectFour
    {
        public class Win
        {
            public int row;
            public int col;
            public int dir;
        }
    
        public class Board
        {
            const int numCols = 7;
            const int numRows = 6;
            const int n = 4;
            int[,] grid = new int[numRows, numCols];
    
            public int[,] Grid
            {
                get
                {
                    return grid;
                }
            }
    
            public int NumRows
            {
                get
                {
                    return numRows;
                }
            }
            public int NumCols
            {
                get
                {
                    return numCols;
                }
            }
    
            public static void DirToDxDy( int dir, out int dx, out int dy )
            {
                // 0: SW: (-1, 1)
                // 1: S:  ( 0, 1)
                // 2: SE: ( 1, 1)
                // 3: E:  ( 1, 0)
                dx = dir - 1;
                if( dx > 1 ) dx = 1;
                dy = 1 - (dir / 3);
            }
    
            public Win CheckWin( int player )
            {
                for( int row = 0; row < numRows; ++row ) {
                    for( int col = 0; col < numCols; ++col ) {
                        if( grid[row, col] == player ) {
                            for( int dir = 0; dir < 4; ++dir ) {
                                int dx, dy;
                                DirToDxDy( dir, out dx, out dy );
                                int lastRow = row + dy * (n - 1);
                                int lastCol = col + dx * (n - 1);
                                if( lastRow >= 0 && lastRow < numRows && lastCol >= 0 && lastCol < numCols ) {
                                    for( int i = 1; i < n; ++i ) {
                                        if( grid[row + dy * i, col + dx * i] != player ) {
                                            goto nextDir;
                                        }
                                    }
                                    // Found!
                                    return new Win() { row = row, col = col, dir = dir };
                                }
                            nextDir:;
                            }
                        }
                    }
                }
                return null;
            }
        }
    }
    

    Friday, March 31, 2017 1:59 PM