fork(4) download
copy 
  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.   def solve(items: Bag[String], anagrams: String) = {
  22.     def branch(trial: String, position: Int, candidates: Bag[String]): Option[Seq[(String, String)]] = {
  23.       val label = anagrams.substring(position, position + trial.length)
  24.       if (trial == label.sorted) {
  25.         if (candidates.isEmpty) Option(Seq((trial, label)))
  26.         else candidates.view
  27.           .map(newTrial => branch(newTrial, position + trial.length, candidates - newTrial))
  28.           .find(_.isDefined).flatten.map((trial, label) +: _)
  29.       } else None
  30.     }
  31.     items.view.map(item => branch(item, 0, items - item)).find(_.isDefined).flatten
  32.   }
  33.  
  34.   val items = readLine().split(" ")
  35.   val anagrams = readLine()
  36.  
  37.   val sortedItems = mutable.Buffer.empty[String]
  38.   val itemOrderRestorator = mutable.Map.empty[String, mutable.Queue[String]]
  39.  
  40.   for (item <- items) {
  41.     val sorted = item.sorted
  42.     sortedItems += sorted
  43.     itemOrderRestorator.getOrElseUpdate(sorted, new mutable.Queue).enqueue(item)
  44.   }
  45.  
  46.   solve(Bag(sortedItems), anagrams) match {
  47.     case None => println("Ne fart")
  48.     case Some(solution) =>
  49.       val (items, labels) = solution.unzip
  50.       labels.foreach(s => print(s + " "))
  51.       println()
  52.       items.foreach(s => print(itemOrderRestorator(s).dequeue() + " "))
  53.   }
  54. }
Success #stdin #stdout 0.44s 382144KB
comments (?)
stdin
copy 
abab ab ab ab ab ab ab ab ab ab ab ab
abababababababababababaabb
stdout
copy 
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/NLxEFs
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!