How does a recursive code determine if palindrome work?

Question

I have a problem question and a snippet code below. The snippet is filled already because I found out the solution but I do not understand why it is like that. Could you help me explain how the codes work?

Problem: Ten tiles each have strings of in between 1 and 4 letters on them (hardcoded in the code below). The goal of this problem is to complete the code below so it counts the number of different orders in which all of the tiles can be placed such that the string they form creates a palindrome (a word that reads the same forwards and backwards). All of main, as well as the function eval which determines if a particular ordering of the tiles forms a palindrome. You may call this function in the function go. Complete the recursive function (named go) to complete the solution.

Snippet code:

#include <stdio.h>
#include <string.h>

#define N 10
#define MAXLEN 5

int go(int perm[], int used[], int k, char tiles[N][MAXLEN]);
int eval(int perm[], char tiles[N][MAXLEN]);

char MYTILES[N][MAXLEN] = {
    "at", "ta", "g", "cc", "ccac", "ca", "cc", "gag", "cga", "gc"
};

int
main(void)
{
    int perm[N];
    int used[N];

    for (int i = 0; i < N; i++)
        used[i] = 0;

    int res = go(perm, used, 0, MYTILES);

    printf("Number of tile orderings that create palindromes is %d\n", res);

    return 0;
}

int
go(int perm[], int used[], int k, char tiles[N][MAXLEN])
{
    if (k == N)
        return eval(perm, tiles);
    int res = 0;

    for (int i = 0; i < N; i++) {
        if (used[i])
            continue;
        used[i] = 1;
        perm[k] = i;
        res += go(perm, used, k + 1, tiles);
        used[i] = 0;
    }

    return res;
}

int
eval(int perm[], char tiles[N][MAXLEN])
{
    char tmp[N * MAXLEN];
    int idx = 0;

    for (int i = 0; i < N; i++) {
        int len = strlen(tiles[perm[i]]);

        for (int j = 0; j < len; j++)
            tmp[idx++] = tiles[perm[i]][j];
    }
    tmp[idx] = '\0';
    for (int i = 0; i < idx / 2; i++)
        if (tmp[i] != tmp[idx - 1 - i])
            return 0;
    return 1;
}

Thank you. I appreciate all help!!

Answer 1

To understand this code, add the following line to the start of eval():

for( int j = 0; j < N; j++ ) printf( "%d ", perm[j] ); putchar('\n');

