Abelian sandpile model/Identity: Difference between revisions
Content added Content deleted
(Add OCaml solution) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
Line 2,240: | Line 2,240: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<lang Phix> |
<!--<lang Phix>--> |
||
<span style="color: #008080;">constant</span> <span style="color: #000000;">s1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"1 2 0"</span><span style="color: #0000FF;">,</span> |
|||
"2 1 1", |
|||
" |
<span style="color: #008000;">"2 1 1"</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #008000;">"0 1 3"</span><span style="color: #0000FF;">},</span> |
|||
s2 = {"2 1 3", |
|||
<span style="color: #000000;">s2</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"2 1 3"</span><span style="color: #0000FF;">,</span> |
|||
"1 0 1", |
|||
" |
<span style="color: #008000;">"1 0 1"</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #008000;">"0 1 0"</span><span style="color: #0000FF;">},</span> |
|||
s3 = {"3 3 3", |
|||
<span style="color: #000000;">s3</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"3 3 3"</span><span style="color: #0000FF;">,</span> |
|||
"3 3 3", |
|||
"3 3 3" |
<span style="color: #008000;">"3 3 3"</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #008000;">"3 3 3"</span><span style="color: #0000FF;">},</span> |
|||
s3_id = {"2 1 2", |
|||
<span style="color: #000000;">s3_id</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"2 1 2"</span><span style="color: #0000FF;">,</span> |
|||
"1 0 1", |
|||
" |
<span style="color: #008000;">"1 0 1"</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #008000;">"2 1 2"</span><span style="color: #0000FF;">},</span> |
|||
s4 = {"4 3 3", |
|||
<span style="color: #000000;">s4</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"4 3 3"</span><span style="color: #0000FF;">,</span> |
|||
"3 1 2", |
|||
" |
<span style="color: #008000;">"3 1 2"</span><span style="color: #0000FF;">,</span> |
||
<span style="color: #008000;">"0 2 3"</span><span style="color: #0000FF;">}</span> |
|||
function add(sequence s, t) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">add</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to 3 do |
|||
<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;">3</span> <span style="color: #008080;">do</span> |
|||
for j=1 to 5 by 2 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
s[i][j] += t[i][j]-'0' |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]-</span><span style="color: #008000;">'0'</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return s |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function topple(sequence s, integer one=0) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">one</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to 3 do |
|||
<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;">3</span> <span style="color: #008080;">do</span> |
|||
for j=1 to 5 by 2 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">5</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span> |
|||
if s[i][j]>'3' then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]></span><span style="color: #008000;">'3'</span> <span style="color: #008080;">then</span> |
|||
s[i][j] -= 4 |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">4</span> |
|||
if i>1 then s[i-1][j] += 1 end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if i<3 then s[i+1][j] += 1 end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if j>1 then s[i][j-2] += 1 end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</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> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if j<5 then s[i][j+2] += 1 end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><</span><span style="color: #000000;">5</span> <span style="color: #008080;">then</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</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> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if one=1 then return s end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">one</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: #000000;">s</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
one = -1 |
|||
<span style="color: #000000;">one</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</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;">for</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return iff(one=1?{}:iff(one=-1?topple(s):s)) |
|||
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?{}:</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">):</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
procedure shout(sequence s) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">shout</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
sequence r = repeat("",5) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</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;">5</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(s) do |
|||
<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;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
sequence si = s[i] |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
if string(si) then |
|||
<span style="color: #008080;">if</span> <span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
string ti = repeat(' ',length(si)) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">ti</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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">si</span><span style="color: #0000FF;">))</span> |
|||
r[1] &= ti |
|||
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ti</span> |
|||
r[2] &= si |
|||
<span style="color: #000000;">r</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;">si</span> |
|||
r[3] &= ti |
|||
<span style="color: #000000;">r</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;">ti</span> |
|||
else |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">3</span> <span style="color: #008080;">do</span> |
|||
r[j] &= si[j] |
|||
<span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">si</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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;">for</span> |
|||
puts(1,join(r,"\n")) |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">))</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
puts(1,"1. Show avalanche\n\n") |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1. Show avalanche\n\n"</span><span style="color: #0000FF;">)</span> |
|||
sequence s = s4, |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s4</span><span style="color: #0000FF;">,</span> |
|||
res = {" ",s} |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">}</span> |
|||
while true do |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
s = topple(s,1) |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
if s={} then exit end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">={}</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> |
|||
res &= {" ==> ",s} |
|||
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">" ==> "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">}</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
shout(res) |
|||
<span style="color: #000000;">shout</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> |
|||
puts(1,"2. Prove s1 + s2 = s2 + s1\n\n") |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"2. Prove s1 + s2 = s2 + s1\n\n"</span><span style="color: #0000FF;">)</span> |
|||
shout({" ",s1," + ",s2," = ",topple(add(s1,s2))}) |
|||
<span style="color: #000000;">shout</span><span style="color: #0000FF;">({</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" = "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #000000;">add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">))})</span> |
|||
shout({" ",s2," + ",s1," = ",topple(add(s2,s1))}) |
|||
<span style="color: #000000;">shout</span><span style="color: #0000FF;">({</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" = "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #000000;">add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s1</span><span style="color: #0000FF;">))})</span> |
|||
puts(1,"3. Show that s3 + s3_id == s3\n\n") |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"3. Show that s3 + s3_id == s3\n\n"</span><span style="color: #0000FF;">)</span> |
|||
shout({" ",s3," + ",s3_id," = ",topple(add(s3,s3_id))}) |
|||
<span style="color: #000000;">shout</span><span style="color: #0000FF;">({</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s3_id</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" = "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #000000;">add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s3_id</span><span style="color: #0000FF;">))})</span> |
|||
puts(1,"4. Show that s3_id + s3_id == s3_id\n\n") |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"4. Show that s3_id + s3_id == s3_id\n\n"</span><span style="color: #0000FF;">)</span> |
|||
shout({" ",s3_id," + ",s3_id," = ",topple(add(s3_id,s3_id))})</lang> |
|||
<span style="color: #000000;">shout</span><span style="color: #0000FF;">({</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s3_id</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s3_id</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" = "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">topple</span><span style="color: #0000FF;">(</span><span style="color: #000000;">add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s3_id</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s3_id</span><span style="color: #0000FF;">))})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |