Tag Archives: Euler

Euler 91 – Right Triangles

Blue Abstraction - Triangle

I haven’t done a Euler problem for a while. This one caught my eye, so I gave it a try in Haskell. Yeah, yeah, yeah, I know the picture is an equilateral…

My solution started out as a brute force, but then I added a few smarts along the way. First I ran a list comprehension of all possible points, then created a routine with guards to eliminate obvious impossible situations. The angle of each was calculated using the inverse cosine of two vectors:

550px-Find-the-Angle-Between-Two-Vectors-Step-6

… then its was simply a matter of checking for a 90 degree angle && the other two angles equalling 90. Oh yeah and then dividing the total by two because the list comprehension finds doubled matches because of transposed points.

I compiled this routine using GHC with flag -O2 and it runs in about 3 seconds for [0..50]. I’m still waiting for GHCi to finish …


result :: Int -> [Int]
result n = [1 | px <- r, py <- r, qx <- r, qy <- r, isRight px py qx qy ]  
	where
		r = [0..n]

isRight :: Int -> Int -> Int -> Int -> Bool
isRight px py qx qy
	| (px,py) == (0,0) = False
	| (qx,qy) == (0,0) = False
	| (px,py) == (qx,qy) = False
	| ao == 90 && (round (ap + aq)) == 90 = True
	| ap == 90 && (round (ao + aq)) == 90 = True
	| aq == 90 && (round (ao + ap)) == 90 = True
	| otherwise = False
	where
		ao = calcAngle px py qx qy
		ap = 180 + (-1 * (calcAngle px py (qx-px) (qy-py)))
		aq = 180 + (-1 * (calcAngle qx qy (px-qx) (py-qy)))

calcAngle :: Int -> Int -> Int -> Int -> Double
calcAngle px py qx qy = acos (num / denom) * 180 / pi
	where
		num = fInt (px * qx + py * qy)
		denom = (calcMag px py) * (calcMag qx qy)

calcMag :: Int -> Int ->  Double
calcMag x y = sqrt $ fInt (x*x) + fInt (y*y)

fInt = fromIntegral

main = do
	putStrLn "Enter limit:"
	limit <- getLine
	let answer = round $ 0.5 * fInt (length $ result $ read limit)
	putStrLn ("Answer = " ++ show answer)

Euler 221 – Alexandrian Numbers


When I came upon this Euler problem, and saw it was based on my namesake, I couldn’t help going for it. As with many of the Project Euler problems, the trick is to find a technique that reduces the brute force solution into something more efficient.

The functions from the original problem can be re-written to:
A = p(p + d)((p^2 + 1)/d + p)

The Alexandrian numbers are calculated from the new function, where d runs over divisors of p^2+1 and p runs over all positive integers. Used a fast Divisor routine that I Googled, then started building a Set (which is speed optimized to avoid duplicates) until length is 15K. Convert to a List, then sort and display 150,000th number. Numbers 1 thru 6 also listed to verify computation working. Runs in about 10 mins on my quad core iMac.

# e221.py

from math import sqrt
from functools import reduce


def appendEs2Sequences(sequences, es):
    result = []
    if not sequences:
        for e in es:
            result.append([e])
    else:
        for e in es:
            result += [seq + [e] for seq in sequences]
    return result


