[C/C++] Project Euler #61 - Cyclical Figurate Numbers

This problem follows directly from problem 60 and is labeled as having a 20% difficulty level, but in my case, I didn’t find it particularly hard to solve.

To tackle problems involving n-gonal numbers, it’s generally effective to focus on correctly checking whether a number satisfies the condition of being an n-gonal number. That approach should be sufficient without much difficulty.

---

drawing n-gonal

In this problem, you’re asked to find a cyclic sequence of six 4-digit numbers, each one being a different type of polygonal number—specifically, a triangle (3-gonal), square (4-gonal), …, up to an octagonal (8-gonal) number—where the numbers are connected by their last two and first two digits.

The strategy is to first generate all 4-digit 3-gonal numbers. Then, for each one, you find a 4-gonal number that starts with the last two digits of the 3-gonal number. You continue this process, chaining the numbers together, aiming to finally return to a number that links back to the original 3-gonal number—thus forming a cycle.

In my case, I precomputed all the relevant polygonal numbers for n from 3 to 8 and then wrote code to test whether the numbers could form such a cyclic sequence. In fact, there aren’t that many 4-digit n-gonal numbers. Since each polygonal number can be represented by a quadratic formula, their values grow rapidly, which limits the total count.

//------------------------------------------------
//    Project Euler #61 - Cyclical Figurate Numbers
//        - by Aubrey Choi
//        - created at 2015-04-09
//------------------------------------------------
#include <stdio.h>
#include <math.h>

int cyclic(int bitflag, int start, int end, int sum);
int polygonal[6][1000];
int pcount[6] = { 0, 0, 0, 0, 0, 0 };

int main()
{
    int pdiff[6] = { 1, 1, 1, 1, 1, 1 };
    int pdiff2[6] = { 1, 2, 3, 4, 5, 6 };

    for( int i = 0 ; i < 6 ; i++ )
    {
        int s = 0;
        for( int n = 0 ; ; n++, pdiff[i] += pdiff2[i] )
        {
            s += pdiff[i];
            if( s < 1000 ) continue;
            if( s >= 10000 ) break;
            if( s%100 < 10 ) continue;
            polygonal[i][pcount[i]++] = s;
        }
        printf("%d : %d\n", i, pcount[i]);
    }
    for( int i = 0 ; i < pcount[0] ; i++ )
    {
        int c = polygonal[0][i];
        int ans = cyclic(1, c%100, c/100, c);
        if( ans ) printf("Ans = %d\n", ans);
    }
}

int cyclic(int bitflag, int start, int end, int sum)
{
    if( bitflag == 0x3f )
    {
        if( start == end ) return sum;
        return 0;
    }
    for( int i = 1 ; i < 6 ; i++ )
    {
        if( (bitflag>>i)&1 ) continue;
        for( int j = 0 ; j < pcount[i] ; j++ )
        {
            int c = polygonal[i][j];
            if( c/100 == start )
            {
                int ans = cyclic(bitflag|(1<<i), c%100, end, sum+c);
                if( ans ) return ans;
            }
        }
    }
    return 0;
}