tag:blogger.com,1999:blog-43410139275208121022018-03-06T22:45:43.948+00:00dragozov.com.: here be dragonz :.Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-4341013927520812102.post-45800829251586110342012-08-07T21:29:00.000+01:002012-08-07T21:29:13.991+01:00Running for 2012I started my own <a href="http://www.ryesoft.com/">company</a> in January, which means I'll be very busy (at least for a while). I'm only doing the <a href="http://www.venicemarathon.it/">Venice marathon</a> this year and it's more of a way to get a nice break with my wife.<br />Of course I'm still very serious about running and do at least 50-60 km per week, but preparing and planning for an event seems like way too much work at this stage.Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0tag:blogger.com,1999:blog-4341013927520812102.post-64560156839522137862011-06-12T12:47:00.003+01:002012-08-07T21:10:36.947+01:002011 marathonsMy plan is to run 4 full marathons in 2011. I already did <a href="http://www.connemarathon.com/">Connemara</a> in April (4:01h) and have finally decided on the other 3:<br />1. The <a href="http://www.galwaycitymarathon.com/">Galway City Marathon</a> on 28th August (Update: cancelled)<br />2. The <a href="http://dublinmarathon.ie/">Dublin Marathon</a> on 31st October (Update: finished in 3:52h)<br />3. The <a href="http://runclon.ie/">Clonakilty Waterfront Marathon</a> on 10th December (Update: finished in 4:10h, it was really cold and hilly!)<br /><br />Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0tag:blogger.com,1999:blog-4341013927520812102.post-54250396731655016782011-06-08T00:11:00.005+01:002011-06-08T01:32:26.266+01:00The Last LectureWhat better topic for my first "daily note" than <a href="http://www.youtube.com/watch?v=ji5_MqicxSo">"The Last Lecture"</a> of Prof. Randy Pausch? I happened to watch it for 3rd or 4th time this Saturday and it's still one of the most inspiring talks you could find online. <br /><br />It's not so much about what he says. Most of it has been said before. <br />But the fact that he is a dying man with nothing to gain, makes it all sound so real and honest that it hurts. <br /><br />And it's totally amazing how you finish watching a little sad, but also smiling and full of energy and love for life. And even if you cried (I guess most people do) you've also laughed a lot. A cocktail of feelings that will stick in your brain for days.Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0tag:blogger.com,1999:blog-4341013927520812102.post-26896658957797302102011-04-08T16:30:00.003+01:002011-04-08T16:49:43.822+01:00ConnemarathonI'm running in the 2011 <a href="http://www.connemarathon.com/">Connemara marathon</a> this Sunday (10th April). <br />It's supposed to be the most scenic but also the hardest in Ireland. And I'm also running in Vibram FiveFingers so should be fun :)<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://2.bp.blogspot.com/-tA79cI3kYl8/TZ8r5NUsh_I/AAAAAAAAALQ/Ev2RhdStzNo/s1600/bikila.jpg"><img style="cursor:pointer; cursor:hand;width: 320px; height: 239px;" src="http://2.bp.blogspot.com/-tA79cI3kYl8/TZ8r5NUsh_I/AAAAAAAAALQ/Ev2RhdStzNo/s320/bikila.jpg" border="0" alt="Vibram FiveFingers" id="BLOGGER_PHOTO_ID_5593237524046448626" /></a>Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0tag:blogger.com,1999:blog-4341013927520812102.post-5906000207477496392010-08-01T22:09:00.007+01:002010-08-02T16:21:44.347+01:00Treaps in Erlang<p>After a few months break I'm back to working on a project written mainly in <a href="http://www.erlang.org">Erlang</a> and I'll be posting the most interesting pieces online to a small open-source project at Google Code, <a href="http://code.google.com/p/erlaz">ErlAZ</a> - Erlang A to Z.<br/>The first module I'm uploading is an implementation of the <a href="http://en.wikipedia.org/wiki/Treap">Treap</a> data structure.</p><p>What is a Treap?<br/>It's a binary search tree where each node, in addition to its key and value, contains a number, called priority, assigned to it at insertion time.<br/>All nodes are sorted horizontally by their key (so that a greater key is always to the right of a smaller one) and vertically by their priority (so that all parents of any given node up to the root have a higher priority than the node).<br/>By choosing the priorities uniformly distributed across all keys (for example randomly), in the long run the treap will have the characteristic of a well-balanced tree, without having to re-balance it periodically.</p><p>I implemented my version as a drop-in replacement for the <a href="http://www.erlang.org/doc/man/dict.html">dict</a> module, with all the <em>dict</em> functions having exactly the same signiture and behaviour, but working on treaps and performing according to the underlying tree structure vs. the hashtable used in <em>dict</em>.<br/>There are also a few additional functions that use the ordered nature of the tree to allow querying and iterating over the keys in a sorted manner (which is pretty much the point of using a treap anyway), as well as functions for splitting the treap in two by a key (the first sub-treap contains all nodes with keys less or equal to the given key and the second - all nodes with greater keys) and for merging back a splitted treap.</p><p>The <em>treap</em> module comes with well documented functions and an extensive EUnit test suit (in a separate module treap_test), which contains tests and examples for the usage of each function.<br/>As always all the code I release is covered by the <a href="http://www.opensource.org/licenses/bsd-license.php">New BSD License</a> unless stated otherwise.<br/>This means you are free to use it in any way you like, so help yourself:<br/><br /><ul><li><a href="http://code.google.com/p/erlaz/source/browse/#svn/trunk">ErlAZ trunk</a> - The ErlAZ project's root with the Makefile for building the code and its documentation.</li><br /><li><a href="http://code.google.com/p/erlaz/source/browse/trunk/src/treap.erl ">treap.erl</a> - The <em>treap</em> module.</li><br /><li><a href="http://code.google.com/p/erlaz/source/browse/trunk/src/treap.erl ">treap_test.erl</a> - The <em>treap_test</em> module with all the EUnit tests. </li><br /></ul><br /></p>Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0tag:blogger.com,1999:blog-4341013927520812102.post-62236417267808118022009-12-27T15:18:00.000+00:002009-12-27T15:18:54.888+00:00Diving into Erlang with Project Euler, Part 1<h2>Project who?</h2><a href="http://projecteuler.net/">Project Euler</a> is probably the largest (270 problems as of December 2009) and best collection of brainteasers specifically designed for programmers. Unlike other puzzles they are not only fun and challenging, but also help you discover and develop new patterns and programming techniques. I'm a big fan of similar computational mind-benders and use them both in job interviews to see how a candidate approaches a real problem and as a way to balance the boring work that's frequently necessary for even the most interesting projects.<br />I've been solving 1-2 problems every day and after completing number 25 today I got a nice message:<br /><br /><span style="font-style: italic;">"Bravo, dragozov! Now that you have solved 25 problems you have achieved what 80.04% of members have failed to do and have advanced to level 1. Good luck as you continue."</span><br /><br />So I thought I'd describe my experience, especially considering that I'm using <a href="http://erlang.org/">Erlang</a>, a language that I'm currently trying to master and which could use a little more sample code and demos online.<br /><h2>Why Erlang?</h2>I'm working on a small side project and one of the decisions I made was to focus on learning new things and exploring technologies and problems that I find interesting, but are not useful or relevant to my day job. So I'm developing everything as a combination of Erlang and Python.<br />Of course I have more pragmatic reasons. Erlang's unique features make lots of sense for some parts of my app and the two languages complement each other quite well. I also wanted to experiment a little more with functional programming and I find the mental shift required to code in Erlang quite enjoyable. I guess the recent hype around the language played its role too.<br />Anyway I've been studying Erlang and OTP (the open source platform behind it) and use any chance to apply my new skills, so Project Euler was too good of an opportunity to miss.<br /><h2>The Idea</h2>In this and the follow-up articles I'm showing how to use Erlang to solve computational problems. As I advance from the simpler questions to the harder ones, I'll try to also move from the language's basics to more advanced topics.<br />However this is not an introduction and I won't be explaining the syntax. There are a few good online tutorials and an excellent <a href="http://www.amazon.com/Programming-Erlang-Software-Concurrent-World/dp/193435600X">book</a>, so you might want to check them first.<br />On the other hand I'll point out Erlang specific features and techniques and discuss their usage. I also keep the solutions as self-contained as possible, so in some cases there might be code implementing functionality that is already available in the standard libraries or functions copied between the modules. <br />I've tried to find the best solutions I could think of and optimize the code as much as possible, but I haven't searched the Internet or checked the forums, so there might be better/faster algorithms. There is rarely a single correct way of doing things in programming and this is not an exception. <br />I'll keep all solution sources in a Google Code project called <a href="http://code.google.com/p/eulerl/">Eulerl</a>. The license is BSD, if you care, so you are free to use them for anything you like.<br /><h2>Level 1 (first 25 problems)</h2><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=1" target="_blank">Problem 1</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p1.erl" target="_blank">Solution</a></div><div class="problem_c">This one is really easy, it just sums two arithmetic progressions, for which the formula is like this:<br /><span style="font-weight:bold;">SumM = 1*M + 2*M + ...+ K*M = M*(1+2+...K)=M*(K*(K+1)/2)</span><br />We add the sums of the multiples of 3 and 5 and subtract the sum of the multiples of 15 as they were added twice.<br />Not much to be seen here, just 2 simple function declarations and the use of the <span style="font-weight: bold;">div</span> operator for integer division.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=2" target="_blank">Problem 2</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p2.erl" target="_blank">Solution</a></div><div class="problem_c">Here we implement a function that iterates through the Fibonacci numbers and sums the even ones.<br />Although it's still a very simple problem, things get a little more interesting.<br />First we have an example of a tail-recursion, the most common (and efficient) way of implementing iterations in Erlang. I use the function's arguments, including an accumulator (a very common pattern for keeping track of the result) to keep the recursion's state between subsequent calls. At each step of the iteration the function receives the complete information and returns the whole result.<br />The code also demonstrates some basic usage of pattern matching and guard expressions. Although they don't make a big difference here, they can make the code for an algorithm shorter and more readable (my personal opinion, of course).</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=3" target="_blank">Problem 3</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p3.erl" target="_blank">Solution</a></div><div class="problem_c">To find the prime factors of a number N iterate from 2 to N/2 checking if N is divisible by the current number. At each iteration collect the factor if testing positive and replace the number tested with the result of the division or, if negative, increment the factor to be tested.<br />Similarly to problem 3 I use tail-recursion and pattern matching to code the solution. Note the <span style="font-weight: bold;">rem</span> operator, which is Erlang's operator for modulo (the remainder of the division of one number by another).</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=4" target="_blank">Problem 4</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p4.erl" target="_blank">Solution</a></div><div class="problem_c">Problem 4 is the first where the solution requires some more coding (at least the solution that I came up with). A palindrome is a number that reads the same both ways. We can generate all palindromes of length 2*N and 2*N - 1 from the numbers with N digits. For example 123321 and 12321 can both be generated from 123.<br />So to solve the problem I iterate backwards starting with 999 and ending with 100, generate all 6 and 5 digit palindromes and return the first that is a product of two 3 digit numbers.<br />On the Erlang side the most interesting is the use of functions as first-class elements of the language. You can see them passed as arguments to other functions and assigned to local variables.<br />Also note the syntax for declaring anonymous (fun) functions and how they have access to the enclosing context (the arguments of the <span style="font-weight: bold;">factor/3</span> function for example). One of the quirks of an anonymous function in Erlang is that it can't call itself directly, so to implement recursion I pass the function as one of its own arguments (Funself is my naming convention, not a rule).<br />The <span style="font-weight: bold;">palindrom_iterator</span> function is interesting for a few reasons.<br />First it shows a common approach in functional programming. It defines some generic functionality and lets you change the behavior later by accepting a function as one of its arguments. In this case <span style="font-weight: bold;">palindrom_iterator</span> iterates through the palindromes and applies the function to each one. Then based on the result it either returns it or continues with the next palindrome.<br />Second it demonstrates how pattern matching can simplify complex logic. In this case the function iterates through all palindromes bellow a given size (although its not strictly a requirement for the solution). For example if we start with length 6, then we'll iterate through lengths 5, 4, 3 and 2. As it uses numbers half the length to generate the palindromes, there are two cases when it reaches the lowest number of a given length. If it was generating even length numbers, we need to run the same iteration but for odd length palindromes, else we need to reduce the length of the "template" numbers and switch to even palindromes. This is all encoded in only 4 lines at the 2nd and 3rd patterns of the function's declaration.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=5" target="_blank">Problem 5</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p5.erl" target="_blank">Solution</a></div><div class="problem_c">To find the smallest number that is divided by every number in a list we need to collect the prime factors of all numbers in the list, then multiply them raised by their maximum powers. For example if we have 6, 8 and 18, all prime factors are 2 and 3 (6 = 2*3, 8 = 2<sup>3</sup> and 18 = 2*(3<sup>2</sup>)) with maximum powers 3 and 2 respectively. So the solution would be (2<sup>3</sup>)*(3<sup>2</sup>)=72.<br />There are a few new concepts introduced in the Erlang code:<br />- The use of a look-up table (in the max_count functions) implemented using the <a href="http://www.erlang.org/doc/man/ets.html">ets</a> module, an efficient library for storage and access of data in a table form.<br />- List comprehensions (in the solution/1 method), Erlang's syntax for "functional" creation of lists.<br />- The syntax for splitting a list into a "head" element and a "tail" sublist or constructing a list in a similar fashion ([H|T] = List and List = [H|T]).<br />- The <a href="http://www.erlang.org/doc/man/lists.html">lists</a> module, one of the most used standard libraries.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=6" target="_blank">Problem 6</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p6.erl" target="_blank">Solution</a></div><div class="problem_c">The square of a sum can be written as:<br /><span style="font-weight:bold;">(a+b+c +c...+y+z)<sup>2</sup> = a<sup>2</sup>+b<sup>2</sup>+c<sup>2</sup>...+y<sup>2</sup> + z<sup>2</sup> + 2*a*b + 2*a*c...+2*a*y+2*a*z + 2*b*c + ...+ 2*b*z + ...2*y*z</span><br />so:<br /><span style="font-weight:bold;">(a+b+c+...+y+z)<sup>2</sup> - (a<sup>2</sup> + b<sup>2</sup> + c<sup>2</sup> +...+ y<sup>2</sup> + z<sup>2</sup>) = 2*(a*(b+c+...+y+z) + b*(c+...+y+z) + ...+y*z)<br /></span><br />The actual implementation is another example of a tail-recursive function, where the state of the computation is kept in the function's arguments. </div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=7" target="_blank">Problem 7</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p7.erl" target="_blank">Solution</a></div><div class="problem_c">To solve this I implement a simple check for primality where I keep a list of all prime numbers found until now and test new candidates against the list.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=8" target="_blank">Problem 8</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p8.erl" target="_blank">Solution</a></div><div class="problem_c">Iterate through the digits, keeping a first-in-last-out list of the last N digits and check if their product is the maximum until now.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=9" target="_blank">Problem 9</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p9.erl" target="_blank">Solution</a></div><div class="problem_c">The solution is an example of a nested iteration. We have 2 conditions:<br />(1) <span style="font-weight:bold;">A<sup>2</sup> + B<sup>2</sup> = C<sup>2</sup> </span><br />(2) <span style="font-weight:bold;">A + B + C = N</span><br />If we postulate that A is the smallest and C the biggest number, we can extract two additional constraints:<br />(3) <span style="font-weight:bold;">A < N/3</span><br />(4) <span style="font-weight:bold;">B < N/2 </span><br />I run an iteration through all possible A, for each run another nested iteration through all possible B and check if the resulting triplet {A, B, C} meets all the conditions and constraints (1,2,3 and 4).<br />The code also demonstrates the use of tuples to return and unpack multiples values as a result of a function.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=10" target="_blank">Problem 10</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p10.erl" target="_blank">Solution</a></div><div class="problem_c">Similar to problem 7, solved with a simple primality check and a tail-recursive iteration until we've collected the sum of the first N primes.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=11" target="_blank">Problem 11</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p11.erl" target="_blank">Solution</a></div><div class="problem_c">My solution is to generate all possible subsquares of a given size, calculate all the different products of each subsqare (4 horizontal, 4 vertical and 2 diagonals in this case) and find the maximum one.<br />The code introduces the <a href="http://www.erlang.org/doc/man/array.html">array</a> module, providing functions for working with arrays in Erlang (0 based unlike most other data structures). It's also an example of extensive use of anonymous (lambda) functions to simplify the implementation of complex logic.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=12" target="_blank">Problem 12</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p12.erl" target="_blank">Solution</a></div><div class="problem_c">The N-th triangular number is equal to the sum of a simple arithmetic progression:<br />(1) <span style="font-weight:bold;">Tn = n*(n+1)/2</span><br />n and n-1 can be written as products of prime factors:<br />(2) <span style="font-weight:bold;">n = 2<sup>p2</sup>*3<sup>p3</sup>...*N<sup>pN</sup></span><br />(3) <span style="font-weight:bold;">n+1 = 2<sup>q2</sup>*3<sup>q3</sup>...*M<sup>pM</sup></span><br />so Tn:<br />(4) <span style="font-weight:bold;">Tn = 2<sup>(p2 + q2 - 1)</sup>*3<sup>(p3 + q3)</sup>*...*K<sup>(pK+qK)</sup></span>, K is the max of M and N and pi,qi >= 0<br />If the prime factors of x are:<br />(5) <span style="font-weight:bold;">x = 2<sup>s2</sup>*3<sup>s3</sup>*...*L<sup>sL</sup></span><br />then all possible divisors of x have the form:<br />(6) <span style="font-weight:bold;">D = 2<sup>t2</sup>*3<sup>t3</sup>*...*L<sup>tL</sup></span>, where 0 <= ti <= si<br />So the total number of unique divisors of x is:<br />(7) <span style="font-weight:bold;">Divisors(x) = (s2 + 1)*(s3+1)*...*(sL+1)</span>, adding 1 for the case where ti = 0 (see 6 above)<br />From 4 and 7:<br />(8) <span style="font-weight:bold;">Divisors(Tn) = (p2 + q2)*(p3+q3+1)*...*(pk+qK+1)</span><br />First I implement a method that returns all the prime factors and their powers. Then I iterate through the triangular numbers and calculate expression 8 for each until I finds the first that meets the problem's condition. <br />The code is another example of a recursive function, with the optimization of reusing (through the function's arguments) the calculated factors and their powers for each number in two consecutive calls, as the (n+1) in one triangular number is the n in the next.<br /></div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=13" target="_blank">Problem 13</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p13.erl" target="_blank">Solution</a></div><div class="problem_c">Yet another example of a recursive function and the use of pattern matching to implement a solution. Just sum the digits from right to left, keeping the addition carry in the function's arguments and storing the resulting digits in an "accumulator" list.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=14" target="_blank">Problem 14</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p14.erl" target="_blank">Solution</a></div><div class="problem_c">My solution is to iterate through all numbers bellow 1 Million and calculate their chain lengths, but using a look-up table to reuse the results in longer chains that contain previously computed shorter ones.<br /></div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=15" target="_blank">Problem 15</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p15.erl" target="_blank">Solution</a></div><div class="problem_c">An N x N grid, contains (N+1)x(N+1) nodes. The number of paths from a node to the bottom-right corner is equal to the sum of the number of paths from its right and bottom neighbor nodes (if they exist). As some nodes have to be counted multiple times a look-up table is used (the <a href="http://www.erlang.org/doc/man/ets.html">ets</a> module to the rescue again).</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=16" target="_blank">Problem 16</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p16.erl" target="_blank">Solution</a></div><div class="problem_c">I implement a function that takes a number as a list of its digits and returns a list of the digits of the number multiplied by 2. Then getting the digits of any power of 2 means, starting with 1 (2<sup>0</sup>), repeatedly calling the function with the result of its previous call. Nothing much else to be seen here.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=17" target="_blank">Problem 17</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p17.erl" target="_blank">Solution</a></div><div class="problem_c">This is an example of using Erlang's pattern matching syntax to implement a set of facts. The solution then uses these facts to iterate through all numbers and calculate the sum.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=18" target="_blank">Problem 18</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p18.erl" target="_blank">Solution</a></div><div class="problem_c">To solve this problem I'm building a tree-like data structure with Erlang (it's not a real tree as each node except the root has two parents). <br />Every node is represented by a tuple of four items. First the value of the node itself, then the tuples of the left and right children (or empty tuples if it's the bottom row) and then the "weight" of the node - the sum of the its value with the maximum weight of its children (as a matter of fact we only need to keep the weights). Building the tree from the bottom up gives the solution as the weight of its root.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=19" target="_blank">Problem 19</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p19.erl" target="_blank">Solution</a></div><div class="problem_c">Another example of using pattern matching to encode the facts of the problem. Then iterate through all the 1-st days of the months of the 20th century's years and check if they were Sundays.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=20" target="_blank">Problem 20</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p20.erl" target="_blank">Solution</a></div><div class="problem_c">Very similar to problem 16, but this time I implement a method that multiplies an arbitrary number to another and returns the result as a list of its digits.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=21" target="_blank">Problem 21</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p21.erl" target="_blank">Solution</a></div><div class="problem_c">From the expression for an arbitrary divisor of a number (problem 12, formula 6) we can calculate the sum of all possible divisors:<br />(1) <span style="font-weight:bold;">DivisorsSum(x) = (p2<sup>0</sup> +p2<sup>1</sup> +...+p2<sup>k2</sup>)*(p3<sup>0</sup> +p3<sup>1</sup> +...+p3<sup>k3</sup>)*...(pN<sup>0</sup> +pN<sup>1</sup> +...+pN<sup>kN</sup>)</span>, where k2,k3, ...kN are the powers of each prime factor of x<br />Using this we can iterate through all numbers and check if they are amicable and meet the other conditions of the problem, then sum them into the result.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=22" target="_blank">Problem 22</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p22.erl" target="_blank">Solution</a></div><div class="problem_c">The solution is very straightforward on a technical level.<br />However the code introduces some important libraries and concepts:<br />- Working with files is usually done using the <a href="http://www.erlang.org/doc/man/file.html">file</a> module (and a few others usually prefixed with file_).<br />- The binary syntax and the pattern matching are a very powerful combination frequently used as a replacement for the standard (and somewhat limited) representation of strings as lists of integers. They make it really easy to parse and construct streams of bytes, while keeping the code short and readable. A personal favorite of mine.<br />I could have probably used standard libraries for a few of the functions, but chose to implement them myself:<br />- The qsort function demonstrates a very cool (but not optimal) one-line implementation of the QSort algorithm using list comprehensions, guard expressions and recursion.<br />- The a2i function demonstrates the syntax for retrieving the integer value of a character by prefixing it with a '$'.<br />- The split function demonstrates the binary syntax as discussed above.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=23" target="_blank">Problem 23</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p23.erl" target="_blank">Solution</a></div><div class="problem_c">The sum of all numbers that CAN'T be represented as a sum of 2 abundant ones in a given range is equal to the sum of all numbers in the range minus the sum of the numbers that CAN be represented like this:<br />(1)<span style="font-weight:bold;"> SumNA(Max) = Sum(Max) - SumA(Max) = Max*(Max + 1) /2 - SumA(Max)</span><br />If we know all abundant numbers in the range their sum can be calculated like this:<br />(2) <span style="font-weight:bold;">SumA(Max) = (2*A1 + 2*A2 + ...+ 2*AN + (A1 + A2) + (A1 + A3) + ...+ (A1+AN) + (A2+A3) +...)</span>, where A1,...,AN are all abundant numbers bellow Max<br />So my solution is to iterate through all numbers in the range, check if they are abundant and update their sum according to formula 2 above. Then the solution is computed using formula 1.<br />The code is a combination of previous techniques, so nothing much to be explained.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=24" target="_blank">Problem 24</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p24.erl" target="_blank">Solution</a></div><div class="problem_c">Basic combinatorics. The number of permutations of N unique items is N!. Using this I compute every digit of the I-th permutation noting that the digit at position P changes at every (P-1)! permutations.</div></div><br /><div class="problem"><div class="problem_h"><a href="http://projecteuler.net/index.php?section=problems&id=25" target="_blank">Problem 25</a></div><div class="problem_s"><a href="http://code.google.com/p/eulerl/source/browse/trunk/p25.erl" target="_blank">Solution</a></div><div class="problem_c">Another Fibonacci numbers problem solved with a tail recursive iteration until the problem's conditions are met.</div></div><br /><h2>Conclusion of Level 1</h2>This was the first post about my experience as I move through the problems. It's a demonstration of the sequential style of programming in Erlang. In the future I intend to focus on the parallel and distributed concepts of the language, which is what makes it so different. I hope that the problems will get a little harder and less repetitive so that I'll be also able to introduce and experiment a little more with the OTP modules.<br /><h2>Links</h2><a href="http://projecteuler.net/">http://projecteuler.net/</a> - the home page of Project Euler.<br /><a href="http://erlang.org/">http://erlang.org/</a> - the home page of the language.<br /><a href="http://code.google.com/p/eulerl/">http://code.google.com/p/eulerl/</a> - my project at Google Code, where I keep all the sources.Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com6tag:blogger.com,1999:blog-4341013927520812102.post-71359004260116150702009-12-13T22:34:00.004+00:002009-12-14T00:05:26.203+00:00Random Subset of CombinationsI was solving an interesting problem today and thought I'd write about it and post some nice code.<br />Imagine you have a list of fields with a discrete set of possible values each. Example:<br /><pre class="brush:xml;wrap-lines: false; gutter: false"><br /><person><br /> <name>one of [John, Paul, Marie, ….]</name><br /> <surname>one of [Turner, Conner, Lennon…]</surname><br /> <date_of_birth>a date between 01 January and 31 December</date_of_birth><br /> <nationality>one of [USA, Canada, Germany, France...]</nationality><br /></person><br /></pre><br />The number of possible combinations is equal to the multiplication of the number of possible values for each field and grows very fast.<br />So now imagine that you want a way to randomly generate a small number of combinations, where there are no repetitions (like 100 random, unique people from the example above) and you want it done in an optimal way.<br />My solution (I have the source in Python so don't freak out from my attempt at explaining):<br />1. Map every combination to an integer in the range between 0 and the total number of combinations (so the first possible person has id of 0 and the last one has id of TOTAL - 1).<br />2. Generating a random combination is equivalent to generating a random id between 0 and TOTAL - 1 and then building the corresponding combination. <br />3. The mapping is done by representing the combinations as points in a multidimensional space using each field as a dimension. The index of the value of the field in the set of all possible value is the coordinate in this dimension.<br />4. Lets say that we have N fields each with a list of possible values, L1, …, LN and sizes Size1, …, SizeN.<br />The number of all combinations in a space is the multiplication of all the sizes:<br />TOTAL = Size1*Size2…*SizeN<br />5. If we remove the Nth field we are left with a space with a lower dimension and a total of:<br />TotalN-1 = Size1*Size2*…SizeN-1<br />We can call this the Subtotal of N or SubN. With some calculations it's clear that<br />SubN = SizeN-1*SubN-1<br />and we set Sub1 = 1<br />6. Lets name the index of the value of the i-th field of a combination Xi. Then the id of a combination can be calculated like this:<br />ID = XN*SubN + XN-1*SubN-1 + …+ X1 * Sub1<br />7. If we have the ID we can calculate X1, …XN like this:<br />XN = ID/SubN (/ is integer division, i.e we ignore the remainder)<br />XN-1 = (ID % SubN)/SubN-1 (% is modulo i.e. the remainder of the division)<br />…<br />X1 = ((ID % SubN)%SubN-1)…%Sub2<br />8. So this gives us a way to quickly generate a random combination, but still doesn't solve the initial problem of getting a whole subset of non-repeating, random combinations. <br />This is equivalent to generating a list of random, non-repeating numbers in the range 0 - (TOTAL - 1).<br />9. I wasn't sure if this can be done optimally, but after some reading (<a href="http://www.techuser.net/randpermgen.html">Great article on k-permutations</a>) it seemed that there is a very efficient algorithm. <br />For a subset of size K from N numbers it is possible to do it in O(K) both for space and speed. After I implemented the algorithm I found out that Python has a method that can do this (random.sample) so I'm using it in my code, but my implementation is also there (shuffle_range) if you need to do it in a different language or would like to appreciate how short and beautiful it is ;-)<br />10. The idea of the algorithm is to take all the numbers from 1 to N (bare with me, it gets optimized later) and shuffle them. Then get the first K numbers and throw the rest.<br />The shuffling is done by putting the numbers in a big array, iterating through them and for each position generating a random number between 0 and n-1 then swapping the value at the current position with the value at the random position.<br />The optimization that I mention allows this to be reduced from an O(N) to an O(K) algorithm both for space and speed.<br />Instead of creating an array of size N we use a hash table with the rule that if the table contains a value for a position this is the value at that position, else the value is equal to the index of the position. Then we only iterate from 0 to K-1 and generate the result using the above rule.<br /><br />And after this long explanation, which will either put you to sleep or make you have nightmares in the next few nights, here is the source code, which I hope will clarify things a bit:<br /><pre class="brush:python;wrap-lines: false; gutter: false"><br />"""Generation of a random subset of all possible combinations for a list<br />of list of options.<br /><br />This code is released in the public domain, meaning it is free for any<br />use.<br />2009 Plamen Dragozov<br />"""<br />import random<br /><br />class Combinator(object):<br /> """Manages a list of lists and generates combinations of the elements of these lists.<br /> """<br /> def __init__(self, lists):<br /> """Initialize with the given lists and pre-calculate the subtotals.<br /><br /> Subtotals are the number of combinations of all lists without the last one,<br /> so subtotal3 is equal to Size2*Size1.<br /> Total is the number of all possible combinations.<br /> """<br /> subtotals = [] <br /> total = 1<br /> for l in lists:<br /> subtotals.append(total)<br /> total = total * len(l)<br /> <br /> self.total = total<br /> self.lists = lists<br /> self.subtotals = subtotals<br /> <br /> def combination(self, n):<br /> """ A combination is a list where the element at position 'i' is one of the elements in list 'i'.<br /><br /> All possible combinations (with a count of Total) can be mapped to the first Total integers.<br /> This method returns the n-th combination, calculating all element indices in the lists.<br /> """<br /> result = []<br /> for i in range(len(self.lists) - 1, -1, -1):#iterate backwards, from the last to the 1st<br /> subtotal = self.subtotals[i]<br /> pos = n / subtotal<br /> result.append(self.lists[i][pos])<br /> n = n % subtotal<br /> result.reverse()<br /> return result<br /><br /> def random(self, count):<br /> """Generate 'count' random combinations without repetition.<br /> """<br /> ids = random.sample(xrange(self.total), min(count, self.total))<br /> return [self.combination(i) for i in ids]<br /> <br />def shuffle_range(n, k = None):<br /> """Creates a random sub-permutation of size k for the first n integers.<br /><br /> This is pretty much equivalent to random.sample.<br /> """<br /> if (not k) or (k > n):<br /> k = n<br /> hashT = {}<br /> for i in xrange(k):<br /> j = random.randint(0, n - 1)<br /> #swap whats at i with what's at j and vice versa<br /> hashT[i], hashT[j] = hashT.get(j, j), hashT.get(i, i)<br /><br /> return [hashT.get(i, i) for i in xrange(k)]<br /><br /></pre>Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0tag:blogger.com,1999:blog-4341013927520812102.post-5928649790099824292009-10-25T13:36:00.009+00:002009-10-25T17:50:25.727+00:00Hit testing for arbitrary paths on the iPhone<p>I'm doing something cool for the iPhone. Can't tell yet, but I'll be posting hacks and interesting code as I go.<br />For the first one all credit goes to Graham Cox of <a href="http://apptree.net/drawkitmain.htm">DrawKit</a> (an awesome open-source project). I just ported his idea to the iPhone and tweaked it to match my problem.</p><p>I've been working on an algorithm for detecting a finger touch over a random, complex path. It was quickly clear that it's not a trivial problem and my requirement for the path to have a stroke (border) of significant width made it even harder. <br />So I was searching and reading forums and documentation and even had some ideas and rudimentary code when suddenly I found this <a href="http://osdir.com/ml/cocoa-dev/2009-06/msg01882.html">post</a>. Such a beautiful idea that I had to try it. And once I got the code to work I felt I should share it with everyone.</p><p>I represent the finger as a rectangle around the touch point, so my problem is reduced to checking for intersection between a rectangle and a path. Here is the algorithm:<br /><ol><br /><li>Filter all trivial cases to avoid unnecessary calculations.</li><br /><li>Get the intersection between the bounding box of the path and the rectangle (of the finger).</li><br /><li>If that's a non-zero rectangle, smaller than the bounding box (else the path and the rect intersect), draw the intersection into a 1x1 off-screen, alpha-only, bitmap buffer</li><br /><li>If the resulting pixel is non-zero the two intersect, i.e. the intersection contains at least one non-transparent pixel from the path.</li><br /><li>Integrate into your code, test and feel totally awesome ;)</li><br /></ol><br />And bellow is the code (the implementation part only, assuming the class name is GraphicsUtil!):<br /><br /><pre class="brush:cpp;wrap-lines: false; gutter: false"><br /><br />//check if the rect contains any non transparent part of the path<br />//as it is drawn on the screen<br />+ (BOOL)rect: (CGRect)rect <br />intersectsPath: (CGPathRef)path <br /> strokeWidth: (CGFloat)strokeWidth<br /> strokeColor: (UIColor *)strokeColor<br /> fillColor: (UIColor *)fillColor;<br />{ <br /> CGRect bbox = [GraphicsUtil boundingBoxForPath: path<br /> withStrokeWidth: strokeWidth<br /> strokeColor: strokeColor<br /> fillColor: fillColor];<br /> CGRect intersection = CGRectIntersection(rect, bbox);<br /> BOOL result = NO;<br /> <br /> if (intersection.size.width > 0.0f && intersection.size.height > 0.0f)<br /> {<br /> // if the rect contains the path then we are sorted<br /> if( CGRectEqualToRect(intersection, bbox))<br /> {<br /> return YES;<br /> }<br /> else<br /> {<br /> //Take the intersection rect and find out if it contains at least one<br /> // non 0 pixel. <br /> //Scale the pixels from the intersection into an 1x1 <br /> //image context<br /> <br /> //cache these so they are created once and then cleared<br /> static CGContextRef bitmap1x1 = NULL;<br /> static uint8_t pixels[8]; //some unused padding<br /> static CGRect rect1x1 = {{0, 0},{1, 1}};<br /> <br /> if( bitmap1x1 == NULL )<br /> {<br /> bitmap1x1 = CGBitmapContextCreate(pixels, 1, 1, 8, 1, NULL, <br /> kCGImageAlphaOnly);<br /> CGContextSetInterpolationQuality(bitmap1x1, kCGInterpolationNone);<br /> CGContextSetShouldAntialias(bitmap1x1, NO);<br /> CGContextSetShouldSmoothFonts(bitmap1x1, NO);<br /> }<br /> <br /> pixels[0] = 0;<br /> <br /> [self drawPath: path <br /> fromRect: intersection <br /> inRect: rect1x1 <br /> inContext: bitmap1x1 <br /> strokeWidth: strokeWidth <br /> strokeColor: strokeColor <br /> fillColor: fillColor];<br /> <br /> result = ( pixels[0] != 0 );<br /> }<br /> }<br /> <br /> return result;<br />}<br /><br />//Draws a rectangular part of the path into another rectangular<br />//region scaling it to fit.<br />+ (void)drawPath: (CGPathRef)path<br /> fromRect:(CGRect)srcRect<br /> inRect: (CGRect)destRect <br /> inContext: (CGContextRef)context<br /> strokeWidth: (CGFloat)strokeWidth<br /> strokeColor: (UIColor *)strokeColor<br /> fillColor: (UIColor *)fillColor;<br />{ <br /> NSAssert( destRect.size.width > 0.0 && destRect.size.height > 0.0, @"destination rect has zero size");<br /> CGRect bbox = [GraphicsUtil boundingBoxForPath: path <br /> withStrokeWidth: strokeWidth <br /> strokeColor: strokeColor <br /> fillColor: fillColor];<br /> if (CGRectEqualToRect(srcRect, CGRectZero))<br /> {<br /> srcRect = bbox;<br /> }<br /> else<br /> {<br /> srcRect = CGRectIntersection(srcRect, bbox);<br /> }<br /> <br /> if( CGRectEqualToRect(srcRect, CGRectZero))<br /> {<br /> return;<br /> }<br /> <br /> CGContextSaveGState(context);<br /> CGContextClipToRect(context, destRect);<br /> <br /> CGContextConcatCTM(context, [GraphicsUtil mapFrom: srcRect to: destRect]);<br /> CGContextAddPath(context, path); <br /> <br /> CGContextSetLineWidth(context, strokeWidth);<br /> <br /> CGPathDrawingMode mode;<br /> if(strokeColor)<br /> {<br /> CGContextSetStrokeColorWithColor(context, strokeColor.CGColor);<br /> mode= kCGPathStroke;<br /> }<br /> <br /> if(fillColor)<br /> {<br /> CGContextSetFillColorWithColor(context, fillColor.CGColor);<br /> if(strokeColor)<br /> {<br /> mode = kCGPathFillStroke;<br /> }<br /> else <br /> {<br /> mode = kCGPathFill;<br /> }<br /> }<br /> <br /> CGContextDrawPath(context, mode); <br /> CGContextRestoreGState(context);<br />}<br /><br />//The strokes on the iPhone are drawn so that half of the stroke is on <br />//one side of the path edge and half is on the other<br />//So the actual bounding box is bigger than the one returned by the API<br />//Or I may be smoking something and there could be an official//better <br />//way to calcualate this. <br />//Worked for me!!!<br />+ (CGRect)boundingBoxForPath: (CGPathRef)path <br /> withStrokeWidth: (CGFloat)strokeWidth<br /> strokeColor: (UIColor *)strokeColor <br /> fillColor: (UIColor *)fillColor<br />{<br /> BOOL noStroke = (strokeColor == nil || <br /> strokeWidth <= 0 || <br /> [strokeColor isEqual:[UIColor clearColor]]);<br /> if((fillColor == nil || [fillColor isEqual:[UIColor clearColor]]) &&<br /> noStroke)<br /> {<br /> return CGRectZero;<br /> }<br /> else<br /> {<br /> CGRect bbox = CGPathGetBoundingBox(path);<br /> if(!noStroke)<br /> {<br /> CGFloat border = ceil(strokeWidth/2.0f);<br /> bbox = CGRectMake(bbox.origin.x - border, <br /> bbox.origin.y - border, <br /> bbox.size.width + 2*border, <br /> bbox.size.height + 2*border);<br /> }<br /> return bbox;<br /> }<br />}<br /><br />//Create an affine transform that transitions the source rectangle<br />//into the destination one.<br />+ (CGAffineTransform) mapFrom:(CGRect)src to:(CGRect)dst<br />{<br /> CGFloat a = (dst.size.width/src.size.width);<br /> CGFloat b = 0.0;<br /> CGFloat tX = dst.origin.x - a*src.origin.x;<br /> CGFloat c = 0.0;<br /> CGFloat d = (dst.size.height/src.size.height);<br /> CGFloat tY = dst.origin.y - d*src.origin.y;<br /> return CGAffineTransformMake(a, b, c, d, tX, tY);<br />}<br /></pre>Plamen Dragozovhttp://www.blogger.com/profile/01916912704086561904noreply@blogger.com0