79 lines
22 KiB
Text
79 lines
22 KiB
Text
(phixonline)-->
|
|
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">perequiv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #000080;font-style:italic;">-- Works by aligning and rotating in one step, so theoretically much faster on massive sets.
|
|
-- (ahem, faster than multiple rotates, index-only loops would obviously be even faster...)</span>
|
|
<span style="color: #004080;">bool</span> <span style="color: #000000;">res</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;">a</span><span style="color: #0000FF;">)==</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">))</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
|
|
<span style="color: #008080;">else</span>
|
|
<span style="color: #000080;font-style:italic;">-- align with a (ie make b[1]==a[1], by
|
|
-- rotating b k places in one operation)</span>
|
|
<span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">..$]&</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">k</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">b</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000080;font-style:italic;">-- eg {8,3,4,5} <=> {8,5,4,3}, ie
|
|
-- rotate *and* keep in alignment.</span>
|
|
<span style="color: #000000;">b</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;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$])</span>
|
|
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">==</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000080;font-style:italic;">-- return res</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"false"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"true"</span><span style="color: #0000FF;">}[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">function</span> <span style="color: #000000;">edge2peri</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">edges</span><span style="color: #0000FF;">)</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #000000;">was</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edges</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
|
|
<span style="color: #004080;">string</span> <span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">lnk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"too short"</span>
|
|
<span style="color: #008080;">else</span>
|
|
<span style="color: #000080;font-style:italic;">-- edges = sort(deep_copy(edges)) -- (see note below)</span>
|
|
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
|
|
<span style="color: #000000;">edges</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
|
|
<span style="color: #000000;">lnk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">and</span> <span style="color: #000000;">error</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
|
|
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lnk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #000000;">lnk</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">3</span><span style="color: #0000FF;">-</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
|
|
<span style="color: #000000;">edges</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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: #0000FF;">{}</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">edges</span><span style="color: #0000FF;">={}</span> <span style="color: #008080;">then</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #000000;">lnk</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span> <span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"oh dear"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">else</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lnk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"oops"</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">lnk</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
|
|
<span style="color: #008080;">exit</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span> <span style="color: #000000;">error</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"bad link"</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">error</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">error</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lnk</span><span style="color: #0000FF;">,</span><span style="color: #000000;">edges</span><span style="color: #0000FF;">,</span><span style="color: #000000;">was</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
|
|
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
|
|
|
|
<span style="color: #008080;">constant</span> <span style="color: #000000;">ptests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">}},</span>
|
|
<span style="color: #0000FF;">{{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">}},</span>
|
|
<span style="color: #000080;font-style:italic;">-- (check our results below against Go etc)</span>
|
|
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">}},</span>
|
|
<span style="color: #0000FF;">{{</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</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: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">,</span><span style="color: #000000;">17</span><span style="color: #0000FF;">}}}</span>
|
|
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ptests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
|
|
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ptests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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;">"%v equivalent to %v: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">perequiv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">)})</span>
|
|
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
|
|
|
|
<span style="color: #008080;">constant</span> <span style="color: #000000;">etests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">}},</span>
|
|
<span style="color: #0000FF;">{{</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">23</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">}},</span>
|
|
<span style="color: #0000FF;">{{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">12</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">14</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">17</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">18</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">19</span><span style="color: #0000FF;">}},</span>
|
|
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">}}}</span>
|
|
<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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">etests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</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;">"%v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">edge2peri</span><span style="color: #0000FF;">(</span><span style="color: #000000;">etests</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>
|
|
<!--
|