TapeEquilibrium ScalaCheck

Question

I have been trying to code some scalacheck property to verify the Codility TapeEquilibrium problem. For those who do not know the problem, see the following link: https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/.

I coded the following yet incomplete code.

test("Lesson 3 property"){
val left = Gen.choose(-1000, 1000).sample.get
val right = Gen.choose(-1000, 1000).sample.get
val expectedSum = Math.abs(left - right)
val leftArray =  Gen.listOfN(???, left) retryUntil (_.sum == left)
val rightArray =  Gen.listOfN(???, right) retryUntil (_.sum == right)

val property = forAll(leftArray, rightArray){ (r: List[Int], l: List[Int]) =>
  val array = (r ++ l).toArray
  Lesson3.solution3(array) == expectedSum
}

property.check()
}

The idea is as follows. I choose two random numbers (values left and right) and calculate its absolute difference. Then, my idea is to generate two arrays. Each array will be random numbers whose sum will be either "left" or "right". Then by concatenating these array, I should be able to verify this property.

My issue is then generating the leftArray and rightArray. This itself is a complex problem and I would have to code a solution for this. Therefore, writing this property seems over-complicated.

Is there any way to code this? Is coding this property an overkill?

Best.

Answer 1

My issue is then generating the leftArray and rightArray

One way to generate these arrays or (lists), is to provide a generator of nonEmptyList whose elements sum is equal to a given number, in other word, something defined by method like this:

import org.scalacheck.{Gen, Properties}
import org.scalacheck.Prop.forAll

def listOfSumGen(expectedSum: Int): Gen[List[Int]] = ???

That verifies the property:

forAll(Gen.choose(-1000, 1000)){ sum: Int =>
    forAll(listOfSumGen(sum)){ listOfSum: List[Int] =>
      (listOfSum.sum == sum) && listOfSum.nonEmpty
    }
  }

To build such a list only poses a constraint on one element of the list, so basically here is a way to generate:

• Generate list
• The extra constrained element, will be given by the expectedSum - the sum of list
• Insert the constrained element into a random index of the list (because obviously any permutation of the list would work)

So we get:

  def listOfSumGen(expectedSum: Int): Gen[List[Int]] =
    for {
      list <- Gen.listOf(Gen.choose(-1000,1000))
      constrainedElement = expectedSum - list.sum
      index <- Gen.oneOf(0 to list.length)
    } yield list.patch(index, List(constrainedElement), 0)

Now we the above generator, leftArray and rightArray could be define as follows:

val leftArray =  listOfSumGen(left)
val rightArray =  listOfSumGen(right)

However, I think that the overall approach of the property described is incorrect, as it builds an array where a specific partition of the array equals the expectedSum but this doesn't ensure that another partition of the array would produce a smaller sum. Here is a counter-example run-through:

val left = Gen.choose(-1000, 1000).sample.get //  --> 4
val right = Gen.choose(-1000, 1000).sample.get // --> 9
val expectedSum = Math.abs(left - right) // --> |4 - 9| = 5
val leftArray =  listOfSumGen(left) // Let's assume one of its sample would provide List(3,1) (whose sum equals 4)
val rightArray =  listOfSumGen(right)// Let's assume one of its sample would provide List(2,4,3) (whose sum equals 9)

val property = forAll(leftArray, rightArray){ (l: List[Int], r: List[Int]) =>
  // l = List(3,1)
  // r = List(2,4,3)
  val array = (l ++ r).toArray // --> Array(3,1,2,4,3) which is the array from the given example in the exercise
  Lesson3.solution3(array) == expectedSum 
// According to the example Lesson3.solution3(array) equals 1 which is different from 5
}

Here is an example of a correct property that essentially applies the definition:

def tapeDifference(index: Int, array: Array[Int]): Int = {
  val (left, right) = array.splitAt(index)
  Math.abs(left.sum - right.sum)
}

forAll(Gen.nonEmptyListOf(Gen.choose(-1000,1000))) { list: List[Int] =>
    val array = list.toArray
    forAll(Gen.oneOf(array.indices)) { index =>
      Lesson3.solution3(array) <= tapeDifference(index, array)
    }
  }

This property definition might collides with the way the actual solution has been implemented (which is one of the potential pitfall of scalacheck), however, that would be a slow / inefficient solution hence this would be more a way to check an optimized and fast implementation against slow and correct implementation (see this presentation)

Answer 2

Try this with c# :

using System;
using System.Collections.Generic;
using System.Linq;

private static int TapeEquilibrium(int[] A)
    {
        var sumA = A.Sum();
        var size = A.Length;
        var take = 0;
        var res = new List<int>();
        for (int i = 1; i < size; i++)
        {
            take = take + A[i-1];
            var resp = Math.Abs((sumA - take) - take);
            res.Add(resp);
            if (resp == 0) return resp;
        }
        return res.Min();

    }