! Copyright (C) 2008 Slava Pestov.
! See http://factorcode.org/license.txt for BSD license.
-USING: backtrack shuffle math math.ranges quotations locals fry
-kernel words io memoize macros prettyprint sequences assocs
-combinators namespaces ;
+USING: assocs backtrack kernel math memoize ranges sequences
+words ;
IN: benchmark.backtrack
! This was suggested by Dr_Ford. Compute the number of quadruples
{ + - * } amb-execute ;
: some-rots ( a b c -- a b c )
- #! Try to rot 0, 1 or 2 times.
+ ! Try to rot 0, 1 or 2 times.
{ nop rot -rot } amb-execute ;
MEMO: 24-from-1 ( a -- ? )
[ some-rots do-something 24-from-3 ] [ 4drop ] if-amb ;
: find-impossible-24 ( -- n )
- 1 10 [a,b] [| a |
- 1 10 [a,b] [| b |
- 1 10 [a,b] [| c |
- 1 10 [a,b] [| d |
+ 10 [1..b] [| a |
+ 10 [1..b] [| b |
+ 10 [1..b] [| c |
+ 10 [1..b] [| d |
a b c d 24-from-4
] count
] map-sum
] map-sum
] map-sum ;
-CONSTANT: words { 24-from-1 24-from-2 24-from-3 24-from-4 }
+CONSTANT: 24-words { 24-from-1 24-from-2 24-from-3 24-from-4 }
: backtrack-benchmark ( -- )
- words [ reset-memoized ] each
+ 24-words [ reset-memoized ] each
find-impossible-24 6479 assert=
- words [ "memoize" word-prop assoc-size ] map
+ 24-words [ "memoize" word-prop assoc-size ] map
{ 1588 5137 4995 10000 } assert= ;
MAIN: backtrack-benchmark