Project Euler with Befunge


Fork me on GitHub
2016-09-01

Problem 094: Almost equilateral triangles

Description:

It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units.

We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit.

Find the sum of the perimeters of all almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).


Solution:
"}}2( "****04003pp201p102p>04g01g2*`#v_v
Xv2*2g10**!%3*g20-2g10!-1%3*g102`2g10< 0
X>-*03g+03p01g2*3%2-!01g2+# 02g*3%v    3
Xv*2g10+*2g20g10p30+g30*+* g1022*!< @.g<
C>02g3*+01p02p            ^
Start
??
Pause
Reset
Output:
Stack:   (0)

Explanation:

Nothing much to say about this one, we play a bit with the triangle formulas until we reach something that looks like a Pell equation. My approach is basically the same as the one on mathblog.dk, but he explains it better. (And I improved my approach a bit after I read his article, his math skills are pretty good :D).

The code is in a way interesting because it only has a single conditional operator. I could remove two conditional by multiplying the increment with the normalized condition (0|1). This way if (condition) { x += increment; } becomes x += (int)(condition) * increment, which is a neat way to safe a bit of space in our program (and the resulting 40x5 code is pretty compact)


Interpreter steps: 2 009
Execution time (BefunExec): 0ms (? MHz)
Program size: 40 x 5 (fully conform befunge-93)
Solution: 518408346
Solved at: 2016-09-01



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