1 ! Copyright (c) 2009 Guillaume Nargeot.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: fry io.encodings.ascii io.files locals kernel math
4 math.order math.parser math.ranges sequences splitting
8 ! http://projecteuler.net/index.php?section=problems&id=081
13 ! In the 5 by 5 matrix below, the minimal path sum from the top
14 ! left to the bottom right, by only moving to the right and
15 ! down, is indicated in bold red and is equal to 2427.
23 ! Find the minimal path sum, in matrix.txt (right click and
24 ! 'Save Link/Target As...'), a 31K text file containing a 80 by
25 ! 80 matrix, from the top left to the bottom right by only
26 ! moving right and down.
32 ! Shortest path problem solved using Dijkstra algorithm.
36 : source-081 ( -- matrix )
37 "resource:extra/project-euler/081/matrix.txt"
38 ascii file-lines [ "," split [ string>number ] map ] map ;
40 : get-matrix ( x y matrix -- n ) nth nth ;
42 : change-matrix ( x y matrix quot -- )
43 [ nth ] dip change-nth ; inline
45 :: minimal-path-sum-to ( x y matrix -- n )
47 x zero? [ 0 y 1 - matrix get-matrix
50 x 1 - 0 matrix get-matrix
52 x 1 - y matrix get-matrix
53 x y 1 - matrix get-matrix
59 : update-minimal-path-sum ( x y matrix -- )
60 3dup minimal-path-sum-to '[ _ + ] change-matrix ;
62 : (euler081) ( matrix -- n )
63 dup first length iota dup
64 [ pick update-minimal-path-sum ] cartesian-each
69 : euler081 ( -- answer )
70 source-081 (euler081) ;
72 ! [ euler081 ] 100 ave-time
73 ! 9 ms ave run time - 0.39 SD (100 trials)