(Coding) Pearls

Programming, Algorithms, Math.

Bird's book

"Pearls of Functional Algorithm Design", by Richard Bird. Cambridge University Press. 2010.
Great book!
Inspirational in it's succinct and clear way of presenting the material.
No wonder: It is a collection of some of the pearls published in the 20-years period (1990-2010) in the Journal of Functional Programming.

Coding Pearls in Haskell

  1. Dijkstra -- Shortest path in a graph (no heuristics).
  2. Needleman-Wunsch -- Global sequences alignment.
  3. Smith-Waterman -- Local sequences alignment.

  4. Clock -- Measuring execution time -- Easy. The goal is to time a ceratin function or program. Of course, there's difference between "wall-time" and "CPU time", and whether you want to count IO-Time as well (waiting for File I/O), multi-threads, and so on.
    1. System.CPUTime- Simplest. Coems with Base. clock1.hs
    2. Clock package - Various options for 'Time' definition. Also using the Formatting package for nicer output. clock2.hs
    3. Other possible packages : Timeit package, Criterion package.
    [0] http://chrisdone.com/posts/measuring-duration-in-haskell
    [1] http://rosettacode.org/wiki/Time_a_function#Haskell
  5. Random number(s).
  6. Formatting: Using Text.Printf - part of Base -- Easy. printf.hs
    -- Others options are available: Formatting package (opens in new window)
  7. Rooms map -- Creating a room map for an adventure game -- Random, SVG -- Med. roomsSVG.hs.
    An example result opens in a new tab: roomsSVG_Output.JPG.
  8. foldr and fusion -- Simple example of fusing function on foldr -- Med.
    Source code example: fusion1.hs.
    Fusion is the idea of combining (or 'fusing') a few operations together in a manner that avoids intemediate data-structures or claculations. This is a very common practice in functional programming, where fusion can improve dramatically performance.
    Basic text-definition of fusion for foldr is: " f*foldr g a = foldr h b ", Provided f is strict, f a = b, and f (g x y) = h x (f y) for all x and y.
    The fusion condition on "f strict" can be relaxed if we just want to use " f (foldr g a xs) = foldr h b xs ", for all finite sets xs.
    A note about foldr: " foldr:: (a->b->b) -> b -> [a] -> b " : Takes the second argument, and the last item of the list, and applies the function. Then, takes the result and the pentumilate element of the list, and repeats.
    For a more elaborated example, see the Celebrity Clique pearl (P9) in Bird's book.
  9. Triangular numbers -- Fiding all triangular numbers. triWizard.hs.
  10. Purple America -- Coloring the US/counties map based on voting. Full credit for this problem goes to nifty.stanford.edu (see link below). Printed from there the problem and slides: assignment and slides. And here are the files you need to run it: purpleAmerica.hs, USA.txt, USA2012.txt, and the results: purpleUSA.jpg.
    The full description is available here: http://nifty.stanford.edu/2014/wayne-purple-america/s.
  11. Jumble solver -- Given sequence of letters, find if they constitute a word. Jumble.hs. Here is also a text file containing all legal words wordsEn.txt
  12. Input from user -- Can be done through command-line-arguments, external file, or simple keyboard.
    -- For command-line-arguments, and file-input, see Jumble.hs
    -- For keyboard, see userInput.hs
  13. Wolf-and-Sheep -- AI game. Pawns .vs. Queen on a chess board. Who has the forced win? (spoiler alert: White).

Coding Pearls in Matlab

  1. Fractal Image Coding -- Using IFS (Iterated Functions system) to encode and decode an image. ifs_encode.m and ifs_decode.m. Sample images to use: lena.png, barbara.png, baboon.png.

Coding Pearls in Python

  1. (see in projects some practical examples)

Project E-u-l-e-r

