1 ! Copyright (c) 2009 Guillaume Nargeot.
2 ! See https://factorcode.org/license.txt for BSD license.
3 USING: arrays grouping io.encodings.ascii io.files kernel math
4 math.parser sequences splitting project-euler.common ;
7 ! https://projecteuler.net/problem=102
12 ! Three distinct points are plotted at random on a Cartesian
13 ! plane, for which -1000 ≤ x, y ≤ 1000, such that a triangle is
16 ! Consider the following two triangles:
18 ! A(-340,495), B(-153,-910), C(835,-947)
19 ! X(-175,41), Y(-421,-714), Z(574,-645)
21 ! It can be verified that triangle ABC contains the origin,
22 ! whereas triangle XYZ does not.
24 ! Using triangles.txt (right click and 'Save Link/Target
25 ! As...'), a 27K text file containing the coordinates of one
26 ! thousand "random" triangles, find the number of triangles for
27 ! which the interior contains the origin.
29 ! NOTE: The first two examples in the file represent the
30 ! triangles in the example given above.
36 ! A triangle of coordinates (x1, y1) (x2, y2) (x3, y3) contains
37 ! the origin when (ab * bc > 0) and (bc * ca > 0) where:
38 ! ab = x1 * (y2 - y1) - y1 * (x2 - x1)
39 ! bc = x2 * (y3 - y2) - y2 * (x3 - x2)
40 ! ca = x3 * (y1 - y3) - y3 * (x1 - x3)
44 : source-102 ( -- seq )
45 "resource:extra/project-euler/102/triangles.txt"
47 "," split [ string>number ] map 2 group
50 : det ( coord coord -- n )
51 dupd [ [ last ] bi@ - ] [ [ first ] bi@ - ] 2bi 2array
52 [ [ first ] bi@ * ] [ [ last ] bi@ * ] 2bi - ;
54 : include-origin? ( coord-seq -- ? )
55 dup first suffix 2 clump [ [ first ] [ last ] bi det ] map
56 2 clump [ product 0 > ] all? ;
60 : euler102 ( -- answer )
61 source-102 [ include-origin? ] count ;
63 ! [ euler102 ] 100 ave-time
64 ! 12 ms ave run time - 0.92 SD (100 trials)