Naloga6.scala

import java.util.Scanner
import collection.mutable.{Map,ListBuffer,Queue}

object Naloga6{
  def main(args: Array[String]){
    val start = args(0)
    val pathMode = args.length == 2
    val end = if(pathMode) args(1) else start.sorted
    val graph = new Graph()
    
    val sc = new Scanner(System.in)
    while(sc.hasNextLine){
        val word = sc.nextLine
        graph.insertNode(new GraphNode(word, if(pathMode) word==end else word.sorted == end && word!=start))  
    }
    
    graph.search(start)
    for{
      node <- graph.nodes.values if node.target && !node.parents.isEmpty
    } node.printPathToHere()
  } 
}

class GraphNode(val key: String, val target: Boolean){
  val edges, parents = ListBuffer[GraphNode]()
  var cost = Int.MaxValue
  var visited = false
  
  def printPathToHere(): Unit = printPathToHere("")
  
  private def printPathToHere(alsoPrint: String): Unit = 
    if(parents.isEmpty) println(key+alsoPrint)
    else parents.foreach(_.printPathToHere("->"+key+alsoPrint))
}

class Graph {
  val nodes = Map[String,GraphNode]()

  def insertNode(node: GraphNode){
    nodes.values.filter(n => diff(n.key, node.key) ==1 ).foreach{ n =>
      n.edges append node
      node.edges append n
    }
    nodes.put(node.key, node)
  }
  
  def diff(s1:String, s2:String)= s1 zip s2 filter {case (a,b)=>a!=b} length

  def search(startKey: String){
    val queue = Queue[GraphNode]()
    val start = nodes(startKey)
    start.cost = 0
        
    def step(node: GraphNode){
      if(node.target) return
      if(!node.visited){
        node.edges.foreach{ edge =>
          if(edge.cost > node.cost + 1) edge.parents.clear()
          if(edge.cost > node.cost){
            edge.cost = node.cost + 1
            edge.parents append node
          }
          if(!edge.visited) queue enqueue edge
        }
      }
      node.visited = true
      if(!queue.isEmpty) step(queue.dequeue)
    }
    step(start)
  }
}