(Un)folding a sheet of paper according to a pattern and giving the order of the layers
At each step you only need to know the first element and the last element of your list. If the first element should be on the left of the last one, then the folding direction was left (idem with right, top and bottom).
Here's my attempt. It sounds pretty easy but as usual the devil is in the detail.
First, 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))
}
Second, 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
I ran a few tests and it passed...