tag:blogger.com,1999:blog-3465346478273690122024-03-14T04:12:05.294-07:00ProjectEuler solverShlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-346534647827369012.post-51549541180767910012011-04-15T14:30:00.000-07:002011-04-16T12:45:31.544-07:00Project Euler - Problem 13 - SpreadsheetI've copied the whole given table to a spreadsheet (open office was good enough). Then, I've summed them all and divided by 10^42 to get the first 10 digits.<br />
<br />
Here are the first leading 10 digits: 5537376230.<br />
<br />
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgorehNRImwD7CnTLC1LlzAAVTJAAvrFjybwg7029fQCFYpq2hKmGEXw5Zb_SYUuYi7Rb1P-sD77t3CX6kaaR2BvgQ7-azr7JJzdzSuFVKFlIVT0UB_uZH96uTgTGGGfMZ0BCafvzDMogc/s1600/prob13.jpg" imageanchor="1" style="clear: left; float: left; margin-bottom: 1em; margin-right: 1em;"><img border="0" height="182" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgorehNRImwD7CnTLC1LlzAAVTJAAvrFjybwg7029fQCFYpq2hKmGEXw5Zb_SYUuYi7Rb1P-sD77t3CX6kaaR2BvgQ7-azr7JJzdzSuFVKFlIVT0UB_uZH96uTgTGGGfMZ0BCafvzDMogc/s320/prob13.jpg" width="320" /></a></div>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-23739444602774783092011-04-15T13:57:00.001-07:002011-04-15T14:01:11.770-07:00Project Euler - Problem 10 - C#<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c1" style="color: #60a0b0; font-style: italic;"><a href="http://projecteuler.net/project/resources/010_7c4950764b52402fe1d29323af4e6c6f/010_overview.pdf">http://projecteuler.net/project/resources/010_7c4950764b52402fe1d29323af4e6c6f/010_overview.pdf</a></span></pre><pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"></pre><pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c1" style="color: #60a0b0; font-style: italic;">//The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">//Find the sum of all the primes below two million.</span>
<span class="k" style="color: #007020; font-weight: bold;">static</span> <span class="n">UInt64</span> <span class="nf" style="color: #06287e;">Problem10</span><span class="p">()</span>
<span class="p">{</span>
<span class="n">UInt64</span> <span class="n">sum_of_primes</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> <span class="p">(</span><span class="n">var</span> <span class="n">prime</span> <span class="k" style="color: #007020; font-weight: bold;">in</span> <span class="n">primes</span><span class="p">(</span><span class="m" style="color: #40a070;">2000000</span><span class="p">))</span>
<span class="p">{</span>
<span class="n">sum_of_primes</span> <span class="p">+=</span> <span class="n">prime</span><span class="p">;</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">//Console.Write(prime.ToString() + ", ");</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="n">sum_of_primes</span><span class="p">;</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">// Problem10: 142913828922</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">static</span> <span class="n">IEnumerable</span><span class="p"><</span><span class="n">UInt64</span><span class="p">></span> <span class="n">primes</span><span class="p">(</span><span class="n">UInt64</span> <span class="n">limit</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">List</span><span class="p"><</span><span class="n">UInt64</span><span class="p">></span> <span class="n">primes_list</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">new</span> <span class="n">List</span><span class="p"><</span><span class="n">UInt64</span><span class="p">>();</span> <span class="c1" style="color: #60a0b0; font-style: italic;">// reset with 0</span>
<span class="kt" style="color: #902000;">bool</span><span class="p">[]</span> <span class="n">nums_list</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">new</span> <span class="kt" style="color: #902000;">bool</span><span class="p">[</span><span class="n">limit</span><span class="p">];</span> <span class="c1" style="color: #60a0b0; font-style: italic;">// reset with 0</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">/* Create a list of all candidates. </span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> * false - Marks an invalid candidate.</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> * true - A valid candidate.</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> */</span>
<span class="n">nums_list</span><span class="p">[</span><span class="m" style="color: #40a070;">2</span><span class="p">]</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">true</span><span class="p">;</span>
<span class="n">primes_list</span><span class="p">.</span><span class="n">Add</span><span class="p">(</span><span class="m" style="color: #40a070;">2</span><span class="p">);</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="p">(</span><span class="n">UInt64</span> <span class="n">current_num</span> <span class="p">=</span> <span class="m" style="color: #40a070;">3</span><span class="p">;</span> <span class="n">current_num</span> <span class="p"><=</span> <span class="n">limit</span><span class="p">;</span> <span class="n">current_num</span> <span class="p">+=</span> <span class="m" style="color: #40a070;">2</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">nums_list</span><span class="p">[</span><span class="n">current_num</span><span class="p">]</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">true</span><span class="p">;</span>
<span class="p">}</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">// Sieve of Eratosthenes algorithm</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="p">(</span><span class="n">UInt64</span> <span class="n">current_num</span> <span class="p">=</span> <span class="m" style="color: #40a070;">3</span><span class="p">;</span> <span class="n">current_num</span> <span class="p"><=</span> <span class="n">limit</span><span class="p">;</span> <span class="n">current_num</span> <span class="p">+=</span> <span class="m" style="color: #40a070;">2</span><span class="p">)</span>
<span class="p">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="p">(</span><span class="n">nums_list</span><span class="p">[</span><span class="n">current_num</span><span class="p">]</span> <span class="p">==</span> <span class="k" style="color: #007020; font-weight: bold;">true</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">primes_list</span><span class="p">.</span><span class="n">Add</span><span class="p">(</span><span class="n">current_num</span><span class="p">);</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="p">(</span><span class="n">UInt64</span> <span class="n">elemenator</span> <span class="p">=</span> <span class="m" style="color: #40a070;">2</span> <span class="p">*</span> <span class="n">current_num</span><span class="p">;</span>
<span class="n">elemenator</span> <span class="p"><</span> <span class="n">limit</span><span class="p">;</span>
<span class="n">elemenator</span> <span class="p">+=</span> <span class="n">current_num</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">nums_list</span><span class="p">[</span><span class="n">elemenator</span><span class="p">]</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">false</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> <span class="p">(</span><span class="n">var</span> <span class="n">prime</span> <span class="k" style="color: #007020; font-weight: bold;">in</span> <span class="n">primes_list</span><span class="p">)</span>
<span class="p">{</span>
<span class="k" style="color: #007020; font-weight: bold;">yield</span> <span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="n">prime</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-88188052838118319672011-04-15T01:23:00.000-07:002011-04-15T01:23:57.843-07:00Project Euler - Problem 9 - C#<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="cm" style="color: #60a0b0; font-style: italic;">/*</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> A Pythagorean triplet is a set of three natural numbers, a b c, for which,</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> a^2 + b^2 = c^2</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> There exists exactly one Pythagorean triplet for which a + b + c = 1000.</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> Find the product abc.</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> */</span>
<span class="k" style="color: #007020; font-weight: bold;">static</span> <span class="kt" style="color: #902000;">int</span> <span class="nf" style="color: #06287e;">Problem9</span><span class="p">()</span>
<span class="p">{</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">/* HLD:</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> * a + b + c = 1000 ==> c = 1000 - a - b</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> * foreach {a, b} in {{1,1}, {1,2} ... {2,2} ... {499,1} ... {499,499}}</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> * predicate of pass: a^2 + b^2 = c^2</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> */</span>
<span class="n">var</span> <span class="n">solution_found</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">false</span><span class="p">;</span>
<span class="kt" style="color: #902000;">int</span> <span class="n">a</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">,</span> <span class="n">b</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="kt" style="color: #902000;">int</span> <span class="n">c</span> <span class="p">=</span> <span class="m" style="color: #40a070;">1000</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="p">(</span><span class="n">b</span> <span class="p">=</span> <span class="m" style="color: #40a070;">1</span><span class="p">;</span> <span class="n">b</span> <span class="p"><</span> <span class="m" style="color: #40a070;">499</span><span class="p">;</span> <span class="n">b</span><span class="p">++)</span>
<span class="p">{</span>
<span class="n">c</span> <span class="p">=</span> <span class="m" style="color: #40a070;">1000</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="p">(</span><span class="n">a</span> <span class="p">=</span> <span class="n">b</span><span class="p">;</span> <span class="n">a</span> <span class="p"><=</span> <span class="n">c</span><span class="p">;</span> <span class="n">a</span><span class="p">++)</span>
<span class="p">{</span>
<span class="n">c</span> <span class="p">=</span> <span class="m" style="color: #40a070;">1000</span> <span class="p">-</span> <span class="n">a</span> <span class="p">-</span> <span class="n">b</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="p">((</span><span class="n">a</span> <span class="p">*</span> <span class="n">a</span> <span class="p">+</span> <span class="n">b</span> <span class="p">*</span> <span class="n">b</span><span class="p">)</span> <span class="p">==</span> <span class="p">(</span><span class="n">c</span> <span class="p">*</span> <span class="n">c</span><span class="p">))</span>
<span class="p">{</span>
<span class="n">solution_found</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">true</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="p">(</span><span class="n">solution_found</span><span class="p">)</span>
<span class="p">{</span>
<span class="k" style="color: #007020; font-weight: bold;">break</span><span class="p">;</span>
<span class="p">}</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="n">a</span> <span class="p">*</span> <span class="n">b</span> <span class="p">*</span> <span class="n">c</span><span class="p">;</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">// Problem9: 31875000</span>
<span class="p">}</span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-21440622774148352682011-04-14T22:35:00.000-07:002011-04-15T01:25:11.372-07:00Project Euler - Problem 8 - C#<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="Apple-style-span" style="color: #007020;"><b><span class="Apple-style-span" style="color: black; font-family: 'Times New Roman'; font-size: small; font-weight: normal; white-space: normal;"><pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="cm" style="color: #60a0b0; font-style: italic;">/*</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">Find the greatest product of five consecutive digits in the 1000-digit number.</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> </span>
<span class="cm" style="color: #60a0b0; font-style: italic;">73167176531330624919225119674426574742355349194934</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">96983520312774506326239578318016984801869478851843</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">85861560789112949495459501737958331952853208805511</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">12540698747158523863050715693290963295227443043557</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">66896648950445244523161731856403098711121722383113</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">62229893423380308135336276614282806444486645238749</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">30358907296290491560440772390713810515859307960866</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">70172427121883998797908792274921901699720888093776</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">65727333001053367881220235421809751254540594752243</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">52584907711670556013604839586446706324415722155397</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">53697817977846174064955149290862569321978468622482</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">83972241375657056057490261407972968652414535100474</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">82166370484403199890008895243450658541227588666881</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">16427171479924442928230863465674813919123162824586</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">17866458359124566529476545682848912883142607690042</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">24219022671055626321111109370544217506941658960408</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">07198403850962455444362981230987879927244284909188</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">84580156166097919133875499200524063689912560717606</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">05886116467109405077541002256983155200055935729725</span>
<span class="cm" style="color: #60a0b0; font-style: italic;">71636269561882670428252483600823257530420752963450</span>
<span class="cm" style="color: #60a0b0; font-style: italic;"> */</span>
<span class="k" style="color: #007020; font-weight: bold;">static</span> <span class="kt" style="color: #902000;">int</span> <span class="nf" style="color: #06287e;">Problem8</span><span class="p">()</span>
<span class="p">{</span>
<span class="n">StringBuilder</span> <span class="n">data</span> <span class="p">=</span> <span class="k" style="color: #007020; font-weight: bold;">new</span> <span class="n">StringBuilder</span><span class="p">(</span><span class="m" style="color: #40a070;">1000</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"73167176531330624919225119674426574742355349194934"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"96983520312774506326239578318016984801869478851843"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"85861560789112949495459501737958331952853208805511"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"12540698747158523863050715693290963295227443043557"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"66896648950445244523161731856403098711121722383113"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"62229893423380308135336276614282806444486645238749"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"30358907296290491560440772390713810515859307960866"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"70172427121883998797908792274921901699720888093776"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"65727333001053367881220235421809751254540594752243"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"52584907711670556013604839586446706324415722155397"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"53697817977846174064955149290862569321978468622482"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"83972241375657056057490261407972968652414535100474"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"82166370484403199890008895243450658541227588666881"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"16427171479924442928230863465674813919123162824586"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"17866458359124566529476545682848912883142607690042"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"24219022671055626321111109370544217506941658960408"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"07198403850962455444362981230987879927244284909188"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"84580156166097919133875499200524063689912560717606"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"05886116467109405077541002256983155200055935729725"</span><span class="p">);</span>
<span class="n">data</span><span class="p">.</span><span class="n">Append</span><span class="p">(</span><span class="s" style="color: #4070a0;">"71636269561882670428252483600823257530420752963450"</span><span class="p">);</span>
<span class="k" style="color: #007020; font-weight: bold;">const</span> <span class="kt" style="color: #902000;">int</span> <span class="n">aggregation_consecutives</span> <span class="p">=</span> <span class="m" style="color: #40a070;">5</span><span class="p">;</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">// Starting point initialization</span>
<span class="n">var</span> <span class="n">data_string</span> <span class="p">=</span> <span class="n">data</span><span class="p">.</span><span class="n">ToString</span><span class="p">();</span>
<span class="n">var</span> <span class="n">global_max_mul</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="n">var</span> <span class="n">consicutives_so_far</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="n">var</span> <span class="n">local_max_mul</span> <span class="p">=</span> <span class="m" style="color: #40a070;">1</span><span class="p">;</span>
<span class="n">var</span> <span class="n">tail_num</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="n">var</span> <span class="n">current_num</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="p">(</span><span class="kt" style="color: #902000;">int</span> <span class="n">current_char_idx</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span> <span class="n">current_char_idx</span> <span class="p"><</span> <span class="n">data</span><span class="p">.</span><span class="n">Length</span><span class="p">;</span> <span class="n">current_char_idx</span><span class="p">++)</span>
<span class="p">{</span>
<span class="n">current_num</span> <span class="p">=</span> <span class="p">(</span><span class="kt" style="color: #902000;">int</span><span class="p">)</span><span class="n">data_string</span><span class="p">[</span><span class="n">current_char_idx</span><span class="p">]</span> <span class="p">-</span> <span class="sc" style="color: #4070a0;">'0'</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="p">(</span><span class="n">current_num</span> <span class="p">==</span> <span class="m" style="color: #40a070;">0</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">consicutives_so_far</span> <span class="p">=</span> <span class="m" style="color: #40a070;">0</span><span class="p">;</span>
<span class="n">local_max_mul</span> <span class="p">=</span> <span class="m" style="color: #40a070;">1</span><span class="p">;</span>
<span class="k" style="color: #007020; font-weight: bold;">continue</span><span class="p">;</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="p">(</span><span class="n">consicutives_so_far</span> <span class="p"><</span> <span class="n">aggregation_consecutives</span><span class="p">)</span>
<span class="p">{</span>
<span class="n">local_max_mul</span> <span class="p">*=</span> <span class="n">current_num</span><span class="p">;</span>
<span class="n">global_max_mul</span> <span class="p">=</span> <span class="n">Math</span><span class="p">.</span><span class="n">Max</span><span class="p">(</span><span class="n">global_max_mul</span><span class="p">,</span> <span class="n">local_max_mul</span><span class="p">);</span>
<span class="n">consicutives_so_far</span><span class="p">++;</span>
<span class="k" style="color: #007020; font-weight: bold;">continue</span><span class="p">;</span>
<span class="p">}</span>
<span class="n">tail_num</span> <span class="p">=</span> <span class="n">data_string</span><span class="p">[</span><span class="n">current_char_idx</span> <span class="p">-</span> <span class="m" style="color: #40a070;">5</span><span class="p">]</span> <span class="p">-</span> <span class="sc" style="color: #4070a0;">'0'</span><span class="p">;</span>
<span class="n">local_max_mul</span> <span class="p">=</span> <span class="p">(</span><span class="n">local_max_mul</span> <span class="p">/</span> <span class="n">tail_num</span><span class="p">)</span> <span class="p">*</span> <span class="n">current_num</span><span class="p">;</span>
<span class="n">global_max_mul</span> <span class="p">=</span> <span class="n">Math</span><span class="p">.</span><span class="n">Max</span><span class="p">(</span><span class="n">global_max_mul</span><span class="p">,</span> <span class="n">local_max_mul</span><span class="p">);</span>
<span class="n">consicutives_so_far</span><span class="p">++;</span>
<span class="n">Console</span><span class="p">.</span><span class="n">WriteLine</span><span class="p">(</span><span class="kt" style="color: #902000;">string</span><span class="p">.</span><span class="n">Format</span><span class="p">(</span>
<span class="s" style="color: #4070a0;">"current_char_idx:{0}, consicutives_so_far={1}, current_num={2} local_max_mul={3}"</span><span class="p">,</span>
<span class="n">current_char_idx</span><span class="p">,</span> <span class="n">consicutives_so_far</span><span class="p">,</span> <span class="n">current_num</span><span class="p">,</span> <span class="n">local_max_mul</span><span class="p">));</span>
<span class="p">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="n">global_max_mul</span><span class="p">;</span>
<span class="c1" style="color: #60a0b0; font-style: italic;">// Problem8: 40824</span>
<span class="p">}</span></pre></span></b></span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-19376632474303830042011-04-13T12:56:00.000-07:002011-04-14T22:43:07.181-07:00Project Euler - Problem 7 - Tcl<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;">#By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#What is the 10001st prime number?</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem7-v2 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># Much faster.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#REMARK: Based on problem-3</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> primes <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">list</span> <span class="mi" style="color: #40a070;">2</span> <span class="mi" style="color: #40a070;">3</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> current_number <span class="mi" style="color: #40a070;">5</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> primes_found <span class="mi" style="color: #40a070;">2</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> finished FALSE
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="o" style="color: #666666;">!</span><span class="nv" style="color: #bb60d5;">$finished</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> is_prime TRUE
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> prime <span class="nv" style="color: #bb60d5;">$primes</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">$current_number</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$prime</span> <span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> is_prime FALSE
<span class="k" style="color: #007020; font-weight: bold;">break</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$prime</span> <span class="o" style="color: #666666;">></span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$current_number</span> <span class="o" style="color: #666666;">/</span> <span class="nv" style="color: #bb60d5;">2</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># Can't be bigger than factor 2!</span>
<span class="k" style="color: #007020; font-weight: bold;">break</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$is_prime</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">incr</span> primes_found <span class="mi" style="color: #40a070;">1</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> last_prime <span class="nv" style="color: #bb60d5;">$current_number</span>
<span class="nb" style="color: #007020;">lappend</span> primes <span class="nv" style="color: #bb60d5;">$last_prime</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> finished <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$primes_found</span> <span class="o" style="color: #666666;">==</span> <span class="mi" style="color: #40a070;">10001</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="nb" style="color: #007020;">incr</span> current_number <span class="mi" style="color: #40a070;">2</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"solution-7: [lindex $primes end]"</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># solution-7: solution-7: 104743</span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-59077695953877411062011-04-13T11:19:00.001-07:002011-04-14T22:43:32.311-07:00Project Euler - Problem 6 - Tcl<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;">#The sum of the squares of the first ten natural numbers is,</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#1^2 + 2^2 + ... + 10^2 = 385</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#The square of the sum of the first ten natural numbers is,</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#(1 + 2 + ... + 10)^2 = 55^2 = 3025</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 - 385 = 2640.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem6 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> sum_of_squares <span class="mi" style="color: #40a070;">0</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> squares_of_sum <span class="mi" style="color: #40a070;">0</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">set</span> idx <span class="mi" style="color: #40a070;">1</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="o" style="color: #666666;"><=</span> <span class="nv" style="color: #bb60d5;">100</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx<span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> sum_of_squares <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$sum_of_squares</span> <span class="o" style="color: #666666;">+</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$idx</span> <span class="o" style="color: #666666;">*</span> <span class="nv" style="color: #bb60d5;">$idx</span><span class="k" style="color: #007020; font-weight: bold;">)]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> squares_of_sum <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$squares_of_sum</span> <span class="o" style="color: #666666;">+</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> squares_of_sum <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$squares_of_sum</span><span class="o" style="color: #666666;">*</span><span class="nv" style="color: #bb60d5;">$squares_of_sum</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"Solution-6: [expr $squares_of_sum - $sum_of_squares]"</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#Solution-6: 25164150</span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-39189668296264148712011-04-13T10:58:00.000-07:002011-04-14T22:43:46.651-07:00Project Euler - Problem 4 - Tcl<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;">#A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#Find the largest palindrome made from the product of two 3-digit numbers.</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem4 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> palindrom_found FALSE
<span class="k" style="color: #007020; font-weight: bold;">set</span> current_palindrom <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="mi" style="color: #40a070;">999</span><span class="o" style="color: #666666;">*</span><span class="mi" style="color: #40a070;">999</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$palindrom_found</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">FALSE</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> current_palindrom <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nv" style="color: #bb60d5;">next_polindrom</span> <span class="nv" style="color: #bb60d5;">$current_palindrom</span> <span class="o" style="color: #666666;">-</span><span class="mi" style="color: #40a070;">1</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">set</span> idx <span class="mi" style="color: #40a070;">999</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="o" style="color: #666666;">></span> <span class="nv" style="color: #bb60d5;">900</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx <span class="o" style="color: #666666;">-</span><span class="mi" style="color: #40a070;">1</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">$current_palindrom</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span> <span class="o" style="color: #666666;">&&</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$current_palindrom</span> <span class="o" style="color: #666666;">/</span> <span class="nv" style="color: #bb60d5;">$idx</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;"><</span> <span class="mi" style="color: #40a070;">1000</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"$idx*[expr $current_palindrom / $idx]=$current_palindrom"</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> palindrom_found TRUE
<span class="k" style="color: #007020; font-weight: bold;">break</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#****f* math/next_polindrom</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># FUNCTION</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># Generates the next polindrom according to a given polindrom.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># INPUTS</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># pre_polindrom:</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * TBD</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># direction:</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * (+n) - next (n) polindrom up</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * (-n) - next (n) polindrom down</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># RESULT</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * int - The consecutive (n) polinom from the given number/polinom.</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * {} - error with parameters or none found.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># EXAMPLE</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># TBD</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># NOTES</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * Good for solving problem-4. Jumps from 100000 to 9999 (see BUGS).</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># BUGS</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># * Wrong sequance: {... 102201 101101 100001 9999 9889 9779 ... }</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># SYNOPSIS</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> next_polindrom <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">pre_polindrom</span> direction <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># SOURCE</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># E.g. pre_polindrom ==> 123000</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> polindrom_len <span class="k" style="color: #007020; font-weight: bold;">[expr</span> round<span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">ceil</span><span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">log10</span><span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">$pre_polindrom</span> <span class="k" style="color: #007020; font-weight: bold;">)))</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> polindrom_mid_len <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$polindrom_len</span> <span class="o" style="color: #666666;">/</span> <span class="nv" style="color: #bb60d5;">2</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">+</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$polindrom_len</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">2</span><span class="k" style="color: #007020; font-weight: bold;">)]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> digits_to_align <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$polindrom_len</span> <span class="o" style="color: #666666;">-</span> <span class="nv" style="color: #bb60d5;">$polindrom_mid_len</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> polindrom_core <span class="nv" style="color: #bb60d5;">$pre_polindrom</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. polindrom_core ==> 123000</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$digits_to_align</span> <span class="o" style="color: #666666;">></span> <span class="nv" style="color: #bb60d5;">0</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> polindrom_core <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$polindrom_core</span> <span class="o" style="color: #666666;">/</span> <span class="mi" style="color: #40a070;">10</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="nb" style="color: #007020;">incr</span> digits_to_align <span class="o" style="color: #666666;">-</span><span class="mi" style="color: #40a070;">1</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. polindrom_core ==> 123</span>
<span class="nb" style="color: #007020;">incr</span> polindrom_core <span class="nv" style="color: #bb60d5;">$direction</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. (of +1): polindrom_core ==> 124</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> splited_polindrom_core <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">split</span> <span class="nv" style="color: #bb60d5;">$polindrom_core</span> <span class="k" style="color: #007020; font-weight: bold;">{}]</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. splited_polindrom_core ==> {1 2 3}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> splited_reversed_polindrom_core <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">lreverse</span> <span class="nv" style="color: #bb60d5;">$splited_polindrom_core</span><span class="k" style="color: #007020; font-weight: bold;">]</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. splited_reversed_polindrom_core ==> {3 2 1}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> splited_reversed_polindrom_core <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">lrange</span> <span class="nv" style="color: #bb60d5;">$splited_reversed_polindrom_core</span> <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$polindrom_len</span> <span class="o" style="color: #666666;">%</span> <span class="mi" style="color: #40a070;">2</span><span class="k" style="color: #007020; font-weight: bold;">]</span> end<span class="k" style="color: #007020; font-weight: bold;">]</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. for 123000: {3 2 1} ==> {3 2 1}, for 12300: {3 2 1} ==> {2 1}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> reversed_polindrom_core <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">join</span> <span class="nv" style="color: #bb60d5;">$splited_reversed_polindrom_core</span> <span class="k" style="color: #007020; font-weight: bold;">{}]</span> <span class="k" style="color: #007020; font-weight: bold;">;</span> <span class="c" style="color: #60a0b0; font-style: italic;"># E.g. splited_reversed_polindrom_core ==> {321}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> next_polinom <span class="s2" style="color: #4070a0;">"$polindrom_core$reversed_polindrom_core"</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="nv" style="color: #bb60d5;">$next_polinom</span>
<span class="c" style="color: #60a0b0; font-style: italic;">######</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#Solution-4: 993*913=906609</span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-54756731606823057002011-04-10T14:30:00.000-07:002011-04-14T22:44:06.140-07:00Project Euler - Problem 5 - Tcl<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;">#2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem5 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># REMARK: Runs forever :)</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> dividers <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">list</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">set</span> idx <span class="mi" style="color: #40a070;">20</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="o" style="color: #666666;">>=</span> <span class="nv" style="color: #bb60d5;">2</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx <span class="o" style="color: #666666;">-</span><span class="mi" style="color: #40a070;">1</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">lappend</span> dividers <span class="nv" style="color: #bb60d5;">$idx</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> largest_divider <span class="mi" style="color: #40a070;">20</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> divisible FALSE
<span class="k" style="color: #007020; font-weight: bold;">set</span> current_number <span class="mi" style="color: #40a070;">20</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="o" style="color: #666666;">!</span> <span class="nv" style="color: #bb60d5;">$divisible</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">incr</span> current_number <span class="nv" style="color: #bb60d5;">$largest_divider</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> divisible TRUE
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> divider <span class="nv" style="color: #bb60d5;">$dividers</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{(</span> <span class="nv" style="color: #bb60d5;">$current_number</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$divider</span> <span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">!=</span> <span class="nv" style="color: #bb60d5;">0</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> divisible FALSE
<span class="k" style="color: #007020; font-weight: bold;">break</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> divider <span class="nv" style="color: #bb60d5;">$dividers</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"$current_number / $divider = [expr $current_number / $divider] + [expr $current_number % $divider]/$divider"</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="nv" style="color: #bb60d5;">$current_number</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem5-v2 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># REMARK: will get me very fast to the wanted number</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> largest_divider <span class="mi" style="color: #40a070;">1</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> dividers <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">list</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">set</span> idx <span class="mi" style="color: #40a070;">20</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="o" style="color: #666666;">>=</span> <span class="nv" style="color: #bb60d5;">2</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx <span class="o" style="color: #666666;">-</span><span class="mi" style="color: #40a070;">1</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> largest_divider <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$largest_divider</span> <span class="o" style="color: #666666;">*</span> <span class="nv" style="color: #bb60d5;">$idx</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="nb" style="color: #007020;">lappend</span> dividers <span class="nv" style="color: #bb60d5;">$idx</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"largest divider=$largest_divider"</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> divider <span class="nv" style="color: #bb60d5;">$dividers</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{(</span> <span class="nv" style="color: #bb60d5;">$largest_divider</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$divider</span> <span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> largest_divider <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$largest_divider</span> <span class="o" style="color: #666666;">/</span> <span class="nv" style="color: #bb60d5;">$divider</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> largest_divider <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$largest_divider</span> <span class="o" style="color: #666666;">*</span> <span class="nv" style="color: #bb60d5;">$divider</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> divider <span class="nv" style="color: #bb60d5;">$dividers</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"$largest_divider / $divider = [expr $largest_divider / $divider] + [expr $largest_divider % $divider]/$divider"</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="nv" style="color: #bb60d5;">$largest_divider</span> <span class="k" style="color: #007020; font-weight: bold;">;</span><span class="c" style="color: #60a0b0; font-style: italic;"># == 9699690</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem5-v3 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># REMARK: Based on v2, all we need is to correct the results manually.</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> largest_divider <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="mi" style="color: #40a070;">9699690</span><span class="o" style="color: #666666;">*</span><span class="mi" style="color: #40a070;">4</span><span class="o" style="color: #666666;">*</span><span class="mi" style="color: #40a070;">3</span><span class="o" style="color: #666666;">*</span><span class="mi" style="color: #40a070;">2</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> dividers <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">list</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">set</span> idx <span class="mi" style="color: #40a070;">20</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$idx</span> <span class="o" style="color: #666666;">>=</span> <span class="nv" style="color: #bb60d5;">2</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx <span class="o" style="color: #666666;">-</span><span class="mi" style="color: #40a070;">1</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">lappend</span> dividers <span class="nv" style="color: #bb60d5;">$idx</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> divider <span class="nv" style="color: #bb60d5;">$dividers</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">puts</span> <span class="s2" style="color: #4070a0;">"$largest_divider / $divider = [expr $largest_divider / $divider] + [expr $largest_divider % $divider]/$divider"</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># solution-4: 232792560</span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-8836664755994062902011-04-10T13:34:00.000-07:002011-04-14T22:44:12.553-07:00Project Euler - Problem 3 - Tcl<pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="Apple-style-span" style="color: #60a0b0;"><i><span class="Apple-style-span" style="font-family: 'Times New Roman'; font-size: small; white-space: normal;"><pre style="background-color: transparent; border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="Apple-style-span" style="color: black; font-family: 'Times New Roman'; font-size: small; font-style: normal; white-space: normal;"><pre style="background-color: transparent; border-bottom-color: rgb(204, 204, 204); border-bottom-style: none; border-bottom-width: 1px; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-top-width: 1px; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;">#The prime factors of 13195 are 5, 7, 13 and 29.</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#What is the largest prime factor of the number 600851475143 ?</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem3 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> target_number <span class="mi" style="color: #40a070;">600851475143</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> primes <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">list</span> <span class="mi" style="color: #40a070;">2</span> <span class="mi" style="color: #40a070;">3</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> current_number <span class="mi" style="color: #40a070;">5</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># let's speed things up a little...</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> prime <span class="nv" style="color: #bb60d5;">$primes</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">$target_number</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$prime</span> <span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> target_number <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$target_number</span> <span class="o" style="color: #666666;">/</span> <span class="nv" style="color: #bb60d5;">$prime</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> finished FALSE
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="o" style="color: #666666;">!</span><span class="nv" style="color: #bb60d5;">$finished</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> is_prime TRUE
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> prime <span class="nv" style="color: #bb60d5;">$primes</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$current_number</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$prime</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> is_prime FALSE
<span class="k" style="color: #007020; font-weight: bold;">break</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="nv" style="color: #bb60d5;">$is_prime</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> last_prime <span class="nv" style="color: #bb60d5;">$current_number</span>
<span class="nb" style="color: #007020;">lappend</span> primes <span class="nv" style="color: #bb60d5;">$last_prime</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">(</span> <span class="nv" style="color: #bb60d5;">$target_number</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">$last_prime</span> <span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> target_number <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$target_number</span> <span class="o" style="color: #666666;">/</span> <span class="nv" style="color: #bb60d5;">$last_prime</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> finished <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="k" style="color: #007020; font-weight: bold;">(</span><span class="nv" style="color: #bb60d5;">$target_number</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">1</span><span class="k" style="color: #007020; font-weight: bold;">)]</span>
<span class="nb" style="color: #007020;">incr</span> current_number 2
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">lindex</span> <span class="nv" style="color: #bb60d5;">$primes</span> end<span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># solution-3: 6857</span></pre></span></pre></span></i></span></pre>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-26471549600687196502011-04-09T14:26:00.001-07:002011-04-14T22:44:22.081-07:00Project Euler - Problem 2 - Tcl<div class="post-body entry-content" id="post-body-6786485318381586471" style="color: #222222; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 14px; line-height: 1.4; position: relative; width: 520px;"><pre style="background-color: transparent; border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;">#Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</span>
<span class="c" style="color: #60a0b0; font-style: italic;">#By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> problem2 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> term <span class="mi" style="color: #40a070;">2</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> term-1 <span class="mi" style="color: #40a070;">1</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> sum <span class="mi" style="color: #40a070;">0</span>
<span class="k" style="color: #007020; font-weight: bold;">while</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nv" style="color: #bb60d5;">$term</span> <span class="o" style="color: #666666;"><=</span> <span class="nv" style="color: #bb60d5;">4000000</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{(</span><span class="nv" style="color: #bb60d5;">$term</span> <span class="o" style="color: #666666;">%</span> <span class="nv" style="color: #bb60d5;">2</span><span class="k" style="color: #007020; font-weight: bold;">)</span> <span class="o" style="color: #666666;">==</span> <span class="nv" style="color: #bb60d5;">0</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">incr</span> sum <span class="nv" style="color: #bb60d5;">$term</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> tmp <span class="err" style="border-bottom-color: rgb(255, 0, 0); border-bottom-style: solid; border-bottom-width: 1px; border-left-color: rgb(255, 0, 0); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(255, 0, 0); border-right-style: solid; border-right-width: 1px; border-top-color: rgb(255, 0, 0); border-top-style: solid; border-top-width: 1px;">$</span><span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nv" style="color: #bb60d5;">term-1</span><span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> term-1 <span class="nv" style="color: #bb60d5;">$term</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> term <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$term</span> <span class="o" style="color: #666666;">+</span> <span class="nv" style="color: #bb60d5;">$tmp</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">return</span> <span class="nv" style="color: #bb60d5;">$sum</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># solution-2: 4613732</span></pre></div>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0tag:blogger.com,1999:blog-346534647827369012.post-22514810363531767562011-04-09T14:25:00.001-07:002011-04-14T22:44:28.257-07:00Project Euler - Problem 1 - Tcl<div class="post-body entry-content" id="post-body-2337261887373605256" style="color: #222222; font-family: Arial, Tahoma, Helvetica, FreeSans, sans-serif; font-size: 14px; line-height: 1.4; position: relative; width: 520px;"><pre style="background-color: transparent; border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="c" style="color: #60a0b0; font-style: italic;"># If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># Find the sum of all the multiples of 3 or 5 below 1000.</span>
<span class="k" style="color: #007020; font-weight: bold;">proc</span> Problem1 <span class="k" style="color: #007020; font-weight: bold;">{}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> items <span class="k" style="color: #007020; font-weight: bold;">{}</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{set</span> idx <span class="mi" style="color: #40a070;">3</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nv" style="color: #bb60d5;">$idx</span><span class="o" style="color: #666666;"><</span><span class="nv" style="color: #bb60d5;">1000</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx <span class="mi" style="color: #40a070;">3</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">lappend</span> items <span class="nv" style="color: #bb60d5;">$idx</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">for</span> <span class="k" style="color: #007020; font-weight: bold;">{set</span> idx <span class="mi" style="color: #40a070;">5</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nv" style="color: #bb60d5;">$idx</span><span class="o" style="color: #666666;"><</span><span class="nv" style="color: #bb60d5;">1000</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span><span class="nb" style="color: #007020;">incr</span> idx <span class="mi" style="color: #40a070;">5</span><span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">if</span> <span class="k" style="color: #007020; font-weight: bold;">{</span> <span class="k" style="color: #007020; font-weight: bold;">[</span><span class="nb" style="color: #007020;">lsearch</span> <span class="nv" style="color: #bb60d5;">$items</span> <span class="nv" style="color: #bb60d5;">$idx</span><span class="k" style="color: #007020; font-weight: bold;">]</span> <span class="o" style="color: #666666;"><</span> <span class="nv" style="color: #bb60d5;">0</span> <span class="k" style="color: #007020; font-weight: bold;">}</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="nb" style="color: #007020;">lappend</span> items <span class="nv" style="color: #bb60d5;">$idx</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> rval <span class="mi" style="color: #40a070;">0</span>
<span class="k" style="color: #007020; font-weight: bold;">foreach</span> item <span class="nv" style="color: #bb60d5;">$items</span> <span class="k" style="color: #007020; font-weight: bold;">{</span>
<span class="k" style="color: #007020; font-weight: bold;">set</span> rval <span class="k" style="color: #007020; font-weight: bold;">[expr</span> <span class="nv" style="color: #bb60d5;">$rval</span> <span class="o" style="color: #666666;">+</span> <span class="nv" style="color: #bb60d5;">$item</span><span class="k" style="color: #007020; font-weight: bold;">]</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
</pre><pre style="background-color: transparent; border-bottom-style: none; border-color: initial; border-left-style: none; border-right-style: none; border-top-color: rgb(204, 204, 204); border-top-style: none; border-width: initial; font-family: 'Bitstream Vera Sans Mono', monospace; font-size: 13px; margin-bottom: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; overflow-x: auto; overflow-y: auto; padding-bottom: 10px; padding-left: 10px; padding-right: 10px; padding-top: 10px;"><span class="k" style="color: #007020; font-weight: bold;"><span class="Apple-style-span" style="color: black; font-weight: normal;"> </span>return</span> <span class="nv" style="color: #bb60d5;">$rval</span>
<span class="k" style="color: #007020; font-weight: bold;">}</span>
<span class="c" style="color: #60a0b0; font-style: italic;"># solution: 233168</span></pre></div>Shlomi O.http://www.blogger.com/profile/09905484986732700707noreply@blogger.com0