Sunday, May 11, 2014

Problem 85 - Idris (Also, I should be doing a problem set)

So, Problem 85 involves counting the number of rectangles that can be found in a rectangular grid. Finding a formula to compute this was kind of fun, and the resulting formula is kind of nice. Once that formula was found, writing up a solution isn't too bad. I solved this problem in Idris, a functional programming language with fully dependent types. The theory behind all that stuff seems cool and I will probably study it more fully later (I am taking a course in Functional Programming next semester), but for now, it was just a language with Haskell like syntax that was easy enough to use for this problem, and I have been trying to find a home for it for a while. And oh yeah, fun fact: two of the main authors of Idris are the guys who designed Whitespace, if that helps increase any confidence in the quality of the language. I do like that it is, like Haskell, a compiled language, despite being highly theoretical, that is a nice feature, solution runs in .7s on my machine...only .1s slower than my python solution (both run on the same rather exaggerated search space):
tri : Int -> Int

tri n = divInt (n * (n + 1)) 2

rectangles : Int -> Int -> Int

rectangles n 0 = 0
rectangles n k = ((tri n) * k) + (rectangles n (k - 1))

N : Int
N = 2000000
findans : Int -> Int -> Int -> Int -> Int

findans 1000 h optarea optcount = optarea
findans w 1000 optarea optcount = findans (w + 1) 1 optarea optcount
findans w h optarea optcount = 
    let numrects = rectangles w h in
        if (abs (N - numrects)) < (abs (N - optcount)) then
            findans w h (w * h) numrects else
            if numrects > N then
                findans (w + 1) 1 optarea optcount else
                findans w (h + 1) optarea optcount
main : IO ()
main = putStrLn (show (findans 1 1 0 0))

No comments:

Post a Comment