Rosetta Code

Solve hanging lantern problem: Difference between revisions

Page Discussion

Solve hanging lantern problem (view source)

Revision as of 11:29, 24 May 2022

2,569 bytes removed ,  2 years ago
m
→‎full solution: merged the two approaches, much faster
m (→‎{{header|Phix}}: added 1..9 and 10,14,12 (verifying/matching Julia above and my other test below))
m (→‎full solution: merged the two approaches, much faster)
Line 494:
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<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> <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>▼
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>▼
<span style="color: #008080;">function</span> <span style="color: #000000;">get_lantern</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">z</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;">bool</span> <span style="color: #000000;">bJustCount</span><span style="color: #0000FF;">=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">na</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;">bJustCount</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integersequence</span> <span style="color: #000000;">nodel</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_indexapply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #0000007060A8;">dlength</span><span style="color: #0000FF;">)</span>
<span style="color: #0080807060A8;">ifmpz_fac_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodez</span><span style="color: #0000FF;">!,</span><span style="color: #7060A8;">sum</span><span style="color: #0046000000FF;">NULL(</span><span style="color: #000000;">l</span><span style="color: #0080800000FF;">then))</span>
<span style="color: #7060A8004080;">mpz_set_strmpz</span><span style="color: #0000FF;">(</span><span style="color: #000000;">zf</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #0000007060A8;">dmpz_init</span><span style="color: #0000FF;">)()</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span> <span style="color: #008080;">returnin</span> <span style="color: #000000;">0l</span> <span style="color: #008080;">do</span>
<span style="color: #0080807060A8;">endmpz_fac_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0080800000FF;">if)</span>
▲ <span style="color: #004080;">atom</span> <span style="color: #0000007060A8;">t0mpz_fdiv_q</span> <span style="color: #0000FF;">=(</span> <span style="color: #7060A8000000;">timez</span><span style="color: #0000FF;">(),</span> <span style="color: #000000;">t1z</span> <span style="color: #0000FF;">=,</span> <span style="color: #7060A8000000;">timef</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">iffor</span>▼
<span style="color: #008080;">endreturn</span> <span style="color: #008080000000;">if0</span>▼
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">na</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">na</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">na</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">setd</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;">s</span><span style="color: #0000FF;">)),</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_set_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">}</span>
Line 517:
<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: #0000FF;">=</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;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">z2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_lantern</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000004600;">bJustCountfalse</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">na</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">iffor</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">notto</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">bJustCountr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">thendo</span>
<span style="color: #008080000000;">forres</span> <span style="color: #0000000000FF;">k=</span> <span style="color: #0000FF7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1res</span> <span style="color: #0080800000FF;">to,</span> <span style="color: #7060A8000000;">lengthsi</span><span style="color: #0000FF;">(&</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">k</span><span style="color: #0080800000FF;">do])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>▼
<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;">si</span><span style="color: #0000FF;">&</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">])</span>
▲ <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
▲ <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z</span><span style="color: #0000FF;">,</span><span style="color: #000000;">z2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">progress</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"working... dict_size:%d\r"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)})</span>
<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>
▲ <span style="color: #008080;">end</span> <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: #0000FF;">&=</span> <span style="color: #000000;">si</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: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">z</span><span style="color: #0000FF;">),</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</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>
Line 560 ⟶ 553:
<span style="color: #008000;">"FGHIJK"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"LMNOPQR"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"STUVWXYZ"</span><span style="color: #0000FF;">},</span>
<span style="color: #000080008000;font-">"abcdefghi"</span><span style="color:italic #0000FF;">-- JS copes fine, but 7 in 3.5s vs 8 in 41.5s,}</span>
▲ <span style="color: #004080008080;">integerfor</span> <span style="color: #000000;">di</span> <span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #7060A8008080;">new_dictto</span> <span style="color: #0000FF000000;">9</span> <span style="color: #008080;">()do</span>
-- - tad too long to stare at a blank screen.
-- (vs desktop with progress & as-completed.)</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: #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;">7</span><span style="color: #0000FF;">:</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">test</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><span style="color: #000000;">i</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>
1 = 1:
1 = 1:
1
 
1, 23  23 = 3 3:
132,312,321
 
1, 23 23, 456  456 = 60 60:
132654,136254,136524,136542,163254,163524,163542,165324,165342,165432
312654,316254,316524,316542,321654,326154,326514,326541,361254,361524
Line 585 ⟶ 575:
651432,653124,653142,653214,653241,653412,653421,654132,654312,654321
 
1, 234, 567 = 140
1, 234, 567 = 140
1234567890, ABCDEFGHIJKLMN, OPQRSTUVWXYZ = 2454860399191200
1234567890, ABCDEFGHIJKLMN, OPQRSTUVWXYZ = 2454860399191200
1 = 1
1 = 1
1, 23 = 3
1, 23 = 3
1, 23, 456 = 60
1, 23, 456 = 60
1, 23, 456, 7890 = 12600
1, 23, 456, 7890 = 12600
1, 23, 456, 7890, ABCDE = 37837800
1, 23, 456, 7890, ABCDE = 37837800
1, 23, 456, 7890, ABCDE, FGHIJK = 2053230379200
1, 23, 456, 7890, ABCDE, FGHIJK = 2053230379200
1, 23, 456, 7890, ABCDE, FGHIJK, LMNOPQR = 2431106898187968000
1, 23, 456, 7890, ABCDE, FGHIJK, LMNOPQR = 2431106898187968000
1, 23, 456, 7890, ABCDE, FGHIJK, LMNOPQR, STUVWXYZ = 73566121315513295589120000
1, 23, 456, 7890, ABCDE, FGHIJK, LMNOPQR, STUVWXYZ = 73566121315513295589120000
1, 23, 456, 7890, ABCDE, FGHIJK, LMNOPQR, STUVWXYZ, abcdefghi = 65191584694745586153436251091200000
"41.4s"
</pre>
 
Petelomax
7,820

edits

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