Solution to part 1 of Day 7 Advent of Code in Scala

Question

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"))
 }
}

Answer 1

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 = {
 // ...
 }
 // ...
 }
 // ...
}

• Michiel Borkent: 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.