package qualification
object ProblemC extends App {
case class Board(cell: IndexedSeq[collection.BitSet], cMax: Int) {
lazy val numberOfMine: Int = cell.map(_.size).sum
lazy val isOneClickWinnable: Boolean = {
for {
(r, c) <- zeroCoord
} yield numberOfRevealedCell(r, c) + numberOfMine == cell.size * cMax
}.getOrElse {
cell.size * cMax == numberOfMine + 1
}
def isMine(r: Int, c: Int): Boolean = {
if (r < 0 || r >= cell.size) false
else cell(r) contains c
}
def neighbors(r: Int, c: Int): Seq[(Int, Int)] = (for {
i <- (r - 1 max 0) to (r + 1 min (cell.size - 1))
j <- (c - 1 to c + 1) if j >= 0 && j < cMax
} yield (i, j)) diff (r, c) :: Nil
def digit(r: Int, c: Int): Option[Int] =
if (isMine(r, c)) None
else Some {
neighbors(r, c).filter { case (i, j) => cell(i) contains j }.size
}
lazy val zeroCoord: Option[(Int, Int)] =
(for {
r <- Stream.from(0).take(cell.size)
c <- Stream.from(0).take(cMax) if digit(r, c) == Some(0)
} yield (r, c)).headOption
def numberOfRevealedCell(r: Int, c: Int): Int = {
val buf = collection.mutable.BitSet.empty
def hash(r: Int, c: Int): Int = r * cMax + c
@annotation.tailrec
def reveal(targets: List[(Int, Int)]): Unit = {
// println(targets)
targets match {
case Nil => ()
case (r, c) :: tails =>
// println(targets.head)
buf += hash(r, c)
val nexts = for {
(i, j) <- neighbors(r, c) if !(buf contains hash(i, j))
} yield (i, j)
// println(nexts)
buf ++= nexts.map { case (r, c) => hash(r, c) }
reveal(nexts.filter { case (r, c) => digit(r, c) == Some(0) }.toList ::: tails)
}
}
reveal((r, c) :: Nil)
buf.size
}
override val toString: String = cell.map { row =>
Seq.tabulate(cMax)(i => if (row contains i) '*' else '.').mkString
}.mkString("\n")
def toString(r: Int, c: Int): String = {
for {
i <- 0 until cell.size
val row = cell(i)
} yield Seq.tabulate(cMax) { j =>
if (i == r && j == c) 'c'
else if (row contains j) '*' else '.'
}.mkString
}.mkString("\n")
}
def toBoard(iter: Iterator[String], r: Int): Board = {
val input = Vector.fill(r)(iter.next())
val lines = input.map { s =>
collection.BitSet.empty ++ (for {
i <- 0 until s.size if s(i) == '*'
} yield i)
}
Board(lines, input.head.size)
}
// def bigint2bitset(n: BigInt) = {
// collection.BitSet.empty ++ (0 until n.bitLength).filter(n testBit _)
// }
lazy val memo = {
def from(n: BigInt): Stream[BigInt] = {
// if (n%10000==0) println(n)
n #:: from(n + 1)
}
def div(n: BigInt, r: Int, c: Int, acc: List[Int] = Nil): Vector[Int] = {
if (r == 0) acc.toVector else div(n / c, r - 1, c, (n % c).toInt :: acc)
}
val memo = collection.mutable.Map.empty[(Int, Int, Int), Board]
for {
r <- 5 to 5
c <- 5 to 5
//val set = collection.mutable.BitSet.empty
val bs = collection.BitSet.empty +: (0 until c).map(i => collection.BitSet.empty ++ (0 to i))
} yield {
from(0).takeWhile(_ < (BigInt(c + 1) pow r)).map { n =>
Board(div(n, r, c + 1).map(bs(_)), c)
}.
// filter(_.isOneClickWinnable).
foreach { b =>
val nm = b.numberOfMine
if (!(memo contains (r, c, nm))) {
memo += ((r, c, nm) -> b)
}
}
}
memo.toMap
}
memo.toSeq.sortBy(_._1) foreach {
case ((r, c, m), b) =>
println((r, c, m))
println(b)
println(b.isOneClickWinnable)
}
def oneClick(r: Int, c: Int, m: Int): Option[(Board, Int, Int)] = for {
b <- memo.get(r, c, m)
val (i, j) = b.zeroCoord.getOrElse((for {
i <- Stream.from(0).take(r)
j <- Stream.from(0).take(c) if !b.digit(i, j).isEmpty
} yield (i, j)).head)
} yield (b, i, j)
def process(iter: Iterator[String])(println: String => Unit) =
for (i <- 1 to iter.next().toString.toInt) {
val Array(r, c, m) = iter.next.split(' ').map(_.toInt)
println(s"Case #$i:")
println {
val o = oneClick(r, c, m)
if (o.isEmpty) "Impossible" else {
val (r, i, j) = o.get
r.toString(i, j)
}
}
}
}