Cavity Map · Coding Gym

Solutions

We can check each element against its neighbors’ depth and mark it with ‘X’ if the cavity condition is satisfied.

Here is a C++ Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


size_t n;
cin >> n;
vector<vector<char>> data; data.reserve(n);
for (auto i=0u; i<n; ++i)
{
    data.emplace_back(n);
    copy_n(istream_iterator<char>(cin), n, begin(data[i]));
}

for (auto i=1u; i<n-1; ++i)
{
    for (auto j=1u; j<n-1; ++j)
    {
        auto cavity = data[i][j]-'0';
        if (cavity > (data[i][j+1]-'0') && 
            cavity > (data[i][j-1]-'0') &&
            cavity > (data[i-1][j]-'0') &&
            cavity > (data[i+1][j]-'0'))
            data[i][j] = 'X';
    }    
}

for (const auto& row : data)
{
    copy(begin(row), end(row), ostream_iterator<char>(cout));
    cout << endl;
}

Here is an alternative Python 3 solution, suggested by Alessandro Cicerale:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


import os
import numpy as np


def cavityMap(grid):
    array_2d = np.array([list(row) for row in grid], dtype=np.int8)
    n = len(grid)
    inner = array_2d[1:-1, 1:-1]
    is_peak = (inner > array_2d[0:-2, 1:-1]) & (inner > array_2d[2:, 1:-1]) & (inner > array_2d[1:-1, 0:-2]) & (inner > array_2d[1:-1, 2:])
    cavities = np.pad(is_peak, pad_width=1, mode='constant', constant_values=False)

    result = []
    for i in range(n):
        row = list(grid[i])
        for j in range(len(row)):
            if cavities[i][j]:
                row[j] = 'X'
        result.append(''.join(row))

    return result

This version differs from the previous one because it uses NumPy array slicing to compare all inner cells with their four neighbors at once, instead of checking them one by one with nested loops. The final reconstruction of the output grid is still done row by row, but the cavity detection step is vectorized. To run this solution, the NumPy dependency is required.

ad hoc