上个星期五，在法国节目比赛中，我们得到了纸张折叠问题，如下：
- 给一张方纸和一个折叠图案，写一个
函数“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
现在是有趣的部分。
- 编写一个函数展开（顺序），对于给定的结果层
排序，给出产生这种排序的模式。注意
展开（折叠（“LRTB”））=>“LRTB”
然后我的大脑停止工作了一段时间，我没有时间（总共4小时还剩2小时）来提出足够快的解决方案。
我最初的想法是：
试着暴力吧。因为我们知道输入的长度是N ^ 2，所以我们可以创建一个初始矩阵并尝试所有可能的折叠，直到我们达到与输入相同的顺序。 O（4 ^ N）复杂性，不可行。
蛮力逆转。从输入开始，尝试所有展开的可能性，直到我们达到正确的初始状态。好一点，但仍然太慢。
???
有人有想法吗？
在每一步中，您只需要知道列表的第一个元素和最后一个元素。如果第一个元素应该在最后一个元素的左侧，则保留折叠方向（同上，右上，下）。
在每一步中，您只需要知道列表的第一个元素和最后一个元素。如果第一个元素应该在最后一个元素的左侧，则保留折叠方向（同上，右上，下）。
这是我的尝试。这听起来很容易，但像往常一样，魔鬼在细节中。
第一， 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
我跑了几个测试，它通过了......