Project Euler with Befunge


Fork me on GitHub
2014-09-22

Problem 032: Pandigital products

Description:

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.


Solution:
v
 $$$$$$$$$
 ###############################

    vp2\0:<
>" ">  1-:|
       v                                                                                                                                                 <  *"ce"<
v   p01 1$<       vp1\0:<         >v    >v          >$v         >v    >v          >$v         >v    >v          >$v   v\g1:< >10g:1+10p2pv
>9"ec"*>80p:80g55+>  1-:|  >:55+%:|>:1g!|>1\1p55+/:!| >\:>:55+%:|>:1g!|>1\1p55+/:!| >*:>:55+%:|>:1g!|>1\1p55+/:!| >55+> 1-:|>|           >80g1-:5558***-#^_$1-:1-|
                        >$:^      $#    $#          <    ^      $#    $#          <    ^      $#    $#          <v++++++++$< >$          ^v                     $<
v            <                    >     >                       >     >                      $>     >$        $00>9-!       ^             1
             |                                                                                                                            <0               <*9*3+1*94<
                        vp1\0:<         >v    >v          >$v         >v    >v          >$v         >v    >v          >$v   v\g1:< >10g:1+10p2pv
>"c"49*1+3*9*>80p:80g55+>  1-:|  >:55+%:|>:1g!|>1\1p55+/:!| >\:>:55+%:|>:1g!|>1\1p55+/:!| >*:>:55+%:|>:1g!|>1\1p55+/:!| >55+> 1-:|>|           >80g1-:"d"-#^_$1-:55+-|
                              >$:^      $#    $#          <    ^      $#    $#          <    ^      $#    $#          <v++++++++$< >$          ^                     $
                                        >     >#v                     >#    >#   #<                $>     >$        $00>9-!       ^
v                                               <                   v\<           ^                                                                                  <
    v                                                    -1<       v< |:g2:<
             v          ># $#    >#     v#     -1<                  ^$<
>" ">80p80g1->70p80g2g:!|>70g2g -|      > 70g:1-#^_$80g:2-#^_$0>" ">    1-:| >+#<\:#<_+.@
                        >^       >070g2p^                                  >$^
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

The main focus here was optimizing the pandigital testing. The rest is just looping over every possible number.
We can optimize the outer loop a little bit if we look at the possible multiplicands. There are only 2 possibilities if we need 9 digits in our calculation:

  • 1-digit number * 4-digit number = 4-digit number
  • 2-digit number * 3-digit number = 4-digit number

Interpreter steps: 42 123 428
Execution time (BefunExec): 7.19s (5.86 MHz)
Program size: 166 x 21
Solution: 45228
Solved at: 2014-09-22



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