7
\$\begingroup\$

I've started writing a piece of code to help me search for an object in all the objects found in the diagonals of an M x M 2D array.

Though the code works, I'd like to know if there is a way I can improve on it or there exists a different technique I could use to achieve the same result with fewer lines of code. I just don't want to re-invent the wheel.

// board must be a square matrix    
bool allDiagonals(string[] board, string strToFind)
{
    string s = "";
    for (int col = board[0].Length - 1; col >= 0; col--)
    {

        int row = 0;
        int j = col;
        s = "";
        while (j <= board[0].Length - 1)
        {
            s += board[row++][j++];
        }
        if (s.Contains(strToFind))
            return true;
    }

    for (int row = board.Length - 1; row > 0; row--)
    {
        int colmin = 0;
        s = "";
        for (int i = row; i < board.Length; i++)
        {
            s += board[i][colmin++];
        }
        if (s.Contains(strToFind))
            return true;
    }

    for (int col = 0; col <= board[0].Length - 1; col++)
    {

        int row = 0;
        int j = col;
        s = "";
        while (j >= 0)
        {
            s += board[row++][j--];
        }
        if (s.Contains(strToFind))
            return true;
    }
    for (int row = board.Length - 1; row > 0; row--)
    {
        s = "";
        int colmax = board[0].Length - 1;
        //scan from bottom right to main diagonal
        for (int i = row; i < board.Length; i++)
        {
            s += board[i][colmax--];
        }
        if (s.Contains(strToFind))
            return true;
    }
    return false;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ from a performance standpoint this can be improved (s.Contains(strToFind)) - by using the usual techniques from lexing (basically you can look for strToFind while looking through the diagonals with a state-machine) \$\endgroup\$ – Carsten Jul 4 '14 at 8:32
  • \$\begingroup\$ @CarstenKönig make that an answer. Flesh it a bit and you will get upvotes for sure;) \$\endgroup\$ – Vogel612 Jul 4 '14 at 8:45
  • \$\begingroup\$ flesh out like implemnting the state-machine ... I think this will take me a while ;) \$\endgroup\$ – Carsten Jul 4 '14 at 8:49
  • \$\begingroup\$ @CarstenKönig I wrote an answer just now, is that the kind of state-machine you were thinking of? (I still think the question can have another answer) \$\endgroup\$ – Simon Forsberg Jul 4 '14 at 9:53
  • \$\begingroup\$ The idea is just that you check as you go along - but as there may be cycles (you search for "abac" and see "ababac" you have to look into more than one possible route at once and cannot just compare characterwise ... BUT I guess this is just for some Word game and it would be overkill (or even slower than Contains for small words) \$\endgroup\$ – Carsten Jul 4 '14 at 9:59
5
\$\begingroup\$

This reminds me of what I wrote a while ago for my Tic Tac Toe Ultimate game.

In case I get anything wrong, here is a relevant part of my original code:

// Scan diagonals for a winner: Bottom-right
for (int yy = 0; yy < board.getSizeY(); yy++) {
    newWin(conds, consecutive, loopAdd(board, 0, yy, 1, 1));
}

private static List<Winnable> loopAdd(HasSub<? extends Winnable> board,
        int xx, int yy, int dx, int dy) {
    List<Winnable> winnables = new ArrayList<>();

    Winnable tile;
    do {
        tile = board.getSub(xx, yy);
        xx += dx;
        yy += dy;
        if (tile != null)
            winnables.add(tile);
    }
    while (tile != null);

    return winnables;
}

When making this in C#, you can return IEnumerable<char>. The idea of the method is to start at a specific point and to iterate until you're outside the valid area.

I think it's a bad idea that you're currently using String concatenation first, and then checking if the string contains the char. Instead you can indeed as Carsten points out in the comments use a state machine for that. It only needs to be about an int really that keeps track of how many consecutive matches you've had so far, and when it reaches a non-match it starts over at zero. When it reaches the string length, it returns true.

Anyways, back to the main part, here's what I would try to do:

private IEnumerable<char> loopOver(string[] board,
        Point position, Point delta) {

    char value;
    while (true) {
        if (!charIsInsideBoard(board, position))
            break;

        value = getCharInBoard(board, position);
        position.x += delta.x;
        position.y += delta.y;
        yield return value;
    }
}

Whenever I'm using C#, I love using the wonderful yield keyword.

private boolean contains(IEnumerable<char> loop, string searchFor) {
    int matches = 0;
    foreach (char ch in loop) {
        if (ch == searchFor[matches]) {
             matches++;
        }
        else {
             matches = 0;
             if (ch == searchFor[matches]) {
                 matches++;
             }
        }
        if (matches == searchFor.Length) {
             return true;
        }
    }
    return false;
}

Then in your allDiagonals method (which really could be renamed to searchAllDiagonals) all you need to do is to call the contains and loopOver methods a couple of times.

boolean searchAllDiagonals(string[] board, string searchFor)
{
    boolean result = false;
    for (int i = 0; i < board[0].Length; i++) {
        result = result || contains(loopOver(board, new Point(i, 0), new Point(1, 1), searchFor);
    }
    for (int i = 0; i < board.Length; i++) {
        result = result || contains(loopOver(board, new Point(0, i), new Point(1, 0), searchFor);
    }
    ...
}

Please note that I have not tested this code, and as I haven't done any C# development since last time I might have mixed something up. I also might have mixed up X and Y, but that happens for me in Java too every now and then.

Other Suggestions:

  • Don't use i and j when you're using nested loops. row and col are so much better, or x and y. I myself use xx and yy sometimes for loops when I already have another x / y variable.

  • As your variable is named board, what do I know, perhaps your whole point is to check for a winner in a Tic Tac Toe game. If a game is your context, then I'd recommend not using string[]. Use a BoardField[][] variable instead, or preferably wrap such a 2D array in a Board class (which can contain the charIsInsideBoard and getCharInBoard methods).

\$\endgroup\$
4
\$\begingroup\$
  • Let me tell you something about strings. In .NET, String is an immutable type -- it can only be set when it's created, and it can't be changed. The only way to change it is to create an entirely new string which has the desired content. String concatenation doesn't change the original string; it creates a new string. Repeated string concatenation is very time and space inefficient, as the whole string has to get copied each time.
  • But what about when you need to build a string up from pieces? .NET also provides the StringBuilder class, which is mutable: you can change it however you like, most notably, it's efficient to add pieces onto the end of it.
  • However you don't actually need to do either of these; using a state machine is the right way to do things.
  • Don't repeat yourself. You have practically the same code written four times (even though you accomplish the same thing in different ways), to search the 45,135,215, and 305 diagonals. You need to find some way to refactor that so the code is only written once. Simon's idea (passing dx and dy) is a good one. I also wonder if it would be profitable to build the state machine (lexer) to simultaneously search for the target string and its reversal, so that way you only need to run over two diagonals.
\$\endgroup\$
  • \$\begingroup\$ thanks for this, didn't know string concatenation creates a new string. \$\endgroup\$ – TheJackal Jul 5 '14 at 10:53
1
\$\begingroup\$

There's a different algorithm that could be more efficient, however it is quite complicated and you probably don't want to implement it.

Along with your board, you build (once) a map: letter -> positions of that letter in the board. When you are given a word, you first check if all letters of that word are in the board. If not, you are done. If all letters are present, you then pick the letter in your word which is the rarest on the board and scan from that position in both diagonal directions. Either you find the word or not. If not, you then iterate over each letter like that until you find the word, or don't find it anywhere.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.