extra/project-euler/102/102.factor

   1 ! Copyright (c) 2009 Guillaume Nargeot.
   2 ! See http://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 ;
   5 IN: project-euler.102
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=102
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! Three distinct points are plotted at random on a Cartesian plane, for which
  13 ! -1000 ≤ x, y ≤ 1000, such that a triangle is formed.
  14
  15 ! Consider the following two triangles:
  16
  17 ! A(-340,495), B(-153,-910), C(835,-947)
  18 ! X(-175,41), Y(-421,-714), Z(574,-645)
  19
  20 ! It can be verified that triangle ABC contains the origin, whereas triangle
  21 ! XYZ does not.
  22
  23 ! Using triangles.txt (right click and 'Save Link/Target As...'), a 27K text
  24 ! file containing the co-ordinates of one thousand "random" triangles, find the
  25 ! number of triangles for which the interior contains the origin.
  26
  27 ! NOTE: The first two examples in the file represent the triangles in the
  28 ! example given above.
  29
  30
  31 ! SOLUTION
  32 ! --------
  33
  34 ! A triangle of coordinates (x1, y1) (x2, y2) (x3, y3) contains
  35 ! the origin when (ab * bc > 0) and (bc * ca > 0) where:
  36 ! ab = x1 * (y2 - y1) - y1 * (x2 - x1)
  37 ! bc = x2 * (y3 - y2) - y2 * (x3 - x2)
  38 ! ca = x3 * (y1 - y3) - y3 * (x1 - x3)
  39
  40 <PRIVATE
  41
  42 : source-102 ( -- seq )
  43     "resource:extra/project-euler/102/triangles.txt"
  44     ascii file-lines [
  45         "," split [ string>number ] map 2 group
  46     ] map ;
  47
  48 : det ( coord coord -- n )
  49     dupd [ [ last ] bi@ - ] [ [ first ] bi@ - ] 2bi 2array
  50     [ [ first ] bi@ * ] [ [ last ] bi@ * ] 2bi - ;
  51
  52 : include-origin? ( coord-seq -- ? )
  53     dup first suffix 2 clump [ [ first ] [ last ] bi det ] map
  54     2 clump [ product 0 > ] all? ;
  55
  56 PRIVATE>
  57
  58 : euler102 ( -- answer )
  59     source-102 [ include-origin? ] count ;
  60
  61 ! [ euler102 ] 100 ave-time
  62 ! 12 ms ave run time - 0.92 SD (100 trials)
  63
  64 SOLUTION: euler102