Tag Archives: functional programming

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)

The Classical Josephus Problem

OLYMPUS DIGITAL CAMERA

This is another one taken from Programming Praxis #5 – Flavius Josephus, has a historical context which can be found here. For this exercise, write a function j that takes two values n & m that returns a list of n people, numbered from 0 to n-1, in the order in which they are executed, every mth person in turn, with the sole survivor as the last person in the list. What is the value of j (41,3)? In what position did Josephus survive?

Built a recursive routine that executes each soldier and creates a smaller and smaller live soldier list. Used Debug.Trace to list each one executed, rather than build an execution list.


import Debug.Trace

execute :: [Int] -> Int -> Int -> [Int]
execute [a] _ _ = [a]
execute soldiers inc pos = trace (show v) $ execute [x | x <- soldiers, x /= soldiers !! pos] inc newPos
	where
		newPos
			| (pos + inc) >= length soldiers = pos + inc - length soldiers
			| otherwise = pos + inc - 1
		v = (soldiers, inc, pos, newPos)

main = print $ j 41 3
	where
		j numSoldiers inc = execute [1..numSoldiers] inc $ inc - 1

Simplicity

zen-garden-983809

Programming Praxis 4: Sudoku Solution

Sudoku problems can be perceived as quite complex. Counter-intuitively and from a mathematical standpoint, the solution is actually quite simple. I wrote this solution a while back in Python by pulling together algorithms from a number of sources. But by translating it into Haskell again, I think its acheived a certain Zen-like simplicity and elegance. Or maybe its the homebrew talking.

import Data.List
import Data.Maybe

check :: Int -> Int -> Bool
check i j
	| (f i)/9 == (f j)/9 = True
	| mod (i-j) 9 == 0 = True
	| (f i)/27 == (f j)/27 && (f $ mod i 9)/3 == (f $ mod j 9)/3 = True
	| otherwise = False
	where
		f = fromIntegral

solve :: [Int] -> [Int]
solve s
	| elem 0 s = solve $ a ++ [n | n <- [1..9], elem n e == False] ++ b
	| otherwise = s
	where
		a = take i s
		b = drop (i + 1) s
		i = fromJust $ elemIndex 0 s
		e = [s !! j | j <- [0..80], check i j]
		
main = print $ solve [7,0,0,1,0,0,0,0,0,0,2,0,0,0,0,0,1,5,0,0,0,0,0,6,3,9,0,2,
        0,0,0,1,8,0,0,0,0,4,0,0,9,0,0,7,0,0,0,0,7,5,0,0,0,3,0,7,8,5,0,0,0,0,0,
        5,6,0,0,0,0,0,4,0,0,0,0,0,0,1,0,0,2]

Dirty Little Monad

water bottle1
Never tried random numbers before in Haskell. Obviously it must involve a Monad, because randomness is considered so unpure. Found this great line somewhere, worth sharing here:

Using Monads in Haskell is like drinking from the communal water bottle, but never letting your lips touch the bottle.

Programming Praxis 3: Bingo

Such a simple game, Bingo, but such an annoying problem in Haskell. I suppose most of my grief stems from the fact that I’m still thinking in imperative concepts. Eventually I figured out that I would need to use higher order functions (and/or tail recursion) in lieu of iteration. Then I spent the next week reviewing mind numbing concepts like filters, maps, folds, scans. All are incredibly powerful but eventually I didn’t need them. Everything reduced down to good old fashioned list comprehensions. Still my favourite Haskell feature.

Found that System.Random provided lots of handy functions. “randomRs” needs seeds, so I just used the count numbers. Not very random, but ok for these purposes. Since its a random generator, I couldn’t guarantee that all my needed numbers were picked. So I generated more than enough numbers over a range, removed duplicates with “nub” and took the right number.

The other interesting note is the use of Data.Maybe. When using “elemIndex“, it could throw an error, so the function will return a type “Maybe“, akin to a Null value in other languages. Used “fromJust” to strip the “Maybe” off and use the “Int“. Didn’t worry about the error because the pool always held all 75 numbers.

In main, printed just the two calculations. The first shows the average number of balls called to get to Bingo with only one card and 500 different pools. The second shows the average number calls used to get to Bingo with one pool and 500 different cards. Routine only takes a second to run in GHCi.

import System.Random
import Data.List
import Data.Maybe

