Ip Address Summarization.scala

package Main

import java.io.{FileOutputStream, FileInputStream}

import scala.annotation.tailrec
import scala.io.StdIn

case class IP(num:Long, p:Int)

object Main extends App {
    Console.setIn(new FileInputStream("example.in"))

    Console.setIn(new FileInputStream("C-large-practice.in"))
    Console.setOut(new FileOutputStream("C-large-practice.out"))

    def base(s:String): Long = if (s.isEmpty) 0 else (base(s.init) << 1) | (s.last - '0')
    def toIP(s:String) = IP(base(s + ("0" * (32 - s.length))), s.length)

    def solve(ipList:List[IP]): List[IP] = {
        @tailrec
        def _solve(result:List[String], datas:List[IP]):List[String] = {
            if (datas.isEmpty) {
                result
            } else {
                val newOne: IP = datas.head
                val changed = ("0" * (32 - newOne.num.toBinaryString.length) +  newOne.num.toBinaryString).take(newOne.p)
                val compare = changed.init + (if ('0' == changed.last) '1' else '0')
                if (result.contains(compare)) {
                    _solve(result, toIP(changed.init) +: datas.tail)
                } else {
                    val newResult = result.filter(x => !x.startsWith(changed) || x == changed)
                    if (result.exists(x => changed.startsWith(x))) {
                        _solve(newResult, datas.tail)
                    } else {
                        _solve(changed +: newResult, datas.tail)
                    }
                }
            }
        }
        _solve(Nil, ipList).map(toIP).sortBy(_.num)
    }

    val cases = StdIn.readLine().toInt
    (1 to cases) foreach { num =>
        val n = StdIn.readLine().toInt
        val ipList = for (i <- 0 until n) yield {
            val Array(text, p) = StdIn.readLine().trim.split("/")
            val Array(a, b, c, d) = text.split("\\.").map(_.toLong)
            IP((a << 24) | (b << 16) | (c << 8) | d, p.toInt)
        }

        val result: List[IP] = solve(ipList.toList)
        println(s"Case #$num:")
        result.foreach(x =>
            println(s"${(x.num >> 24) & 255}.${(x.num >> 16) & 255}.${(x.num >> 8) & 255}.${x.num & 255}/${x.p}")
        )
    }
}