Consider the array:

original_array1 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}


I want to sort it in such a way that:

1. Sum of adjacent numbers should be a perfect square
2. You cannot reuse a number

So a possible solution is:

16 9 7 2 14 11 5 4 12 13 3 6 10 15 1 8 17


I write a C++ program to get this done using a recursive function and it works.

I was wondering how can I improve the program to:

1. Make it more readable and easy to understand (variable names, better handling or elimination of boundary conditions, comments etc.)
2. Use better library functions or C++ language features to make the code compact.
3. Is there a better algorithm/strategy that I can use instead of using recursive functions.

The motivation for this came from a daily problem posted on brilliant.org, I thought I would solve it by writing a program. But now I want to ask the community for pointers on how to become better at coding in general.

Here is the code have:

//Compile using g++ -std=c++11 arrange.cpp

#include <iostream>
#include <cstdint>
#include <cmath>

using namespace std;

int original_array1 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

bool isSumPerfectSquare(int x, int y) {
long double sr = sqrt((long double)x + (long double)y);
return ((sr - floor(sr)) == 0);
}

int * ArrangeNumbers(int * done, int * remaining, int size_done, int size_remaining) {
static int ctr = 0;
// cout<<"ArrangeNumbers() "<< (ctr++) << endl<<"    ";
// if(done != nullptr) {
//  for(int jj = 0; jj<size_done;jj++) {
//      cout<<done[jj]<<" ";
//  }
// }
// cout<<" | ";
// if(remaining != nullptr) {
//  for(int jj = 0; jj<size_remaining;jj++) {
//      cout<<remaining[jj]<<" ";
//  }
// }
// cout<<endl;
if(size_remaining == 1) { // Border Case 1: Last number remaining, lets check if pairs up with the last number in sorted array
if(isSumPerfectSquare(done[size_done-1],remaining)) {
int * finally_done = (int *) calloc(size_done+1,sizeof(int));
for(int jj = 0; jj<size_done;jj++) {
finally_done[jj] = done[jj];
}
finally_done[size_done] = remaining;
return finally_done;
} else {
return nullptr;
}
} else if(size_done == 0) { // Border Case 2:  Come back and choose the first number again
int * done1 = (int *) calloc(size_done+1,sizeof(int));
int * remaining1 = (int *) calloc(size_remaining-1,sizeof(int));

for(int kk = 0; kk<size_remaining;kk++) {
done1 = remaining[kk];
for(int ll = 0; ll<kk;ll++) {
remaining1[ll] = remaining[ll];
}
for(int ll = kk+1; ll<size_remaining;ll++) {
remaining1[ll-1] = remaining[ll];
}
int * sr_arr = ArrangeNumbers(done1, remaining1, size_done+1, size_remaining-1);
if(sr_arr != nullptr) {
free(done1);
free(remaining1);
return sr_arr;
}
}
free(done1);
free(remaining1);
return nullptr;
} else {
int * done1 = (int *) calloc(size_done+1,sizeof(int));
int * remaining1 = (int *) calloc(size_remaining-1,sizeof(int));

// Copy array till now
if(done != nullptr) {
for(int jj = 0; jj<size_done;jj++) {
done1[jj] = done[jj];
}
}

// Choose next number and respawn
for(int kk = 0; kk<size_remaining;kk++) {
if(isSumPerfectSquare(done1[size_done-1],remaining[kk])) {
done1[size_done] = remaining[kk];
for(int ll = 0; ll<kk;ll++) {
remaining1[ll] = remaining[ll];
}
for(int ll = kk+1; ll<size_remaining;ll++) {
remaining1[ll-1] = remaining[ll];
}
int * sr_arr = ArrangeNumbers(done1, remaining1, size_done+1, size_remaining-1);
if(sr_arr != nullptr) {
free(done1);
free(remaining1);
return sr_arr;
}
}
}
free(done1);
free(remaining1);
return nullptr;
}
}

int main() {
int * sorted_array = ArrangeNumbers(nullptr, original_array1, 0, 17);
cout<<"Original Array :";
for(int i = 0; i<17;i++) {
cout<<" "<<original_array1[i];
}
cout<<endl<<"Sorted Array   :";
if(sorted_array != nullptr) {
for(int i = 0; i<17;i++) {
cout<<" "<<sorted_array[i];
}
free(sorted_array);
}
cout<<endl;
return 0;
}



# Compilation options

Use more warnings, e.g. g++ -std=c++11 -Wall -Wextra. This will identify the unused variable ctr, for instance.

# Avoid using namespace std

Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

# Choice of type

If all the numbers are guaranteed to be positive, consider using an unsigned type for the array elements.

Prefer using std::array over raw (C-style) arrays.

