from hypothesis import assume, given, strategies as st
@given(st.lists(st.integers()))
def test_peak_is_in_original_list(xs):
"""The peak of a list is in the list."""
assume(len(xs) > 0)
assert peakfinder(xs) in xs
from hypothesis import given, strategies as st
@given(st.lists(st.integers()))
def test_peak_is_in_original_list(xs):
"""The peak of a list is in the list."""
assert peakfinder(xs) in xs
from hypothesis import assume, given, strategies as st
@given(st.lists(st.integers()))
def test_peak_is_in_original_list(xs):
"""The peak of a list is in the list."""
assume(len(xs) > 0)
assert peakfinder(xs) in xs
Crashing bug
If I call peakfinder([0, 0]), I get an IndexError:
Traceback (most recent call last):
File "peaks.py", line 32, in <module>
peakfinder([0, 0])
File "peaks.py", line 22, in peakfinder
if arr[left] <= arr[mid] >= arr[right]:
IndexError: list index out of range
(I’m not sure if these are the "size constraints" you allude to in the question, you didn’t provide details.)
If we inspect these, we discover that we have (L, M, R) = (0, 1, 2), but trying to get the element at index 2 will fail. This will fail whenever you have an array of length 2.
One way to handle this would be to add an extra base case for when you have an array of length 2. Alternatively, you could tweak the bounds checking so that it only looks for elements within the bounds of the array.
Let’s suppose we never pass in an array of size 2. But it turns out other arrays will hit the same, if they reduce to an length-2 array at an intermediate step. For example:
>>> peakfinder([0, 1, 0, 0])
Traceback (most recent call last):
File "peaks.py", line 35, in <module>
peakfinder([0, 1, 0, 0])
File "peaks.py", line 29, in peakfinder
return peakfinder(arr[:mid])
File "peaks.py", line 31, in peakfinder
if arr[mid] < arr[right]: # Look to right side of array for peak.
IndexError: list index out of range
Here’s a small test I wrote with Hypothesis to find some counterexamples:
from hypothesis import given, strategies as st
@given(st.lists(st.integers()))
def test_peakfinder_doesnt_crash(xs):
"""Finding the peak of a list doesn't crash."""
peakfinder(xs)
The peak of an array must be an element of the array
Sounds reasonable enough, right? But your code will return a list of length 1 if any of the intermediate steps reduce to such a list, an element otherwise. For example:
>>> from peaks import peakfinder
>>> peakfinder([1, 0])
[1]
>>> [1] in [1, 0]
False
>>> peakfinder([1, 2, 3])
2
>>> 2 in [1, 2, 3]
True
You should tweak the case when len(arr) == 1 to return the single element:
if len(arr) == 1:
return arr[0]
Here’s another small test I wrote to find a counterexample:
from hypothesis import given, strategies as st
@given(st.lists(st.integers()))
def test_peak_is_in_original_list(xs):
"""The peak of a list is in the list."""
assert peakfinder(xs) in xs