extra/project-euler/079/079.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: assocs io.encodings.ascii io.files kernel make math math.parser
   4     sequences sets project-euler.common ;
   5 IN: project-euler.079
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=79
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! A common security method used for online banking is to ask the user for three
  13 ! random characters from a passcode. For example, if the passcode was 531278,
  14 ! they may asked for the 2nd, 3rd, and 5th characters; the expected reply would
  15 ! be: 317.
  16
  17 ! The text file, keylog.txt, contains fifty successful login attempts.
  18
  19 ! Given that the three characters are always asked for in order, analyse the
  20 ! file so as to determine the shortest possible secret passcode of unknown
  21 ! length.
  22
  23
  24 ! SOLUTION
  25 ! --------
  26
  27 <PRIVATE
  28
  29 : source-079 ( -- seq )
  30     "resource:extra/project-euler/079/keylog.txt" ascii file-lines ;
  31
  32 : >edges ( seq -- seq )
  33     [
  34         [ string>digits [ 2 head , ] keep 2 tail* , ] each
  35     ] { } make ;
  36
  37 : find-source ( seq -- elt )
  38     unzip diff
  39     [ "Topological sort failed" throw ] [ first ] if-empty ;
  40
  41 : remove-source ( seq elt -- seq )
  42     [ swap member? not ] curry filter ;
  43
  44 : (topological-sort) ( seq -- )
  45     dup length 1 > [
  46         dup find-source dup , remove-source (topological-sort)
  47     ] [
  48         [ first [ , ] each ] unless-empty
  49     ] if ;
  50
  51 PRIVATE>
  52
  53 : topological-sort ( seq -- seq )
  54     [ [ (topological-sort) ] { } make ] keep
  55     combine over diff append ;
  56
  57 : euler079 ( -- answer )
  58     source-079 >edges topological-sort 10 digits>integer ;
  59
  60 ! [ euler079 ] 100 ave-time
  61 ! 1 ms ave run time - 0.46 SD (100 trials)
  62
  63 ! TODO: set words on sequences are relatively slow; topological sort could be
  64 ! cleaned up and generalized much better, but it works for this problem
  65
  66 SOLUTION: euler079