extra/project-euler/100/100.factor

   1 ! Copyright (c) 2008 Eric Mertens.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: kernel math math.functions project-euler.common ;
   4 IN: project-euler.100
   5
   6 ! http://projecteuler.net/index.php?section=problems&id=100
   7
   8 ! DESCRIPTION ! -----------
   9
  10 ! If a box contains twenty-one colored discs, composed of fifteen blue discs
  11 !  and six red discs, and two discs were taken at random, it can be seen that
  12 !  the probability of taking two blue discs, P(BB) = (15/21)*(14/20) = 1/2.
  13
  14 ! The next such arrangement, for which there is exactly 50% chance of taking
  15 !  two blue discs at random, is a box containing eighty-five blue discs and
  16 !  thirty-five red discs.
  17
  18 ! By finding the first arrangement to contain over 10^12 = 1,000,000,000,000
  19 !  discs in total, determine the number of blue discs that the box would contain.
  20
  21
  22 ! SOLUTION
  23 ! --------
  24
  25 : euler100 ( -- answer )
  26     1 1
  27     [ dup dup 1 - * 2 * 10 24 ^ <= ]
  28     [ [ 6 * swap - 2 - ] keep swap ] while nip ;
  29
  30 ! TODO: solution needs generalization
  31
  32 ! [ euler100 ] 100 ave-time
  33 ! 0 ms ave run time - 0.14 SD (100 trials)
  34
  35 SOLUTION: euler100