sums-of-ints.scala

import scala.annotation.tailrec

object Solution extends App {

    implicit class SolutionOps(value: Int) {

        def isExpressedWith(xs: List[Int]) = {
            // reverse the list and drop the items bigger than the target
            val basis = xs.reverse.dropWhile(_ > this.value)
            // start the recursive implementation
            isExpressedWithAcc(this.value, 0, basis, basis.tail)
        }

        @tailrec private def isExpressedWithAcc(target: Int, acc: Int,
                                                basis: List[Int], nextBasis: List[Int]): Boolean = {
            if (basis.isEmpty) { // run out of options in the current basis
                if (nextBasis.isEmpty) false // run out of any options -> can not be expressed
                else isExpressedWithAcc(target, 0, nextBasis, nextBasis.tail) // try out with a new basis
            }
            else {
                if (basis.head + acc == target) true
                else if (basis.head + acc > target) isExpressedWithAcc(target, acc, basis.tail, nextBasis)
                else isExpressedWithAcc(target, acc + basis.head, basis.tail, nextBasis)
            }
        }
    }

    def solve(xs: List[Int]) = {
        Stream.from(1) // an infinite sequence from 1 - (1, 2, 3, 4, .... )
            .filter(!xs.contains(_)) // filter out the values contained in the input list
            .filter(!_.isExpressedWith(xs)) // filter out values that can be expressed as a sum
            .head // take the first element from the sequence
    }

    def solveAndPrint(xs: List[Int], f: List[Int] => Int) :Unit = {
        println(s"The solution for $xs is ${f(xs)}.")
    }

    solveAndPrint(List(1, 2, 5, 7), solve)
    solveAndPrint(List(1, 1, 2, 3, 4, 5), solve)
}