extra/benchmark/ant/ant.factor

   1 ! Copyright (C) 2011 John Benediktsson
   2 ! See http://factorcode.org/license.txt for BSD license
   3
   4 USING: accessors hash-sets kernel math sequences sets vectors ;
   5
   6 IN: benchmark.ant
   7
   8 ! There is an ant which can walk around on a planar grid. The ant
   9 ! can move one space at a time left, right, up or down. That is,
  10 ! from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and
  11 ! (x, y-1).
  12 !
  13 ! Points where the sum of the digits of the x coordinate plus the
  14 ! sum of the digits of the y coordinate are greater than 25 are
  15 ! inaccessible to the ant.  For example, the point (59,79) is
  16 ! inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than
  17 ! 25.
  18 !
  19 ! How many points can the ant access if it starts at (1000, 1000),
  20 ! including (1000, 1000) itself?
  21
  22 : sum-digits ( n -- x )
  23     0 swap [ 10 /mod swap [ + ] dip ] until-zero ;
  24
  25 TUPLE: point x y ;
  26 C: <point> point
  27
  28 ! USE: alien.c-types
  29 ! USE: classes.struct
  30 ! STRUCT: point { x uint } { y uint } ;
  31 ! : <point> ( x y -- point ) point <struct-boa> ; inline
  32
  33 : walkable? ( point -- ? )
  34     [ x>> ] [ y>> ] bi [ sum-digits ] bi@ + 25 <= ; inline
  35
  36 :: ant-benchmark ( -- )
  37     200000 <hash-set> :> seen
  38     100000 <vector> :> stack
  39     0 :> total!
  40
  41     1000 1000 <point> stack push
  42
  43     [ stack empty? ] [
  44         stack pop :> p
  45         p seen ?adjoin [
  46             p walkable? [
  47                 total 1 + total!
  48                 p clone [ 1 + ] change-x stack push
  49                 p clone [ 1 - ] change-x stack push
  50                 p clone [ 1 + ] change-y stack push
  51                 p clone [ 1 - ] change-y stack push
  52             ] when
  53         ] when
  54     ] until total 148848 assert= ;
  55
  56 MAIN: ant-benchmark