extra/project-euler/079/079.factor

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