Skip to content

Instantly share code, notes, and snippets.

@dpapathanasiou
Created July 26, 2015 23:54
Show Gist options
  • Save dpapathanasiou/b9d85685a0381f1deea0 to your computer and use it in GitHub Desktop.
Save dpapathanasiou/b9d85685a0381f1deea0 to your computer and use it in GitHub Desktop.
DSL processing in Scala
/* This is a scala solution for a mini domain specific language (DSL)
* defining instructions for populating an empty matrix.
*
* Input consists of a single string separated by spaces:
* - the first number represents the size of the matrix, NxN
* - the rest of the input consists of one or more strings defining
* the range of cells and how each of their populations will be
* incremented
*
* Increment pattern possibilities:
* x1:x2;y1:y2;+i -> add i to the current population in each cell defined by matrix(x, y) where x1 <= x <= x2 and y1 <= y <= y2
* x1:x2;y1:y2;*m -> multiply the current population in each cell by m
* x1:x2;y1:y2;^n -> raise the current population in each cell by a power of n
*
* Example input and expected outputs (input is a single string command-line argument):
*
* scala MatrixDSL "10 1:2;2:3;+1 2:2;3:3;+5 7:9;5:8;^3"
* 9
*
* This solution is a pure functional approach, using curried increment
* functions, regular expressions and scala's built-in pattern matching
* to parse and process input correctly, even without resorting to
* Option/Some or Try/Success/Failure constructs.
*
* @author Denis Papathanasiou (https://github.com/dpapathanasiou)
* @license The MIT License (http://opensource.org/licenses/MIT)
* Copyright (c) 2015 Denis Papathanasiou
*
*/
object MatrixDSL {
/* define the valid input patterns */
val argsPattern = """^(\d+)\s(.*)""".r
val inputPattern = """(\d+:\d+);(\d+:\d+);((\^|\+|\*)\d+)""".r
val plusPattern = """^(\+)(\d+)""".r
val multiplyPattern = """^(\*)(\d+)""".r
val raisePattern = """^(\^)(\d+)""".r
/* define the valid population increments as curried functions
* b is the factor from the input pattern
* a is the current population in a given matrix cell
*/
def popPlus (b: Long)(a: Long): Long = a + b
def popRaise (b: Long)(a: Long): Long = scala.math.pow(a, b).toLong
def popMultiply (b: Long)(a: Long): Long = a * b
/* Apply the increment function to the matrix
* for the given ranges (Xi:Xj), (Yi:Yj)
*/
def incrementPopulation (matrix: Array[Array[Long]], x: Array[Int], y: Array[Int], func:(Long) => Long): Array[Array[Long]] = {
for( i <- x )
for( j <- y )
matrix(i)(j) = func(matrix(i)(j))
matrix
}
/* Convert the Xi:Xj or Yi:Yj string into an array of ints
* we can do this without error checking b/c this function
* is not called unless the pattern regex matches
*/
def parseInputRange (s: String): Array[Int] = {
val ab = s.split(":").map(_.toInt)
(ab(0) until ab(1)+1).toArray
}
/* Convert the (+|*|^)\d string to a curried function
* to add, multiply, or raise to a power by the given number
*/
def parseIncrementFunction (s: String): Long => Long =
s match {
case plusPattern(sign, value) => popPlus(value.toLong)
case multiplyPattern(sign, value) => popMultiply(value.toLong)
case raisePattern(sign, value) => popRaise(value.toLong)
case _ => {
println("Invalid increment pattern: %s".format(s)) // side effect (we could do without, but useful perhaps for feedback)
popPlus(0) // an invalid pattern does not change the matrix
}
}
/* Apply the input string to the matrix, updating the population,
* but only if it matches the expected input pattern
*/
def processInput (s: String, m: Array[Array[Long]]): Array[Array[Long]] =
s match {
case inputPattern(x, y, inc, op) => incrementPopulation(m, parseInputRange(x), parseInputRange(y), parseIncrementFunction(inc))
case _ => {
println("Invalid input pattern: %s".format(s)) // side effect (we could do without, but useful perhaps for feedback)
m // return the matrix unchanged
}
}
/* Create and return a two-dimensional array
* with both dimensions the same size (n)
*/
def createMatrix(n: Int): Array[Array[Long]] =
Array.ofDim[Long](n, n)
/* Create the two-dimensional array (nxn), apply each of the input strings
* to increment the population if each input string pattern is valid,
* and return the fully-populated two-dimensional array
*/
def setPopulation (n: Int, inputs: Array[String]): Array[Array[Long]] = {
@annotation.tailrec
def calculate(m: Array[Array[Long]], inp: Array[String]): Array[Array[Long]] = {
if( 0 == inp.length ) m
else calculate(processInput(inp(0), m), inp.tail)
}
calculate(createMatrix(n), inputs)
}
/* Calculate the sum of the two-dimensional array */
def getPopulation (matrix: Array[Array[Long]]): Long = {
for {
row <- matrix
cell <- row.filter(_ > 0)
} yield cell
}.sum
def main(args: Array[String]): Unit = {
if( args.length < 1 )
println("Need an input argument (single string)")
else {
args(0) match {
case argsPattern (n, rest) => println(getPopulation(setPopulation(n.toInt, rest.split(" "))))
case _ => println("Invalid input")
}
}
}
}
@dpapathanasiou
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment