# Paste: ant

Author: mrjbq7 factor Wed, 21 Sep 2011 00:57:48
Plain Text |
```USING: accessors combinators hash-sets hashtables kernel locals
math math.parser sequences sets vectors ;

IN: ant

: sum-digits ( n -- x )
0 swap [ dup zero? ] [
10 [ mod + ] [ /i ] 2bi
] until drop ;

TUPLE: point x y ;

C: <point> point

: walkable? ( point -- ? )
[ x>> ] [ y>> ] bi [ sum-digits ] bi@ + 25 <= ;

:: ant ( -- total )
HS{ } clone :> seen
V{ } clone :> stack
0 :> total!

1000 1000 <point> stack push

[ stack empty? total 10000 > or ] [
stack pop :> p
p seen in? [
p walkable? [
total 1 + total!
p clone [ 1 + ] change-x stack push
p clone [ 1 - ] change-x stack push
p clone [ 1 + ] change-y stack push
p clone [ 1 - ] change-y stack push
] when
] unless
] until total ;```

## Annotation: ant.py

Author: mrjbq7 python Wed, 21 Sep 2011 00:58:15
Plain Text |
```from collections import deque
# import psyco; psyco.full()

def sum_digits(n):
tot = 0
while n:
tot += n % 10
n //= 10

def ant():
seen = set()
count = 0
stack = deque([(1000, 1000)])

while stack:
p = stack.pop()
if p not in seen:
x, y = p
if sum_digits(x) + sum_digits(y) <= 25:
count += 1
stack.append((x+1, y  ))
stack.append((x-1, y  ))
stack.append((x,   y+1))
stack.append((x,   y-1))

return count

print ant()```

## Annotation: times

Author: mrjbq7 text Wed, 21 Sep 2011 00:59:17
Plain Text |
```\$ time python ant.py
148848

real	0m1.058s
user	0m1.018s
sys	0m0.035s```

## Annotation: ant puzzle

Author: mrjbq7 text Wed, 21 Sep 2011 01:13:24
Plain Text |
```There is an ant which can walk around on a planar grid. The ant can move one
space at a time left, right, up or down. That is, from (x, y) the ant can go
to (x+1, y), (x-1, y), (x, y+1), and (x, y-1).

Points where the sum of the digits of the x coordinate plus the sum of the
digits of the y coordinate are greater than 25 are inaccessible to the ant.
For example, the point (59,79) is inaccessible because 5 + 9 + 7 + 9 = 30,
which is greater than 25.

How many points can the ant access if it starts at (1000, 1000), including
(1000, 1000) itself?```

## Annotation: factor running time

Author: mrjbq7 factor Wed, 21 Sep 2011 02:43:44
Plain Text |
```( scratchpad ) [ ant ] time
Running time: 431.449506665 seconds

dispatch-stats.  - Print method dispatch statistics
gc-events.       - Print all garbage collection events
gc-stats.        - Print breakdown of different garbage collection events
gc-summary.      - Print aggregate garbage collection statistics

Number Total     Mean     Median   Min      Max
Copying from nursery 17     25,530 µs 1,501 µs 1,371 µs 27 µs    3,627 µs
Copying from aging   6      35,204 µs 5,867 µs 5,483 µs 3,168 µs 10,256 µs
Copying to tenured   1      8,860 µs  8,860 µs 8,860 µs 8,860 µs 8,860 µs

Collections:          24
Cards scanned:        63,807
Decks scanned:        298
Code blocks scanned:  1,574
Total time:           69,595 µs
Card scan time:       28,112 µs
Code block scan time: 963 µs
Data heap sweep time: 0 µs
Code heap sweep time: 0 µs
Compaction time:      0 µs

Megamorphic hits    528092
Megamorphic misses  2
Cold to monomorphic 23
Mono to polymorphic 0
Poly to megamorphic 1
Tag check count     4
Tuple check count   22```

## Annotation: using specialized-vector for stack

Author: j factor Wed, 21 Sep 2011 02:49:49
Plain Text |
```USING: accessors alien.c-types classes.struct combinators
hash-sets hashtables kernel locals math math.parser sequences
sets specialized-vectors vectors ;
IN: ant

STRUCT: point { x uint } { y uint } ;

SPECIALIZED-VECTOR: point

: <point> ( x y -- point ) point <struct-boa> ; inline
: push-point ( x y stack -- )
push-new [ y<< ] [ x<< ] bi ; inline
: >point< ( point -- x y ) [ x>> ] [ y>> ] bi ; inline

: sum-digits ( n -- x )
0 swap [ dup zero? ] [ 10 /mod swap [ + ] dip ] until drop ; inline

: walkable? ( point -- ? )
[ x>> ] [ y>> ] bi [ sum-digits ] bi@ + 25 <= ; inline

:: ant ( -- total )
HS{ } clone :> seen
point-vector{ } clone :> stack
0 :> total!

1000 1000 <point> stack push

[ stack empty? ] [
stack pop clone :> p
p seen in? [
p walkable? [
total 1 + total!
p >point< stack {
[ [ 1 + ] 2dip push-point ]
[ [ 1 - ] 2dip push-point ]
[ [ 1 + ] dip  push-point ]
[ [ 1 - ] dip  push-point ]
} 3cleave
] when
] unless
] until total ;```

