Variations on a 3-sum

Brute Force Search

package io.github.davepkennedy

import scala.annotation.tailrec

object ThreeSum {
  def parseInt (s: String): Option[Int] = try {
    Some (java.lang.Integer.parseInt(s))
  } catch {
    case e: NumberFormatException => None
  }

  @tailrec
  def three_sum (g: Int, a: Int, b: Int, s: Seq[Int]): Boolean = s match {
    case Seq() => false
    case h :: t => if (a + b + h == g) true
      else three_sum(g, a, b, t)
  }

  @tailrec
  def three_sum (g: Int, a: Int, s: Seq[Int]): Boolean = s match {
    case Seq() => false
    case h :: t => if (three_sum(g, a, h, t)) true
      else three_sum(g, a, t)
  }

  @tailrec
  def three_sum (g: Int, s: Seq[Int]): Boolean = s match {
    case Seq() => false
    case h :: t => if (three_sum (g, h, t)) true
      else three_sum(g, t)
  }

  def main (args: Array[String]) = {
    val values = args.map(parseInt).flatten.toSeq
    val goal = values.head
    val input = values.tail
    println (s"Three-sum of $input seeking $goal is ${three_sum(goal,input)}")
  }
}

Brute Force Test

package io.github.davepkennedy

import org.scalatest._

class ThreeSumSpec extends FlatSpec with Matchers {

  "ThreeSum" should "find a value which adds to the total with 2 values given" in {
    ThreeSum.three_sum(5, 1, 2, Seq(1,2)) should be(right = true)
  }

  "ThreeSum" should "not find a value which adds to the total with 2 values given" in {
    ThreeSum.three_sum(5, 1, 2, Seq(1,3)) should be(right = false)
  }

  "ThreeSum" should "find a value which adds to the total with 1 value given" in {
    ThreeSum.three_sum(5, 1, Seq(1,2,2)) should be(right = true)
  }

  "ThreeSum" should "not find a value which adds to the total with 1 value given" in {
    ThreeSum.three_sum(5, 1, Seq(1,1,1)) should be(right = false)
  }

  "ThreeSum" should "find a value which adds to the total" in {
    ThreeSum.three_sum(5, Seq(1,2,2,3)) should be(right = true)
  }

  "ThreeSum" should "not find a value which adds to the total" in {
    ThreeSum.three_sum(5, 1, Seq(1,1,1,1)) should be(right = false)
  }
}

Optimized Approach

package io.github.davepkennedy

import scala.annotation.tailrec

object ThreeSum {
  def contains (g: Int, s: Seq[Int]): Boolean = {
    @tailrec
    def helper(g: Int, s:Seq[Int], low: Int, high: Int): Boolean = {
      if (low <= high) {
        val mid = (low + high) / 2
        if (s(mid) == g) true
        else if (s(mid) < g) helper(g, s, mid+1, high)
        else helper(g, s, low, mid-1)
      }
      else false
    }
    helper(g, s, 0, s.length)
  }

  def parseInt (s: String): Option[Int] = try {
    Some (java.lang.Integer.parseInt(s))
  } catch {
    case e: NumberFormatException => None
  }

  def three_sum (g: Int, a: Int, b: Int, s: Seq[Int]): Boolean = s match {
    case Seq() => false
    case h :: t => contains(g-(a+b), s)
  }

  @tailrec
  def three_sum (g: Int, a: Int, s: Seq[Int]): Boolean = s match {
    case Seq() => false
    case h :: t => if (three_sum(g, a, h, t)) true
      else three_sum(g, a, t)
  }

  @tailrec
  def three_sum (g: Int, s: Seq[Int]): Boolean = s match {
    case Seq() => false
    case h :: t => if (three_sum (g, h, t)) true
      else three_sum(g, t)
  }

  def main (args: Array[String]) = {
    val values = args.map(parseInt).flatten.toSeq.sorted // It's important to *sort* the imnut here
    val goal = values.head
    val input = values.tail
    println (s"Three-sum of $input seeking $goal is ${three_sum(goal,input)}")
  }
}

Optimized Test

package io.github.davepkennedy

import org.scalatest._

class ThreeSumSpec extends FlatSpec with Matchers {

  "Contains" should "find a value" in {
    ThreeSum.contains(5, Seq(1,2,3,4,5,6)) should be(right = true)
  }

  "Contains" should "not find a value" in {
    ThreeSum.contains(5, Seq(1,2,3,4,6)) should be(right = false)
  }

  "ThreeSum" should "find a value which adds to the total with 2 values given" in {
    ThreeSum.three_sum(5, 1, 2, Seq(1,2)) should be(right = true)
  }

  "ThreeSum" should "not find a value which adds to the total with 2 values given" in {
    ThreeSum.three_sum(5, 1, 2, Seq(1,3)) should be(right = false)
  }

  "ThreeSum" should "find a value which adds to the total with 1 value given" in {
    ThreeSum.three_sum(5, 1, Seq(1,2,2)) should be(right = true)
  }

  "ThreeSum" should "not find a value which adds to the total with 1 value given" in {
    ThreeSum.three_sum(5, 1, Seq(1,1,1)) should be(right = false)
  }

  "ThreeSum" should "find a value which adds to the total" in {
    ThreeSum.three_sum(5, Seq(1,2,2,3)) should be(right = true)
  }

  "ThreeSum" should "not find a value which adds to the total" in {
    ThreeSum.three_sum(5, 1, Seq(1,1,1,1)) should be(right = false)
  }
}