Project Euler with Befunge


Fork me on GitHub
2014-10-12

Problem 042: Coded triangle numbers

Description:

The nth term of the sequence of triangle numbers is given by t(n) = 0.5 * n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t(10). If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?


Solution:
                              v ################################################################################
                                ################################################################################
A                               ################################################################################
ABILITY                         ################################################################################
ABLE                            ################################################################################
ABOUT                          v                                       <
ABOVE                         > 1"/&"*+00p>"P":10p 5:20p *30p 050p 260p^
ABSENCE
ABSOLUTELY                     >50g1+:50p :1+*2/  "0"\ :10g%" "+\10g/p v
ACADEMIC                       |`\g03                      /2*+1: +1g05<
ACCEPT
ACCESS                         >070p0>70g60gg:" "-!#v_"@"-+v
ACCIDENT                             ^p07+1g07      $#     <
ACCOMPANY                      |-g00p06+1:g06pg06*39<
ACCORDING
ACCOUNT                        >260p 0 >93*60gg:10g%" "+\10g/g"0"-!v
ACHIEVE                                |-g00 p06+1:g06            +<
ACHIEVEMENT                          @.<
...
...
This program is too big to display/execute here, click [download] to get the full program.

Explanation:

Similar to problem 22 this is not quite befunge-friendly due to enormous input size. But otherwise it wasn't hard, I create for every word the word value and count the triangle numbers in it.

Two little tricks:

  • I cached the triangle numbers from 1 to 400 (biggest possible word value is 364 because the longest word is 14 letters)
  • to count the triangle numbers just add the boolean results of the isTriangle function. Because true is 1 and false is 0 this results equals the number of triangle numbers.

Interpreter steps: 526 637
Execution time (BefunExec): 406ms (1.30 MHz)
Program size: 112 x 1788
Solution: 162
Solved at: 2014-10-12



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