makePool :: Int -> [Int]
makePool s = take 75 $ nub $ take (1000) $ randomRs (1,75) (mkStdGen s) :: [Int]

makeCard :: Int -> [Int]
makeCard seed = (b ++ i ++ n ++ g ++ o)
  where
    b = take 5 $ nub $ take 20 $ randomRs (1,15) (mkStdGen seed) :: [Int]
    i = take 5 $ nub $ take 20 $ randomRs (16,30) (mkStdGen $ sum b) :: [Int]
    n = take 5 $ nub $ take 20 $ randomRs (31,45) (mkStdGen $ sum i) :: [Int]
    g = take 5 $ nub $ take 20 $ randomRs (46,60) (mkStdGen $ sum n) :: [Int]
    o = take 5 $ nub $ take 20 $ randomRs (61,75) (mkStdGen $ sum g) :: [Int]

filterCard :: [Int] -> [[Int]]
filterCard card = [[card !! x | x <- r] | r <- ranges]
  where
    ranges = [[0..4],[5..9],[10,11,13,14],[15..19],[20..24],
      [0,5..20],[1,6..21],[2,7,17,22],[3,8..23],[4,9..24],[0,6,18,24],[4,8,16,20]]

evaluate :: [Int] -> [Int] -> Int
evaluate pool subcard = maximum [fromJust $ elemIndex x pool | x <- subcard, elem x pool]

bingoTest :: [Int] -> [Int] -> Int
bingoTest pool card = minimum [evaluate pool x | x <- (filterCard card)]

main = do
  print $ 0.002 * fromIntegral (sum [bingoTest (makePool x) $ makeCard 1 | x <- [1..500]])
  print $ 0.002 * fromIntegral (sum [bingoTest (makePool 1) $ makeCard x | x <- [1..500]])

Basket Making 101

Kalathos_Louvre_MNE1176
Praxis 2: Write a function that calculates the list of prime numbers using the Sieve of Eratosthenes.

Ummm, yeah. Done it a couple dozen times before over at Project Euler. Never hurts to review. I did manage to use more function composition this time around. Oh, and don’t forget to install module data.ordlist using Cabal.


import Data.List.Ordered

primes :: Integer -> [Integer]
primes m = 2 : sieve [3,5..m]
    where
        sieve [] = []
        sieve (p:xs) = p : sieve (minus xs [p*p, p*p+2*p..m])

main = do
    putStrLn "Enter n: "  
    input <- getLine
    putStrLn $ "# of primes: " ++ (show . length . primes $ read input)

Back to Functional Programming Purity

3200587025_f4d7c94c71_zGot the itch to start studying Haskell again. Best to scratch it. I’m a bit sick of gluing together bits of Javascript code that don’t look like they should be together in the same script, then wondering why in the world it works. Granted, I did enjoy coding everything in the cloud, and my ultimate hope is for the same treatment be given to Haskell.

I keep getting drawn to Haskell’s simplicity, consistency, structural elegance, and perfect typing system, even though it still causes me a great deal of mental strain to understand it. And I found that after being away from it for several months, even the simplest concepts have to be re-learned.

So I did two things. One, I began re-reading Haskell guides like “Real World Haskell” and “Learn you a Haskell for Great Good!“. There are tons of very helpful resources online.

The second thing I did is to give “Programming Praxis” a try. In the past I used Project Euler, but having solved 108+ problems, I’m getting tired of the same old, same old. I’m sure I’ll get to the same point with Praxis, but for now its giving me a change.

Praxis 1 – Create a RPN calculator:
Loved my HP 48sx+ calculator in Engineering. Sad day when it kak’d. Still have trouble using regular algebraic calculators. So this one was is right up my alley. Lots of sample code online, but I started noticing that most code used function composition, rather than using variables. Up until now I always avoided function composition, but it really does make things clearer.


import Data.List

solveRPN :: String -> Float  
solveRPN = head . foldl calcme [] . words  
    where
        calcme (x:y:ys) "*" = (x * y):ys  
        calcme (x:y:ys) "+" = (x + y):ys  
        calcme (x:y:ys) "-" = (y - x):ys  
        calcme (x:y:ys) "/" = (y / x):ys  
        calcme xs numStr = read numStr:xs  

main = do
    putStrLn "Enter calculation: "  
    input <- getLine
    putStrLn $ "Result = " ++ (show $ solveRPN input)