This question is inspired by the game Disco Zoo
Disco Zoo is a game where you can go into the wild and rescue animals. Once you have found an animal you can put it in your zoo for your visitors to see.
To find animals you first select a field to search, and you get to see a 5x5 grid where the animals are hiding. At the top of the screen you can see which animals are hiding in the field.
Each animal has a different pattern, which never changes for the same animal. E.g. (
X is pattern,
o is padding)
Animal=Sheep Animal=Unicorn Pattern: Pattern: XXXX Xoo oXX
Some animals use 2 blocks, some 3 and some 4. The pattern will be translated, but not rotated.
The user gives you a pattern or the name of an animal (your choice) and you have to generate an optimum strategy to search for that animal/pattern. A strategy is a set of blocks from the 5x5 grid; an optimum strategy is one which guarantees to find at least 1 block from the pattern, and where there is no strategy with fewer blocks which can make the same guarantee.
For sheep and unicorns the optimum strategy would be searching the middle column:
ooXoo ooXoo ooXoo ooXoo ooXoo
Animal: Hippo Pattern: Optimum strategy: ooooo XoX oXXoo ooo oXXoo XoX ooooo ooooo
The Disco Zoo wiki's Patterns page lists all the animals and their patterns. You may hard-code the patterns. The wiki also lists optimum strategies for all the animals. Feel free to look at them but you're not allowed to hard-code them.
Input: Either a pattern made of
O or the name of the animal.
Output: a 5x5 grid made of
O where X marks an optimum strategy.