TapeEquilibrium ScalaCheck - PullRequest
Новая
       13

TapeEquilibrium ScalaCheck

1 голос
/ 26 апреля 2019

Я пытался закодировать какое-либо свойство 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. Само по себе это сложная проблема, и мне придется написать решение для этого. Поэтому написание этого свойства кажется слишком сложным.

Есть ли способ закодировать это? Является ли кодирование этого свойства излишним?

Best.

1 Ответ

1 голос
/ 27 апреля 2019

Моя проблема генерирует 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
  • Вставка ограниченного элемента в случайный индекс списка (поскольку очевидно, что любая перестановка списка будет работать)

Итак, мы получаем: 

  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), однако это будет медленное / неэффективное решение, следовательно, это будет больше способ проверить оптимизированная и быстрая реализация против медленной и правильной реализации (см. эту презентацию )

...