迪斯科动物园动物狩猎

Question

这个问题是由游戏迪斯科动物园激发的。

背景

迪斯科动物园是一种游戏，你可以到野外去拯救动物。一旦你找到了一只动物，你就可以把它放在动物园里，让游客看看。

要找到动物，你首先要选择一个字段来搜索，然后你就可以看到一个5x5的网格，这些动物躲在那里。在屏幕的顶部，你可以看到哪些动物躲在田野里。

每种动物都有不同的模式，对同一种动物来说，这种模式永远不会改变。例如(X是模式，o是填充)

Animal=Sheep    Animal=Unicorn
Pattern:        Pattern:  

 XXXX            Xoo
                 oXX

有些动物使用2块，一些3和4。模式将被翻译，但不旋转。

任务

用户给出一个模式或动物的名称(您的选择)，您必须生成一个搜索该动物/模式的最佳策略。策略是来自5x5网格的一组块；最优策略是保证从模式中找到至少一个块的策略，并且没有能够保证相同保证的块较少的策略。

对于绵羊和独角兽来说，最佳的策略是搜索中间栏：

ooXoo
ooXoo
ooXoo
ooXoo
ooXoo

另一个例子是：

Animal: Hippo  
Pattern:       Optimum strategy:
               ooooo
 XoX           oXXoo
 ooo           oXXoo
 XoX           ooooo
               ooooo

迪斯科动物园维基的模式页面列出了所有的动物和它们的模式。你可以对模式进行硬编码。wiki还列出了所有动物的最佳策略。你可以随便看看，但你不允许硬编码。

输入:由X和O构成的图案或动物的名称。

输出:由X或O组成的5x5网格，其中X表示最佳策略。

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}/}

输入输出

这是一个Ruby函数，它接受一个表示动物的参数并返回解决方案，两者都表示为字符串数组。

例如，河马被表示为：

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

其解决办法是：

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

测试

这是一个工作版本。可以自由地用它做实验，并输入更多的动物作为参数。

算法

我发现这个问题非常有趣，我尝试用不同的方法来解决它，包括蛮力，这是不可行的，但是对于给定的输入来说是可能的(但是对于输入['X']来说，这是非常低效的)。

我发现最有效的算法如下：

1. 计算动物在5x5板上的所有可能位置。
2. 给定现有位置，计算25个单元中每个单元的频率图。
3. 取一个包含最大“点击”数的单元格，并将其作为解决方案的一部分。排除在特定单元格中“命中”的所有位置。
4. 重复步骤2-3，直到没有剩下的位置.

对于这个算法，我没有最优性的证明，但它测试了维基页面上的大多数动物，并返回了所有人的最优解。

请注意，对于某些动物来说，解决方案与wiki中的解决方案并不相同，而是涉及相同数量的块。

例如，羊毛犀牛页提供了这个解决方案：

ooooo
ooooo
oXXXo
ooooo
ooooo

该算法返回这个算法：

ooooo
oooXo
ooXXo
ooooo
ooooo

这也是正确和最优的(3块)。

下面是这个程序的(稍微更易读的)版本：

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