anagram-seeker-so.scala

import scala.collection._

class Bag[E] private (val items: Map[E, Int]) {
  def isEmpty = items.isEmpty
  def view = items.keys.view
  def -(item: E) = new Bag[E](items(item) match {
    case 1 => items - item
    case n => items.updated(item, n - 1)
  })
}

object Bag {
  def apply[E](items: Traversable[E]): Bag[E] = {
    val itemCounts = mutable.HashMap.empty[E, Int].withDefaultValue(0)
    items.foreach(itemCounts(_) += 1)
    new Bag[E](itemCounts)
  }
}

object Main extends App {
  type Solution = Option[Seq[(String, String)]]

  def solve(items: Bag[String], anagrams: String, matches: Solution = None): Solution =
    if (items.isEmpty) matches
    else (for {
      item <- items.view
      (label, rest) = anagrams.splitAt(item.length)
      if item == label.sorted
      newMatches = Option(matches.getOrElse(immutable.Queue.empty) :+ (item, label))
      solution <- solve(items - item, rest, newMatches)
    } yield solution).headOption

  val items = io.StdIn.readLine().split(" ")
  val anagrams = io.StdIn.readLine()

  val sortedItems = mutable.Buffer.empty[String]
  val itemOrderRestorator = mutable.Map.empty[String, mutable.Queue[String]]

  for (item <- items) {
    val sorted = item.sorted
    sortedItems += sorted
    itemOrderRestorator.getOrElseUpdate(sorted, new mutable.Queue).enqueue(item)
  }

  solve(Bag(sortedItems), anagrams).map(_.unzip) match {
    case None => println("Ne fart")
    case Some((items, labels)) =>
      println(labels.mkString(" "))
      items.foreach(s => print(itemOrderRestorator(s).dequeue() + " "))
  }
}

// ab ba abab
// ababaabb

// abab ab ab ab ab ab ab ab ab ab ab ab
// abababababababababababaabb

// abab abab abab abab abab abab abab abab abab abab abab abab abab abab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab ab
// ababababababababababababababababababababababababababababaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabbaabb

//  val items = Set("ab", "ba", "abab")
//  val anagrams = "ababaabb"

/*  def solve(items: Bag[String], anagrams: String) = {
    def branch(trial: String, position: Int, candidates: Bag[String]): Option[Seq[(String, String)]] = {
      val label = anagrams.substring(position, position + trial.length)
      if (trial == label.sorted) {
        if (candidates.isEmpty) Option(Seq((trial, label)))
        else candidates.view
          .map(newTrial => branch(newTrial, position + trial.length, candidates - newTrial))
          .find(_.isDefined).flatten.map((trial, label) +: _)
      } else None
    }
    items.view.map(item => branch(item, 0, items - item)).find(_.isDefined).flatten
  }*/