※ただし体調がよければ

Google DevFest 2010のクイズ(2)

Scala

Google DevFest 2010の参加者選別のために出題されたクイズ（その2）。

パッチワーク

ここに "A" または "B" という文字のみを含む 600 桁、600 行のテキストがあります。これを 600 x 600 の升目状に並べ、上下左右に同じ文字がある部分をつながっているとみなします。

まず、最も多くの文字がつながっている領域をすべて "_" で塗りつぶしてください。 最も多くの文字がつながっている領域が複数存在するならば、それらすべての領域を "_"で塗りつぶすこととします。

そして、各行ごとに "_" が何個含まれているかを数え、それらの数値を改行区切りのテキスト（600 行）として答えてください。

以下の例1を見てください。この入力には単一の文字4つでつながった領域が3箇所あります。これらすべてが「最も多くの文字がつながっている領域」なので、全て"_"で塗りつぶし、その数を数えています。

http://devquiz.appspot.com/problems?problem=patchwork

具体的には、

ABAAB
BABAA
BAABB
ABABB
BABAA

という入力に対して

AB__B
B_B__
B____
AB___
BABAA

という塗りつぶしを行い、

2
3
4
3
0

という出力を行う。

僕はScala (Scala 2.8)で書いた。これが初めてのScalaプログラム。多分、初めてにしてはそこそこよく書けてる（自画自賛）

package googlepatchwork

import scala.io.Source
import scala.collection.mutable.Set

object Main {

  def main(args: Array[String]) {
    measure {
      val patchwork = toPatchwork(Source.fromPath("test.txt").getLines().toSeq)

      fillAreas(patchwork, areaToFill(patchwork))

      // 塗りつぶした部分を出力
      println(patchwork)

      val nums = countFilledCells(patchwork)
      
      // 最終的な答えを出力
      println(nums.mkString("\n"))
    }
  }
  
  def measure(toRun: => Unit) {
    val time = System.currentTimeMillis
    try {
      toRun
    } finally {
      val diff = System.currentTimeMillis - time
      System.err.println("Executed in " + diff + "ms.")
    }
  }
  
  def countFilledCells(pw: Patchwork[Char]): Array[Int] = {
    val res = Array.fill[Int](pw.height)(0)
    for ((x, y) <- pw.indices) {
      if (pw(x, y) == '_') {
        res(y) += 1
      }
    }
    res
  }

  def toPatchwork(str: Seq[String]): Patchwork[Char] = {
    val lines = str.map(_.trim).filterNot(_.isEmpty)
    new Patchwork[Char](
      lines(0).length, lines.size, 'C', lines.mkString.toCharArray)
  }
  
  def fillAreas(pw: Patchwork[Char], toFill: Set[(Int, Int)]) {
    toFill.foreach {
      case (x: Int, y: Int) => pw(x, y) = '_'
    }
  }
  
  def areaToFill(pw: Patchwork[Char]): Set[(Int, Int)] = {
    val scanned = new Patchwork[Boolean](
      pw.width, pw.height, true, Array.fill[Boolean](pw.width * pw.height)(false))
    var max = 0
    var cellsToFill = Set[(Int, Int)]()
    for ((x, y) <- pw.indices) {
      if (!scanned(x, y)) {
        val area = getNeighbors(pw, x, y)
        area.foreach {
          case (x: Int, y: Int) => scanned(x, y) = true
        }
        
        if (max < area.size) {
          max = area.size
          cellsToFill = area
        } else if (max == area.size) {
          cellsToFill ++= area
        }
      }
    }
    cellsToFill
  }
  
  def getNeighbors(pw: Patchwork[Char], x: Int, y: Int): Set[(Int, Int)] = {
	  val value = pw(x, y)
	  def neighbors(scanned: Set[(Int, Int)], curX: Int, curY: Int): Set[(Int, Int)] = {
	 	  if (pw(curX, curY) == value && !scanned.contains((curX, curY))) {
	 		  val nextCand = List((curX + 1, curY), (curX - 1, curY), (curX, curY + 1), (curX, curY - 1))
	 	 	  ((scanned + ((curX, curY))) /: nextCand) ((scanned2, next) => neighbors(scanned2, next._1, next._2))
	 	  } else
	 	 	  scanned
	  }
	  neighbors(Set(), x, y)
  }
}

class Patchwork[T](
  val width: Int, val height: Int, val defaultValue: T, private val values: Array[T]) {

  require(width * height == values.size)
  
  def indices = new Iterable[(Int, Int)] {
	  
	  private val len = width * height
	  
	  override def iterator = new Iterator[(Int, Int)] {
	 	  
	 	private var idx = 0
	 	
	 	def next = if (idx < len) {
	 	  val ret = (idx % width, idx / height)
	 	  idx += 1
	 	  ret
	 	} else {
	 	  throw new IllegalStateException
	 	}
	 	
	 	def hasNext = idx < len
	  }
  }

  def apply(x: Int, y: Int) =
    if (isInBound(x, y)) values(x + y * height) else defaultValue

  def update(x: Int, y: Int, e: T) {
    assume(isInBound(x, y))
    values(x + y * height) = e
  }

  def isInBound(x: Int, y: Int) = 0 <= x && x < width && 0 <= y && y < height
  
  override def toString = values.grouped(width).map(_.mkString + "\n").mkString
}

しかし、それでもいろいろ言い訳をばw

まず、mutableのSetを使ったのは、そっちの方が速かったから。最初はもちろんimmutable使ってたんだが、mutableにしたら0.2秒くらい速くなった（もともと1.4秒だったのが1.2秒になった）。実は、そのあといろいろ書き換えて中間の塗りつぶしもすっ飛ばして1秒切るくらいになったんだけれども、なんかTwitterで「90msで実行できた」とかいう人がいたのでそれは書かない。

あと、neighborsメソッド内でfoldLeft (/:)使ってるのは、ついうっかりHaskell使ってた癖が出ただけ。

それから、インデント一部ぐちゃぐちゃなのは、エディタのインデントの挿入がScalaの一般的な2文字インデントの書き方と異なってたから。

ほかにも何かおかしいところあったら、指摘していただけると幸いです。

それにしても、初めてのScalaで、しかもScala 2.7の情報しかほとんどない状態でScala 2.8を使うってのは大変だった。特にコレクションフレームワークが。

Permalink | コメント(0) | トラックバック(0) | 21:41