I got this problem statement from a programming puzzle book. I am able to find out the horizontal palindromes, but only if the entire row is a palindrome.
How can I fulfill this? Also how can be diagonal palindromes acquired?
A pseudo code is okay too, I just need the basic logic behind this. I will perform the rest.
Thank You.
The trick behind finding the horizontal palindromes is the take an entire row and then split it into various strings. Once that is done, you need to check if that string is a palindrome. For vertical strings, you need to do the same thing for the columns.
Now for the diagonal ones, you need to start from a point at the edge and then move forward diagonally (+[1][1]) for going to the bottom right until you reach the end. Now keep doing for every tactical point of every edge which will help you get all the diagonal strings, the next thing you need to do is to split these strings and check if each of these short strings are a palindrome or not.
This would come under dynamic programming most likely. Although I am confused it might come under greedy approach as well. I'll confirm it once with my professor.
Here is the code I did back when I was trying to solve the same thing -
#define PALLEN 2
#include <stdio.h>
#include <string.h>
int a[10][10];
/*int a[5][5] = {
{ 1, 2, 1, 3, 5 } ,
{ 4, 5, 6, 7, 4 } ,
{ 4, 5, 5, 4, 1 } ,
{ 1, 9, 2, 1, 4 } ,
{ 1, 9, 4, 1, 5 }
};*/
int n=0;
void checkPalindrome(char*);
void diagonalPal();
void stringSpliter(char*);
int main() {
int i, j, k, l, x;
int c = 0;
int jmp;
int ptr = 0;
int diag;
char recycler[20];
char diaglist[25];
char revdiaglist[25];
system("cls");
printf("\nEnter the dimension (n) of this square matrix i.e. (n*n) - ");
scanf("%d", &n);
printf("\nNow enter the elements for this %d*%d matrix - ", n,n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d", &a[i][j]);
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("-%d-", a[i][j]);
}
printf("\n");
}
printf("\nHorizontal Palindromes");
for (i = 0; i < n; i++) {
for (j = n-1, k = PALLEN; j > 0; j--, k++) {
while (c < j) {
jmp = c;
memset(recycler, 0, 20);
ptr = 0;
for (l = 0; l < k; l++) {
recycler[ptr] = a[i][jmp]; //0,0 -- 0,1
ptr++;
jmp++;
}
checkPalindrome(recycler);
c++;
}
c = 0;
}
}
printf("\n\nVertical Palindromes");
for (i = 0; i < n; i++) {
for (j = n-1, k = PALLEN; j > 0; j--, k++) {
while (c < j) {
jmp = c;
memset(recycler, 0, 20);
ptr = 0;
for (l = 0; l < k; l++) {
recycler[ptr] = a[jmp][i]; //0,0-- 1,0
ptr++;
jmp++;
}
checkPalindrome(recycler);
c++;
}
c = 0;
}
}
printf("\n\nDiagonal Palindromes");
diagonalPal();
}
void stringSpliter(char *a){
int i,j,k,ptr,jmp,c=0,l;
int len;
len = strlen(a);
char recycler[20];
for (j = len-1, k = PALLEN; j > 0; j--, k++) {
while (c < j) {
jmp = c;
memset(recycler, 0, 20);
ptr = 0;
for (l = 0; l < k; l++) {
recycler[ptr] = a[jmp]; //0,0 -- 0,1
ptr++;
jmp++;
}
checkPalindrome(recycler);
c++;
}
c = 0;
}
}
void diagonalPal(){
int i, x=0, j, k, ptr=0;
char diagrecycler[20];
for(i = 0; i < n; i++){
memset(diagrecycler, 0, 25);
ptr = 0;
for(j = i, k = 0; j < n, k < n; j++, k++){
diagrecycler[ptr++] = a[j][k];
}
stringSpliter(diagrecycler);
}
for(i = 1; i < n; i++){
memset(diagrecycler, 0, 25);
ptr = 0;
for(j = 0, k = i; j < n, k < n ;j++, k++){
diagrecycler[ptr++] = a[j][k];
}
stringSpliter(diagrecycler);
}
}
void checkPalindrome(char *string){
int isPalindrome = 1, i=0;
char rev[20];
strcpy(rev, string);
strrev(rev);
isPalindrome = strcmp(rev, string);
if(isPalindrome == 0){
printf("\n");
while(string[i]!='\0') printf("%d", string[i++]);
}
}
// Output
/*Enter the dimension (n) of this square matrix i.e. (n*n) - 4
Now enter the elements for this 4*4 matrix - 1 2 3 4
5 2 1 6
8 1 1 8
9 5 3 2
-1--2--3--4-
-5--2--1--6-
-8--1--1--8-
-9--5--3--2-
Horizontal Palindromes
11
8118
Vertical Palindromes
22
11
3113
Diagonal Palindromes
121
212
G:\Code snippets\C programmes>*/