extra/project-euler/206/206.factor

   1 ! Copyright (c) 2010 Aaron Schaefer.
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: grouping kernel math project-euler.common ranges
   4 sequences sequences.cords ;
   5 IN: project-euler.206
   6
   7 ! https://projecteuler.net/problem=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
  20 ! end in 00, and the only way to get the last digits to be 900,
  21 ! is for our answer to end in 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 } sequence= ;
  34
  35 : candidates ( -- seq )
  36     lo lo 40 + [ hi 100 <range> ] bi@ cord-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