factor/extra/project-euler/079/079.factor

! Copyright (c) 2008 Aaron Schaefer.
! See http://factorcode.org/license.txt for BSD license.
USING: assocs io.encodings.ascii io.files kernel make math
    math.parser sequences sets project-euler.common ;
IN: project-euler.079

! http://projecteuler.net/index.php?section=problems&id=79

! DESCRIPTION
! -----------

! A common security method used for online banking is to ask the user for three
! random characters from a passcode. For example, if the passcode was 531278,
! they may asked for the 2nd, 3rd, and 5th characters; the expected reply would
! be: 317.

! The text file, keylog.txt, contains fifty successful login attempts.

! Given that the three characters are always asked for in order, analyse the
! file so as to determine the shortest possible secret passcode of unknown
! length.


! SOLUTION
! --------

<PRIVATE

: source-079 ( -- seq )
    "resource:extra/project-euler/079/keylog.txt" ascii file-lines ;

: >edges ( seq -- seq )
    [
        [ string>digits [ 2 head , ] keep 2 tail* , ] each
    ] { } make ;

: find-source ( seq -- elt )
    unzip diff
    [ "Topological sort failed" throw ] [ first ] if-empty ;

: remove-source ( seq elt -- seq )
    [ swap member? ] curry reject ;

: (topological-sort) ( seq -- )
    dup length 1 > [
        dup find-source dup , remove-source (topological-sort)
    ] [
        [ first [ , ] each ] unless-empty
    ] if ;

PRIVATE>

: topological-sort ( seq -- seq )
    [ [ (topological-sort) ] { } make ] keep
    combine over diff append ;

: euler079 ( -- answer )
    source-079 >edges topological-sort digits>number ;

! [ euler079 ] 100 ave-time
! 1 ms ave run time - 0.46 SD (100 trials)

! TODO: set words on sequences are relatively slow; topological sort could be
! cleaned up and generalized much better, but it works for this problem

SOLUTION: euler079