Paste: ant

Author:	mrjbq7
Mode:	factor
Date:	Wed, 21 Sep 2011 00:57:48

Plain Text |

Delete Paste

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 seen adjoin
            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
Mode:	python
Date:	Wed, 21 Sep 2011 00:58:15

Plain Text |

Delete Annotation

from collections import deque
# import psyco; psyco.full()

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

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

    while stack:
        p = stack.pop()
        if p not in seen:
            seen.add(p)
            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
Mode:	text
Date:	Wed, 21 Sep 2011 00:59:17

Plain Text |

Delete Annotation

$ time python ant.py 
148848

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

Annotation: ant puzzle

Author:	mrjbq7
Mode:	text
Date:	Wed, 21 Sep 2011 01:13:24

Plain Text |

Delete Annotation

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
Mode:	factor
Date:	Wed, 21 Sep 2011 02:43:44

Plain Text |

Delete Annotation

( scratchpad ) [ ant ] time
Running time: 431.449506665 seconds

Additional information was collected.
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


( scratchpad ) gc-stats.
                     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


( scratchpad ) gc-summary.
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



( scratchpad ) dispatch-stats.
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
Mode:	factor
Date:	Wed, 21 Sep 2011 02:49:49

Plain Text |

Delete Annotation

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 seen adjoin
            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
Mode:	factor
Date:	Wed, 21 Sep 2011 03:05:23

Plain Text |

Delete Annotation

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 seen adjoin
            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
Mode:	factor
Date:	Thu, 22 Sep 2011 22:25:31

Plain Text |

Delete Annotation

: 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 ] [
            [ pick adjoin ] keep
            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
Mode:	factor
Date:	Thu, 22 Sep 2011 22:42:23

Plain Text |

Delete Annotation

: 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
Mode:	factor
Date:	Thu, 22 Sep 2011 22:46:32

Plain Text |

Delete Annotation

: 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) ;

New Annotation

Summary:
Author:
Mode:	textPostgreSQLPowerCenter Parameter Fileactionscriptadaada95ans-forth94antantlrantlr4apacheconfapdlapplescriptaspaspect-jassembly-agcassembly-agsassembly-arm32assembly-m68kassembly-macro32assembly-mcs51assembly-parrotassembly-r2000assembly-x86avroawkbbatchbbjbcelbeanshellbibtexbinsource-agccc#c++cfscriptchillcilclipsclojurecmakecobolcoffeescriptcoldfusioncplex-lpcsscsvcvs-commitddartdjangodockerfiledotdoxygendrawj2ddsssleiffelembperlerlangfactorfhtmlforthfortranfortran90foxprofreemarkergcbasicgettextgherkingnuplotgogradlegroovygsphaskellhaxehexhl7v2hlslhtaccesshtmlhxmli4glicalendariconidlinforminiinno-setupinterlisiojamonjavajava module-infojavaccjavafxjavascriptjcljedit-actionsjflexjhtmljmkjsonjspkotlinlatexlexlilypondlispliterate-haskelllogslogtalklotosluam4macroschedulermailmakefilemaplemarkdownmavenmavscriptmetapostmlmodula3moinmqscmustache-templatemxmlmyghtymysqln3netrexxnqcnsis2objective-cobjectrexxoccamomnimarkopensipsoutlinepascalpatchperlphppikepl-sqlpl-sql9pl1plaintexplantumlpop11postscriptpovraypowerdynamopowershellprogressprologpropertiesprotobufpspptlpurepvwavepyrexpythonqdocrakefilercprdrebolredcoderelax-ng-compactrenderman-ribrestrfcrhtmlroffrpm-specrtfrubyrustrviews#s+sassbtscalaschemesdl/prsgmlshellscriptshtmlsipsippslateslaxsmalltalksmartysmi-mibsparqlsql-loadersqrsquidconfstatasvn-commitswiftswigtcltemplate-toolkittextexinfotldtransact-sqltsptwikityposcripturluscriptvalavbscriptvelocityverilogvhdlvisualbasicvrml2wellknowntextxmlxqxslyabyamlzpt
Body:

Done