TapeEquilibrium ScalaCheck

Question

我一直在尝试编写一些scalacheck属性来验证Codility TapeEquilibrium问题。对于那些不知道问题的人，请参阅以下链接：https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/。

我编写了以下不完整的代码。

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()
}

这个想法如下所示。我选择两个随机数(左边和右边的值)并计算它的绝对差。然后，我的想法是生成两个数组。每个数组都是随机数，它们的和要么是“左”，要么是“右”。然后，通过连接这些数组，我应该能够验证这个属性。

我的问题是生成leftArray和rightArray。这本身就是一个复杂的问题，我必须为此编写一个解决方案。因此，编写此属性似乎过于复杂。

有没有办法对此进行编码？编写这个属性是不是有点过头了？

最好的。

Answer 1

然后，我的问题是生成leftArray和rightArray

生成这些数组或(列表)的一种方法是提供一个nonEmptyList生成器，它的元素和等于给定的数字，换句话说，由如下方法定义的内容：

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

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

这将验证属性：

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

构建这样一个列表只会对列表的一个元素造成约束，所以基本上是这样生成的：

the expectedSum - the sum of list

• Insert
• 额外的约束元素，将通过将约束元素生成到列表的随机索引中(因为显然列表的任何排列都会起作用)

所以我们得到：

  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)

现在我们上面的生成器，leftArray和rightArray可以定义如下：

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

然而，我认为所描述的属性的总体方法是不正确的，因为它构建了一个数组，其中该数组的特定分区等于expectedSum，但这不能确保该数组的另一个分区会产生较小的和。下面是一个反例演示：

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
}

下面是一个正确的属性示例，它实际上应用了该定义：

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)
    }
  }

这个属性定义可能会与实际解决方案的实现方式发生冲突(这是scalacheck的潜在陷阱之一)，然而，这将是一个缓慢/低效的解决方案，因此这将是一种检查优化的快速实现与缓慢而正确的实现的方法(请参阅此presentation)

Answer 2

用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();

    }