[Community puzzle] Zergling rush

Puzzles
#1

This topic is about the puzzle Zergling rush.

Feel free to send your feedback or ask some help here!

#2

I am stuck with the impassable obstacles as I kind of thinking there must be a simpler way other than checking the relation between each obstacles one by one. Any ideas or advice would be appreciated.

#3

Think like Zergling, from each cell on the sides of the map (top, bottom, left, right) try to fill all the map, and if you touch a building (even diagonally) put a “z” there.

1 Like
#4

You can use the algorithm of Disjoint-set. (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

It easy to program and have low cost of execution.

#5

You could also reverse it. For all locations adjacent to a building, see if there’s a path outside. I guess the flood-fill is more efficient.

#6

Are you saying that the correct solution for map:
.#.
#B#
.#.

will be
z#z
#B#
z#z
Doesn’t this contradict the statement that zerglings will surround only the buildings that they can reach? To me it looks like the building can’t be reached so no zerglings should be displayed.

Note that I’m currently unable to pass validator 3 on submission so just trying to understand what exactly did I miss.

#7

From the statement:

Zerglings will surround all enemy buildings they can reach, taking up horizontally, vertically, and diagonally adjacent cells

So yes, Zerglings will stick to buildings even diagonally

#8

My confusion here is that the building can’t actually be reached since zerglings can’t move diagonally - they can only surround diagonally as long as there is a horizontal or vertical path to the building.

Anyway, even with this adjustment I still can’t pass the validator :frowning:

#9

Move on X-Y axis, “capture” on X-Y AND diagonal.
I solved it this way, a pathfinder that moves on X-Y but captures also on diagonal.

#10

I used the exact same strategy but moved from buildings towards borders. Now I changed to move from borders and all validators passed. It’s a pity the validator test cases aren’t available even after the puzzle is 100% solved, because I’m too curious to find what my bug was :slight_smile:

Thanks for the hint

#11

Hi, I think there’s a bug with the Lua validator. I can’t pass any validators or testcases even tough my output seems right.
For instance, I got with the first test case
Standard Output Stream:
…
.zzz.
.zBz.
.zzz.
…

Failure
Found:    Nothing
Expected: Nothing

But if I take this exact same testcase into custom it pass.

#12

@Manzazuu: You might have an extra new line at the end of the output. That was the issue in my case on another puzzle.