Month: September 2014

Problem 037

Project Euler

Truncatable primes

Problem 37

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Since there are only eleven solution, a counter will be use to stop the execution once the program found all the solutions. However, having a list of prime to check against the value would be very helpful, the program will start using an arbitrary list of prime under 1 million and add to it if needed.

This problem is very similar to the problem from problem 35 where the prime in question must not include any even digit or it will never pass the test. Therefore, starting with a list of prime and check if any digit is even, then check both left and right truncatability, stop when eleven solution is found and add them for the final result.


Problem 036

Project Euler

Double-base palindromes

Problem 36

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

First, select only palindromic in decimal number to check by using the following method. Pick i, j, k where 1<= i <= 9, and 0 <= j,k <= 9. Create the following numbers when looping through each value.
  • i
  • ii
  • iji
  • ijji
  • ijkji
  • ijkkji

Now create a function that convert these number into binary and then create another function to check if the binary number is a palindrome. The remaining problem is to add all the results up. Since each value of i, j, k and position are unique, there will not be any repeat representation of a solution.

Problem 035

Project Euler

Circular primes

Problem 35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

First of all, except 2, there can be no other circular prime contains any even number. Also, for every circular prime found with x digits, there at most x-1 other circular prime found unless there are duplicate digits within the circular prime.

Starting with a list of prime numbers (by now, finding all prime under a million should be quite familiar if the problems are done in sequence), record 2 as circular prime since it is a special case and then go through each subsequent prime by checking if any of them contain an even digit, check if the number is still prime after rotating a single digit, and record all of the corresponding circular prime once a circular prime is found.

Problem 034

Project Euler

Digit factorials

Problem 34

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Since no mention of what the upper limit would be for this search, the first thing is to find this upper limit. Notice the following:
  • 9! = 362880
  • 9! * 5 = 1814400 (5 represents the number of digits)
  • 9! * 6 = 2177280
  • 9! * 7 = 2540160
  • 9! * 8 = 2903040 (There is no way to get this.)

Therefore, we will stop at 10 million. Before start doing the search, calculate factorial 1 to 9 and store them in an array for fast access and avoid calculating each one over and over again. Now, search from 10 to 10 million and check if the sum of the factorial of the digit equal to the number itself.

Problem 033

Project Euler

Digit canceling fractions

Problem 33

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

For the canceling to work, one of the digit in the numerator must be the same as one of the digit in the denominator. Since only non-trivial examples are to be consider, no number (numerator or denominator) will contain any zero. Also, notice the following relationships:

\frac{cx}{yc} = \frac{x}{y} or \frac{xc}{cy} = \frac{x}{y}

where c, x and y denote a digit between 1 to 9, we have

y*cx=x*yc or y*xc = x*cy

With cx < yc, xc < cy and x < y in order for the fraction to be less than one. Therefore, looping through 1 to 9 for x, x+1 to 9 for y and 1 to 9 for c in this order, we can find the four solutions quickly.

Finally, the answer is \frac{\Pi(y_i)}{gcd(\Pi(x_i),\Pi(y_i))}

Episode 07 – Architecture

Clean Code

Episode 07

