Lychrel numbers: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
|||
| Line 2,852: | Line 2,852: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<lang Phix> |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
limit = 10000 |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">iterations</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">500</span><span style="color: #0000FF;">,</span> |
|||
<span style="color: #000000;">limit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">10000</span> |
|||
sequence seeds = {}, |
|||
cache = {} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">seeds</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> |
|||
<span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
sequence temp = repeat(0,iterations) |
|||
sequence palin = {} |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">temp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">iterations</span><span style="color: #0000FF;">)</span> |
|||
integer related = 0 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">palin</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">related</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
for n=1 to limit do |
|||
string num = sprintf("%d",n), |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">limit</span> <span style="color: #008080;">do</span> |
|||
rev = reverse(num) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">num</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span> |
|||
bool palindrome = (num=rev) |
|||
<span style="color: #000000;">rev</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to iterations do |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">palindrome</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rev</span><span style="color: #0000FF;">)</span> |
|||
integer digit, carry = 0 |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">iterations</span> <span style="color: #008080;">do</span> |
|||
for x=length(num) to 1 by -1 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
digit = num[x]+rev[x]+carry-'0' |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
carry = digit>'9' |
|||
<span style="color: #000000;">digit</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">rev</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span> |
|||
num[x] = digit-carry*10 |
|||
<span style="color: #000000;">carry</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">></span><span style="color: #008000;">'9'</span> |
|||
end for |
|||
<span style="color: #000000;">num</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">-</span><span style="color: #000000;">carry</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span> |
|||
if carry then num = "1" & num end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
temp[i] = num |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">carry</span> <span style="color: #008080;">then</span> <span style="color: #000000;">num</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"1"</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">num</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
rev = reverse(num) |
|||
<span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">num</span> |
|||
if num=rev then exit end if |
|||
<span style="color: #000000;">rev</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
end for |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">=</span><span style="color: #000000;">rev</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if num!=rev then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
bool no_match = true |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">rev</span> <span style="color: #008080;">then</span> |
|||
num = sprintf("%d",n) |
|||
<span style="color: #004080;">bool</span> <span style="color: #000000;">no_match</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span> |
|||
if palindrome then |
|||
<span style="color: #000000;">num</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
palin = append(palin, num) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">palindrome</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">palin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">palin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
for c=1 to length(cache) do |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
string seed = cache[c] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
-- check against previous found seeds |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">seed</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cache</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">]</span> |
|||
for i=iterations to 1 by -1 do |
|||
<span style="color: #000080;font-style:italic;">-- check against previous found seeds</span> |
|||
string ti = temp[i] |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">iterations</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
|||
if length(seed)>length(ti) then |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">temp</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
exit |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seed</span><span style="color: #0000FF;">)></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
elsif seed=ti then |
|||
<span style="color: #008080;">exit</span> |
|||
<span style="color: #008080;">elsif</span> <span style="color: #000000;">seed</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ti</span> <span style="color: #008080;">then</span> |
|||
related += 1 |
|||
<span style="color: #000000;">no_match</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span> |
|||
exit |
|||
<span style="color: #000000;">related</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #008080;">exit</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if no_match=false then exit end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">no_match</span><span style="color: #0000FF;">=</span><span style="color: #004600;">false</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if no_match then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
seeds = append(seeds,num) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">no_match</span> <span style="color: #008080;">then</span> |
|||
cache = append(cache,temp[$]) |
|||
<span style="color: #000000;">seeds</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seeds</span><span style="color: #0000FF;">,</span><span style="color: #000000;">num</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">,</span><span style="color: #000000;">temp</span><span style="color: #0000FF;">[$])</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
printf(1,"%d lychrel seeds: %s\n",{length(seeds),join(seeds, ", ")}) |
|||
printf(1,"related lychrel: %d\n",related) |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d lychrel seeds: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seeds</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seeds</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span> |
|||
printf(1,"%d lychrel palindromes: %s\n", {length(palin),join(palin, ", ")})</lang> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"related lychrel: %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">related</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d lychrel palindromes: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">palin</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">palin</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">", "</span><span style="color: #0000FF;">)})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
Completes in under a second |
Completes in under a second on desktop/Phix, but takes about 10s under pwa/p2js |
||
<pre> |
<pre> |
||
5 lychrel seeds: 196, 879, 1997, 7059, 9999 |
5 lychrel seeds: 196, 879, 1997, 7059, 9999 |
||