extra/project-euler/112/112.factor

   1 ! Copyright (c) 2009 Guillaume Nargeot.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math project-euler.common sequences sorting ;
   4 IN: project-euler.112
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=112
   7
   8 ! DESCRIPTION
   9 ! -----------
  10
  11 ! Working from left-to-right if no digit is exceeded by the digit to its left
  12 ! it is called an increasing number; for example, 134468.
  13
  14 ! Similarly if no digit is exceeded by the digit to its right it is called a
  15 ! decreasing number; for example, 66420.
  16
  17 ! We shall call a positive integer that is neither increasing nor decreasing a
  18 ! "bouncy" number; for example, 155349.
  19
  20 ! Clearly there cannot be any bouncy numbers below one-hundred, but just over
  21 ! half of the numbers below one-thousand (525) are bouncy. In fact, the least
  22 ! number for which the proportion of bouncy numbers first reaches 50% is 538.
  23
  24 ! Surprisingly, bouncy numbers become more and more common and by the time we
  25 ! reach 21780 the proportion of bouncy numbers is equal to 90%.
  26
  27 ! Find the least number for which the proportion of bouncy numbers is exactly
  28 ! 99%.
  29
  30
  31 ! SOLUTION
  32 ! --------
  33
  34 <PRIVATE
  35
  36 : bouncy? ( n -- ? )
  37     number>digits dup natural-sort
  38     [ = not ] [ reverse = not ] 2bi and ;
  39
  40 PRIVATE>
  41
  42 : euler112 ( -- answer )
  43     0 0 0 [
  44         2dup swap 99 * = not
  45     ] [
  46         [ 1 + ] 2dip pick bouncy? [ 1 + ] [ [ 1 + ] dip ] if
  47     ] do while 2drop ;
  48
  49 ! [ euler112 ] 100 ave-time
  50 ! 2749 ms ave run time - 33.76 SD (100 trials)
  51
  52 SOLUTION: euler112