There are a few idiomatic approaches to Minesweeper. The most common approach is some variant of iterating over each square of the board, counting the mines in the 8 neighboring squares (being sure to correctly handle the edges and corners of the board that do not have all 8 neighbors), and outputting the appropriate character according to whether the current square has a mine and what the surrounding count is: '*' if the current square has a mine, a space for a count of 0, otherwise the count as a single digit.
There are other possible approaches that are a bit more optimized than this straightforward approach, reducing redundant calculations that can be shared between neighboring squares.
All approaches have to deal with how best to index into the minefield and how best to map a count of neighboring mines to the appropriate output character.
Given the requirements of the exercise and the test cases provided, namely that all input is ASCII, it is probably simplest and most efficient to index into the minefield rows using row.as_bytes()[idx] but other approaches are possible, like using row.chars().enumerate() or row.chars().nth(idx).
Mapping the surrounding mine count to the required output character can be done using a lookup table or by using char::from_digit(count, 10) and handling 0 as a special case.
It's worth noting that squares with a mine in will be represented in the output as '*' rather than as a count of neighboring mines. This means that the neighboring mine count can include the current square rather than only the 8 neighboring squares, as if the current square contains a mine the count will not be displayed. This fact can be used to simplify or optimize certain approaches.
Probably the most common approach is a pair of nested map() calls: the outer mapping over the rows of the board (the &strs from the input slice of &strs) and the inner mapping over the columns within each row (the characters within the &str for each row).
For each square, the mines in the 8 surrounding squares are counted and the appropriate character for the output square is produced. The results for each row are collected into a String and the rows are collected into a Vec<String>.
pub fn annotate(minefield: &[&str]) -> Vec<String> {
let mine_count = |row: usize, col: usize| ...
(0..minefield.len())
.map(|row| {
(0..minefield[row].len())
.map(|col| match minefield[row].as_bytes()[col] {
b'*' => '*',
_ => " 12345678".as_bytes()[mine_count(row, col)] as char,
})
.collect()
})
.collect()
}
This same basic approach can also be implemented in a more imperative style by declaring a mutable output Vec<String> and filling it in using nested for loops.
The mine count can be calculated in a few different ways. For more information, check the nested maps approach.
Counting all the surrounding mines for each square involves some redundant work. The nested maps approach with a mine count for each square is essentially the same operation as an image filter with a 3x3 filter kernel, where the 'image' contains 1 for a mine ('*') and 0 for no mine (' '). If we use the observation from earlier that we can count a mine in the current square (since squares with a mine will output '*' rather than a count) then this filter kernel is all 1s.
+---+---+---+---+---+
| * | | | | * |
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
| | * | | | |
+---+---+---+---+---+
+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 1 |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+
| 0 | 1 | 0 | 0 | 0 |
+---+---+---+---+---+
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
| 1 | 1 | 1 |
+---+---+---+
+-----+-----+-----+---
| 1*1 | 0*1 | 0*1 |
+-----+-----+-----+---
| 0*1 | 0*1 | 0*1 |
+-----+-----+-----+---
| 0*1 | 1*1 | 0*1 |
+-----+-----+-----+---
Sum: 1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 = 2
If we think of sliding this filter kernel along a row one square at a time it should be clear that two of the three columns remain the same, one rolls off to the left and a new one rolls in from the right. By keeping track of columns calculated for previous squares we can use this fact to reduce the new work for each square from summing up 9 numbers to summing up 3.
Scan or prefix sum is a useful building block for algorithms. It is like a combination of map and fold - where map only looks at each element in a sequence in isolation and produces a new sequence, and fold carries state across multiple elements of a sequence to accumulate a result, scan carries state across elements but outputs the intermediate state along the way.
In Rust, scan takes two arguments: an initial value for the internal state and a closure with two arguments, the first being a mutable reference to the internal state and the second being an iterator element. The closure is applied to each element of the iterator and returns an Option of either Some transformed element value or None to end the iteration.
We can use scan to keep track of our sliding filter window and so reduce the amount of work required compared to the nested maps approach, where the state is an array of 3 elements tracking the mine count for each of the current 3 columns of our 3x3 filter:
pub fn annotate(minefield: &[&str]) -> Vec<String> {
let vertical_mine_count = |r: usize, c: usize| {
minefield[r.saturating_sub(1)..(r + 2).min(minefield.len())]
.iter()
.filter(|&&s| s.as_bytes().get(c).map_or(false, |&ch| ch == b'*'))
.count()
};
(0..minefield.len())
.map(|r| {
(0..minefield[r].len())
.scan([0, 0, vertical_mine_count(r, 0)], |st, c| {
*st = [st[1], st[2], vertical_mine_count(r, c + 1)];
(minefield[r].as_bytes()[c] == b'*')
.then_some('*')
.or_else(|| Some(" 12345678".as_bytes()[st[0] + st[1] + st[2]] as char))
})
.collect()
})
.collect()
}
In this approach, instead of counting mines in all the surrounding squares for each square in a row, we just count the 3 mines in the filter column to the right of our current square and reuse the counts for the central and left hand columns from previous iterations, reducing the number of additions we have to do for each column from 7 to 4.
This type of approach gains more of an advantage the larger the filter kernel is so it is a common optimization in image processing algorithms where filter kernels can get much larger than 3x3.
Viewing this problem through the lens of image processing suggests another approach: a separable filter.
Our 2D filter of all 1s is separable so we can split it into 2 1D passes, a horizontal pass applying a 1x3 filter and a vertical pass applying a 3x1 filter to the results of the horizontal pass.
Here's an implementation of the separable filter approach:
pub fn annotate(minefield: &[&str]) -> Vec<String> {
let horizontal_pass: Vec<Vec<u8>> = (0..minefield.len())
.map(|r| {
(0..minefield[r].len())
.map(|c| {
minefield[r].as_bytes()[c.saturating_sub(1)..(c + 2).min(minefield[r].len())]
.iter()
.filter(|&&b| b == b'*')
.count() as u8
})
.collect()
})
.collect();
(0..minefield.len())
.map(|r| {
(0..minefield[r].len())
.map(|c| {
let sum = horizontal_pass[r][c]
+ if r > 0 { horizontal_pass[r - 1][c] } else { 0 }
+ if r + 1 < minefield.len() { horizontal_pass[r + 1][c] } else { 0 };
match minefield[r].as_bytes()[c] {
b'*' => '*',
_ => " 12345678".as_bytes()[sum as usize] as char,
}
})
.collect()
})
.collect()
}
This approach also reduces the number of operations relative to visiting the full 3x3 region at each square but the implementation here does involve allocating an extra temporary grid for the horizontal pass. This could be optimized further to eliminate the need for a full grid sized temporary buffer but that is left as an exercise for the reader!