CODEWITHSUNDEEP
c#multidimensional-array
PrestonJ
PrestonJ

Reputation: 25

Quick way of checking if a 2D array contains an element c#

I'm currently coding battleships as a part of a college project. The game works perfectly fine but I'd like to implement a way to check if a ship has been completely sunk. This is the method I'm currently using:

public static bool CheckShipSunk(string[,] board, string ship){
    for(int i = 0; i < board.GetLength(0); i++){
        for(int j = 0; j < board.GetLength(1); j++){
            if(board[i,j] == ship){return false;}
        }
    }
    return true;
}

The problem with this is that there are 5 ships, and this is very inefficient when checking hundreds of elements 5 times over, not to mention the sub-par quality of college computers. Is there an easier way of checking if a 2D array contains an element?

Upvotes: 1

Views: 467

Answers (3)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186688

Willy-Nilly you have to scan either the entire array or up to the first ship.

You can simplify the code by quering the array with help of Linq, but not increase performance which has O(length * width) time complexity.

using System.Linq;

...

// No explicit loops, juts a query (.net will loop for you) 
public static bool CheckShipSunk(string[,] board, string ship) => board is null
  ? throw new ArgumentNullException(nameof(board))
  : board.AsEnumerable().Any(item => item == ship);

If you are looking for performance (say, you have a really huge array, many ships to test etc.), I suggest changing the data structure: Dictionary<string, (int row, int col)> instead of the string[,] array:

Dictionary<string, (int row, int col)> sunkShips = 
  new Dictionary<string, (int row, int col)>(StringComparer.OrdinalIgnoreCase) {
    { "Yamato",          (15, 46) },
    { "Bismark",         (11, 98) },
    { "Prince Of Wales", (23, 55) },
  };

and then get it as easy as

public static bool CheckShipSunk(IDictionary<string, (int row, int col)> sunkShips, 
                                 string ship) =>
  sunkShips?.Keys?.Contains(ship) ?? false;

Note that time complexity is O(1) which means it doesn't depend on board length and width

Upvotes: 0

JonasH
JonasH

Reputation: 36361

this is very inefficient when checking hundreds of elements 5 times over

Have you done any profiling? Computers are fast even your old college computers. Checking hundreds of elements should take microseconds. From Donald Knuths famous quote

There is no doubt that the grail of efficiency leads to abuse. Programmers waste enormous amounts of time thinking about, or worrying about, the speed of noncritical parts of their programs, and these attempts at efficiency actually have a strong negative impact when debugging and maintenance are considered. We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

So if you feel your program is slow I would recommend to start with profiling. If you are in university this might be a very valuable skill to learn.

There are also better algorithms/datastructures that could be employed. I would for example expect each ship to know what locations they are at, and various other information, like if it is sunk at all. Selecting appropriate data structures are also a very important skill to learn, but a difficult one. Also, try to not get stuck in analysis-paralysis, a terrible inefficient ugly working solution is still better than the most beautiful code that does not work.

However, a very easy thing to fix is moving .GetLength out of the loop. This is a very slow call, and only doing this once should make your loop a several times faster for almost no effort. You might also consider replacing the strings with some other identifier, like an int.

Upvotes: 1

Beyondo
Beyondo

Reputation: 3247

Use an arithmetic approach to loop-through with just 1 loop.

public static bool CheckShipSunk(string[,] board, string ship){
    int rows = board.GetLength(0);
    int cols = board.GetLength(1);
    for (int i = 0; i < rows * cols; i++) {
        int row = i / cols;
        int col = i % cols;
        if (board[row, col] == ship)
            return false;
    }
    return true;
}

But I am with Nysand on just caching and storing that information in cells. The above code although might work, is not recommended as it is still not as efficient

Upvotes: 1

Related Questions