extra/project-euler/206/206.factor

   1 ! Copyright (c) 2010 Aaron Schaefer. All rights reserved.
   2 ! The contents of this file are licensed under the Simplified BSD License
   3 ! A copy of the license is available at http://factorcode.org/license.txt
   4 USING: grouping kernel math math.ranges project-euler.common sequences ;
   5 IN: project-euler.206
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=206
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! Find the unique positive integer whose square has the form
  13 ! 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit.
  14
  15
  16 ! SOLUTION
  17 ! --------
  18
  19 ! Through mathematical analysis, we know that the number must end in 00, and
  20 ! the only way to get the last digits to be 900, is for our answer to end in
  21 ! 30 or 70.
  22
  23 <PRIVATE
  24
  25 ! 1020304050607080900 sqrt, rounded up to the nearest 30 ending
  26 CONSTANT: lo 1010101030
  27
  28 ! 1929394959697989900 sqrt, rounded down to the nearest 70 ending
  29 CONSTANT: hi 1389026570
  30
  31 : form-fitting? ( n -- ? )
  32     number>digits 2 group [ first ] map
  33     { 1 2 3 4 5 6 7 8 9 0 } = ;
  34
  35 : candidates ( -- seq )
  36     lo lo 40 + [ hi 100 <range> ] bi@ append ;
  37
  38 PRIVATE>
  39
  40 : euler206 ( -- answer )
  41     candidates [ sq form-fitting? ] find-last nip ;
  42
  43 ! [ euler206 ] 100 ave-time
  44 ! 321 ms ave run time - 8.33 SD (100 trials)
  45
  46 SOLUTION: euler206