Delete empty unit tests files, remove 1- and 1+, reorder IN: lines in a lot of places...

[factor.git] / extra / project-euler / 150 / 150.factor

diff --git a/extra/project-euler/150/150.factor b/extra/project-euler/150/150.factor
index 5b22a1b9f625aeb707b2a1f44626022d7f049439..a54b7d1db0faa147fd98c6b2a82ba21efaa163b8 100644 (file)
--- a/extra/project-euler/150/150.factor
+++ b/extra/project-euler/150/150.factor
@@ -1,44 +1,79 @@
-! Copyright (c) 2008 Eric Mertens
+! Copyright (c) 2008 Eric Mertens.
 ! See http://factorcode.org/license.txt for BSD license.
-USING: kernel math sequences locals ;
+USING: hints kernel locals math math.order math.ranges project-euler.common
+    sequences sequences.private ;
 IN: project-euler.150
 
+! http://projecteuler.net/index.php?section=problems&id=150
+
+! DESCRIPTION
+! -----------
+
+! In a triangular array of positive and negative integers, we wish to find a
+! sub-triangle such that the sum of the numbers it contains is the smallest
+! possible.
+
+! In the example below, it can be easily verified that the marked triangle
+! satisfies this condition having a sum of -42.
+
+! We wish to make such a triangular array with one thousand rows, so we
+! generate 500500 pseudo-random numbers sk in the range +/-2^19, using a type of
+! random number generator (known as a Linear Congruential Generator) as
+! follows:
+
+! ...
+
+! Find the smallest possible sub-triangle sum.
+
+
+! SOLUTION
+! --------
+
 <PRIVATE
 
 ! sequence helper functions
 
-: partial-sums ( seq -- seq )
+: partial-sums ( seq -- sums )
     0 [ + ] accumulate swap suffix ; inline
 
-: generate ( n quot -- seq )
-    [ drop ] swap compose map ; inline
+: (partial-sum-infimum) ( inf sum elt -- inf sum )
+    + [ min ] keep ; inline
+
+: partial-sum-infimum ( seq -- seq )
+    0 0 rot [ (partial-sum-infimum) ] each drop ; inline
 
 : map-infimum ( seq quot -- min )
     [ min ] compose 0 swap reduce ; inline
 
-
 ! triangle generator functions
 
 : next ( t -- new-t s )
-    615949 * 797807 + 1 20 shift mod dup 1 19 shift - ; inline
+    615949 * 797807 + 20 2^ rem dup 19 2^ - ; inline
 
 : sums-triangle ( -- seq )
-    0 1000 [ 1+ [ next ] generate partial-sums ] map nip ;
-
-PRIVATE>
+    0 1000 [1,b] [ [ next ] replicate partial-sums ] map nip ;
 
 :: (euler150) ( m -- n )
     [let | table [ sums-triangle ] |
         m [| x |
-            x 1+ [| y |
-                m x - [| z |
-                    x z + table nth
-                    [ y z + 1+ swap nth ]
-                    [ y        swap nth ] bi -
-                ] map partial-sums infimum
+            x 1 + [| y |
+                m x - [0,b) [| z |
+                    x z + table nth-unsafe
+                    [ y z + 1 + swap nth-unsafe ]
+                    [ y        swap nth-unsafe ] bi -
+                ] map partial-sum-infimum
             ] map-infimum
         ] map-infimum
     ] ;
 
-: euler150 ( -- n )
+HINTS: (euler150) fixnum ;
+
+PRIVATE>
+
+: euler150 ( -- answer )
     1000 (euler150) ;
+
+! [ euler150 ] 10 ave-time
+! 30208 ms ave run time - 593.45 SD (10 trials)
+
+SOLUTION: euler150