• Review - Version Control by Example by Eric Sink

    "Version Control by Example"

    There are quite a bit of Version Control systems, such as CVS, SVN and the newer ones like Git or Mercurial (The book names 3 generations, talks about 2nd and 3rd.)

    When you’re programming alone, you can get away without one, but Version Control is essential for software development by teams. It allows multiple people to work on the same piece of software simultaneously, without conflicting with each other. And did I mentioned ability to see who made which changes and the ability to get every version of code that has ever existed?


    Version Control by Example covers 2 types of Version Control software:

    1. Centralized Version Control System, like CVS

    2. Distributed Version Control Systems, like Mercurial, Git and Veracity

    At first you are presented with each general command, that exist in both types of VCS, like **commit, diff, revert, **and other basics.

    Then for each VCS (CVS, Mercurial, Git and Veracity) the author goes through the same example, but he adapts the example to each VCS to give a better understanding how the same process would be done in different VCS, so along the way you get a pretty good grasp of all 4 VCS.

    In Chapter 11 Workflows are explained. He reviews and explains branching and managing multiple releases.

    And lastly, he explains best practices. If you’re just getting started with VCS like me, the last 13th chapter will be very useful. Simple tips like “Run diff just before you commit, every time” will save you trouble down the road.

    Personal thoughts

    If you’re just getting started, this book is a great way to kickstart working with Version Control. It is very easy to follow, answers many questions (at least in my case) and is relatively short and compact.You can get through it in a matter of hours.

    Unfortunately I have found this book just a couple of days ago. Because I’ve dived head first into Mercurial and Git I didn’t understand much, but this book explained a lot. Explaining by example is a powerful way to learn, so I really recommend this book if you want to get started with Version Control Systems.

    Version Control by Example is a free ebook and is available in HTML and PDF formats. At the time of writing Kindle and printed versions are coming soon.

  • Solving Euler problems Part 4 (Final part)

    Finally, just a few hours after my previous post I have reached my goal. Less than a month ago I started solving Euler problems from ProjectEuler.net. In my mind I set a goal to solve 30 problems and today I can proudly say that I successfully did it. Some more thoughts about the experience later in the post, but now - the last problem.

    Problem 63

    The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power. How many n-digit positive integers exist which are also an _n_th power?

    My solution:

    count = 0
    for a in range(1, 1000):
    	for b in range(1, 1000):
    		if(len(str(a ** b)) == b):
    			count += 1
    print count

    My first thought to solve this was to use logarithms, but obviously it’s the wrong way. Then, by choosing an usual bruteforce path, I realized that I can generate base and power and don’t care about the resulting number - it can be calculated. a ** b is converted to string to get the length of the number (len function does not handle integers) and compared to power. If it matches the counter is incremented.

    And finally - the experience. The problems are really interesting and it was even addicting to solve them. Actually I was surprised how fun it was to solve the problems - there were quite a few “A-ha!” moments, I got to compare my knowledge to the rest of the world, increase the number of Python users and contribute to Lithuania’s score (at the moment there are 251 Lithuanian solvers. I’m 69th on the list) on ProjectEuler.

    I have solved first 14 problems in a row. It’s the most consecutive number of solutions I’ve got there so far. I thought I was going strong, but it wasn’t the case. After that I skipped a whole lot of problems, generally because I came up with and followed this rule: If I can’t come up with an algorithm to solve the problem in 3 minutes, I will skip it. Also I skipped some for no apparent reason.

    Problems I solved

    I certainly haven’t checked out all of the problems in the project, so I believe there is quite a bit of room to improve my score. I shot for the simplest and neatest solutions I could came up with at that time and I am pretty happy with them.

    Was it worth the time and efforts? I think it was. It was a great chance to dive a bit more into Python, check my logic. On top of that - it was really fun. It consumed roughly half a week of work throughout the month.

    I would recommend you to check it out, see how well you can do. You should learn something. If you are interested, you can find the project at ProjectEuler.net

    Thank you for reading that that’s it for now.

  • Solving Euler problems Part 3

    In my previous posts I have reviewed my solutions for 10 problems (problems 4-20). I have skipped some problems, for some solutions were lost. Now problems started to get more difficult and solutions had to get longer.

    Problem 24

    A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012   021   102   120   201   210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

    My solution:

    import itertools
    x = 0
    for i in list(itertools.permutations(range(10))):
    	x += 1
    	if(x == 1000000):
    		print i

    Python has a really nice itertools library. I learned about it from a Python talk on “Easy AI with Python” (AI - Artificial Intelligence.) Count the number with each permutation and on the 1000000th one output it.

    Problem 29

    Consider all integer combinations of a__b for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5: 22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243 42=16, 43=64, 44=256, 45=1024 52=25, 53=125, 54=625, 55=3125 If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms: 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125 How many distinct terms are in the sequence generated by a__b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

    My solution:

    numbers = []
    for a in range(2, 101):
    	for b in range(2, 101):
    		if(not(a ** b in numbers)):
    			numbers.append(a ** b)
    print len(numbers)

    Generate a list of distinct a ** b numbers, print out the length.

    Problem 30

    Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits: 1634 = 14 + 64 + 34 + 44 8208 = 84 + 24 + 04 + 84 9474 = 94 + 44 + 74 + 44 As 1 = 14 is not a sum it is not included. The sum of these numbers is 1634 + 8208 + 9474 = 19316. Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

    My solution:

    def canBeWritten(x):
    	nums = str(x)
    	sum = 0
    	for i in nums:
    		sum += int(i) ** 5
    	if(sum == x):
    		return True
    		return False
    found = []
    for a in range(2, 1000000):
    		print a
    print ''
    print sum(found)

    Function that checks if the number can be written that way makes everything a bit cleaner. Loop through numbers (I didn’t see a point of looping over 1M, but if the answer would have been incorrect - I would have to do it), add required numbers to the list and calculate the sum based on that. You can skip using the list, but I wanted to see which numbers can be written that way .

    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.

    My solution:

    import math
    def sumEqualFactorial(x):
    	number = str(x)
    	factorialSum = 0
    	for i in number:
    		factorialSum += math.factorial(int(i))
    	if(factorialSum == x):
    		return True
    		return False
    suma = 0
    for a in range(3, 1000000):
    		suma += a
    print suma

    To calculate the sum of each numbers factorials I converted the number to string for easier handling and used math.factorial() to calculate sum of factorials. This one seems to be straightforward.

    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?

    My solution:

    import math
    primes = []
    def isPrime(x):
    	if x == 1:
    		return False
    	for z in primes:
    		if(z == x):
    		if(x % z == 0):
    			return False
    	return True
    def isCircularPrime(x):
    	number = list(str(x))
    	for i in range(1, len(number)):
    		y = number.pop(0)
    			return False
    	return True
    for i in range(2, 1000000):
    count = 0
    for a in primes:
    		count += 1
    print count

    This is a bit more complex at a first glance and there’s a bit more code, but actually the algorithm is relatively simple. Firstly we calculate prime numbers up to 1 million. Then we loop through each prime number to check if it is a circular prime. To check that function does some permutations transferring the number from the beginning to the end and each time checking if the number is prime. If the number is prime for all of permutations - the number is a circular prime. Increment the counter and move on!

    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.)

    My solution:

    def isPalindromic(x):
    	binary = bin(x)
    	binary = binary[2:]
    	number = str(x)
    	reversedBinary = binary[::-1]
    	reversedNumber = number[::-1]
    	if(binary == reversedBinary and number == reversedNumber):
    		return True
    		return False
    sum = 0
    for i in range(1, 1000000):
    		sum += i
    print sum

    Loop through each number up to 1M, calculate binary for each number, reverse binary and the number itself and check for validity. “binary[2:]” just removes 0b symbols, that indicate, that the number is binary. “binary[::-1]” reverses the string/list.

    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.

    My solution:

    import math
    primes = []
    def genPrimes(n): 
    	if n==2: return [2]
    	elif n<2: return []
    	mroot = n ** 0.5
    	while m <= mroot:
    		if s[i]:
    			while j>half:
    	return [2]+[x for x in s if x]
    def isPrime(x):
    	if x == 1:
    		return False
    	for z in primes:
    		if(z == x):
    		if(x % z == 0):
    			return False
    	return True
    def isTruncatable(x):
    	number = str(x)
    	length = len(number)
    	for i in range(0, length): #truncate from left
    			return False
    	for i in range(0, length):
    		if(not(isPrime(int(number[:(length - i)])))):
    			return False
    	return True
    primes = genPrimes(1000000)
    print primes
    sum = 0
    for a in range(8, 1000000):
    		sum += a
    		print a
    print sum

    Functions to generate prime numbers that I wrote myself weren’t that effective and fast, so I looked up a more elaborate solution for that (I know, I’m a bit cheating here), but that increased the speed by quite a bit. To check if the number is truncatable,  once again I’ve used python string. The function loops forwards and backwards through the number each time eliminating one more number.

    Problem 45

    Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:



    1, 3, 6, 10, 15, …



    1, 5, 12, 22, 35, …



    1, 6, 15, 28, 45, …

    It can be verified that T285 = P165 = H143 = 40755. Find the next triangle number that is also pentagonal and hexagonal.

    My solution:

    triangles = []
    pentagonals = []
    hexagonals = []
    for i in range(1, 100000):
    	triangles.append(i * (i + 1) / 2)
    	pentagonals.append(i * (3 * i - 1) / 2)
    	hexagonals.append(i * (2 * i - 1))
    for i in triangles:
    	if((i in pentagonals) and (i in hexagonals)):
    		print i

    To make things easier we generate lists of triangles, pentagonals and hexagonals. After that we loop through each number in triangles list (checking based on hexagonals rather than triangles would make it more efficient - less numbers to check) we only need to check if the number exists in other lists.

    Problem 48

    The series, 11 + 22 + 33 + … + 1010 = 10405071317. Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.

    My solution:

    import math
    sum = 0
    for i in range(1000):
    	sum += i ** i
    sum = str(sum)
    print sum[-10:]

    Loop through numbers up to 1000, calculate their powers and calculate their sum. Use Python list slicing to get the last 10 numbers easily.

    Problem 56

    A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1. Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

    My solution:

    maximum = 0
    for a in range(1, 100):
    	for b in range (1, 100):
    		number = str(a ** b)
    		number = [int(i) for i in number]
    		suma = sum(number)
    		if(suma > maximum):
    			maximum = suma
    print maximum

    Use two loops to calculate a ** b. Convert a ** b to string and using Python list comprehension convert each element to an integer, thus creating a list of integers. Find the sum of those integers and that’s it.

    Problem 92

    A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before. For example,

    44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

    Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89. How many starting numbers below ten million will arrive at 89?

    My solution:

    def arrivesAt89(x):
    		a = x
    		x = sum([int(i) ** 2 for i in str(x)])
    		if(a == x):
    			return False
    		if(x == 89):
    			return True
    count = 0
    for i in range(1, 10000000):
    	print i
    		count += 1
    print count

    To calculate the chain we use a loop. Just to make sure that we’re not stuck on the same number (e.g. 1 is the end of the chain), we check if current calculated one is not equal to previous one. If it is equal to previous one (such as we arrived at one) - the chain does not arrive at 89. If we detect number 89 in the chain, we break the loop immediately, because that is our goal.

    Problem 97

    The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 26972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2p−1, have been found which contain more digits. However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×27830457+1. Find the last ten digits of this prime number.

    My solution:

    number = str(28433 * (2 ** 7830457) + 1)
    print number[-10:]

    The solution is shorter than the problem itself. We calculate the number and turn it into a string to get access to Python list slicing. Slice last ten digits and print them out.

    At this point I have solved 29 problems and probably posted not as many solutions, but the goal is near. I will be posting another post soon, which will probably be the last one about my ProjectEuler solutions. Thanks for reading!

  • Solving Euler problems Part 2

    So the quest of solving Euler problems continues. I discovered projecteuler.net quite a bit ago and for past month I’ve been solving some of them bit by bit. In my last post “Solving Euler problems” I walked you through my solutions for problems 4 to 6. Unfortunately started saving the solutions since 4th problem, so… I don’t have first three solutions in code, but those problems are solved.

    Problem 7

    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?

    My solution:

    primes = []
    def isPrime(x):
    	for i in primes:
    		if(x % i == 0):
    			return 0
    	return 1
    primeCount = 0
    i = 2;
    while(primeCount <= 10001):
    		print i
    		primeCount = primeCount + 1
    		if(primeCount == 10001):
    			print i
    	i = i + 1

    This one seemed to be straightforward. You need to generate prime numbers and increment a variable every time a prime number is found until the 10001st prime number is found. When you find it - print it and stop.

    Problem 8

    Find the greatest product of five consecutive digits in the 1000-digit number. 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

    My solution:

    number = '7316717653133062491922511967442\
    length = len(number)
    largest = 0
    batch = 0
    for i in range(length + 1 - 5):
    	batch = number[i:i+5]
    	result = 1;
    	for j in batch:
    		result *= int(j)
    	if(result > largest):
    		largest = result
    print largest

    Product basically means multiplying 5 consecutive numbers. This one seemed like a great way to play a bit with Python lists. Python has a neat way to slice lists and strings can be sliced like lists, so take a batch of 5 numbers, multiply them together, mark it if it is the largest so far and move onto the next batch. Just not forget to deal with different data types or you will be greeted with an error.

    Problem 9

    A Pythagorean triplet is a set of three natural numbers, a < b < c, for which, a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

    My solution:

    for a in range(1, 1000):
    	for b in range(1, 1000):
    		c = 1000 - a - b
    		if(c ** 2 == a ** 2 + b ** 2):
    			print str(a) + ' ' + str(b) + ' ' + str(c) 

    Since there is only a single Pythagorean triplet, looks like this one will be another bruteforce algorithm. Since a + b + c = 1000, we only need to generate 2 parameters (e.g. a and b), because we can calculate the other one (in this case c) using the given formula. c ** 2 is just a way of math.pow(c, 2). Since it is just a puzzle and it does not need to be that much optimized, I got the solution and left it as it is, but there is a problem with my solution that I noticed only now. When the number is found the program would still continue looking for such number, so stopping the program is necessary when a solution is found (Actually you can find this mistake being made by many beginners, but good programmers shouldn’t waste resources.)

    Problem 13

    Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

    37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 74324986199524741059474233309513058123726617309629 91942213363574161572522430563301811072406154908250 … Removed, you can find the number HERE …. 53503534226472524250874054075591789781264330331690

    My solution:

    numbers = """37107287533902102798797998220837590246510135740250
    ... Removed, you can find the number at http://projecteuler.net/index.php?section=problems&id=13 ....
    numbers = numbers.split("\n")
    sum = 0
    for i in numbers:
    	sum += int(i)
    print sum

    This one is really easy to do in Python. Insert the numbers into a variable (triple quotes were used, because data spans across multiple lines), split the big number by new line markers to get a list of 50-digit numbers, calculate the sum and that’s it. If you’d invest a bit more time, you might want to use Python list slicing to get only 10 first numbers, because my solution outputs whole number.

    Problem 14

    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? NOTE: Once the chain starts the terms are allowed to go above one million.

    My solution:

    def getLength(n):
    	length = 0
    	while n > 1:
    		if(n % 2 == 0):
    			n /= 2
    			n = n * 3 + 1
    		length += 1
    	return length + 1
    longest = 0
    number = 0
    for i in range(1000000):
    	x = getLength(i)
    	if(x > longest):
    		longest = x
    		number = i
    print str(number) + ' is ' + str(longest) + ' long'

    Yet another bruteforce solution. GetLength function is created only to make the main loop a bit cleaner (less code to worry about). Go through numbers 0-1000000, calculate each one’s chain length and output the largest.

    Problem 16

    215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 21000?

    My solution:

    number = 2 ** 1000
    number = str(number)
    sum = 0
    for i in number:
    	sum += int(i)
    print sum

    Without computers it would be really hard or maybe even impossible to do that (I do not know of any method to do that, but I certainly don’t know everything), but now in just a few lines you can get the solution in under a second. Calculate the number, convert it to string to access it as a list and get the sum of numbers.

    Problem 20

    n! means n × (n − 1) × … × 3 × 2 × 1 For example, 10! = 10 × 9 × … × 3 × 2 × 1 = 3628800, and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27. Find the sum of the digits in the number 100!

    My solution:

    import math
    number = math.factorial(100)
    number = str(number)
    sum = 0
    for i in number:
    	sum += int(i)
    print sum

    This solution is very similar to the one I wrote for Problem 16. To calculate the 100! I used Python math module, last calculations are made with a simple loop.

    That’s it for now. I have more solutions already (and more complex) and will post them here in next few days. I think there will be one or two posts of solutions and another one of my thoughts on ProjectEuler and my experience. Thanks for reading!

  • Solving Euler problems

    I recently discovered projecteuler.net, where you can find mathematical/computer programming problems and solve them.

    Lately I’ve been trying to learn more Python, so I decided to give it a try - solving Euler problems with Python.

    My progress

    Problem 4

    A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.My solution:

    list = []
    for i in range(100, 1000):
        for j in range(100, 1000):
            x = i * j;
            y = str(x)
            if(x == int(y[::-1])):
                largest = 0
    for i in list:
        if(i > largest):
            largest = i
    print largest

    It basically runs 2 loops to generate the numbers and each calculated number is turned into a string, reversed, turned back into an integer and compared with the original number. One thing I do not like about the code already is that it uses an additional array, which can be removed with a simple if statement (might not even need that either). It needs refactoring, but it got me the answer, so - moving on.

    Problem 5

    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?

    My solution:

    def isEvenlyDivisible(x):
        for i in range(1, 20):
            if(x % i != 0):
                return 0
        return 1
    i = 1
    found = 0
    while(found == 0):
        if(isEvenlyDivisible(i) == 1):
            print i
            found = 1
        i = i + 1

    This one took some time. Because of my brute force approach, it took ~ 5 minutes to complete. I knew that lowest common multiple needed to be found, but because as far as I know LCM is computed for 2 numbers at a time, I couldn’t come up with a quicker algorithm in a few minutes. Rather it became a brute force algorithm, not very effective, but got the job done.

    Problem 6

    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.

    My solution:

    sumOfSquares = sum([i ** 2 for i in range(1, 101)])
    sumSquare = sum(range(1, 101)) ** 2
    print sumSquare - sumOfSquares

    I think this solution is the best so far. Solved in 3 lines, can be easily merged into a single line. Range generates a list of numbers [1, 2, 3… 99, 100]. Using list comprehension I use the same list and square each list element, that also returns a list, which sum function uses to calculate total sum of squares. ** is used instead of a math.pow function.