def primefactors(n):
    i = 2
    while i <= sqrt(n):
        if n % i == 0:
            l = primefactors(n // i)
            l.append(i)
            return l
        i += 1
    return [n]


def factorGenerator(n):
    p = primefactors(n)
    factors = {}
    for p1 in p:
        try:
            factors[p1] += 1
        except KeyError:
            factors[p1] = 1
    return factors


def divisors(n):
    factors = factorGenerator(n)
    divisors = []
    listexponents = [list(map(lambda x:k ** x, list(range(0, factors[k] + 1)))) for k in factors.keys()]
    listfactors = reduce(appendEs2Sequences, listexponents, [])
    for f in listfactors:
        divisors.append(reduce(lambda x, y: x * y, f, 1))
    divisors.sort()
    return divisors


if __name__ == "__main__":
    A = set()
    p = 1
    while len(A) <= 1500001:
        for d in divisors((p * p) + 1):
            A.add(int(p * (p + d) * (p + ((p * p) + 1) / d)))
        p += 1
    L = list(A)
    L.sort()
    for i in [1,2,3,4,5,6,150000]:
        print (str(i) + ": " + str(L[i-1]))

Euler 113 – Bouncy Numbers


This one has to do with combinatorics and we use the good old fashion binomial coefficient identity (built from factorials or Bang!). Any increasing number can be represented using binary strings. For example, all 3-digit increasing numbers using 0, 1, 2 can be represented with 5-digit binary numbers:

11100 = 000
11010 = 001
11001 = 002
10110 = 011
10101 = 012
10011 = 022
01110 = 111
01101 = 112
01011 = 122
00111 = 222

Which means that there are (5 choose 3) - 1 = 9 of these numbers. The reason for subtracting 1 is that we don’t want to count the number “000”. By extension, all 3-digit increasing numbers with the digits 0-9 requires a binary string containing 3 ones and 9 zeroes and so on. The same can be extended to 10^100.

For decreasing numbers, the only difference is that we might have a zero in the front and end of the string. Note the following pattern of zeros.

111000 = 000
110100 = 002
110010 = 001
110001 = 000 *
101100 = 022
101010 = 021
101001 = 020
100110 = 011
100101 = 010
100011 = 000 *
011100 = 222
011010 = 221
011001 = 220
010110 = 211
010101 = 210
010011 = 200
001110 = 111
001101 = 110
001011 = 100
000111 = 000 *

You can see for 3-digit numbers that “000” will be repeated 3 times after the initial time. For an n-digit number the pattern repeats n times. This gives us (n+10 choose 10) -1 -n. Additionally, numbers like 222 and 11 have both properties. Since we have counted them twice, they need to be removed. There are 9*100 of these numbers which are counted twice.

So this gives us:

Here's the Python code. Its pretty short since we've simplified everything down to a couple binomial calculations.

def bang (x):
    return x > 1 and x * bang (x - 1) or 1

def choose (n, k):
    return bang (n) / (bang (k) * bang (n-k))

if __name__ == "__main__":
    print (int (choose (110, 10) + choose (109, 9) - 1002))

Euler 107 – Back to Python


Haskell has a lot going for it. It is brilliantly conceived to ensure functional programming paradigm purity, has hardly any squiggly brackets and most importantly, no freaking semi-colons on every single freaking line. But I digress. I’ve found that package and module management is spotty at best, with Cabal choking regularly. There’s no decent IDE, although I’ve been able to find loads of text editors that can run GHCi in a console. I did finally manage to wrap my brain around functional programming concepts, but interestingly I found that I was spending too much time thinking about how to write it, rather than actually writing. So back to Python. Its might be slow, but its still the best all round language.

Euler problem 107 piqued my interest immediately due to the practical application. Minimum Spanning Tree (MST) routing problems are a cornerstone of networking theory. This solution employs a simple implementation of Kruskal’s algorithm. Also used a very handy Disjointed Set class.

# e107.py

from operator import itemgetter

class DisjointSet (dict):
    def add(self, item):
        self[item] = item
    
    def find(self, item):
        parent = self[item]
        while self[parent] != parent:
            parent = self[parent]
        self[item] = parent
        return parent
    
    def union(self, item1, item2):
        self[item2] = self[item1]

def kruskal (nodes, edges):
    forest = DisjointSet ()
    mst = []
    for n in nodes:
        forest.add (n)
    sz = len(nodes)-1
    for e in sorted (edges, key = itemgetter(2)):
        n1, n2, _ = e
        t1 = forest.find (n1)
        t2 = forest.find (n2)
        if t1 != t2:
            mst.append (e)
            sz -= 1
            if sz == 0:
                return mst
            forest.union (t1, t2)

def convert2Edges (m):
    e = []
    for i in range (1, len(m)):
        for j in range (0,i):
            if m[i][j] != 0:
                e.append ([str(i), str(j), m[i][j]])
    return e

def generateNodes (m):
    n = []
    for i in range(0, len(m)):
        n.append(str(i))
    return n

def calcWeight(e):
    w = 0
    for i in e:
        w += i[2]
    return w

def generateMatrix ():
    m = []
    f = open ("network.txt", "r")
    for line in f.read().split ('\n'):
        m.append (line.split (","))
    f.close()
    num = len(m)
    for i in range (0, num-1):
        for j in range (0, num-1):
            if m[i][j] == '-' or m[i][j] == '-\r':
                m[i][j] = '0'
            m[i][j] = int (m[i][j])
    m.pop()
    return m
    
if __name__=="__main__":
    m = generateMatrix()
    e = convert2Edges (m)
    n = generateNodes (m)
    e1 = kruskal (n,e)
    w1 = calcWeight (e)
    w2 = calcWeight (e1)
    print ("Original weight: " + str (w1))
    print ("New weight: " + str (w2))
    print ("Difference: "+ str (w1-w2))

Sweet! Just found out that Python supports list comprehensions — sort of. Definitely the most useful part of Haskell’s functional syntax. As an example, the weight function can be lightened down to (pun intended):

def calcWeight (e): return sum ([x[2] for x in e])

Pretty cool to use for the simple stuff.

Euler 89 – Haskell Redux

Just for kicks I decided to revisit my Roman numeral routines from Euler 89.

Admittedly, my earlier Python algorithms were not the most efficient, but they got the job done. Thought it might be worth seeing if Haskell can do it better. As usual, I re-wrote some of the more tighter online routines for clarify and fed the Euler roman.txt file through it to get the same answer.

import Data.Maybe

dec2num :: Integer -> String
dec2num x
	| x == 0 = ""
	| otherwise = b ++ dec2num (x - a)
	where
		(a, b) = head $ filter ((<= x) . fst)
			$ zip [1000,900,500,400,100,90,50,40,10,9,5,4,1]
			["M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"]

num2dec :: String -> Integer
num2dec n = fst $ foldr (\p (t,s) -> if p >= s then (t+p,p) else (t-p,p)) (0,0)
	$ map (fromJust . flip lookup numMap) n
	where
		numMap = zip "IVXLCDM" [1,5,10,50,100,500,1000]

main = do
	raw <- readFile "roman.txt"
	print $ (sum [length s|s <- lines raw]- sum [length $ dec2num $ num2dec s|s <- lines raw])

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