The wasp nests in the nursery
- O(n²) · Very hard
- Full plan
- Python
- JavaScript
- grids
- strings
- loops
Problem
Don Aurelio keeps his plant nursery laid out in even squares, and this year wasp nests showed up among the seedlings. Before he sends anybody out to water, he wants the map marked up: on every free square, how many nests are next to it.
Write a function that takes nursery, a list of strings of the same length. Each string is a row of squares: * is a square with a nest and a space is a free square. The nursery is at most 12 rows by 12 squares, and it may come in empty or with empty rows.
Return a new list of strings, the same size. The * stay where they are, and every free square holds a digit: how many of the eight squares around it have a nest, the four beside it and the four on its corners. A free square with no nest around it stays a space, not a 0.
With [" ", " * ", " "] the nest in the middle is next to all eight squares around it, so you return ["111", "1*1", "111"]. With ["* *"] the middle square has no nest next to it and stays a space: ["*1 1*"].
Examples
The nest in the middle
[" ", " * ", " "] → ["111", "1*1", "111"]
A row with nests at both ends
["* *"] → ["*1 1*"]
A nursery with no nests
[" ", " ", " "] → [" ", " ", " "]
Nothing but nests
["***", "***", "***"] → ["***", "***", "***"]
A free square ringed by nests
["***", "* *", "***"] → ["***", "*8*", "***"]
Two nests in the same row
[" * * "] → ["1*2*1"]
Besides these, the challenge has hidden tests that are revealed when you submit your solution.
You start with this
Python
def mark_nests(nursery):
passJavaScript
function markNests(nursery) {
}It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.