I had a CS question that wants me to check for the number of palindromes found inside a single array of 6 cells. i was able to solve it by using many for loops, 7 of them to be exact, and I'm trying to find a way to make the code tidier by reducing the number of loops because they all do similar things with minor differences but i wasn't able to put a finger on the best idea to reduce them.
this my code:
int main()
{
int size = 6;
int array[size];
int palCount = 0;
for (int i = 0; i < size; i )
{
cin >> array[i];
}
bool isPal = true;
int size2 = 2;
for (int i = 1; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int arrToCheck[] = {currentNum, numAfter};
isPal = checkPalindrom(arrToCheck, size2);
if (isPal)
{
palCount ;
}
}
int size3 = 3;
for (int i = 1; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int numAfter2 = array[i 2];
int arrToCheck[] = {currentNum, numAfter, numAfter2};
isPal = checkPalindrom(arrToCheck, size3);
if (isPal)
{
palCount ;
}
}
int size4 = 4;
for (int i = 1; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int numAfter2 = array[i 2];
int numAfter3 = array[i 3];
int arrToCheck[] = {currentNum, numAfter, numAfter2, numAfter3};
isPal = checkPalindrom(arrToCheck, size4);
if (isPal)
{
palCount ;
}
}
int size5 = 5;
for (int i = 1; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int numAfter2 = array[i 2];
int numAfter3 = array[i 3];
int numAfter4 = array[i 4];
int arrToCheck[] = {currentNum, numAfter, numAfter2, numAfter3, numAfter4};
isPal = checkPalindrom(arrToCheck, size5);
if (isPal)
{
palCount ;
}
}
//================================================================
for (int i = 2; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int arrToCheck[] = {currentNum, numAfter};
isPal = checkPalindrom(arrToCheck, size2);
if (isPal)
{
palCount ;
}
}
for (int i = 2; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int numAfter2 = array[i 2];
int arrToCheck[] = {currentNum, numAfter, numAfter2};
isPal = checkPalindrom(arrToCheck, size3);
if (isPal)
{
palCount ;
}
}
for (int i = 2; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int numAfter2 = array[i 2];
int numAfter3 = array[i 3];
int arrToCheck[] = {currentNum, numAfter, numAfter2, numAfter3};
isPal = checkPalindrom(arrToCheck, size4);
if (isPal)
{
palCount ;
}
}
cout << palCount - 1 << endl;
}
in case anyone wants to try the code, this is the code of the function that checks for palindromes:
bool checkPalindrom(int arr[], int sizeOfArray)
{
int size = sizeOfArray;
bool pal = true;
for (int i = 0; i < size / 2; i )
{
if (arr[i] != arr[size - 1 - i])
{
pal = false;
}
}
return pal;
}
the differences between each loop that it starts with 2 elemts then 3 then 4... the arrayToCheck variable is the one that's changing between each loop and also the variable size.
im open to any ideas on how to reduce the number of loops while keeping the same functionality.thanks.
expected:
input: 1 1 1 1 1 1
output: 15
input: 1 2 2 1 5 5
output: 3
CodePudding user response：
Like you said, most of the loops are doing really similar thing, so let look at one of them and see what it is doing:
int size4 = 4;
for (int i = 2; i <= 6; i )
{
int currentNum = array[i];
int numAfter = array[i 1];
int numAfter2 = array[i 2];
int numAfter3 = array[i 3];
int arrToCheck[] = {currentNum, numAfter, numAfter2, numAfter3};
isPal = checkPalindrom(arrToCheck, size4);
if (isPal)
{
palCount ;
}
}
First, there is a bound issue. When
iis greater than 2, you will goi 3is 6, which will create a bound issue when you trying to access that index fromarray.Second, we don't need to create this
arrToCheck. ThecheckPalindromfunction simply want a pointer and a size, so we can just passarray ito it.
And now we can simplify this part like:
for (int i = 2; i < 3; i) {
isPal = checkPalindrom(array i, size4);
if (isPal)
{
palCount;
}
}
Now if we do the same thing with all the other loops, we will realize, the only difference between them now is the condition of the for loop, and the sizeX in there are different. We are getting something like:
for (int i = 1; i < 5; i) { ... size2 ... }
for (int i = 1; i < 4; i) { ... size3 ... }
for (int i = 1; i < 3; i) { ... size4 ... }
for (int i = 1; i < 2; i) { ... size5 ... }
for (int i = 2; i < 5; i) { ... size2 ... }
for (int i = 2; i < 4; i) { ... size3 ... }
for (int i = 2; i < 3; i) { ... size4 ... }
I hope you can see the pattern now. The beginning is from 1 to 2, the end is from 5(size of original array - 1) to beginning 1, and the sizeX is size of original array - end 1. With these information, you can get a 2d for loop like:
for (int i = 1; i < 3; i) {
for (int j = size - 1; j > i; --j) {
... size - j 1 ...
}
}
Now, there is one major bug with your solution(become much easier to spot when we don't need look at 100 lines of repetitive code), remember what i and j are? They are basically the numbers we used with checkPalindrom function:
checkPalindrom(array i, j)
Why exactly does i only range between 1 and 2? Shouldn't we start the check with an array that begins from the first number, and only end after we have less than 2 numbers? So we really should have changed the outer loop to loop from 0 to 5.
CodePudding user response：
First thing to notice, you're essentially copying the array members when you call checkPalindrom(). That's unnecessary: you can simply call it as checkPalindrom(array i, size_i);. Then your code is reduced to essentially do the same loop multiple times. You still need to fix array boundary errors (as the original code over-indexed the array).
So the loop body is:
auto checker = [&](int size_i, int i_min, int i_max) {
for (int i = i_min; i <= i_max && i size_i <= size; i )
{
isPal = checkPalindrom(array i, size_i);
if (isPal)
{
palCount ;
}
}
Then you loop it for the necessary range:
for (int i_min = 1; i_min <= 2; i_min) {
for (int size_i = 2; size_i i_min < size; size_i) {
checker(i_min, 6, size_i);
}
}
Also, it's suggested to change sizes and offsets to size_t.