Rosetta Code

Fraction reduction: Difference between revisions

Page Discussion

Fraction reduction (view source)

Revision as of 16:45, 17 January 2022

18,887 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, marked p2js compatible
m (→‎{{header|Phix}}: added syntax colouring, marked p2js compatible)
Line 3,481:
 
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->
<lang Phix>function to_n(sequence digits, integer remove_digit=0)
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
if remove_digit!=0 then
<span style="color: #008080;">function</span> <span style="color: #000000;">to_n</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">remove_digit</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
integer d = find(remove_digit,digits)
<span style="color: #008080;">if</span> <span style="color: #000000;">remove_digit</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
digits[d..d] = {}
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">remove_digit</span><span style="color: #0000FF;">,</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span>
integer res = digits[1]
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">..</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for i=2 to length(digits) do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
res = res*10+digits[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
return res
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">*</span><span style="color: #000000;">10</span><span style="color: #0000FF;">+</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
 
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
function ndigits(integer n)
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
-- generate numbers with unique digits efficiently
-- and store them in an array for multiple re-use,
<span style="color: #008080;">function</span> <span style="color: #000000;">ndigits</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
-- along with an array of the removed-digit values.
<span style="color: #000080;font-style:italic;">-- generate numbers with unique digits efficiently
sequence res = {},
-- and store them in an array for multiple re-use,
digits = tagset(n),
-- along with an array of the removed-digit values.</span>
used = repeat(1,n)&repeat(0,9-n)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
while true do
<span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span>
sequence nine = repeat(0,9)
<span style="color: #000000;">used</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</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;">9</span><span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
for i=1 to length(used) do
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
if used[i] then
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nine</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;">9</span><span style="color: #0000FF;">)</span>
nine[i] = to_n(digits,i)
<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;">used</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
end for
<span style="color: #000000;">nine</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;">to_n</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
res = append(res,{to_n(digits),nine})
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
bool found = false
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for i=n to 1 by -1 do
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">to_n</span><span style="color: #0000FF;">(</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">),</span><span style="color: #000000;">nine</span><span style="color: #0000FF;">})</span>
integer d = digits[i]
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
if not used[d] then ?9/0 end if
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</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>
used[d] = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
for j=d+1 to 9 do
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</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>
if not used[j] then
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
used[j] = 1
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">d</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
digits[i] = j
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
for k=i+1 to n do
<span style="color: #000000;">used</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>
digits[k] = find(0,used)
<span style="color: #000000;">digits</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;">j</span>
used[digits[k]] = 1
<span style="color: #008080;">for</span> <span style="color: #000000;">k</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: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span>
found = true
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
exit
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
end for
if found then exit end if <span style="color: #008080;">exit</span>
<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>
if not found then exit end if
<span style="color: #008080;">if</span> <span style="color: #000000;">found</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>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<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: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
 
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
atom t0 = time(),
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
t1 = time()+1
for n=2 to 6 do
<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>
sequence d = ndigits(n)
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
integer count = 0
<span style="color: #000080;font-style:italic;">--for n=2 to 6 do</span>
sequence omitted = repeat(0,9)
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
for i=1 to length(d)-1 do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ndigits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
{integer xn, sequence rn} = d[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for j=i+1 to length(d) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">omitted</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;">9</span><span style="color: #0000FF;">)</span>
{integer xd, sequence rd} = d[j]
<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;">d</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
for k=1 to 9 do
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">xn</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">rn</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
integer yn = rn[k], yd = rd[k]
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if yn!=0 and yd!=0 and xn/xd = yn/yd then
<span style="color: #0000FF;">{</span><span style="color: #004080;">integer</span> <span style="color: #000000;">xd</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
count += 1
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span>
omitted[k] += 1
<span style="color: #004080;">integer</span> <span style="color: #000000;">yn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">yd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rd</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
if count<=12 then
<span style="color: #008080;">if</span> <span style="color: #000000;">yn</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">yd</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #000000;">xn</span><span style="color: #0000FF;">/</span><span style="color: #000000;">xd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">yn</span><span style="color: #0000FF;">/</span><span style="color: #000000;">yd</span> <span style="color: #008080;">then</span>
printf(1,"%d/%d => %d/%d (removed %d)\n",{xn,xd,yn,yd,k})
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
elsif time()>t1 then
<span style="color: #000000;">omitted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
printf(1,"working (%d/%d)...\r",{i,length(d)})
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">12</span> <span style="color: #008080;">then</span>
t1 = time()+1
<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/%d =&gt; %d/%d (removed %d)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">xn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">})</span>
end if
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()!=</span><span style="color: #004600;">JS</span> <span style="color: #008080;">then</span>
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;">"working (%d/%d)...\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)})</span>
end for
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
end for
<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>
printf(1,"%d-digit fractions found:%d, omitted %v\n\n",{n,count,omitted})
<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>
?elapsed(time()-t0)</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</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-digit fractions found:%d, omitted %v\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">omitted</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre>
Line 3,626 ⟶ 3,631:
"10 minutes and 13s"
</pre>
Note the code is now limited to 4 digits, which is almost mandatory for running under pwa/p2js unless you like staring at a blank screen.
 
=={{header|Python}}==
Petelomax
7,803

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/293842"