11

上周五，在一次法语编程比赛中，我们得到了一个折纸问题，如下：

给定一张方形纸和一个折叠图案，编写一个函数“fold(pattern)”，该函数将给出层的顺序，该顺序将由纸张相对于图案的累积折叠（一半）产生。

这可能不是很清楚，所以让我解释一下（如果你愿意走那么远来帮助我，手边有一张方形纸可能有助于理解）。

假设我们有一张正方形的纸，我们在上面画了一个 N*N 网格，然后对它的所有内部正方形进行编号。给定一个“LTRB”模式，我们将把这张纸垂直对折，然后把得到的左边部分放在右边部分。然后，我们将它水平折叠并将顶部放在底部。然后，我们将它再次垂直折叠并将右侧部分放在左侧部分上。最后，我们将它水平折叠并将底部放在顶部。这给我们留下了一张大小为一个正方形和 N^2 层的纸。预期的答案是每个原始正方形的结果顺序。

例如，如果我们在一张正方形纸上绘制一个 2*2 的网格，然后将每个内部正方形从 1 到 4 编号（从左上到右下，水平方向），并给定图案“LT”，我们将有发生这种情况：

fold("LT"):

 1 | 2   L  1,2  T
---|--- ==> --- ==> 2,1,3,4
 3 | 4      3,4

并带有“RB”模式，例如：

fold("RB"): 

 1 | 2   R  2,1  B
---|--- ==> --- ==> 3,4,2,1
 3 | 4      4,3

正如您可能已经猜到的那样，它基本上可以归结为 N*N 矩阵的递归变换。这是简单的部分，这是我的解决方案：

http://ideone.com/QaXGq

现在是有趣的部分。

  • 编写一个函数展开(order)，对于给定的结果层排序，它会给出产生这种排序的模式。请注意，展开（折叠（“LRTB”））=>“LRTB”

然后我的大脑停止工作了一段时间，我没有时间（总共 4 小时还剩 2 小时）想出一个足够快的解决方案。

我最初的想法是：

  1. 尝试暴力破解它。因为我们知道输入的长度是 N^2，所以我们可以创建一个初始矩阵并尝试所有可能的折叠，直到我们达到与输入相同的顺序。O(4^N) 复杂度，不可行。

  2. 蛮力逆转。从输入开始，尝试所有展开的可能性，直到我们达到正确的初始状态。稍微好一点，但还是太慢了。

  3. ？？？

有人有想法吗？

4

2 回答 2

9

在每个步骤中，您只需要知道列表的第一个元素和最后一个元素。如果第一个元素应该在最后一个元素的左侧，则折叠方向为左（同上，右、上和下）。

于 2012-05-07T16:39:36.947 回答
2

这是我的尝试。这听起来很简单，但像往常一样，魔鬼在细节中。

首先，fold：

  type Matrix = IndexedSeq[IndexedSeq[IndexedSeq[Int]]]

  def initial(folds: Int): Matrix = {
    val sideLen = math.pow(2, folds / 2).toInt
    (1 to sideLen * sideLen) map (Vector(_)) grouped sideLen toIndexedSeq
  }

  def leftFold (m: Matrix): Matrix = m map { r => 
    val (a, b) = r splitAt (r.size / 2) 
    (a.reverse, b).zipped map (_.reverse ++ _)
  }

  def rightFold(m: Matrix): Matrix = m map { r => 
    val (a, b) = r splitAt (r.size / 2) 
    (b.reverse, a).zipped map (_.reverse ++ _)
  }

  def topFold   (m: Matrix): Matrix = leftFold(m.transpose).transpose
  def bottomFold(m: Matrix): Matrix = rightFold(m.transpose).transpose

  def fold(input: String): Seq[Int] = {
    def go(in: String, m: Matrix): Seq[Int] = in match {
      case "" => m(0)(0)
      case s  => go(s.tail, s.head match {
        case 'L' => leftFold(m)
        case 'R' => rightFold(m)
        case 'T' => topFold(m)
        case 'B' => bottomFold(m)
      })
    }
    go(input, initial(input.length))
  }

二、unfold：

  def unfold(input: Seq[Int]): String = { 
    val m0: Matrix = Vector(Vector(Vector(input: _*)))
    val sideLen = math.sqrt(input.length).toInt 

    def go(m: Matrix, out: String): String = {
      val tl = m.head.head
      val bl = m.last.head
      val tr = m.head.last
      if (m.length == sideLen && m.head.length == sideLen) out.reverse
      else if (tl.head == tl.last - 1)       go(leftUnfold(m),   out + 'L')
      else if (tr.head == tr.last + 1)       go(rightUnfold(m),  out + 'R')
      else if (tl.head == tl.last - sideLen) go(topUnfold(m),    out + 'T')
      else if (bl.head == bl.last + sideLen) go(bottomUnfold(m), out + 'B')
      else sys.error("no fold found " + m) 
    }
    go(m0, "")
  }    

  def leftUnfold (m: Matrix): Matrix = m map { r =>
    val (a, b) = r.map(e => e.splitAt(e.size / 2)).unzip
    a.map(_.reverse).reverse ++ b
  }

  def rightUnfold(m: Matrix): Matrix = m map { r =>
    val (a, b) = r.map(e => e.splitAt(e.size / 2)).unzip
    b ++ a.map(_.reverse).reverse
  }

  def topUnfold   (m: Matrix): Matrix = leftUnfold (m.transpose).transpose
  def bottomUnfold(m: Matrix): Matrix = rightUnfold(m.transpose).transpose

我跑了几个测试，它通过了...

于 2012-05-08T05:12:32.970 回答