factor: trim using lists

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

diff --git a/extra/project-euler/169/169.factor b/extra/project-euler/169/169.factor
index 959715e4f987e453164ae398f6b87f49e1149f8a..174fef12a2805c2114a1e521cdfe1c422c8d637b 100644 (file)
--- a/extra/project-euler/169/169.factor
+++ b/extra/project-euler/169/169.factor
@@ -1,18 +1,18 @@
 ! Copyright (c) 2007 Samuel Tardieu.
 ! See http://factorcode.org/license.txt for BSD license.
 IN: project-euler.169
-USING: combinators kernel math math.functions memoize ;
+USING: combinators kernel math math.functions project-euler.common ;
 
 ! http://projecteuler.net/index.php?section=problems&id=169
 
 ! DESCRIPTION
 ! -----------
 
-! Define f(0)=1 and f(n) to be the number of different ways n can be
-! expressed as a sum of integer powers of 2 using each power no more
-! than twice.
+! Define f(0) = 1 and f(n) to be the number of different ways n can be
+! expressed as a sum of integer powers of 2 using each power no more than
+! twice.
 
-! For example, f(10)=5 since there are five different ways to express 10:
+! For example, f(10) = 5 since there are five different ways to express 10:
 
 ! 1 + 1 + 8
 ! 1 + 1 + 4 + 4
@@ -20,22 +20,23 @@ USING: combinators kernel math math.functions memoize ;
 ! 2 + 4 + 4
 ! 2 + 8
 
-! What is f(1025)?
+! What is f(10^25)?
+
 
 ! SOLUTION
 ! --------
 
 MEMO: fn ( n -- x )
-  {
-    { [ dup 2 < ]  [ drop 1 ] }
-    { [ dup odd? ] [ 2/ fn ] }
-    { [ t ]        [ 2/ [ fn ] keep 1- fn + ] }
-  } cond ;
+    {
+        { [ dup 2 < ]  [ drop 1 ] }
+        { [ dup odd? ] [ 2/ fn ] }
+        [ 2/ [ fn ] [ 1 - fn ] bi + ]
+    } cond ;
 
 : euler169 ( -- result )
-  10 25 ^ fn ;
+    10 25 ^ fn ;
 
 ! [ euler169 ] 100 ave-time
-! 0 ms run / 0 ms GC ave time - 100 trials
+! 0 ms ave run time - 0.2 SD (100 trials)
 
-MAIN: euler169
+SOLUTION: euler169