extra/project-euler/099/099.factor

   1 ! Copyright (c) 2008 Aaron Schaefer.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: io.encodings.ascii io.files kernel math math.functions math.parser
   4     math.vectors sequences splitting project-euler.common ;
   5 IN: project-euler.099
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=99
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! Comparing two numbers written in index form like 2^11 and 3^7 is not difficult,
  13 ! as any calculator would confirm that 2^11 = 2048 < 3^7 = 2187.
  14
  15 ! However, confirming that 632382^518061 519432^525806 would be much more
  16 ! difficult, as both numbers contain over three million digits.
  17
  18 ! Using base_exp.txt (right click and 'Save Link/Target As...'), a 22K text
  19 ! file containing one thousand lines with a base/exponent pair on each line,
  20 ! determine which line number has the greatest numerical value.
  21
  22 ! NOTE: The first two lines in the file represent the numbers in the example
  23 ! given above.
  24
  25
  26 ! SOLUTION
  27 ! --------
  28
  29 ! Use logarithms to make the calculations necessary more manageable.
  30
  31 <PRIVATE
  32
  33 : source-099 ( -- seq )
  34     "resource:extra/project-euler/099/base_exp.txt"
  35     ascii file-lines [ "," split [ string>number ] map ] map ;
  36
  37 : simplify ( seq -- seq )
  38     #! exponent * log(base)
  39     flip first2 swap [ log ] map v* ;
  40
  41 : solve ( seq -- index )
  42     simplify [ supremum ] keep index 1 + ;
  43
  44 PRIVATE>
  45
  46 : euler099 ( -- answer )
  47      source-099 solve ;
  48
  49 ! [ euler099 ] 100 ave-time
  50 ! 16 ms ave run timen - 1.67 SD (100 trials)
  51
  52 SOLUTION: euler099