Cubic permutations

2015-07-07

Problem 062: Cubic permutations

Description:

The cube, 41063625 (345^3), can be permuted to produce two other cubes: 56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

Solution:

v $ # ... #
  $ #     #
  $ .     .
    .     .
  $ .     .
  $ .     .
    #     #
    # ... #
  v                                          _v#!:p/g42\+ <
>5 28p    78*9*3-:    24p    68*:    25p*:26p >1-:0\:24g%4^
v <                           v+1           <
0                                           |-g02<
>1+:::**:22p 0\v   v\-1 <>20p0>:3*:24g%4+\24 g/g:|
$         v+55:<>\1>9*\:|:                     @$$$.g/g42\+4%g42:+1$       <
          >%\:#^|#/+55\$<+                  >    3*:2+:24g%4+\24g/g1+:28g-!|
         >$ #\>#<>\# :#+_^                       >*::2v   vp/g42\+4%g42:+2\<
^p/g42\+4%g42:+2\1p/g42\+4%g42:+1\g22p/g42\+4%g42:\g0 <
^                                                         <

Download

This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Only after at least sixty-two mathematical programs in befunge you will truly appreciate a hashtable.

For real, everything would be so much better if I could retrieve this stuff in O(1).

My approach is pretty straight-forward. We calculate an permutation-insensitive hash. Then store them together with the times it appeared in a hashmap (I mean a list -.-). Now we just go through all the cubes until a single hash appeared five times. In C# with a Dictionary this takes around 10ms.

Interpreter steps:	952 323 293
Execution time (BefunExec):	6min 3s (2.62 MHz)
Program size:	505 x 58
Solution:	127035954683
Solved at:	2015-07-07