Disco Zoo animal hunt

Question

This question is inspired by the game Disco Zoo

Background

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.

Task

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

Another example:

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 X and O or the name of the animal.
Output: a 5x5 grid made of X or O where X marks an optimum strategy.

Answer 1

Ruby 221

->a{l=a.join(?o*(5-w=a[0].size))
s=?o*25
q=(0..25-l.size).select{|i|i/5==(i+w-1)/5}.map{|i|(?o*i+l+s)}
(h=q[0].size.times.map{|i|q.count{|p|p[i]<?o}}
s[c=h.index(h.max)]=?X
q.reject!{|p|p[c]<?o})while q!=[]
s.scan /.{5}/}

Input and Output

This is a Ruby function that takes one parameter representing the animal and returns the solution, both being represented as string arrays.

For example, the Hippo is represented as:

['XoX',
 'ooo',
 'XoX']

and its solution is:

['ooooo',
 'oXXoo',
 'oXXoo',
 'ooooo',
 'ooooo']

Test

Here's a working version. Feel free to experiment with it and enter more animals as parameters.

Algorithm

I found this problem very interesting and I experimented to solve it in different ways, including brute force, which is less feasible, but possible for the given inputs (it would be terribly inefficient for the input ['X'] though).

The algorithm I found to be the most efficient is the following:

1. Compute all possible positions for the animal on the 5x5 board
2. Given the existing positions, compute a map of frequencies for each of the 25 cells
3. Take one of the cells that contain the max number of "hits" and make it part of the solution. Exclude all positions that are "hit" in that particular cell.
4. Repeat steps 2-3 until there are no positions left.

I don't have a proof of optimality for this algorithm, but it tested most animals present on the wiki page and it returned optimal solutions for all.

Note that for some animals the solutions are not identical to the ones presented in the wiki, but involve the same number of blocks.

For example, the Wooly Rhino page presents this solution:

ooooo
ooooo
oXXXo
ooooo
ooooo

and the algorithm returns this one:

ooooo
oooXo
ooXXo
ooooo
ooooo

which is also correct and optimal (3 blocks).

Here's the (slightly more) readable version of the program:

SIZE = 5

# return all possible placements for the animal on a 5x5 board
def get_placements(animal)
  # represent the 5x5 board and the animal as linear arrays
  linear_animal = animal.join(?o*(SIZE - animal[0].size))
  d = SIZE*SIZE
  (0..d-linear_animal.size)
    .select{|i| i/5 == (i+animal[0].size-1)/5} # to avoid wrap-around positions
    .map { |i|
      (?o*i + linear_animal + ?o*d)[0...d]
    }
end

# given a set of possible placements,
# return a map of frequencies for every cell
def heatmap(placements)
  placements[0].size.times.map do |i|
    placements.count {|p|p[i] < ?o}
  end
end

# given an animal, return the solution as an array of 5 5-character strings
def solve(animal)
  placements = get_placements animal
  solution = []

  while placements.any?
    h = heatmap(placements)

    solution << chosen = h.index(h.max)

    placements = placements.reject {|pl| pl[chosen] < ?o }
  end

  (0...25).map{|i| solution.include?(i) ? ?X : ?o }.join.scan /.{5}/
end

Answer 2

Python3, 474 bytes

R=range
E=enumerate
V=lambda d,p,X,Y:not all((x+X,y+Y)in d for x,y in p)
def f(p):
 d={(x,y):[]for x in R(5)for y in R(5)}
 p=[(x,y)for x,r in E(p)for y,v in E(r)if'X'==v]
 X,Y,C=0,0,0
 while 1:
  C+=1
  Q,W=[],[]
  for x,y in p:d[(x+X,y+Y)]+=[C]
  Y+=1
  if V(d,p,X,Y):
   if V(d,p,X:=X+1,Y:=0):break
 M=[]
 while any(d.values()):t=max(d,key=lambda x:len(d[x]));M+=[t];d={i:{*d[i]}-{*d[t]}for i in d}
 s=[['0'for _ in R(5)]for _ in R(5)]
 for x,y in M:s[x][y]='1'
 return s

Try it online!