extra/project-euler/062/062.factor

   1 ! Copyright (c) 2009 Guillaume Nargeot.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: arrays assocs hashtables kernel math math.functions
   4 project-euler.common sequences sorting ;
   5 IN: project-euler.062
   6
   7 ! http://projecteuler.net/index.php?section=problems&id=062
   8
   9 ! DESCRIPTION
  10 ! -----------
  11
  12 ! The cube, 41063625 (345^3), can be permuted to produce two
  13 ! other cubes: 56623104 (384^3) and 66430125 (405^3). In
  14 ! fact, 41063625 is the smallest cube which has exactly three
  15 ! permutations of its digits which are also cube.
  16
  17 ! Find the smallest cube for which exactly five permutations of
  18 ! its digits are cube.
  19
  20
  21 ! SOLUTION
  22 ! --------
  23
  24 <PRIVATE
  25
  26 : cube ( n -- n^3 ) 3 ^ ; inline
  27 : >key ( n -- k ) cube number>digits natural-sort ; inline
  28 : has-entry? ( n assoc -- ? ) [ >key ] dip key? ; inline
  29
  30 : (euler062) ( n assoc -- n )
  31     2dup has-entry? [
  32         2dup [ >key ] dip
  33         [ dup 0 swap [ 1 + ] change-nth ] change-at
  34         2dup [ >key ] dip at first 5 =
  35         [
  36             [ >key ] dip at second
  37         ] [
  38             [ 1 + ] dip (euler062)
  39         ] if
  40     ] [
  41         2dup 1 pick cube 2array -rot
  42         [ >key ] dip set-at [ 1 + ] dip
  43         (euler062)
  44     ] if ;
  45
  46 PRIVATE>
  47
  48 : euler062 ( -- answer )
  49     1 1 <hashtable> (euler062) ;
  50
  51 ! [ euler062 ] 100 ave-time
  52 ! 78 ms ave run time - 0.9 SD (100 trials)
  53
  54 SOLUTION: euler062