# Find the minimum number of operations (concat, add and subtract) for the numbers 1-9 to equal 100

I am beginning to learn Scala and functional programming, and I came across this puzzle.

This looked like good practice and I have a solution but just want some hints in terms of functional approach to this. I did rip off the evaluate function from Stack Overflow.

I particularly am interested in if the approach of creating 3 function and creating a function in the main solve routine is considered a good approach.

def gchq(): Int = {
def solve(total: String, currentValue: Int, f: (String, Int) => String): Int = {

val newtotal: String = f(total, currentValue)

if (currentValue == 9 && evaluate(newtotal.split("\\s").toList) == 100) {
print("SOLUTION: ")
println(newtotal + "/" + currentValue)
1
}
else if (currentValue == 9) 0
else {
solve(newtotal, currentValue + 1, concat)
solve(newtotal, currentValue + 1, minus)
solve(newtotal, currentValue + 1, plus)
}
}

solve("0", 1, concat)
}

def plus(a: String, b: Int): String = {
a + " + " + b
}

def minus(a: String, b: Int): String = {
a + " - " + b
}
def concat(a: String, b: Int): String = {
"" + a + b
}

//this function is taken off stackoverflow
def evaluate(expression: List[String]): Int = expression match {
case l :: "+" :: r :: rest => evaluate((l.toInt + r.toInt).toString :: rest)
case l :: "-" :: r :: rest => evaluate((l.toInt - r.toInt).toString :: rest)
case value :: Nil => value.toInt
}
gchq()


### Nesting

Using nested functions is not a bad practice per se, but all depends on the concrete case. Often they are used to enrich the parameters, to share with locally scoped values, or to hide the def from other members of the same object.

In many cases, they are just equivalent of functions with private visibility. But when too much nesting appears, I'd suggest to flatten the things for the sake of readability.

In this example I don't see any special reason to make the function nested. It does not use any of the values available to gchq. Keeping it nested would not be a mistake, but the flat approach seems cleaner:

def gchq2(): Unit = solve("0", 1, concat)

private def solve(total: String,
currentValue: Int,
f: (String, Int) => String) = ???


Moreover, other referenced functions (plus, minus...) are flat, so all of the pieces are well kept at same level.

### Other Considerations

Returned values. The Int return type from gchq() seems suspicious. I hope to understand the meaning (1 for successful result, 0 for no solution found), but the returned values are hugely falsified. solve() will return an Int only from the last call of solve(newtotal, currentValue + 1, plus), the others will remain hidden. Since the solutions are output into the console, I'd suggest to return nothing from solve:

private def solve(total: String, currentValue: Int, f: (String, Int) => String): Unit = ???


Conditinals. There are two checks for currentValue == 9. One should be enough:

if (currentValue == 9) {
if (evaluate(newtotal.split("\\s").toList) == 100) {
...
}
}
else {
...
}


It introduces one more case of nested ifs, but is fully justified here: this is the end condition of the calls sequence, while else adds more recursion.

Naming. Names like gchq or f are awful and should be changed to more meaningful.

Traversing all permutations of a given pattern often suggests recursion to me.

def solver(digits: Seq[Int], target: Int, eq: String = ""): String =
if (digits.isEmpty)
if (eq.split("(?=[+-])").map(_.toInt).sum == target) eq
else eq + eq
else
Seq( solver(digits.tail, target, s"$eq${digits.head}")
, solver(digits.tail, target, s"$eq+${digits.head}")
, solver(digits.tail, target, s"$eq-${digits.head}")
).minBy(_.length)


Start by testing for the termination condition, i.e. when we've run out of digits to add to the equation we're building. If the finished equation evaluates to the target amount then return it, if not then return some string guaranteed to be too long to be of any interest.

The tricky part is parsing the finished equation. I split() the string at its non-digit characters but I used a non-consuming regex capture pattern (?=[+-]) so that the '+' and the '-' remain in the resulting Array[String]. After that it's just a matter of turning each element into an Int and summing the collection.

If we haven't reached the terminus then recurse once for each of the pattern variations. Return the one with the shortest result string, i.e. the fewest added '+' and '-' characters.

A quick test run ...

solver(1 to 9, 100)


... and, yeah, it appears to work.

It's a little inefficient to call digits.head and digits.tail 3 times in the else block but I'll leave it just to make it a bit clearer, visually, for the reader to follow what's going on.