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 <
^                                                         <
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

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript