3
\$\begingroup\$

Project Euler Problem 61 asks:

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

$$\begin{array}{lll} \textrm{Triangle} & P_{3,n}=n(n+1)/2 & 1, 3, 6, 10, 15, \ldots\\ \textrm{Square} & P_{4,n}=n^2 & 1, 4, 9, 16, 25, \ldots\\ \textrm{Pentagonal} & P_{5,n}=n(3n−1)/2 & 1, 5, 12, 22, 35, \ldots\\ \textrm{Hexagonal} & P_{6,n}=n(2n−1) & 1, 6, 15, 28, 45, \ldots\\ \textrm{Heptagonal} & P_{7,n}=n(5n−3)/2 & 1, 7, 18, 34, 55, \ldots\\ \textrm{Octagonal} & P_{8,n}=n(3n−2) & 1, 8, 21, 40, 65, \ldots \end{array}$$

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

  1. The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
  2. Each polygonal type: triangle \$(P_{3,127}=8128)\$, square \$(P_{4,91}=8281)\$, and pentagonal \$(P_{5,44}=2882)\$, is represented by a different number in the set.
  3. This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

While revising my previous solutions to bound under 5 seconds (because this is the most logical limit for any project Euler solution, otherwise the algorithm is flawed or not the best) I came to this which runs in around 10-15 seconds (peak at 12).

I have tried to make it better but I can't think of any remarkable improvements yet.

    static Stack<Integer> figurateStack;

    public static int get61() {
    figurateStack = new Stack<Integer>();
    int count = -1;
    int i = 1111;// minimum
    final int n = 6;
    final int low_lim = 3;
    int[] a = new int[n];
    boolean flag = false;// flag to use as a stepback conjugate
    boolean stepback = false;
    do {
        flag = false;
        if (count < n - 2) {
            for (; i < 9999; i++) {
                if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
                    if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
                        ++count;
                        a[count] = i;
                        break;
                    } else {
                        figurateStack.pop();
                    }
                }
            }
        } else {
            i = (i % 100) * 100 + a[0] / 100;
            if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
                ++count;
                a[count] = i;
                break;
            } else {
                stepback = true;
            }
        }
        if (i == 9999) {
            stepback = true;
        }
        if (stepback) {
            figurateStack.pop();
            i = a[count] + 1;
            --count;
            flag = true;
            stepback = false;
        }
        if (count < n - 2 && !flag) {
            i = 100 * (i % 100) + 10;
            flag = false;
        }
    } while (count < 6);
    return a[0] + a[1] + a[2] + a[3] + a[4] + a[5];
}

public static boolean isSpecialFigurate(int x, int lowlim, int upplim) {
    for (int index = lowlim; index <= upplim; index++) {
        if (!figurateStack.contains(index)) {
            long n = (long) Math.floor((Math.sqrt(8 * (index - 2) * x + (index - 4) * (index - 4)) + (index - 4)) / (2 * (index - 2)));         
            if (getFigurateNumbers(n, index) == x) {
                figurateStack.push(index);
                return true;
            }
        }
    }
    return false;
}

    public static long getFigurateNumbers(long n, int r) {
    return (n * n * (r - 2) - n * (r - 4)) / 2;
}
\$\endgroup\$
  • \$\begingroup\$ @200_success thankyou so much * bows * \$\endgroup\$ – RE60K Jun 17 '15 at 8:56
  • \$\begingroup\$ You can avoid a lot of unnecessary work if you don't generate lots of useless numbers in order to push them through expensive filters; you can get away with generating each number just once, directly from its respective formula. Can't say much more than that - except perhaps for the word 'bitmask' - without spelling out the whole solution and robbing you of the amazing buzz of discovery... \$\endgroup\$ – DarthGizka Feb 17 '16 at 16:35
2
\$\begingroup\$
boolean flag = false;//FLAG flag to use as a stepback conjugate
boolean stepback = false;
do {
    flag = false;//FLAG
    if (count < n - 2) {
        for (; i < 9999; i++) {
            if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
                if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
                    ++count;
                    a[count] = i;
                    break;
                } else {
                    figurateStack.pop();
                }
            }
        }
    } else {
        i = (i % 100) * 100 + a[0] / 100;
        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
            ++count;
            a[count] = i;
            break;
        } else {
            stepback = true;
        }
    }
    if (i == 9999) {
        stepback = true;
    }
    if (stepback) {
        figurateStack.pop();
        i = a[count] + 1;
        --count;
        flag = true;//FLAG
        stepback = false;
    }
    if (count < n - 2 && !flag) {//FLAG
        i = 100 * (i % 100) + 10;
        flag = false;//FLAG
    }
} while (count < 6);
return a[0] + a[1] + a[2] + a[3] + a[4] + a[5];

