Project Euler with Befunge


Fork me on GitHub
2014-12-10

Problem 044: Pentagon numbers

Description:

Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 - 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = | Pk - Pj | is minimised; what is the value of D?


Solution:
>v%%% %%%%       >    v
v06p09:/2*-1*3:p06::+1<vg07g09                         <<  <
g$ >:70p:3*1   v #      >0v>vv p03+g03*2:p04-\g04+g03:<
v                      <3 pp2# v/4    <   >:30g+40g`! |
1#  >            4**1+:0^ 40>0g>:40g`#^_>:|:/4p03/2g03< $
>-:|^6-p08:/2*-< #        >^ >30g2/30p4/^ >$30g:*-30g\  |
 8 >$$           ^v030:+1**46+g09g08             ># !#  # _^
 >::**::**8*20p1 ^v>vv p03+g03*2:p04-\g04+g03:<@.-g08g0 9<
                  pp2# v/4    <   >:30g+40g`! |  ^5%6   <$
                  40>0g>:40g`#^_>:|:/4p03/2g03< >$     ^
                  >^ >30g2/30p4/^ >$30g:*-30g\ #^_6%5-#^_^
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

My first attempt at this problem took over 5 hours to compute and had a complexity of O(n^3).

The problem is that you need a square root to inverse the pentagonal formula and Befunge has no square root function. So I needed to implement my own version of integer square roots in Befunge (see wikipedia). The program is still not really fast but it's good that I managed to speed it up to a time where you can execute it without waiting the whole night.

Also this program is nicely compact, by the time I'm writing this my Befunge interpreter BefunExec has gotten a display of all possible paths a program can take. And if you look at the graph of this program, it looks pretty interesting...


Interpreter steps: 1 509 045 439
Execution time (BefunExec): 4min 18s (5.83 MHz)
Program size: 60 x 11 (fully conform befunge-93)
Solution: 5482660
Solved at: 2014-12-10



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