Jump to content

List rooted trees: Difference between revisions

List rooted trees (view source)

Revision as of 02:08, 25 January 2022

17,112 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, marked p2js compatible
(→‎{{header|Mathematica}} / {{header|Wolfram Language}}: changed to local variable for n, removed ClearAll, and offered method to output as a tree graph.)
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 1,436:
=={{header|Phix}}==
{{trans|Go}}
<!--<lang Phix>atom t0 = time(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
sequence list = {1},
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
offset = repeat(0,32)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">list</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
offset[1..2] = 1
<span style="color: #000000;">offset</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;">32</span><span style="color: #0000FF;">)</span>
 
<span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
function show(integer t, l)
string res = repeat('?',l)
<span style="color: #008080;">function</span> <span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
integer level = 0
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'?'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
for i=l to 1 by -1 do
<span style="color: #004080;">integer</span> <span style="color: #000000;">level</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
integer r2 = remainder(t,2)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</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>
res[i] = "[}(]{)"[mod(level-r2,6)+1]
<span style="color: #004080;">integer</span> <span style="color: #000000;">r2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
level += r2*4-2
<span style="color: #000000;">res</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: #008000;">"[}(]{)"</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">level</span><span style="color: #0000FF;">-</span><span style="color: #000000;">r2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
t = floor(t/2)
<span style="color: #000000;">level</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">r2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span>
end for
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
if level!=0 then ?9/0 end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<span style="color: #008080;">if</span> <span style="color: #000000;">level</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure listTrees(integer n)
for i:=offset[n+1]+1 to offset[n+2] do
<span style="color: #008080;">procedure</span> <span style="color: #000000;">listTrees</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
printf(1,"%s\n",{show(list[i], n*2)})
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">:=</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
end for
<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;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">show</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure assemble(atom t, integer n, sl, pos, rem)
--
<span style="color: #008080;">procedure</span> <span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">)</span>
-- assemble tree from subtrees
<span style="color: #000080;font-style:italic;">--
-- t: assembled parts so far
-- n: length ofassemble tree we want tofrom makesubtrees
-- slt: length ofassembled subtreeparts weso are looking atfar
-- posn: offset length of subtreetree we arewant lookingto atmake
-- remsl: remaining length toof besubtree putwe togetherare looking at
-- pos: offset of subtree we are looking at
--
-- rem: remaining length to be put together
if rem == 0 then
--</span>
list = append(list, t*2+1)
<span style="color: #008080;">if</span> <span style="color: #000000;">rem</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">list</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
if sl>rem then -- need smaller sub-trees
<span style="color: #008080;">else</span>
sl = rem
<span style="color: #008080;">if</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">></span><span style="color: #000000;">rem</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- need smaller sub-trees</span>
pos = offset[sl+1]
<span style="color: #000000;">sl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rem</span>
elsif pos>=offset[sl+2] then
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
-- used up sl-trees, try smaller ones
<span style="color: #008080;">elsif</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
if sl == 1 then return end if
<span style="color: #000080;font-style:italic;">-- used up sl-trees, try smaller ones</span>
pos = offset[sl]
<span style="color: #008080;">if</span> <span style="color: #000000;">sl</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sl -= 1
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">]</span>
end if
<span style="color: #000000;">sl</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
atom u = or_bits(t*power(2,2*sl),list[pos+1])
assemble(u, n, sl, pos, rem-sl)
<span style="color: #004080;">atom</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">or_bits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">*</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">),</span><span style="color: #000000;">list</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
assemble(t, n, sl, pos+1, rem)
<span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">-</span><span style="color: #000000;">sl</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">sl</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pos</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rem</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure mktrees(integer n)
if offset[n+2]=0 then
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mktrees</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if n>0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
mktrees(n - 1)
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">mktrees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
assemble(0, n, n-1, offset[n], n-1)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
offset[n+2] = length(list)
<span style="color: #000000;">assemble</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</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;">list</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure main(integer n)
mktrees(n)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
atom nt = offset[n+2]-offset[n+1],
<span style="color: #000000;">mktrees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
td = time()-t0
<span style="color: #004080;">atom</span> <span style="color: #000000;">nt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">offset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
string e = iff(td>0.1?" ("&elapsed(td)&")":"")
<span style="color: #000000;">td</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
printf(1,"Number of %d-trees: %,d%s\n", {n, nt, e})
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">td</span><span style="color: #0000FF;">></span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" ("</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">td</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">")"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
if n<=5 then listTrees(n) end if
<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;">"Number of %d-trees: %,d%s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">nt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">listTrees</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=0 to 20 do
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
main(i)
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">12</span><span style="color: #0000FF;">:</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for</lang>
<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 1,550 ⟶ 1,553:
Number of 20-trees: 12,826,228 (13.6s)
</pre>
Beyond that it gets extremely slow. Under pwa/p2js 14-trees exceeded the JavaScript call stack limit, so I knocked a couple more off for safety.
 
=={{header|Python}}==
Petelomax
7,796

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/257854"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information