This is how I’m doing my next beer batch
Leave a reply
Euler 91 – Right Triangles
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:
… 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
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
Best Haskell quote E-VER
I found the best Haskell quote. Interestingly, the more I learn about Haskell, the more I find this to be true…
I haven’t tested it, but it compiles, so it should work.
Basically, if some of your code is written wrong, it just won’t fit, or compile, or let alone work. Its ingenious.
Simplicity
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
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]])
For Great Wine: Take Your Time and Follow the Directions
Decided to try a bottle of my first wine batch a little early. See, I made some Pinot Noir using a 6-week kit fully expecting to let it “age” in the bottle afterwards a good couple months. My mother-in-law who will remain nameless (who got half the batch I might add) decided it was time to open up after only a couple weeks. After several OMG texts, we decided to open one too.
Notwithstanding it was young, there was no nasty aftertaste usually found with homemade wines made on store prem. The wine was smooth, deep flavour and was really enjoyable. Can you hear my surprise?
Brewing in the store can produce some good batches, but considering they’re probably cranking out at least a dozen batches a day, they gotta be cutting some corners. Maybe “it needed an extra day”, or maybe “hey, let’s add these bags together rather than 2 days apart”. In any case, there is nothing better than taking your time at home and following the manufacturer’s instructions exactly. The results are surprising.
My mother-in-law has ordered another batch. So I’m starting a Valpolicella (with grape skins). I am fully confident that its going to kick ass.
