4
\$\begingroup\$

Does someone want to review my solution to part 1 of Day 7 Advent of Code in Scala? The assignment is here: http://adventofcode.com/day/7 Without repeating the whole text, in short:

Given a text file of the following form (simplified):

x AND y -> a
x -> 1
y -> 0

calculate the value of a. Here is an example of a full input file.

My solution:

import scala.io.Source

object Day7 {

  sealed trait Expr

  case class Variable(name: String) extends Expr

  case class Const(value: Int) extends Expr

  case class Not(expr: Expr) extends Expr

  case class And(left: Expr, right: Expr) extends Expr

  case class Or(left: Expr, right: Expr) extends Expr

  case class LShift(expr: Expr, by: Int) extends Expr

  case class RShift(expr: Expr, by: Int) extends Expr

  case class Assignment(v: Variable, expr: Expr) extends Expr

  case object Command {
    def parse(s: String): Assignment = {
      val assignmentRegex = """(.+) -> (.+)""".r
      def innerParse(s: String): Expr = {
        val rShiftRegex = """(\w+) RSHIFT (\d+)""".r
        val lShiftRegex = """(\w+) LSHIFT (\d+)""".r
        val orRegex = """(\w+) OR (\w+)""".r
        val andRegex = """(\w+) AND (\w+)""".r
        val notRegex = """NOT (\w+)""".r
        val constRegex = """(\d+)""".r
        val varRegex = """(\w+)""".r

        s match {
          case rShiftRegex(l, n) =>
            RShift(innerParse(l), n.toInt)
          case lShiftRegex(l, n) =>
            LShift(innerParse(l), n.toInt)
          case orRegex(l, r) =>
            Or(innerParse(l), innerParse(r))
          case andRegex(l, r) =>
            And(innerParse(l), innerParse(r))
          case notRegex(e) =>
            Not(innerParse(e))
          case constRegex(n) =>
            Const(n.toInt)
          case varRegex(n) =>
            Variable(n)
        }
      }
      s match {
        case assignmentRegex(l, r) => Assignment(Variable(r), innerParse(l))
        case _ => throw new Exception(s"Unrecognized command: $s")
      }
    }
  }

  class Environment(mappings: Map[String, Expr]) {

    val cache = new scala.collection.mutable.HashMap[Expr, Int]()

    private def eval(e: Expr): Int = {
      cache.get(e) match {
        case Some(i) => i
        case None => {
          val result = e match {
            case Variable(name) => {
              println(s"evaluating $name")
              eval(mappings(name))
            }
            case Const(value) => value
            case Not(expr) => ~eval(expr)
            case And(l, r) => eval(l) & eval(r)
            case Or(l, r) => eval(l) | eval(r)
            case LShift(expr, n) => eval(expr) << n
            case RShift(expr, n) => eval(expr) >> n
          }
          cache += (e -> result)
          result
        }
      }
    }

    def call(name: String): Int = {
      eval(mappings(name))
    }
  }

  def main(args: Array[String]) = {
    val lines = Source.fromFile("input-day7.txt").getLines()
    val x = lines.map(Command.parse).map((a) => a match {
      case Assignment(Variable(v), e) => (v -> e)
    })
    val m = x.toMap
    println(new Environment(m).call("a"))

  }

}
\$\endgroup\$
2
\$\begingroup\$

It seems to me that your general approach is solid. One small change I noticed you could make would be to move the Regex declarations outside of the functions parse and innerParse. The reason for doing this is that it is expensive to compile the Regexs with every call to these functions. By moving them out we only construct them once. This is supported by the Scala Regex documentation which can be read here.

case object Command {
  val assignmentRegex = """(.+) -> (.+)""".r
  val rShiftRegex     = """(\w+) RSHIFT (\d+)""".r
  val lShiftRegex     = """(\w+) LSHIFT (\d+)""".r
  val constRegex      = """(\d+)""".r
  val varRegex        = """(\w+)""".r
  val notRegex        = """NOT (\w+)""".r
  val andRegex        = """(\w+) AND (\w+)""".r
  val orRegex         = """(\w+) OR (\w+)""".r

  def parse(s: String): Assignment = {
    def innerParse(s: String): Expr = {
      // ...
    }
    // ...
  }
  // ...
}
\$\endgroup\$
  • \$\begingroup\$ Thank you! I thought the Scala compiler would maybe optimize this, like in Clojure, where regex literals are only evaluated once during the reader/compile phase. \$\endgroup\$ – Michiel Borkent Dec 30 '15 at 14:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.