Skip to content

2014년4월18일

Jump to bottom Edit New page
Brandon JeongYeol Choi edited this page Jun 3, 2014 · 3 revisions

체크인

  • JS
  • 프로젝트 완료보고(시원하게) 해서 좋고, 코드잼 통과해서 기분이 좋다.
  • SJ
  • 구석이라 안어색하다. 코드잼도 풀어서 기분이 좋다. 같이 못풀어서 아쉽다. 오늘도 재밌게 공부해요.
  • HT
  • 출장이 있어서 못왔다(해외 파이콘) 남는 시간에 스칼라를 했는데, 스칼로이드 세팅해서 기분 좋다. 알엑스자바. 스칼로이드 세팅이 어렵다.
  • BS
  • 계속 오려다가 시간이 안맞아서 이번에 처음 참여 하게 되었다. 처음이라 분위기 파악중이다. 편안한 분위기다.
  • K
  • 코드잼 문제 읽어 보려다가, 지쳐서 잠들어서 아쉽다. 열심히 하려고 하는데, 프로젝트 때문에 힘들다. 열심히 하겠다.
  • CW
  • 코드잼 계속 푸느라 고생했다. 민방위라서 하루종이 놀아서 컨디션이 좋다.
  • SK
  • 논문 지척이 별로 없어서 고민중이다. 그래도 기분은 좋다. 오늘 어떻게 진행해야 할지 아이디어가 없어서 약간 걱정이다.
  • SK
  • 민방위 부럽다. 마지막 예비군 훈련 체험을 하고, 기분이 좋다. 이제한 번 남았다. 지금도 아무 생각 없다.
  • JY
  • 세월호 때문에 마음이 아프다. 그래도 오늘 많은 분들으 뵐 수 있어서 기분이 좋다. 프로젝트때문에 좀 걱정이 된다. 끝내버리고 싶은데 자꾸 질질 끄는 중. 첨엔 지장을 많이 받지만 요즘엔 맘을 다잡아서 프로젝트 망한다고 죽기야 하겠냐는 심정으로 버티고 있다. 오늘 재밌게 풀었으면 좋겠다.

회고

  • JS
  • 코드를 안 잡아봐서 좀 아쉽다. 페어 프로그래밍을 해 보고 스칼라스러운 코드를 해 보는 게 좋을 것 같은데 알고리즘 이야기만 잔뜩 해서 약간 불만스럽다. 지금까지 개근한 자신이 자랑스럽다.
  • SJ
  • 오늘 손이 놀아서 약간 어색하다. 다음주에는 한글 문제를 풀 계획이니 잘 이해해서 빨리 풀었으면 좋겠다.
  • HT
  • 열정을 채워서 왔는데 코딩을 안해서 아쉽지만 이 아쉬움을 15장을 열심히 읽어서 준비하는 걸로 채웠으면 좋겠다.
  • BS
  • 공부 열심히 하겠습니다. 일단 편안해서 좋았다. 적응을 못하고 있어서 아쉽다.
  • K
  • 뭔가 만반의 준비를 하고 왔는데 코딩을 안해서 아쉬웠다. 다음번에는 재밌게 코딩을 해 봤으면 좋겠다.
  • CW
  • 코딩 안해서 편해서 좋았다. 성큼님 설명 잘 해주셔서 감사했다.
  • SK
  • 오늘 뭐, 일찍 끝나는 것 같아서 좋다. 아시운점은 코드 설명을 제대로 못한 것 같아서 아쉬웠다. 실제 코딩을 못해서 아쉽다. 다음에는 다시 페어프로그래밍 했으면 좋겠다.
  • SK
  • 문제를 비까지만 봤다는게 아쉽다. 코드 공유와 설명이 좋았고 한글 코드가 기대된다.

풀이

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)
        }
      }
    }
}
Add a custom footer
Add a custom sidebar
Clone this wiki locally