Want to make sure I am not a spoiler, so am not linking to the original page and details.
The idea in most is to use some Math to make the coding (and solution) much simpler.
  1. Problem 1 -- Find the sum of all the multiples of 3 or 5 below 1000 -- Easy.
    euler1.hs (opens in new window).
  2. Problem 2 -- Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms -- Easy.
    -- Elements of solution: Even valued are every 3rd element; formula for approximating the elements (==> No need to calculate); and thus the sum is sum of geometric series.
  3. Problem 3 -- Largest prime factor: The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
  4. Problem 4 -- Largest palindrome product: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91x99. Find the largest palindrome made from the product of two 3-digit numbers.
  5. Problem 5 -- Smallest multiple: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?.
  6. Problem 6 -- Sum square difference: The sum of the squares of the first ten natural numbers is, 12 + 22 + ... + 102 = 385. The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10)2 = 552 = 3025. 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. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
  7. Problem 7 -- 10001st prime: By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?
  8. Problem 8 -- Largest product in a series: The four adjacent digits in the 1000-digit number that have the greatest product are 9*9*8*9=5832. Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?
  9. Problem 9 -- Special Pythagorean triplet: A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a^2 + b^2 = c^2. For example, 3^2 + 4^2 = 5^2. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.
  10. Problem 10 -- Summation of primes: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million.
  11. Problem 11 -- Largest product in a grid: In the 20x20 grid below, four numbers along a diagonal line have been marked in red. (The diagonal is NW to SE, starting from (7,9). See in the code file.) The product of these numbers is 26 x 63 x 78 x 14 = 1788696.
    What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20 x 20 grid?
  12. Problem 12 -- Highly divisible triangular number: The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers: (cut).
    We can see that 28 is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors?
  13. Problem 13 -- Large sum: Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
    and so on.
  14. Problem 14 -- Longest Collatz sequence: The following iterative sequence is defined for the set of positive integers:
    n -> n/2 (n is even)
    n -> 3n + 1 (n is odd)
    Using the rule above and starting with 13, we generate the following sequence:
    13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
    It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1. Which starting number, under one million, produces the longest chain?
  15. Problem 15 -- Lattice Paths Starting in the top left corner of a 2x2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20x20 grid?
  16. Problem 16 -- Power digit sum 2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 261000?
  17. Problem 17 -- Number letter counts If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total. If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
    NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.
  18. Problem 18 -- Maximum path sum I By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.
    7 4
    2 4 6
    8 5 9 3
    That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from top to bottom of the triangle below (in the text file)
    NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)
    euler18.hs. euler18.txt.
  19. Problem 19
  20. Problem 20
  21. Problem 21
  22. Problem 22 -- Names scores: Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score. For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714. What is the total of all the name scores in the file?
  23. Problem 23
  24. Problem 24
  25. Problem 25 -- 1000-digit Fibonacci number: The Fibonacci sequence is defined by the recurrence relation: Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1. The 12th term, F12, is the first term to contain three digits. (the 7th is the first with 2 digits). What is the index of the first term in the Fibonacci sequence to contain 1000 digits?
  26. Problem 26
  27. Problem 27
  28. Problem 28 -- Number spiral diagonals Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows (see in the code file). It can be verified that the sum of the numbers on the diagonals is 101.
    What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way? -- Easy.
  29. Problem 29
  30. Problem 30
  31. Problem 206 -- Concealed Square: Find the unique positive integer whose square has the form 1_2_3_4_5_6_7_8_9_0, where each “_” is a single digit:
    -- This can be solved by brute-force: Squaring on the numbers up to ... . You can 'jump' in 30 steps.
    Just to make it more interesting, I solved it using Depth First Search, in two ways:
    euler206_a.hs (DFS pattern design) ; euler206.hs (Just DFS).
  32. Problem 461 -- CS/Algorithm: Evaluate a function and search solution in efficent manner.
  33. Problem 493 -- Combinatorics: 70 colored balls are placed in an urn, 10 for each of the seven rainbow colors. What is the expected number of distinct colors in 20 randomly picked balls?
    -- The idea is to do some calculation by hands of the related combinatorics, and then computer the resulting expression. It turns out that for this one, there is a very easy way to calculate by hand, so a calculator is enough.
  34. Problem 504 -- Square on the Inside: Let ABCD be a quadrilateral whose vertices are lattice points lying on the coordinate axes as follows:
    A(a, 0), B(0, b), C(-c, 0), D(0, -d), where 1 = a, b, c, d = m and a, b, c, d, m are integers.
    It can be shown that for m = 4 there are exactly 256 valid ways to construct ABCD. Of these 256 quadrilaterals, 42 of them strictly contain a square number of lattice points.
    How many quadrilaterals ABCD strictly contain a square number of lattice points for m = 100? -- Easy if you know the theorem.
    -- Pick's theorem. Also did some memoization.
  35. Problem 510 -- Tangent Circles: Circles A and B are tangent to each other and to line L at three distinct points. Circle C is inside the space between A, B and L, and tangent to all three. Let rA, rB and rC be the radii of A, B and C respectively. Let S(n) = S rA + rB + rC, for 0 < rA = rB = n where rA, rB and rC are integers. The only solution for 0 < rA = rB = 5 is rA = 4, rB = 4 and rC = 1, so S(5) = 4 + 4 + 1 = 9. You are also given S(100) = 3072.
    Find S(10^9). -- Easy math. Running time is tricky!
    -- Writing the equations gives you relations between rA, rB, and rC. And for all to be integers, one only need to go over the enumeration.

Questions/Comments: Zachi at Baharav dot Org .