-
Notifications
You must be signed in to change notification settings - Fork 1
/
Euler_Problem-029.b93
151 lines (98 loc) · 13.4 KB
/
Euler_Problem-029.b93
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
v
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
#########################################################################################################################################################################################################
> "]M~A~~~~~h!"++++++*+**10p":~+"+*55+0p"d"2*1+20pv
v < v < "4"< @.g0+55$<
v < "4"< > $v v p05/+55p06< v < >-!#v_ v
>20g"4">80p:0\80gp80g1-:1-#^_$1-:#^_$"dd">80p:80g\20 g>:0\1pv>120g1p40p>050p20g60p>60g1g40g*50g+:55+%60g1p60g1-:#^_$$1-:#v_$0170p>9*70g1g+10g%70g1+:70p20g-1-#^_20g"4">90p30p:30g90gg:| >55+0g1-55+0p$v>30g90g1-:1-#^_$1-:1-#^_@>80g1-:1-#v_$1-:1-#v_^
^_^#!:-1< ^ < >$30g90gp$ > ^
^ <"d" <
[1,0] HASH (357913941)
[2,0] Width (200)
[4,0] (Pow) a
[5,0] (Pow) carry
[6,0] (Pow) pos
[7,0] (Hash) pos
[8,0] (loop) temp
[3,0] (WriteGrid) temp_X
[9,0] (WriteGrid) temp_Y
[10,0] result
"]M~A~~~~~h!"++++++*+** ==> 357913941
// Zero out number-row
> $v
20 g>:0\1pv> @
^_^#!:-1<
// Zero out cache - array (do not use in loop - uses [8,0] )
v < +65<
20g56+>80p:0\80gp80g1-:1-#^_$1-:#^_$
// Multiplicate [number-row] * stack (m -> {} )
v p05/+55p06<
40p050p20g60p>60g1g40g*50g+:55+%60g1p60g1-:#^_$
// Calculate Pow(A, B) (a,b -> {} )
> $v v p05/+55p06<
\20 g>:0\1pv>120g1p40p>050p20g60p>60g1g40g*50g+:55+%60g1p60g1-:#^_$$1-:#v_$
^_^#!:-1< ^ <
// Calculate SIntHash from number-row
v <
0170p>9*70g1g+10g%70g1+:70p20g-1-#^_
// Execute ### [2..100 ; 2..100] times
v < "d" <
"dd">80p:80g ### 80g1-:1-#^_$1-:1-#^_$ @
// Put into Grid (value on stack) (top: no dup || mid: dup || bot: loop)
v < +56<
>-!#v_ v
20g56+>90p30p:30g90gg:| > . v>30g90g1-:1-#^_$1-:1-#^_@>
>$30g90gp$> ^
---------------------------------------
This problem is really not made for Befunge. The numbers become quickly too big to be stored in a 64 bit field, and you need to remember a lot of them.
My solution is probably a bit hacky/cheaty: We calculate the numbers via long multiplication and 200 single fields. Then we calculate a hash of that number and store the hash.
The *cheaty* part is that I needed to be sure there are no hash collisions in our set of numbers - so I tested it beforehand in a quick C# solution. And on a side note: Its disturbing how easy these problems are in a high-level language after working with Befunge for such a log time :(