Broken relations between measures of presortedness
I decided to upgrade the probes/relations.cpp test with RapidCheck as an experiment, because property-based testing felt like the proper tool for that job. Unfortunately it was a bit too quick to find issues:
Start 459: relations between measures of presortedness
459/1252 Test #459: relations between measures of presortedness ............................................................................................................***Failed 0.25 sec
Filters: "relations between measures of presortedness"
Randomness seeded to: 373856
Using configuration: seed=1750367150
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main-tests.exe is a Catch2 v3.8.1 host application.
Run with -? for options
-------------------------------------------------------------------------------
relations between measures of presortedness
Exc(X) + 1 ≤ Ham(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
Falsifiable after 1 tests
std::tuple<std::vector<int>>:
([])
Returned false
-------------------------------------------------------------------------------
relations between measures of presortedness
2 sqrt(Enc(X)) + 1 ≤ Inv(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
Falsifiable after 1 tests
std::tuple<std::vector<int>>:
([])
Returned false
-------------------------------------------------------------------------------
relations between measures of presortedness
2 Enc(X) ≤ Exc(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
Falsifiable after 6 tests and 1 shrink
std::tuple<std::vector<int>>:
([-2, 0, -1])
Returned false
-------------------------------------------------------------------------------
relations between measures of presortedness
Inv(X) + Exc(X) ≤ Spear(X)
-------------------------------------------------------------------------------
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:27
...............................................................................
D:/Morwenn/Projets/cpp-sort/build-mingw/RapidCheck-src/extras/catch/include/rapidcheck/catch.h:52: FAILED:
explicitly with message:
Falsifiable after 9 tests and 2 shrinks
std::tuple<std::vector<int>>:
([-1, -1, -2])
Returned false
===============================================================================
test cases: 1 | 0 passed | 1 failed
assertions: 26 | 22 passed | 4 failed
That's quite a few failing relations to analyze and fix:
- Exc(X) + 1 ≤ Ham(X) with an empty sequence
- 2 sqrt(Enc(X)) + 1 ≤ Inv(X) with an empty sequence
- 2 Enc(X) ≤ Exc(X) with sequence (-2, 0, 1)
- Inv(X) + Exc(X) ≤ Spear(X) with sequence (-1, -1, -2)