fork(5) download 
  1. import scala.collection._
  2.  
  3. class Bag[E] private (val items: Map[E, Int]) {
  4.   def isEmpty = items.isEmpty
  5.   def view = items.keys
  6.   def -(item: E) = new Bag[E](items(item) match {
  7.     case 1 => items - item
  8.     case n => items.updated(item, n - 1)
  9.   })
  10. }
  11.  
  12. object Bag {
  13.   def apply[E](items: Traversable[E]): Bag[E] = {
  14.     val itemCounts = mutable.HashMap.empty[E, Int].withDefaultValue(0)
  15.     items.foreach(itemCounts(_) += 1)
  16.     new Bag[E](itemCounts)
  17.   }
  18. }
  19.  
  20. object Main extends App {
  21.   type Solution = Option[Seq[(String, String)]]
  22.  
  23.   def solve(items: Bag[String], anagrams: String, matches: Solution = None): Solution =
  24.     if (items.isEmpty) matches
  25.     else (for {
  26.       item <- items.view
  27.       (label, rest) = anagrams.splitAt(item.length)
  28.       if item == label.sorted
  29.       newMatches = Option(matches.getOrElse(immutable.Queue.empty) :+ (item, label))
  30.       solution <- solve(items - item, rest, newMatches)
  31.     } yield solution).headOption
  32.  
  33.   val items = readLine().split(" ")
  34.   val anagrams = readLine()
  35.  
  36.   val sortedItems = mutable.Buffer.empty[String]
  37.   val itemOrderRestorator = mutable.Map.empty[String, mutable.Queue[String]]
  38.  
  39.   for (item <- items) {
  40.     val sorted = item.sorted
  41.     sortedItems += sorted
  42.     itemOrderRestorator.getOrElseUpdate(sorted, new mutable.Queue).enqueue(item)
  43.   }
  44.  
  45.   solve(Bag(sortedItems), anagrams).map(_.unzip) match {
  46.     case None => println("Ne fart")
  47.     case Some((items, labels)) =>
  48.       println(labels.mkString(" "))
  49.       items.foreach(s => print(itemOrderRestorator(s).dequeue() + " "))
  50.   }
  51. }
Success #stdin #stdout 0.44s 383168KB
comments (?)
stdin 
abab ab ab ab ab ab ab ab ab ab ab ab
abababababababababababaabb
stdout 
ab ab ab ab ab ab ab ab ab ab ab aabb
ab ab ab ab ab ab ab ab ab ab ab abab
https://ideone.com/8AKTBi
language:
Scala (scala 2.12.8)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!