IPSum.scala

import java.io.FileInputStream
import java.io.FileOutputStream;
import scala.collection.mutable.Map

object IPSum extends App {
  case class IPv4( bits:String, mask:Int )

  def friendIp(ipv4:IPv4) : IPv4 = {
    val lastIndex = ipv4.bits.size -1
    val flipped = if(ipv4.bits(lastIndex) == '0') '1' else '0'
      
    IPv4(ipv4.bits.substring(0, lastIndex) + flipped, ipv4.mask)
  }
  
  def cutIp(ipv4:IPv4) : IPv4 = {
    val lastIndex = ipv4.bits.size -1
    IPv4(ipv4.bits.substring(0, lastIndex), ipv4.mask - 1)
  }
  
  def bitToIpStr(ipv4:IPv4) : String = {
    val ipstr = ipv4.bits + ("0" * (32 - ipv4.mask))
    
    val pos = List(8, 16, 24, 32)
    val ip = pos.map { x => ipstr.substring(x - 8, x) }.map { x => Integer.parseInt(x, 2)}.mkString(".")
    ip + "/" + ipv4.mask
  }
  
  def addToMap(map : Map[String, IPv4], ipv4:IPv4) : Unit = {
	  if (map.contains(friendIp(ipv4).bits)) {
		  map.remove(friendIp(ipv4).bits)
		  val cut = cutIp(ipv4)
		  addToMap(map, cut)
	  } else {
      if (!map.contains(ipv4.bits)) {
  		  map.put(ipv4.bits, ipv4)
  	  }
	  }
  }
    
  
  def solve(ipv4s : Seq[IPv4]) = {
    val mergeIpMap = Map[String, IPv4]()
    
    mergeIpMap.put(ipv4s.head.bits, ipv4s.head)
    
    for(ipv4 <- ipv4s.tail) {
      addToMap(mergeIpMap, ipv4)
    }
    
    val newList = mergeIpMap.values.toList.sortBy { x=> x.mask}
        
    val resultMap = Map[String, IPv4]()
    resultMap.put(newList.head.bits, newList.head)
    
    for(ipv4 <- newList.tail) {
        val found = ( 1 to ipv4.mask).exists(x => resultMap.contains(ipv4.bits.substring(0, x)) ) 
        
        if(! found) {
          resultMap.put(ipv4.bits, ipv4)
        }
    }
    
    resultMap.values.toList.sortBy(x => (x.bits, x.mask)).map(x=>bitToIpStr(x))
  }

  def parseIP(ipStr:String): IPv4 = {
    val bitsMask = ipStr.split("/")
    val ipElems = bitsMask(0).split("\\.")
    val bits =    ipElems.flatMap{ x => {
      val binStr = x.toInt.toBinaryString
        "0" * (8 - binStr.size) + binStr 
      } }.mkString ("")

    val mask = bitsMask(1).toInt;
    IPv4(bits.substring(0,mask), mask)
  }
  
//  val fileName = "sample"
//  val fileName = "C-small-practice"
  val fileName = "C-large-practice"
  
  Console.setIn(new FileInputStream(fileName + ".in"))
  Console.setOut(new FileOutputStream(fileName + ".out"))
  
  val numCase = Console.readLine().toInt
  for ( i <- 1 to numCase ) {
    val numIpAddr = Console.readLine().toInt
    
    val ipAddrs = ( for ( j <- 1 to numIpAddr )  yield {
      val ipAddr = Console.readLine()
      parseIP(ipAddr)
    }).sortBy(x => (-x.mask, x.bits )).reverse
    
    Console println(f"Case #$i:")
    Console.println(solve(ipAddrs).mkString("\n"))
  }
}