Euler Problem 61

This one seemed tricky, but in the end was a pretty straight forward solution once I simplified the digit checking. The other trick was using my old Permutations class from a previous problem.

    public String Problem ()
    {
        Permutations P = new Permutations();
        ArrayList<String> List = P.makePerms("345678");
        int sum = 0;
        int [] s = new int[6];
        main:
        for (String i: List)
        {
            for (int n = 0; n <= 5; n++)
                s[n] = i.charAt(n)-48;
            ArrayList<Integer> P1 = genList(s[0]);
            ArrayList<Integer> P2 = genList(s[1]);
            ArrayList<Integer> P3 = genList(s[2]);
            ArrayList<Integer> P4 = genList(s[3]);
            ArrayList<Integer> P5 = genList(s[4]);
            ArrayList<Integer> P6 = genList(s[5]);
            for (int p1: P1)
                for (int p2: P2)
                    if (front(p2) == back(p1))
                        for (int p3: P3)
                            if (front(p3) == back(p2))
                                for (int p4: P4)
                                    if (front(p4) == back(p3))
                                        for (int p5: P5)
                                            if (front(p5) == back(p4))
                                                for (int p6: P6)
                                                    if (front(p6) == back(p5))
                                                        if (back(p6) == front(p1))
                                                        {
                                                            System.out.format("%d+%d+%d+%d+%d+%d=%d\n",p1,p2,p3,p4,p5,p6,p1+p2+p3+p4+p5+p6);
                                                            sum = p1+p2+p3+p4+p5+p6;
                                                            break main;
                                                        }
        }
        return String.valueOf(sum);
    }
    public int P (int type, int n)
    {
        int result = 0;
        if (type == 3)
            result = n*(n+1)/2;
        if (type == 4)
            result = n*n;
        if (type == 5)
            result = n*(3*n-1)/2;
        if (type == 6)
            result = n*(2*n-1);
        if (type == 7)
            result = n*(5*n-3)/2;
        if (type == 8 )
            result = n*(3*n-2);
        return result;
    }
    public ArrayList<Integer> genList (int type)
    {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int n = 0;
        while (P(type,n) < 10000)
        {
            if (P(type,n) > 999 && P(type,n) % 100 > 9)
                list.add(P(type,n));
            n++;
        }
        return list;
    }
    public int front (int p)
    {
        return (int) Math.floor (p/100);
    }
    public int back (int p)
    {
        return p % 100;
    }
    public class Permutations
    {
        ArrayList<String> Perms = new ArrayList<String>();
        public ArrayList<String> makePerms (String s)
        {
            Perms.clear();
            p1("",s);
            return Perms;
        }
        public void p1(String prefix, String s)
        {
            int N = s.length();
            if (N == 0)
            {
                if (Perms.contains(prefix) == false)
                    Perms.add(prefix);
            }
            else
                for (int i = 0; i < N; i++)
                    p1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s