ICFP Contest 2013

例年のようにicfpのコンテストに @khibino @plaster @dekosuke @Lost_dog_ @m2ym Kee -san達と参加。

ルール等の詳細はhttp://icfpc2013.cloudapp.net/

去年まではSchemeとC++を使っていた人々がふたりともHaskell派になったおかげで、一人でScala書いてた。

dekosukeさんが乱択アルゴリズムに進むようだったので、こちらは小さい問題を全列挙で解いた。

1日目

とりあえずさくっと \BV の eval を実装。

case class Literal(val value: Long) extends Expression {
  val ops = 0
}
object Zero extends Literal(0)
object One extends Literal(1)
case class Id(id: String) extends Expression {
  val ops = 0
}
case class If0(e: Expression, t: Expression, f: Expression) extends Expression {
  val ops = BV.OPS.OP_If0 | e.ops | t.ops | f.ops
}
case class Fold(e: Expression, acc: Expression, l: FoldLambda) extends Expression {
  val ops = BV.OPS.OP_Fold | e.ops | acc.ops | l.exp.ops
}
case class FoldLambda(e: Id, acc: Id, exp: Expression)

object BV {
  def eval(prog: Program, x: Long): Long = {
    eval(prog.e, Env(Map(prog.arg.id -> x), None))
  }

  def eval(exp: Expression, env: IEnv): Long = exp match {
    case v: Literal => v.value
    case Id(id) => env(id)
    case Op1Exp(t, e) =>
      {
        import Op1._
        t match {
          case Not => ~eval(e, env)
          case ShiftL1 => eval(e, env) << 1
          case ShiftR1 => eval(e, env) >>> 1
          case ShiftR4 => eval(e, env) >>> 4
          case ShiftR16 => eval(e, env) >>> 16
        }
      }
...
  }

トレーニングでチェックした範囲では問題なさそう。

次はサイズとoperatorsから合法な全ての構文木を生成。

  def genExpression(size: Int, availables: Int, rests: Int, par: Boolean = false): GenSeq[Expression] = {
    var results: List[Expression] = Nil
    if (canched) throw new InterruptedException
    if (size == 1) {
      return toPar(
        (if (contains(availables, OP_Fold) || contains(availables, OP_TFold))
          List(Zero, One, Id("x"), Id("y"), Id("z"))
        else
          List(Zero, One, Id("x"))), par)
    }
    if (size >= 2) {
      for (
        op <- toPar(flagToList(availables & MASK_OP1), par);
        e <- genExpression(size - 1, availables, unset(rests, op.asInstanceOf[OpOp1].op.id))
      ) {
        val exp = Op1Exp(op.asInstanceOf[OpOp1].op, e)
        if (contains(exp.ops, rests)) {
          results = exp :: results
        }
      }
    }
  ...

全てオンメモリで処理するのでサイズ12程度でOOMEくらう。

サイズ9の問題で全部で1万個ほどプログラムが生成されて、evalからもらった256入出力を満たすかのチェックだけだと200個あって解けなそうと判断。

ライトニングディビジョンに参加するか迷うも全員力尽きて翌日に持ち越し。

2日目

生成したプログラムをそれぞれ簡約化して等価なものを取り除くようにする。

  def simplify(e: Op2Exp): Expression = e match {
    //const
    case Op2Exp(op, Literal(_), Literal(_)) =>
      new Literal(BV.eval(e, Env(Map(), None)))
    // x | 0
    case Op2Exp(Or, Literal(0), other) =>
      other
    case Op2Exp(Or, other, Literal(0)) =>
      other
    // x | ~0
    case Op2Exp(Or, l @ Literal(0xffffffffffffffffL), _) =>
      simplify(l)
    case Op2Exp(Or, _, l @ Literal(0xffffffffffffffffL)) =>
      simplify(l)
    ...
  }

  def simplify(e: If0): Expression = e match {
    //const
    case If0(l: Literal, t, f) =>
      val v = BV.eval(l, Env(Map(), None))
      if (v == 0L)
        t
      else
        f
    case If0(c, t, f) if t == f =>
      t

    ...
  }

のような感じで。これでサイズ10くらいまでは256入出力のペアがあれば、5択〜20択くらいまで候補を絞り込めるようになったのでポチポチと手動でサブミット。
ほぼ、1発で成功していて、簡約化できていないことが判明するも
(and 1 x) == (and 1 (shr1 (shl1 x))) のように値域・定義域の判定まで必要なケースで解くには問題ないのであきらめる。

3日目

サイズ11のトレーニングデータで試すと流石に可能なケース全てを一旦生成して処理するのは不可能だったので、生成しつつ評価していくことに。

  def genExpression(size: Int, availables: Int, rests: Int, par: Boolean = false)(cb: Expression => Unit): Unit = {
    if (size == 1) {
      val es =
        if (contains(availables, OP_Fold) || contains(availables, OP_TFold)) {
          cb(Zero)
          cb(One)
          cb(Id("x"))
          cb(Id("y"))
          cb(Id("z"))
        } else {
          cb(Zero)
          cb(One)
          cb(Id("x"))
        }
      return
    }
    if (size >= 2) {
      for (
        op <- flagToList(availables & MASK_OP1)
      ) {
        genExpression(size - 1, availables, unset(rests, op.asInstanceOf[OpOp1].op.id)) { e =>
          {
            val exp = Op1Exp(op.asInstanceOf[OpOp1].op, e)
              cb(exp)
          }
        }

      }
    }
...

これで、size<=11の問題とsize<=14のtfoldまでは解けるように。

サイズ20前後の通常問題は乱択アルゴリズム班が頑張ってるようだったので、\BVの最適化をしつつボーナス問題の検討を開始するも(if0 a b c)で仮にbを正解に固定しても時間ないに解けない。

しかしその際のBV.eval()とプログラム生成の最適化でsize<=13の問題とsize<=16のtfoldは時間内に解けるようになってた。

4日目

結局残ったままになっていたボーナス問題をダメ元で全探索の順序をランダムに変えつつ試してみるも解けず会社へ。

初日は全員集合してノートで開発していたけれどメモリ4Gの32bit WindowsだとScala IDE走らせつつ、探索問題とくのは厳しく、二日目以降はリモート参加してた。

延々Scalaを書いてたけれど、やはり並列コレクションのparはとりあえずマルチコアを使うのには楽だけどCPUを使い切り続けるのにはつらい。
caseクラスやパターンマッチやラムダ式は便利だけどプロファイリングしたときに意外な所でコストかかってたりする。もちろんそれらがあるお陰で構造的な改良はやりやすいのでトレードオフ関係はあるんだけど。

後知恵だけどある程度のサイズの式の集合は予め生成しておいて、入出力から逆算するようなDP的なやり方でもう1サイズ分ぐらいは稼げたかもしれない。