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