(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...