The seventh episode talks about how architecture encompass the highest level of abstract decision to the lower level of implementation.

  • What is architecture
    • Architecture is about usage
      • Architecture should expose the use case and not the delivery mechanism. Use case that should not be couple with the delivery mechanism.
      • Architecture should show the intent
    • Deferring decision
      • Good Architecture maximize the number of decision not make
      • Defer to make the decision by designing a structure that decouple from them and make the decision irrelevant.
      • Decouple tool, frame work and database by focuses the architecture on the use cases not on the software environments.
    • Separation of value
      • Make UI as a plug in to the use cases. By separating them, it is easy to understand the cost of UI and use cases individually. All system component should be isolated because of this.
  •  Use cases
    • What really is Architecture
      • The system of an accounting system should scream accounting and not web system, which is a delivery mechanism to the accounting.
      • How the user interact the system with the delivery mechanism. Use cases that does not use word to imply delivery mechanism.
      • Use cases should be the central structure of the system where the abstraction is build upon. This is the intent of the system.
    • What are Use cases
      • Its a formal description on how the user interact with the system. It talks about what data and command that goes into the system and how the system response to them.
      • Primary course is normal interaction between user and system while Exception course is where error handling uses.
  • Partitioning
    • Three fundamental objects
      • Business object – Entities
        • application independent business rules
        • the method on Entity objects performance is valid on any application that the entity can be use in.
        • Entity object should not have any application specific method. Any such method should be in the interactor object.
      • User Interface object – Boundaries
        • Boundaries object shoulder one of the job of use case is to accept data from user and output data back to user.
        • Boundaries object isolate the use cases from the delivery mechanism to the system use cases.
      • Use case object – Interactors
        • Use cases are application specific business rules and implement by interactor object.
      • User <–> Delivery Mechanism <–> [ ( Boundary <–> Interactor <–> Entity ) System Architecture ]
  • Isolation
    • The delivery mechanism should have source code dependency pointing toward the system.
    • Model View Controller.
    • Database
  • Case Study
    • The stalk holder meeting
    • Analysis
      • Make use cases agnostic by separate what is matter (how to response to commands and data) and what is not (delivery mechanism)
    • Interaction and Databases
    • The underlying abstraction
  • References
    • Object-Oriented Software Engineering, by Ivar Jacobson
    • Writing Effective Use Cases by Alistair Cockburn
    • User Stories Applied by Mike Cohns
    • Agile Software Development by Robert Martin
    • Agile Principles, Pattern and Practices in C# by Robert Martin

Chapter 6: Higher Order Functions

Learn You a Haskell for Great Good!

Curried functions

  • Every function in Haskell officially only takes one parameter
  • If we call a function with too few parameters, we get back a partially applied function (the return ->)
multThree :: (Num a) => a -> a -> a -> a
multThree x y z = x * y * z
  • If we do multThree 3 4 5, which is same as ((multThree 3) 4) 5, the 3 is applied to multThree and the function type is the same as
multThree :: (Num a) => a -> (a -> (a -> a))
  • and will return another function that has type as follow
multThree :: (Num a) => a -> (a -> a)
  • applied 4 to this function and it is return a function with the following type
multThree :: (Num a) => a -> a
  • and finally apply 5 to the last function and return a. By calling the function  with too few parameter, we create new function on the fly.
  • The following two functions are the same because compare has type (Ord a) => a -> (a -> Ordering) and we can use that function for the value we need to compare with.
compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x

compareWithHundred = compare 100
  • Similarly, Infix function works the same way. The function will take one parameter and then applied to the missing operand. Thus, calling divideByTen 200 is equivalent to 200 / 10 or (/10) 200.
divideByTen :: (Floating a) => a -> a
divideByTen = (/10)

Some higher-orderism is in order

  • Function can take a function as parameter
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
  • applyTwice take two parameters, a function (a->a) and a of the same type and return a. This function apply whatever the function is twice and then apply it to the value.
  • zipWith’ takes two lists and a function and apply the function to each corresponding element of the lists and produce a result list.
zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' _ [] _ = []
zipWith' _ _ [] = []
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
  • We can use this function in many ways as long as the type is consistent with the declaration. The last one zipWith list of list.
