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