web developer & system programmer

coder . cl

ramblings and thoughts on programming...

project euler: problem 102

published: 20-04-2012 / updated: 20-04-2012
posted in: development, haskell, programming, tips
by Daniel Molina Wegener

I have started my own solutions to the Project Euler in Haskell. Just to practice Haskell and its features. The past problem was the problem 255. Now I have solved the problem 102, using some additional features, not taking the problem as it comes in the Project Euler. Rather than doing a simple solution in plain text, I have created a program which renders the triangles in the problem using OpenGL, placing the triangles in a Windows rather than just indicating the number of triangles.

Is nice to work with Haskell, you may know that you can work with a very wide variety of technologies in Haskell. Also, the Glasgow Haskell Compiler or GHC, is able to compile machine byte code, creating native executables for its runtime. Since all Project Euler problems are very nice to solve, I have created a github repository with my solutions, to share them, probably you can use them to examine some Haskell code and see if you want to learn it.

The problem 102 is related to triangles and point positions, and it can be seen in this link. The main goal of the problem is to indicate the number of triangles which are containing the origin or point p(0, 0), where I have used the Cross Product to solve this problem.

First I have defined plane points and triangles as data types in Haskell, deriving the Num type class instance on the LPt data type which represents a point in a two dimensional space.

data LPt = LPt (Int, Int)
         deriving (Eq, Show, Ord)

data LTrg = LTrg {
  tA        :: LPt
  , tB      :: LPt
  , tC      :: LPt
  } deriving (Eq, Show, Ord)

instance Num LPt where
  x + y = LPt (fstp x + fstp y, sndp x + sndp y)

  x - y = LPt (fstp x - fstp y, sndp x - sndp y)

  x * y = LPt (fstp x * fstp y, sndp x * sndp y)

  abs x = LPt (abs (fstp x), abs (sndp x))

  fromInteger x = LPt (fromInteger x, fromInteger x)

  signum x | fstp x < 0 && sndp x < 0 = -1
  signum x | fstp x > 0 && sndp x > 0 = 1
  signum x = 0

crossPt :: LPt -> LPt -> LPt
crossPt x y = LPt (0, fstp x * sndp y - sndp x * fstp y)

Then is easy to reach the solution. Where I have plain text file parsing triangle points using the following functions.

mkTriangle :: String -> LTrg
mkTriangle s = LTrg { tA = head g, tB = g !! 1, tC = last g }
               where g = fmap (\x -> LPt (head x, last x) )
                         $ splitEvery 2 ln
                     ln = fmap (read . strip) $ splitOn "," s

mkTriangles :: String -> Int -> Int -> [LTrg]
mkTriangles s l h = drop l
                    $ take h
                    $ fmap mkTriangle
                    $ filter (\ x -> length x > 0 )
                    $ fmap strip
                    $ lines s

So, my solution do not creates all triangles on the file, rather than creating all triangles, it just takes a given segment of the file, and renders their position in the OpenGL windows.

trgColor :: LTrg -> IO ()
trgColor xs | trgContained zeroPt xs = colorCyan
trgColor xs = colorGreen

displayTriangle :: LTrg -> IO ()
displayTriangle xs = do _ <- renderPrimitive Polygon $ do
                          trgColor xs
                          mapM ptToGlPt [tA xs, tB xs, tC xs]

displayTriangles :: [LTrg] -> F.Font -> IO ()
displayTriangles xs f = do clear [ ColorBuffer, DepthBuffer ]
                           mapM_ displayTriangle xs
                           trgTextCont xs f

Where the call to the trgContained in the guard at the trgColor function is what indicates if the triangle contains or not the point p(0, 0) or zeroPt. So, you can see two sample results as follows.

Project Euler: Problem 102 Visualization

Project Euler: Problem 102 Visualization Sample 1
./problem102 triangles.txt 70 90
Project Euler: Problem 102 Visualization

Project Euler: Problem 102 Visualization Sample 2
./problem102 triangles.txt 23 48

No coments yet.

post a comment

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>