Project Euler with Befunge


Fork me on GitHub
2015-07-04

Problem 061: Cyclical figurate numbers

Description:

Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Triangle        P3,n=n(n+1)/2    1, 3, 6, 10, 15, ...
Square          P4,n=n2          1, 4, 9, 16, 25, ...
Pentagonal      P5,n=n(3n?1)/2   1, 5, 12, 22, 35, ...
Hexagonal       P6,n=n(2n?1)     1, 6, 15, 28, 45, ...
Heptagonal      P7,n=n(5n?3)/2   1, 7, 18, 34, 55, ...
Octagonal       P8,n=n(3n?2)     1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

  • The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).
  • Each polygonal type: triangle (P(3,127)=8128), square (P(4,91)=8281), and pentagonal (P(5,44)=2882), is represented by a different number in the set.
  • This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.


Solution:
v$$  ### ---------------------------------------------------------------- ###
 $$  ### ---------------------------------------------------------------- ###
 $   ### ---------------------------------------------------------------- ###
 $   ### ---------------------------------------------------------------- ###
 $   ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
     ### ---------------------------------------------------------------- ###
           v_v#!          _v#                       <1      g02$$<
  #####    1 v  p02g01_v#! #  g02$_v#!:p\+9%*88g02 <0
> # 6 # 10p   288** 20p>20g1-20p10g>1-:0\2*20g88*/+^^ $<0p03+1g03 p+*2g02/*88g<
  #####    0 >20g1-20p030p0>1+::::*\-2/20g1+*+:"}"8*\`#^_:"ec"*`#^_30g88*%9+30^
           >g>1-:0\5\p:0\6\p:0\7\p:#v_$  01-60p011p v
v<         $_^#!:                   <0              <     <       <$$<
>611gg1+611gp611gg12p511gg13p12g10g-!#v_13g"_ "+`#v_712gg#^_13g88* %9+13g88*/12v
^<pg115+1gg115pg116-10                <v88g-1g115+9%*88g-1g115g11_^#g41p41g+*2g<
^<pgg11670p11-1g11                     *#        $<v05+9%*8        8g05%"d"g41<
                                       >/611g1-g2*+g"d"%14g"d"/-*#^_10g1-11g`!|
^<pg1150pg116-10p11+1g11pg2171                                                <
>2*+g:.+55+,21g1+:21p10g-#v_" =  ",,,,.@           >88*/60g2*+g"d"/-#^_v
^gg126/*88gg125+9%*88gg125<0p120                                       <
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

Pretty cool problem, I have to say.

It's one of these problem that you can easily make dynamic. In the middle-left of this program you see the number 6 surrounded with #. This is the "amount of resulting numbers" parameter of our program. For this Euler-problem you need to set this to 6. But for debugging purposes I mostly tested it with 3. And if you want you can try it out with bigger numbers 7 or 8. (But then you need to move the code down a bit - otherwise the cache-part will intersect with the code-part).

With this number we first generate all the polygon-numbers from 3 to SIDES_COUNT + 2 with the formula (n-2) * (n^2 - n)/2 + n. Then we go recursively through all these numbers. First we test triangle[1] with square[1], then with square[2] and so on. (The recursion is - as always - just a stack and a stack pointer).

A last note: This was (until now) probably the hardest program to fit in the befunge 80x25 size restriction. I barely managed to get it (and now its exactly 80x25) and I had to use quite some trickery.


Interpreter steps: 50 105 245
Execution time (BefunExec): 14s (3.48 MHz)
Program size: 80 x 25 (fully conform befunge-93)
Solution: 28684
Solved at: 2015-07-04



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