SequenceSum

package sequence

import scala.annotation.tailrec
import scala.util.Random

/**
 * Created by Owner on 10/21/14.
 *
 *    Problem:  In an array of uniformly distributed digits from 0-9 find two sequences such that
 *    the first sequence and second sequence add to the same sum and that sequence 1 and sequence 2 are
 *    adjacent to one another with no intervening elements in the array
 *           seq 1 sum=x
 *    |--------------------|  seq 2 sum =x
 *                         |---------------|
 *                         
 *  Sample output for one simulation:  oneRun
 *  Vector(6, 0, 0, 1, 8, 8, 8, 1, 6, 3, 1, 8, 0, 1, 3, 9, 1, 0, 1, 7, 8, 7, 7, 3, 7, 4, 4, 7, 6, 2, 7, 9, 7, 5....
 *  true seq 0 to 7  seq 8 to 16  sums 32  32
 *  
 *  check
 *   (6+0+0+1+8+8+8+1) = 32 = (6+ 3+ 1+ 8+ 0+ 1+ 3+ 9+ 1)
 */


object SequenceSum extends App {
  for (i <- 1 to 2000)
      oneRun

  def oneRun = {
    val rand = new Random
    val arr = for (i <- 1 to 100) yield rand.nextInt(10)
    print( arr.toString + "\n" )
    val (len1,len2,sum1, sum2) = findSequence( arr, 1)

    // remember index 0 starts an array
    print(s"${sum1==sum2} seq 0 to ${len1-1}  seq $len1 to ${len1+len2-1}  sums $sum1  $sum2\n")
  }


  def findSequence( xs: Seq[Int], n: Int) : (Int,Int,Int,Int) = {
    val sum1 = sumTo( xs, n)
    val (n2,sum2) = sumFrom( xs, n+1, 1, sum1 )
    if ( sum2 <= sum1  ) (n, n2, sum1, sum2) else findSequence( xs, n+1)
  }

  def sumTo( xs : Seq[Int], n: Int) = {
      xs.slice(0,n).sum
  }


  @tailrec
  def sumFrom( xs: Seq[Int], n: Int, len: Int ,goal : Int) : (Int,Int) = {
    if ( n+len > xs.size ) (0,0)
    else {
      val seq2 = xs.slice(n-1, n-1 + len)
      if (seq2.sum >= goal) (seq2.size, seq2.sum) else sumFrom(xs, n, len + 1, goal)
    }
  }
}