# Checking for perfect square

It's good that we have a self-contained function for checking whether a number is a perfect square. However, it has accuracy problems when values reach the limit of a double's mantissa. It's also relatively slow, due to the use of std::sqrt(). One thing we could do instead is to create a std::set (or std::unordered_set) of the possible square numbers, and then simply test for membership of that set.

That looks something like this:

#include <algorithm>
#include <unordered_set>

unsigned original_array1 = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

bool isSumPerfectSquare(unsigned x) {
static auto const squares =
[]{
std::unordered_set<unsigned> s;
auto max = *std::max_element(std::begin(original_array1), std::end(original_array1));
for (auto value = 1u, diff = 1u;  value < max * 2;  value += (diff += 2))
s.insert(value);
return s;
}();

return squares.find(x) != squares.end();
}


# Prefer new[] and delete[]

When writing C++, prefer the new and delete operators and their array counterparts rather than C-style std::malloc(), std::calloc(), std::realloc() and std::free(). Prefer smart pointers and collections to bare pointers.

However, this algorithm shouldn't need any allocations at all, if we modify the input in place.

Here's how I'd do that, using std::swap to move each candidate in turn to the front of the array:

// shuffle [a..b), given preceding number
bool arrange_numbers(unsigned prev, unsigned *a, unsigned *b)
{
if (a == b) {
// no more numbers; we've done it!
return true;
}

for (unsigned *p = a;  p != b;  ++p) {
if (is_perfect_square(prev + *p)) {
std::swap(*a, *p);
if (arrange_numbers(*a, a+1, b)) {
// found a match
return true;
}
// reinstate the order, for our caller
std::swap(*a, *p);
}
}

// no satisfactory solution
return false;
}

bool arrange_numbers(std::array<unsigned,17>& array)
{
unsigned *a = array.begin();
unsigned *b = array.end();

for (unsigned *p = a;  p != b;  ++p) {
std::swap(*a, *p);
if (arrange_numbers(*a, a+1, b)) {
// found a match
return true;
}
}

// no matches
return false;
}


# Full modified code

#include <algorithm>
#include <array>
#include <iostream>
#include <unordered_set>
#include <utility>

std::array<unsigned,17> numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17};

bool is_perfect_square(unsigned x) {
static auto const squares =
[]{
std::unordered_set<unsigned> s;
auto max = *std::max_element(numbers.begin(), numbers.end());
for (auto value = 1u, diff = 1u;  value < max * 2;  value += (diff += 2))
s.insert(value);
return s;
}();

return squares.find(x) != squares.end();
}

// shuffle [a..b), given preceding number
bool arrange_numbers(unsigned prev, unsigned *a, unsigned *b)
{
if (a == b) {
// no more numbers; we've done it!
return true;
}

for (unsigned *p = a;  p != b;  ++p) {
if (is_perfect_square(prev + *p)) {
std::swap(*a, *p);
if (arrange_numbers(*a, a+1, b)) {
// found a match
return true;
}
// reinstate the order, for our caller
std::swap(*a, *p);
}
}

// no satisfactory solution
return false;
}

bool arrange_numbers(std::array<unsigned,17>& array)
{
unsigned *a = array.begin();
unsigned *b = array.end();

for (unsigned *p = a;  p != b;  ++p) {
std::swap(*a, *p);
if (arrange_numbers(*a, a+1, b)) {
// found a match
return true;
}
}

// no matches
return false;
}

int main()
{
std::cout << "Original array:";
for (auto i: numbers) {
std::cout << " " << i;
}
std::cout << '\n';

if (arrange_numbers(numbers)) {
std::cout << "Sorted array:";
for (auto i: numbers) {
std::cout << " " << i;
}
std::cout << '\n';
}
}


Better strategy at the first glance does not exist. Consider a graph formed by the numbers an array, with the edges connecting vertices which add up to a perfect square. The problem then is reduced to finding a Hamiltonian path. The problem is known to be NP-complete. There is an algorithm solving it in $$\O(n^2 2^n)\$$ time; in general case it is better than brute force, but still exponential.

Your case could have a better asymptotic, because the graph has a very particular structure. For starters, for path to exist the should be no more than 2 vertices of the degree 1 (if the array had 18, there would be 3 such vertices). Also your graph is very sparsely connected, and has quite a few vertices of degree 2. This suggests a heuristic similar to the Warnsdorf's rule: start with a vertex of the least degree, and always inspect the neighbors in the ascending order of degrees (smallest first).

For example in your array, starting with 16 (degree 1) forces the resulting sequence with not a single branch point.

• Even if you can reduce a problem to an NPC problem, it does not mean the original problem is necessarily hard. – Juho Feb 8 '19 at 19:29