## Annotation: struct only

Author: j factor Wed, 21 Sep 2011 03:05:23
Plain Text |
```USING: accessors alien.c-types classes.struct combinators
hash-sets hashtables kernel locals math math.parser sequences
sets specialized-vectors vectors ;
IN: ant

! TUPLE: point { x uint } { y uint } ;
! : <point> ( x y -- point ) point boa ; inline

STRUCT: point { x uint } { y uint } ;
: <point> ( x y -- point ) point <struct-boa> ; inline

: push-point ( x y stack -- )
[ <point> ] dip push ; inline
: >point< ( point -- x y ) [ x>> ] [ y>> ] bi ; inline

: sum-digits ( n -- x )
0 swap [ dup zero? ] [ 10 /mod swap [ + ] dip ] until drop ; inline

: walkable? ( point -- ? )
[ x>> ] [ y>> ] bi [ sum-digits ] bi@ + 25 <= ; inline

:: ant ( -- total )
HS{ } clone :> seen
200,000 <vector> :> stack

1000 1000 <point> stack push

0 [ stack empty? ] [| total |
stack pop :> p
p seen in? [ total ] [
p walkable? [
p >point< stack {
[ [ 1 + ] 2dip push-point ]
[ [ 1 - ] 2dip push-point ]
[ [ 1 + ] dip  push-point ]
[ [ 1 - ] dip  push-point ]
} 3cleave
total 1 +
] [ total ] if
] if
] until ;```

## Annotation: no locals

Author: mrjbq7 factor Thu, 22 Sep 2011 22:25:31
Plain Text |
```: walk ( stack point -- stack' )
{
[ clone [ 1 + ] change-x over push ]
[ clone [ 1 - ] change-x over push ]
[ clone [ 1 + ] change-y over push ]
[ clone [ 1 - ] change-y over push ]
} cleave ;

: (ant) ( total seen stack -- total' )
[ dup empty? ] [
dup pop pick dupd in? [ drop ] [
dup walkable? [ [ 1 + ] 3dip walk ] [ drop ] if
] if
] until 2drop ;

: ant-no-locals ( -- total )
0 HS{ } clone V{ } clone 1000 1000 <point> over push (ant) ;```

## Annotation: or this

Author: mrjbq7 factor Thu, 22 Sep 2011 22:42:23
Plain Text |
```: walk ( stack point -- stack' )
{
[ clone [ 1 + ] change-x over push ]
[ clone [ 1 - ] change-x over push ]
[ clone [ 1 + ] change-y over push ]
[ clone [ 1 - ] change-y over push ]
} cleave ;

: ?walk ( total seen stack point -- total seen stack )
dup walkable? [ [ 1 + ] 3dip walk ] [ drop ] if ;

: until-empty ( seq quot -- )
[ dup empty? ] swap until drop ; inline

: ?adjoin ( elt set -- elt/f )
2dup in? [ 2drop f ] [ dupd adjoin ] if ;

: (ant) ( total seen stack -- total' )
[ dup pop pick ?adjoin [ ?walk ] when* ] until-empty drop ;

: ant-no-locals ( -- total )
0 HS{ } clone V{ } clone 1000 1000 <point> over push (ant) ;```

## Annotation: with fry

Author: mrjbq7 factor Thu, 22 Sep 2011 22:46:32
Plain Text |
```: walk ( stack point -- stack' )
{
[ clone [ 1 + ] change-x over push ]
[ clone [ 1 - ] change-x over push ]
[ clone [ 1 + ] change-y over push ]
[ clone [ 1 - ] change-y over push ]
} cleave ;

: ?walk ( total stack point -- total stack )
dup walkable? [ walk [ 1 + ] dip ] [ drop ] if ;

: until-empty ( seq quot -- )
[ dup empty? ] swap until drop ; inline

: ?adjoin ( elt set -- elt/f )
2dup in? [ 2drop f ] [ dupd adjoin ] if ;

: (ant) ( total stack seen -- total' )
'[ dup pop _ ?adjoin [ ?walk ] when* ] until-empty ;

: ant-no-locals ( -- total )
0 1000 1000 <point> 1vector HS{ } clone (ant) ;```