2014년2월28일

• Programming in Scala 30분 읽기
• Lawnmower ( https://code.google.com/codejam/contest/2270488/dashboard#s=p1 ) 문제 풀이

체크인

• HT
• 오늘도 다른 분들과 함께 문제를 즐겁게 풀 수 있었던 점이 좋았습니다. ^^
• 하지만 알고리즘을 너무 간단하게 생각했더니, 같이 하던 분들께서 구현을 너무 잘 해주셨지만 알고리즘이 잘못 되어 테스트를 통과하지 못했던 점이 너무 아쉽습니다.
• 다음에는 문제를 간단히 풀어보고 참석해야 할 것 같습니다.
• 아쉬움을 달래기 위해 2x2만 확인 하던 코드를 수평/수직으로 확인하도록 변경한 후 아래에 첨부합니다.
• Large 테스트 통과를 확인하였습니다.
• SK
• 오늘 소감입니다.
• 오늘은 좀 피곤했는데, 스터디를 하니까 기분이 좀 좋아졌습니다.
• 다들 열심히 하셔서 게으름을 덜 피우게 되는 것 같아 좋습니다.
• 다음 주에는 예습을 좀 더 많이 해서 시간 안에 제대로 된 답을 내도록 노력하겠습니다.
• JY
• ㅋ.. 다들 적어주셨군요. 요즘 갑자기 허리가 갑자기 나빠졌는데, 컨디션이 무척 안좋네요.
• 그래도 문제도 풀고 무사히 마쳤습니다. 항상 느끼는 것이 많습니다.

풀이

• Lawnmower: https://github.com/myeesan/codejam/blob/master/src/main/scala/lawnmower/Lawnmower.scala
• TicTacToe: https://github.com/myeesan/codejam/blob/master/src/main/scala/tictactoe/TicTacToe.scala

Large Case 처리할 수 있도록 수정하고 리팩토링해봤습니다. 제일 밑바닥 레벨을 체크하고 깎아낼 수 있으면 그 다음 레벨까지 채워올린 다음 그 레벨을 또 체크하는 걸 반복하는 식입니다.

object Lawnmower extends App {
  type Grass = IndexedSeq[IndexedSeq[Int]]

  def isCuttable(grass: Grass): Boolean = {

    def isCuttableLevel(grass: Grass)(level: Int): Boolean = {
      val iRows = grass.filter(_ exists (_ > level))
      val colCuttability: IndexedSeq[Boolean] = (iRows.head.map(_ :: Nil) /: grass.tail) {
        (acc, row) => acc zip row map { case (vec, n) => n :: vec }
      } map (_ forall (_ == level))
      iRows flatMap (_ zip colCuttability) filter (_._1 == level) forall (_._2)
    }

    def uncut(grass: Grass, from: Int, to: Int): Grass = grass map (_ map (x => if (x == from) to else x))

    @annotation.tailrec
    def isCuttable0(grass: Grass, levels: List[Int]): Boolean = levels match {
      case x :: Nil => true
      case current :: next :: tail =>
        isCuttableLevel(grass)(current) && isCuttable0(uncut(grass, current, next), next :: tail)
    }
    isCuttable0(grass, (collection.mutable.SortedSet.empty[Int] ++ grass.flatten).toList)
  }

  import java.io._

  def process(iter: Iterator[String])(out: PrintStream) =
    {
      for (i <- 1 to iter.next().toInt) {

        val n = iter.next().split(' ')(0).toInt
        val grass: Grass = Vector.fill(n)(iter next () split (' ') map (_.toInt))
        out.println(s"Case #$i: ${if (isCuttable(grass)) "YES" else "NO"}")
      }
    }

  val out = new PrintStream(new File("out"))
  try {
    process(io.Source.fromFile("B-large-practice.in").getLines)(out)
  } finally {
    out.flush; out.close
  }
}