You've got a flag variable in there. But from what I see, you don't need it. I've labeled all the usages with //FLAG.

The only line that sets flag to true is inside the if statement stepback. stepback is triggered by i == 9999 or some other condition earlier.

flag is set to false at the top of your do-while loop. So every iteration, it's set to false.

Because of this, the flag variable cannot be changed from false until the stepback if-statement.

So we can do this:

    if (stepback) {
        figurateStack.pop();
        i = a[count] + 1;
        --count;
        flag = true;//FLAG
        stepback = false;
    } else if (count < n - 2) {
        i = 100 * (i % 100) + 10;
        flag = false;//FLAG
    }

if stepback occured, flag is true, and the if statement thereafter becomes always false. So turn it into an else.

You don't make any other checks for flag, so now flag can be removed.

boolean stepback = false;
do {
    if (count < n - 2) {
        for (; i < 9999; i++) {
            if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
                if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
                    ++count;
                    a[count] = i;
                    break;
                } else {
                    figurateStack.pop();
                }
            }
        }
    } else {
        i = (i % 100) * 100 + a[0] / 100;
        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
            ++count;
            a[count] = i;
            break;
        } else {
            stepback = true;
        }
    }
    if (i == 9999) {
        stepback = true;
    }
    if (stepback) {
        figurateStack.pop();
        i = a[count] + 1;
        --count;
        stepback = false;
    } else if (count < n - 2) {
        i = 100 * (i % 100) + 10;
    }
} while (count < 6);
return a[0] + a[1] + a[2] + a[3] + a[4] + a[5];

Next, we can collapse the if statement i == 9999 to be included in the stepback check:

Instead of

    if (i == 9999) {
        stepback = true;
    }
    if (stepback) {

We just do

    if (stepback || i == 9999) {

Because stepback disables itself, we don't need to worry about previous iterations of the while loop having stepback = true.

There's also an explicit else that we can make implicit...

        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
            ++count;
            a[count] = i;
            break;
        } else {
            stepback = true;
        }

to

        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
            ++count;
            a[count] = i;
            break;
        } 
        stepback = true;

Making the total code

boolean stepback = false;
do {
    if (count < n - 2) {
        for (; i < 9999; i++) {
            if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
                if (count == -1 || (count >= 0 && i / 100 == a[count] % 100) && i > 1000) {
                    ++count;
                    a[count] = i;
                    break;
                } else {
                    figurateStack.pop();
                }
            }
        }
    } else {
        i = (i % 100) * 100 + a[0] / 100;
        if (isSpecialFigurate(i, low_lim, low_lim + (n - 1))) {
            ++count;
            a[count] = i;
            break;
        }
        stepback = true;
    }
    if (stepback || i == 9999) {
        figurateStack.pop();
        i = a[count] + 1;
        --count;
        stepback = false;
    } else if (count < n - 2) {
        i = 100 * (i % 100) + 10;
    }
} while (count < 6);
return a[0] + a[1] + a[2] + a[3] + a[4] + a[5];
\$\endgroup\$
  • \$\begingroup\$ Your code still uses the same generate-everything-and-apply-expensive-filters approach as the original code, which involves quite a bit of unnecessary/repeated work. Do your micro-optimisations make the code fast enough to meet ADG's target? \$\endgroup\$ – DarthGizka Feb 17 '16 at 15:26
  • \$\begingroup\$ I... didn't check, and most likely they wont. I didn't spot the correct solution, but thought my points were at least valid as cleanup / micro-optimizations. \$\endgroup\$ – Pimgd Feb 17 '16 at 17:47
  • \$\begingroup\$ The points that you raised in your article are valid indeed, and I did not mean to belittle your work in any way (I know only too well how difficult it is to hone a non-trivial piece of someone else's code to make it leaner and meaner, to take it closer to its true essence). I was just curious about the result... You didn't mention it and my skills regarding mental execution of Java code are woefully inadequate for the task. I guess other readers might wonder, too, given that ADG explicitly mentioned 5 seconds. BTW - Kudos to ADG for the 're-Euler with time limit' thing. That's the spirit! \$\endgroup\$ – DarthGizka Feb 17 '16 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.