(Un), складывая лист бумаги в соответствии с рисунком и задавая порядок слоев

В прошлую пятницу на французском конкурсе программирования нам была задана проблема с бумажной складкой, которая была следующей:

• Учитывая квадратный лист бумаги и складной узор, напишите функция "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

Теперь идет интересная часть.

• Напишите функцию разворачивания (порядка), которая будет, для заданного результирующего слоя упорядочивая, дайте шаблон, который произвел это упорядочение. Обратите внимание, что развернуть (fold ( "LRTB" )) = > "LRTB"

И тогда мой мозг прекратил работать некоторое время, и у меня не было времени (2 часа осталось от 4 часов), чтобы придумать достаточно быстрое решение.

Мои первоначальные идеи:

• Попробуйте переборщить его. Поскольку мы знаем, что длина ввода N ^ 2, мы можем создать начальную матрицу и попробовать все возможное сгибание до тех пор, пока мы не достигнем того же порядка, что и вход. O (4 ^ N), не являются жизнеспособными.

• Перемещение в обратном направлении. Начните с ввода и попробуйте все возможности разворачивания, пока мы не достигнем правильного начального состояния. Чуть лучше, но все же слишком медленно.

• ???

У кого-нибудь есть идея?

Ответы

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

  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