Disco Zoo animal hunt
Ruby 221



-&gt;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]&lt;?o}}
s[c=h.index(h.max)]=?X
q.reject!{|p|p[c]&lt;?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:


Compute all possible positions for the animal on the 5x5 board
Given the existing positions, compute a map of frequencies for each of the 25 cells
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.
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] &lt; ?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 &lt;&lt; chosen = h.index(h.max)

    placements = placements.reject {|pl| pl[chosen] &lt; ?o }
  end

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