#include
#include
#include
bool solution(std::vector& A)
{
std::cout << "Working on vector: [";
for(auto i = 0; i < A.size()-1; ++i)
{
std::cout << A[i] << ",";
}
if(A.size() > 0)
{
std::cout << A[A.size()-1];
}
std::cout << "]\n";
if(A.size() < 2)
{
return true; //There's - or 1 elements: inherently sorted
}
int chain_len = 0;
int longest_chain = 0;
int last_chain_start = 0;
int chain_count = 0;
bool pair_found = false;
for(auto i = 1; i < A.size(); ++i)
{
std::cout << "\tA[i]=" << A[i] << ":\n";
if(A[i] < A[i-1])
{
std::cout << "\t\tDecreasing chain\n";
if(chain_len == 0) //This is a new chain
{
//The existence of multiple chains of decreasing numbers does not make the problem unsolvable. Consider:
// [4,2,3,1]
//Here, we have two chains of length 1, but the result is sortable in a single swap. However, the same is not true of the similar vector:
// [2,1,4,3]
//In this case, the second chain begins higher than the former chain, meaning that they would need to be swapped independently to become sorted (in the previous case, multiple swaps would be needed in an independent approach - [4,2,3,1] -> [2,4,1,3] -> [2,1,4,3] -> [1,2,3,4]. Oh, hi, BubbleSort. What are you doing in my O(N) algorithm?)
if(last_chain_start > A[i-1])
{
std::cout << "\t\tFalse: too many chains that can't be swapped over.\n";
return false;
}
last_chain_start = A[i-1];
}
++chain_len; //New or not, the length of this chain is now one higher
//A continuously-decreasing chain may be sortable in a single swap if sufficiently short. Consider:
// [3,2,1] => Sortable in a single swap
// [4,3,2,1] => Not sortable in a single swap
//Thus, if a number is a decreasing chain of length 0, any decreasing chain of length > 2 cannot be sorted in a single swap
if(chain_len > 2)
{
std::cout << "\t\tFalse: Chain too long to sort in one swap.\n";
return false;
}
if(chain_len == 2 && pair_found)
{
std::cout << "\t\tFalse: Long chain started with a sequence of the same digits.\n";
return false;
}
}
//Finding a sequence of successive equal numbers can be effectively ignored (or, rather, treated as a single instance of that number)
//In the case where this is not part of a chain, the order doesn't matter for sorting so they can be treated as sorted.
//If they are in the middle of a chain, then numbers either side of the pair need to be swapped anyway
//If they are at one end of a chain, then either the first or last needs to be swapped, *unless* the chain is length > 2. Consider:
// [1,2,5,4,3,3]
//In which the last 3 cannot be swapped for the 5, as this would yield [1,2,3,4,3,5]. So, if the chain length is already 2, finding a duplicate at the end is a filure
//Conversely, we need to ensure that we know if we began with a pair
else if(A[i] == A[i-1])
{
std::cout << "\t\tSame value\n";
pair_found = true;
}
else //These numbers are correctly sorted already, so reset everything
{
std::cout << "\t\tIncreasing chain: Terminate any existing chain.\n";
pair_found = false;
chain_count++;
chain_len = 0;
}
}
//We've escaped the loop: Need to perform all the loop logic again to make sure that we trap all the right values
if(chain_len > 2)
{
return false;
}
return true;
}
int main()
{
//Basic tests
//Short input
std::vector empty{}; //Expect true
assert(solution(empty));
std::vector single_el{1}; //Expect true
assert(solution(single_el));
//Already sorted
std::vector short_sorted{1,2,3}; //Expect true
assert(solution(short_sorted));
//Trivially sortable
std::vector short_trivial{3,2,1}; //Expect true
assert(solution(short_trivial));
//Sortable - multiple chains
std::vector sortable_multichain{4,2,3,1}; //Expect true
assert(solution(sortable_multichain));
//Not sortable
//Chain too long
std::vector unsortable_single{4,3,2,1}; //Expect false
assert(!solution(unsortable_single));
//Too many chains
std::vector unsortable_multichain{2,1,4,3}; //Expect false
assert(!solution(unsortable_multichain));
//Less trivial
//Duplicate numbers
std::vecotr all_same{3,3,3,3,3,3}; //Expect true
assert(solution(all_same));
//Pair starts chain
std::vector pair_starts_chain{1,2,4,4,3,5}; //Expect true
assert(solution(pair_starts_chain));
//Pair ends chain
std::vector pair_ends_chain{1,2,3,5,4,4,6}; //Expect true
assert(solution(pair_ends_chain));
//Pair within chain
std::vector pair_within_chain{1,2,5,4,4,3}; //Expect true
assert(solution(pair_within_chain));
//Pair - pathological
std::vector pair_ends_long_chain{1,2,5,4,3,3,6}; //Expect false
assert(solution(pair_ends_long_chain));
std::vector pair_starts_long_chain{1,2,5,5,4,3,6}; //Expect false
assert(solution(pair_starts_long_chain));
return 0;
}