The for() loop in go() causes a recursion that is 10 levels deep, ultimately generating 10! (~3.6 million) permutations of the 10 indices from 0 to 9. In sequence, each of those permutations is used to concatenate the 'tokens' (the short ACTG variations) into a single string that is then tested for being palindromic by `eval()'

This is called a "brute force" search through the possibility space.

Below I've revised the code to be slightly more compact, adding two "printf debugging" lines (marked "/**/") that report what the program is doing. You'll need some patience if you wish to watch millions of permutations of 0 to 9 scroll by, or simply comment out that line and recompile. I also shuffled things around and made the two interesting arrays global instead of "whacking the stack" by passing them up/down the recursion. Less code is better. This program is "single purpose". The clarity gained justifies using global variables in this instance, imho.

More interesting is the additional puts() line that reports the palindromic sequences.

#include <stdio.h>
#include <string.h>

#define N 10
#define MAXLEN 5

char MYTILES[N][MAXLEN] = { "AT","TA","G","CC","CCAC","CA","CC","GAG","CGA","GC" };
int perm[N], used[N] = { 0 };

int go( int k ) {
    if (k == N) {
        // At extent of recursion here.
/**/    for( int j = 0; j < k; j++ ) printf( "%d ", perm[j] ); putchar('\n');

        // Make a string in this sequence
        char tmp[N*MAXLEN] = {0};
        for( int i = 0; i < N; i++ )
            strcat( tmp, MYTILES[ perm[ i ] ] );

        // Test string for being palidromic
        for( int l = 0, r = strlen( tmp ) - 1; l <= r; l++, r-- )
            if( tmp[l] != tmp[r] )
                return 0; // Not palidrome

/**/    puts( tmp );
        return 1; // Is palidrome
    }

    // recursively generate permutations here
    int res = 0;
    for( int i = 0; i < N; i++ )
        if( !used[i] ) {
            used[i] = 1;
            perm[k] = i;
            res += go( k+1 );
            used[i] = 0;
        }
    return res;
}

int main( void ) {
    printf( "Palindromic tile orderings: %d\n", go( 0 ) );

    return 0;
}

An immediate 'speed-up' would be to test that the first letter of the 0th string to be permuted matches the last letter of the 9th string... Don't bother concatenating if a palindrome is impossible from the get-go. Other optimisations are left as an exercise for the reader...

BTW: It's okay to make a copy of code and add your own print statements so that the program reports what it is doing when... Or, you could single-step through a debugger...

UPDATE
Having added a preliminary generation of a 10x10 matrix to 'gate' the workload of generating strings to be checked as palindromic, with the 10 OP supplied strings, it turns out that 72% of those operations were doomed to fail from the start. Of the 3.6 million "brute force" attempts, a quick reference to this pre-generated matrix prevented about 2.6 million of them.

It's worthwhile trying to make code efficient.

UPDATE #2:
Bothered that there was still a lot of 'fat' in the execution after trying to improve on the "brute force" in a simple way, I've redone some of the code.

Using a few extra global variables (the state of processing), the following now does some "preparation" in main(), then enters the recursion. In this version, once the string being assembled from fragments is over half complete (in length), it is checked from the "middle out" if it qualifies as being palindromic. If so, each appended fragment causes a re-test. If the string would never become a palindrome, the recursion 'backs-up' and tries another 'flavour' of permutation. This trims the possibility space immensely (and really speeds up the execution.)

char *Tiles[] = { "AT","TA","G","CC","CCAC","CA","CC","GAG","CGA","GC" };
const int nTiles = sizeof Tiles/sizeof Tiles[0];
int used[ nTiles ];

char buildBuf[ 1024 ], *cntrL, *cntrR; // A big buffer and 2 pointers.
int fullLen;

int cntTested, goCalls; // some counters to report iterations

uint32_t factorial( uint32_t n ) { // calc n! (max 12! to fit uint32_t)
    uint32_t f = 1;
    while( n ) f *= n--;
    return f;
}

int hope() { // center outward testing for palindromic characteristics
    int i;
    for( i = 0; cntrL[ 0 - i ] == cntrR[ 0 + i ]; i++ ) ; // looping
    return cntrR[ 0 + i ] == '\0';
}

int go( int k ) {
    goCalls++;
    if( k == nTiles ) { // at full extent of recursion here
        // test string being palindromic (from ends toward middle for fun)
        cntTested++;
        for( int l = 0, r = fullLen - 1; l <= r; l++, r-- )
            if( buildBuf[l] != buildBuf[r] )
                return 0; // Not palindrome
/**/    puts( buildBuf );
        return 1; // Is palindrome
    }

    // recursively generate permutations here
    // instead of building from sequence of indices
    // this builds the (global) sequence string right here
    int res = 0;
    char *at = buildBuf + strlen( buildBuf );
    for( int i = 0; i < nTiles; i++ )
        if( !used[i] ) {
            strcpy( at, Tiles[ i ] );
            // keep recursing until > half assembled and hope persists
            if( at < cntrL || hope() ) {
                used[i] = 1;
                res += go( k+1 ); // go 'deeper' in the recursion
                used[i] = 0;
            }
        }
    return res;
}

int main( void ) {
    for( int i = 0; i < nTiles; i++ )
        fullLen += strlen( Tiles[i] );

    if( fullLen % 2 == 0 ) // even count
        cntrR = (cntrL = buildBuf + fullLen/2 - 1) + 1; // 24 ==> 0-11 & 12->23
    else
        cntrR = cntrL = buildBuf + fullLen/2; // 25 ==> 0-12 & 12->24

    printf( "Palindromic tile orderings: %d\n", go( 0 ) );

    printf( "Potential: %d\n", factorial( nTiles ) );
    printf( "Calls to go(): %d\n", goCalls );
    printf( "Actual: %d\n", cntTested );

    return 0;
}

ATCCACGAGCCGCCGAGCACCTA
ATCCACGAGCCGCCGAGCACCTA
ATCCACGCCGAGAGCCGCACCTA
ATCCACGCCGAGAGCCGCACCTA
ATCACCGAGCCGCCGAGCCACTA
ATCACCGCCGAGAGCCGCCACTA
ATCACCGAGCCGCCGAGCCACTA
ATCACCGCCGAGAGCCGCCACTA
TACCACGAGCCGCCGAGCACCAT
TACCACGAGCCGCCGAGCACCAT
TACCACGCCGAGAGCCGCACCAT
TACCACGCCGAGAGCCGCACCAT
TACACCGAGCCGCCGAGCCACAT
TACACCGCCGAGAGCCGCCACAT
TACACCGAGCCGCCGAGCCACAT
TACACCGCCGAGAGCCGCCACAT
CCACATGAGCCGCCGAGTACACC
CCACATGAGCCGCCGAGTACACC
CCACATGCCGAGAGCCGTACACC
CCACATGCCGAGAGCCGTACACC
CCACTAGAGCCGCCGAGATCACC
CCACTAGAGCCGCCGAGATCACC
CCACTAGCCGAGAGCCGATCACC
CCACTAGCCGAGAGCCGATCACC
CACCATGAGCCGCCGAGTACCAC
CACCATGCCGAGAGCCGTACCAC
CACCTAGAGCCGCCGAGATCCAC
CACCTAGCCGAGAGCCGATCCAC
CACCATGAGCCGCCGAGTACCAC
CACCATGCCGAGAGCCGTACCAC
CACCTAGAGCCGCCGAGATCCAC
CACCTAGCCGAGAGCCGATCCAC
Palindromic tile orderings: 32
Potential: 3628800
Calls to go(): 96712
Actual: 32

UPDATE #3 (having fun)
When there's too much code, and an inefficient algorithm, it's easy to get lost and struggle to work out what is happening.

Below produces exactly the same results as above, but shaves a few more operations from the execution. In short, go() is called recursively until at least 1/2 of the candidate string has been built-up. At that point, hope() is asked to evaluate the string "from the middle, out." As long as the conditions of being palindromic (from the centre, outward) are being met, that evaluation is repeated as the string grows (via recursion) toward its fullest extent. It is the "bailing-out early" that makes this version far more efficient than the OP version.

One further 'refinement' is that the bottom of the recursion is found without an extra call to \0. Once one has the concepts of recursion and permutation, this should all be straight forward...

char *Tiles[] = { "AT", "TA", "G", "CC", "CCAC", "CA", "CC", "GAG", "CGA", "GC" };
const int nTiles = sizeof Tiles/sizeof Tiles[0];
int used[ nTiles ];

char out[ 1024 ], *cntrL, *cntrR;

int hope() { // center outward testing for palidromic characteristics
    char *pL = cntrL, *pR = cntrR;
    while( *pL == *pR ) pL--, pR++;
    return *pR == '\0';
}

int go( int k ) {
    int res = 0;
    char *at = out + strlen( out );
    for( size_t i = 0; i < nTiles; i++ )
        if( !used[i] ) {
            strcpy( at, Tiles[ i ] );
            if( at >= cntrL && !hope() ) // abandon this string?
                continue;
            if( k+1 == nTiles ) { // At extent of recursion here.
                puts( out );
                return 1;
            }
            used[i] = 1, res += go( k+1 ), used[i] = 0;
        }
    return res;
}

int main( void ) {
    int need = 0;
    for( size_t i = 0; i < nTiles; i++ )
        need += strlen( Tiles[ i ] );

    cntrL = cntrR = out + need/2; // odd eg: 25 ==> 0-12 & 12->24
    cntrL -= (need % 2 == 0 ); // but, if even eg: 24 ==> 0-11 & 12->23

    printf( "Palindromic tile orderings: %d\n", go( 0 ) );

    return 0;
}