2
\$\begingroup\$

I've recently decided to get into functional programming with F#, and decided to learn the language through Project Euler. The following is my implementation of problem 102:

Problem:

Three distinct points are plotted at random on a Cartesian plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is formed.

Consider the following two triangles:

A(-340,495), B(-153,-910), C(835,-947)

X(-175,41), Y(-421,-714), Z(574,-645)

It can be verified that triangle ABC contains the origin, whereas triangle XYZ does not.

Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text file containing the co-ordinates of one thousand "random" triangles, find the number of triangles for which the interior contains the origin.

NOTE: The first two examples in the file represent the triangles in the example given above.

Implementation:

type Coord = { x: int; y: int }

let origin = { x = 0; y = 0 }

let intToCoord [x; y] = { x = x; y = y }

let twiceTriangleArea a b c =
    abs (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y))

let containsOrigin [a; b; c] =
    twiceTriangleArea a b c = twiceTriangleArea origin a b +
        twiceTriangleArea origin b c +
        twiceTriangleArea origin a c

let solution =
    System.IO.File.ReadLines "triangles.txt"
    |> Seq.map (fun line -> 
        line.Split ',' |> Array.map int |> List.ofArray |> List.chunkBySize 2 |> List.map intToCoord
    )
    |> Seq.filter containsOrigin
    |> Seq.length

printfn "%i" solution

Explanation:

  1. This code iterates through each line of triangles.txt.
  2. It then splits each line (by comma), takes elements in groups of 2, and converts them to coordinates.
  3. For each of these three coordinates, it checks if they make a triangle containing the origin by checking if the sum of the areas of all triangles made from two of the passed points and the origin is equal to the total triangle area (with all three points). Note that the area isn't divided by 2 in order to prevent floating point errors. All triangles that do not meet this criteria are filtered out.
  4. The number of remaining triangles are summed and printed to the user.

While making this, I tried to maintain a functional style as much as possible.

Here is what mainly I want to get from a review:

  1. Is my code idiomatic and functional? Where can it be improved in this regard?
  2. Are there any areas where I am unnecessarily doing extra computation and the code can be simplified?
\$\endgroup\$
3
\$\begingroup\$

It looks OK to me. You can avoid the List.ofArray call, if you change the arguments to intToCoord and containsOrigin to arrays instead of lists:

let intToCoord [|x; y|] = { x = x; y = y }

let containsOrigin [|a; b; c|] =
    twiceTriangleArea a b c = twiceTriangleArea origin a b +
        twiceTriangleArea origin b c +
        twiceTriangleArea origin a c



let solution =
    System.IO.File.ReadLines "p102_triangles.txt"
    |> Seq.map (fun line -> 
        line.Split ',' |> Array.map int |> Array.chunkBySize 2 |> Array.map intToCoord
    )
    |> Seq.filter containsOrigin
    |> Seq.length

Update:

You could though "rearrange" the mapping from string to a "triangle" in this way:

let toCoord [|x; y|] = { x = int x; y = int y}

let toTriangle line = (string line).Split ',' |> Array.chunkBySize 2 |> Array.map toCoord

And then change the main function to:

let solution =
    System.IO.File.ReadLines "p102_triangles.txt"
    |> Seq.map toTriangle
    |> Seq.filter containsOrigin
    |> Seq.length

In this way you gain more even abstraction levels in the pipe chain in the main function.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.