Project Euler with Befunge


Fork me on GitHub
2014-07-10

A lot of you probably know Project Euler.
For those who don't here a short explanation: Project Euler is a collection of mathematical/programming problems. Most problems consist of finding a single number and are solved by writing a program in the programming language of your choice.

Most people solve these by using normal languages like C, Java, Phyton, Haskell etc. But you can also go a step further and try solving it with a little bit more exotic languages.

So here are my solutions written in Befunge

Note:
Similar to most Befunge content on this site I only used the Befunge-93 instruction-set but ignored the 80x25 size restriction.
Still I tries to keep the programs in the Befunge-93 grid size, but that wasn't possible for all. So I guess some programs are technically Befunge-98.

Also the original befunge-93 spec didn't specify the word size of the stack or the grid
So, while most programs run happily with 32bit integers some need an interpreter that supports 64bit integers for both stack and grid.

I have a included javascript runner here, but for one I only enabled it for programs of reasonable sizes (a few soutions had source files in the megabyte range).
And also it's not the fastest interpreter and some solution take quite a while to finish.
I recommend using BefunExec. I specially made that interpreter for this project. It can run befunge code with around 6.5 MHz (on my machine)

My favorites:

All solved problems

Number Title Time Size Solution (hover to reveal)
1 Multiples of 3 and 5
62ms
30x5
Bef-93
233,168
2 Even Fibonacci numbers
62ms
26x5
Bef-93
4,613,732
3 Largest prime factor
9.55s
55x4
Bef-93
6,857
4 Largest palindrome product
1min 17s
71x6
Bef-93
906,609
5 Smallest multiple
47ms
73x6
Bef-93
232,792,560
6 Sum square difference
7.35s
72x16
Bef-93
25,164,150
7 10001st prime
7.63s
1000x156
Bef-93+
104,743
8 Largest product in a series
234ms
116x29
Bef-93+
23,514,624,000
9 Special Pythagorean triplet
6min 34s
79x7
Bef-93
31,875,000
10 Summation of primes
1min 7s
2000x1007
Bef-93+
142,913,828,922
11 Largest product in a grid
78ms
151x31
Bef-93+
70,600,674
12 Highly divisible triangular number
7.57s
1000x170
Bef-93+
76,576,500
13 Large sum
78ms
59x113
Bef-93+
5,537,376,230
14 Longest Collatz sequence
11min
51x5
Bef-93
837,799
15 Lattice paths
47ms
78x27
Bef-93+
137,846,528,820
16 Power digit sum
4.23s
60x14
Bef-93
1,366
17 Number letter counts
47ms
48x15
Bef-93
21,124
18 Maximum path sum I
16ms
120x16
Bef-93+
1,074
19 Counting Sundays
546ms
72x12
Bef-93
171
20 Factorial digit sum
265ms
101x6
Bef-93+
648
21 Amicable numbers
1min 42s
400x33
Bef-93+
31,626
22 Names scores
16min
109x5164
Bef-93+
871,198,282
23 Non-abundant sums
32min
400x88
Bef-93+
4,179,871
24 Lexicographic permutations
31ms
61x8
Bef-93
2,783,915,460
25 1000-digit Fibonacci number
1min 56s
123x28
Bef-93+
4,782
26 Reciprocal cycles
4.48s
100x16
Bef-93+
983
27 Quadratic primes
6.24s
600x162
Bef-93+
-59,231
28 Number spiral diagonals
15ms
54x2
Bef-93
669,171,001
29 Distinct powers
23min
248x59
Bef-93+
9,183
30 Digit fifth powers
7.33s
59x8
Bef-93
443,839
31 Coin sums
47s
60x11
Bef-93
73,682
32 Pandigital products
7.19s
166x21
Bef-93+
45,228
33 Digit canceling fractions
109ms
67x18
Bef-93
100
34 Digit factorials
1min 20s
45x7
Bef-93
40,730
35 Circular primes
27s
2000x516
Bef-93+
55
36 Double-base palindromes
172ms
78x8
Bef-93
872,187
37 Truncatable primes
20s
2000x514
Bef-93+
748,317
38 Pandigital multiples
624ms
169x6
Bef-93+
932,718,654
39 Integer right triangles
827ms
72x6
Bef-93
840
40 Champernowne's constant
16ms
69x7
Bef-93
210
41 Pandigital prime
31ms
40x17
Bef-93
7,652,413
42 Coded triangle numbers
406ms
112x1788
Bef-93+
162
43 Sub-string divisibility
140ms
68x23
Bef-93
16,695,334,890
44 Pentagon numbers
4min 18s
60x11
Bef-93
5,482,660
45 Triangular, pentagonal, and hexagonal
3.49s
48x6
Bef-93
1,533,776,805
46 Goldbach's other conjecture
13s
200x57
Bef-93+
5,777
47 Distinct primes factors
8min 57s
400x518
Bef-93+
134,043
48 Self powers
3.73s
37x3
Bef-93
9,110,846,700
49 Prime permutations
124ms
66x8
Bef-93
296,962,999,629
50 Consecutive prime sum
30s
2000x512
Bef-93+
997,651
51 Prime digit replacements
1min 53s
78x20
Bef-93
121,313
52 Permuted multiples
2.92s
45x6
Bef-93
142,857
53 Combinatoric selections
125ms
80x7
Bef-93
4,075
54 Poker hands
2.54s
118x1009
Bef-93+
376
55 Lychrel numbers
2.22s
56x5
Bef-93
249
56 Powerful digit sum
13s
75x11
Bef-93
972
57 Square root convergents
15s
80x54
Bef-93+
153
58 Spiral primes
12s
50x17
Bef-93
26,241
59 XOR decryption
6.30s
273x128
Bef-93+
107,359
60 Prime pair sets
33min
3323x3360
Bef-93+
26,033
61 Cyclical figurate numbers
14s
80x25
Bef-93
28,684
62 Cubic permutations
6min 3s
505x58
Bef-93+
127,035,954,683
63 Powerful digit counts
2.76s
80x10
Bef-93
49
64 Odd period square roots
5.80s
51x9
Bef-93
1,322
65 Convergents of e
124ms
80x14
Bef-93
272
66 Diophantine equation
55s
80x25
Bef-93
661
67 Maximum path sum II
266ms
299x101
Bef-93+
7,273
68 Magic 5-gon ring
78ms
39x25
Bef-93
6,531,031,914,842,725
69 Totient maximum
16ms
80x10
Bef-93
510,510
70 Totient permutation
3.71s
150x47
Bef-93+
8,319,823
71 Ordered fractions
11s
73x8
Bef-93
428,570
72 Counting fractions
50s
486x1047
Bef-93+
303,963,552,391
73 Counting fractions in a range
3min 22s
2000x12010
Bef-93+
7,295,372
74 Digit factorial chains
49s
1224x833
Bef-93+
402
75 Singular integer right triangles
39s
1000x1515
Bef-93+
161,667
76 Counting summations
32ms
104x108
Bef-93+
190,569,291
77 Prime summations
47ms
101x39
Bef-93+
71
78 Coin partitions
2min 50s
251x256
Bef-93+
55,374
79 Passcode derivation
0ms
56x21
Bef-93
73,162,890
80 Square root digital expansion
1min 56s
69x18
Bef-93
40,886
81 Path sum: two ways
234ms
500x180
Bef-93+
427,337
82 Path sum: three ways
2.11s
500x180
Bef-93+
260,324
83 Path sum: four ways
1.75s
500x180
Bef-93+
425,185
84 Monopoly odds
19s
77x20
Bef-93
101,524
85 Counting rectangles
109ms
35x8
Bef-93
2,772
86 Cuboid route
1min 31s
66x10
Bef-93
1,818
87 Prime power triples
27s
1000x1018
Bef-93+
1,097,343
88 Product-sum numbers
23s
1024x50
Bef-93+
7,587,457
89 Roman numerals
78ms
73x1009
Bef-93+
743
90 Cube digit pairs
54s
80x45
Bef-93+
1,217
91 Right triangles with integer coordinates
343ms
36x5
Bef-93
14,234
92 Square digit chains
6min 19s
80x16
Bef-93
8,581,146
93 Arithmetic expressions
42s
111x211
Bef-93+
1,258
94 Almost equilateral triangles
0ms
40x5
Bef-93
518,408,346
95 Amicable chains
4min 2s
2017x1035
Bef-93+
14,316
96 Su Doku
1min 30s
218x50
Bef-93+
24,702
97 Large non-Mersenne prime
21s
13x5
Bef-93
8,739,992,577
98 Anagramic squares
22s
258x199
Bef-93+
18,769
99 Largest exponential
1.11s
63x1000
Bef-93+
709
100 Arranged probability
0ms
56x3
Bef-93
756,872,327,473
101 Optimum polynomial
250ms
83x37
Bef-93+
37,076,114,526
102 Triangle containment
281ms
80x1009
Bef-93+
228

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