Tag Archives: Permutations

Euler Problem 105 – Disjoint Sets

The interesting thing about this one was that I had to figure out how to load a file in Haskell by using IO inside a Monad. Maybe something pretty basic, but still a novel concept. And a little weird.

This solution could be considered a brute force solution, but it still runs in about 45 seconds on an old PC. The routine first reads the file, splits the lines, then converts the strings into Integers.

For each set, it calculates the perfect series of sub-sets (tricky understanding disjoint sets), then creates a test series against the criteria. Then it simply sums up each set if the sub-set counts are the same.

Now to solve for related problems 103 and 106.

import Data.List
import Data.List.Split

testSubs :: [Integer] -> [Integer] -> Bool
testSubs b c
	| sb /= sc && lb > lc && sb > sc = True
	| sb /= sc && lb <= lc = True 
	| otherwise = False
	where
		sb = sum b
		sc = sum c
		lb = length b
		lc = length c

isSpecial :: [Integer] -> Bool
isSpecial set
	| perfectSet == testSet = True
	| otherwise = False
	where
		list = init $ tail $ subsequences set
		perfectSet = [(b,c)| b <- list, c <- list, b /= c]
		testSet = [(b,c)| b <- list, c <- list, b /= c && testSubs b c]
		
main = do
	raw <- readFile "sets.txt"
	print $ sum [sum $ clean x | x <- [splitOn "," y | y <- lines raw], isSpecial $ clean x]
	where
		clean = map read

Euler Problem 85

This one has to do with combinatorics. Here is a page that contain a formula to solve all permutations on a m x n grid.
http://www.gottfriedville.net/mathprob/comb-subrect.html

I used a simple quadratic equation to determine that if one dimension never exceeds 1, then the other cannot exceed 2000 (roughly). So I just created a nested loop for m & n and tested for a smaller and smaller delta.

class Problem:
    def Solution(self):
        mBest = 0
        nBest = 0
        delta = 2000000
        goal = 2000000
        for m in range (1,2001):
            for n in range (1, 2001):
                test = m*(m+1)*n*(n+1)/4
                if abs(test-goal) < delta:
                    mBest = m
                    nBest = n
                    delta = abs(test-goal)
            if m % 100 == 0:
                print m,
        print "\nBest m, Best n, Delta =", mBest, nBest, delta
        print "Answer =", mBest*nBest
if __name__ == '__main__':
    P = Problem()
    P.Solution()

Euler Problem 68

I finally got it, after months of twisting in the wind. Just used a simple permutations routine and created a custom data map to test each set.Looks like I’m switching back to Python. I’ve decided to ditch Squarespace too, to save a few bucks. I can accomplish pretty much the same here on WordPress.

#Euler68
def permutate(seq):
    if not seq:
        return [seq]
    else:
        temp = []
        for k in range(len(seq)):
            part = seq[:k] + seq[k+1:]
            for m in permutate(part):
                temp.append(seq[k:k+1] + m)
        return temp
print "Calculating Permutations of 1234567890"
list = permutate("1234567890")
print "Done. Size:" + str(len(list))
print "Calculating Maximum Set"
max = 0L
for set in list:
    n = []
    n.append(int(set[5]))
    n.append(int(set[3]))
    n.append(int(set[2]))
    n.append(int(set[6]))
    n.append(int(set[2]))
    n.append(int(set[1]))
    n.append(int(set[7]))
    n.append(int(set[1]))
    n.append(int(set[0]))
    n.append(int(set[8]))
    n.append(int(set[0]))
    n.append(int(set[4]))
    n.append(int(set[9]))
    n.append(int(set[4]))
    n.append(int(set[3]))
    for i in range(0,15):
        if n[i] == 0:
            n[i] = 10
    if n[3] > n[0]:
        if n[6] > n[0]:
            if n[9] > n[0]:
                if n[12] > n[0]:
                    if n[0]+n[1]+n[2] == n[3]+n[4]+n[5]:
                        if n[0]+n[1]+n[2] == n[6]+n[7]+n[8]:
                            if n[0]+n[1]+n[2] == n[9]+n[10]+n[11]:
                                if n[0]+n[1]+n[2] == n[12]+n[13]+n[14]:
                                    S = ""
                                    for i in range(0,15):
                                        S = S + str(n[i])
                                    if len(S) == 16:
                                        if long(S) > max:
                                            max = long(S)
                                        print "Total:"+str(x)+" Set:"+S+" Max:"+str(max)
print "Answer:"+str(max)

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));
        }
    }