ghci> zipWith' (+) [4,2,5,6] [2,6,2,3]  
[6,8,7,9ghci> zipWith' max [6,3,2,1] [7,3,1,5]  
[7,3,2,5ghci> zipWith' (++) ["foo ""bar ""baz "] ["fighters""hoppers""aldrin"]  
["foo fighters","bar hoppers","baz aldrin"ghci> zipWith' (*) (replicate 5 2) [1..]  
[2,4,6,8,10ghci> zipWith' (zipWith' (*)) [[1,2,3],[3,5,6],[2,3,4]] [[3,2,2],[3,4,5],[5,4,3]]  

Maps and filters

  • map take a function and a list and applies that function to every element in the list
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs

ghci> map (+3) [1,2,3,4,5]
  • You can do this with list comprehension
[x + 3 | x <- [1,2,3,4,5]]
  • filter is a function that takes a predicate (which is a function that return true or false) and a list and returns the list of elements that satisfy the predicate.
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
    | p x       = x : filter p xs
    | otherwise = filter p xs

ghci > filter (>3) [1,2,3,4,5]
  • Again, you can do this with list comprehension
[ x | x <- [1,2,3,4,5], x > 3]
  • find the largest number under 100000 that’s divisible by 3829
largestDivisible :: (Integral a) => a
largestDivisible = head (filter p [100000,99999..])
    where p x = x `mod` 3829 == 0
  • more general largestDivisible’ with the max limit and the divisor.
largestDivisible' :: (Integral a) => a -> a -> a
largestDivisible' x y = head (filter p [x,(x-1)..])
    where p z = z `mod` y == 0
  • takeWhile function takes a predicate and a list and then goes from the beginning of the list and returns its elements while the predicate holds true.
  • take the first word of the string “elephants know how to party”. Not equal is /=.
ghci> takeWhile (/=' ') "elephants know how to party"
  • find the sum of all odd squares that are smaller than 10000. We  use both filter & map or list comprehension to achieve the same result. However, both needed takeWhile as a stopping condition.
ghci> sum (takeWhile (<10000) (filter odd (map (^2) [1..])))

ghci> sum (takeWhile (<10000) [n^2 | n <- [1..], odd (n^2)])
  •  you can use pure list comprehension to do the same thing without takeWhile but must upper bound the list
ghci> sum ([n^2 | n <- [1..10000], odd (n^2), (n^2) < 10000])
  •  the following create a list of function and use it by selecting an element from it. The first line create a list of [(0*), (1*), (2*)..] or (Num a) => [a -> a].
ghci> let listOfFunc = map (*) [0..]
ghci> (listofFunc !! 4) 5


  • Lambdas are anonymous functions that are used because we need some functions only once.
chain :: (Integral a) => a -> [a]
chain 1 = [1]
chain n
    | even n = n:chain (n `div` 2)
    | odd n  = n:chain (n * 3 + 1)

numLongChains :: Int
numLongChains = length (filter isLong (map chain [1..100]))
    where isLong xs = length xs > 15

numLongChains :: Int
numLongChains = length (filter (\xs -> length xs > 15) (map chain [1..100]))
  • Lambdas is an expression (e.g \xs -> length xs > 15) return a function.
  • Lambdas can take multiple parameters (e.g. \a b)
  • Lambdas can use pattern matching but can’t define multiple patterns for the same parameter. Any fall through will result in error.

Only folds and horses

  • fold takes a binary function, a starting value and a list to fold up. The type signature
foldl :: (a -> b -> a) -> a -> [b] -> a
  • foldl function (left fold) fold from the left side. The following are equivalent function to sum a list
sum' :: (Num a) => [a] -> a
sum' xs = foldl (\acc x -> acc + x) 0 xs

sum' :: (Num a) => [a] -> a
sum' = foldl (+) 0
  • any function with signature foo a = bar b a can be rewritten to foo = bar b.
elem' :: (Eq a) => a -> [a] -> Bool
elem' y ys = foldl (\acc x -> if x == y then True else acc) False ys
  • foldr function folds from the right side. use accumulator signature (\x acc -> …).
  • right fold works on infinite list and left don’t.
  • foldl1 and foldr1 is similar to foldl and foldr except they take the first or last (respectively) value as starting value. Therefore, the same sum function can implement as follow but will have runtime error on empty list
sum' = foldl1 (+)
  • scanl and scanr are like foldl and foldr but create a list of all the intermediate accumulator states. scanl1 and scanr1 are scanl and scanr without using starting value.

Function application with $

  • function application ($) is right associative. Lowest precedence. Consider the following two lines are equivalent. $ replaced parentheses.
sum (map sqrt [1..130])
sum $ map sqrt [1..130]
  • map function application over a list of functions. The following maps 3 to all the function in the list
ghci> map ($ 3) [(4+), (10*), (^2), sqrt]

Function composition

  • definition: (f \circ g) (x) = f(g(x))
  • function composition is represented by the period “.” and is right associative. therefore, f(g(h x)) is equivalent to (f.g.h) x. Its implementation is as follow:
(.) :: (b -> c) -> (a -> b) -> a -> c
f . g = \x -> f (g x)
  • For functions with multiple parameters, we must first partially apply them so that each function only take one parameter before being use in function composition.

Other commands

  • To change directory
    • :cd
  • To use shell commands
    • :! (e.g. :!ls to list file)