extra/project-euler/042/042.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: ascii io.encodings.ascii io.files kernel make math math.functions
   4 project-euler.common sequences splitting ;
   5 IN: project-euler.042
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=42
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The nth term of the sequence of triangle numbers is given by,
  13 ! tn = n * (n + 1) / 2; so the first ten triangle numbers are:
  14
  15 !     1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  16
  17 ! By converting each letter in a word to a number corresponding to its
  18 ! alphabetical position and adding these values we form a word value. For
  19 ! example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value
  20 ! is a triangle number then we shall call the word a triangle word.
  21
  22 ! Using words.txt (right click and 'Save Link/Target As...'), a 16K text file
  23 ! containing nearly two-thousand common English words, how many are triangle
  24 ! words?
  25
  26
  27 ! SOLUTION
  28 ! --------
  29
  30 <PRIVATE
  31
  32 : source-042 ( -- seq )
  33     "resource:extra/project-euler/042/words.txt"
  34     ascii file-contents [ quotable? ] filter "," split ;
  35
  36 : (triangle-upto) ( limit n -- )
  37     2dup nth-triangle > [
  38         dup nth-triangle , 1 + (triangle-upto)
  39     ] [
  40         2drop
  41     ] if ;
  42
  43 : triangle-upto ( n -- seq )
  44     [ 1 (triangle-upto) ] { } make ;
  45
  46 PRIVATE>
  47
  48 : euler042 ( -- answer )
  49     source-042 [ alpha-value ] map dup supremum
  50     triangle-upto [ member? ] curry count ;
  51
  52 ! [ euler042 ] 100 ave-time
  53 ! 19 ms ave run time - 1.97 SD (100 trials)
  54
  55
  56 ! ALTERNATE SOLUTIONS
  57 ! -------------------
  58
  59 ! Use the inverse function of n * (n + 1) / 2 and test if the result is an integer
  60
  61 <PRIVATE
  62
  63 : triangle? ( n -- ? )
  64     8 * 1 + sqrt 1 - 2 / 1 mod zero? ;
  65
  66 PRIVATE>
  67
  68 : euler042a ( -- answer )
  69     source-042 [ alpha-value ] map [ triangle? ] count ;
  70
  71 ! [ euler042a ] 100 ave-time
  72 ! 21 ms ave run time - 2.2 SD (100 trials)
  73
  74 SOLUTION: euler042a