extra/project-euler/099/099.factor

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