Narcissistic numbers


Here is a nice mathematical exercise from Programming Praxis. Is about finding the “narcissistic numbers”, n digit numbers numbers where the sum of all the nth power of their digits is equal to the number.

To reduce the problem a little, I decided to start by limiting the number of digits. So, the first approach will be just calculate if a number is narcissistic of not. So, after checking it and making a couple of performance adjustments, the code is as follows…

Continue reading

Travelling salesman


I'm selling this fine leather jackets

I’m selling this fine leather jackets

One classic computation problem, the travelling salesman. Even if it’s quite simple to describe, it’s one of those hideous NP complete problems, the ones that are quite difficult to resolve, as the computation time needed grows greatly with the length of the data. On Programming Praxis they have proposed to resolve the problem using brute force, and using the closest neighbor (a simplification of the problem).

I’ve created this program, in Python.

import random
import itertools
import operator
import datetime

MAX_X = 100
MAX_Y = 100

def random_cities(number):
    ''' Generate a number of cities located on random places '''

    cities = [ (random.randrange(0, MAX_X),
                random.randrange(0, MAX_Y))
                for i in range(number) ]

    return cities

def path_lenght(path):
    ''' Get the lenght of a path '''
    lenght = 0
    for i in xrange(len(path) - 1):
        # Add the distance between two cities
        lenght += abs(complex(path[i][0], path[i][1])
                       - complex(path[i + 1][0], path[i + 1][1]))

    return lenght

def find_path_bruteforce(cities):
    ''' Find the smallest path using brute force '''

    lenghts = []

    for path in itertools.permutations(cities, len(cities)):
        # Get the length of the path, adding the returning point
        total_path = path + (path[0],)
        lenght = path_lenght(total_path)
        lenghts.append((total_path, lenght))

    # Get minimum
    lenghts.sort(key=operator.itemgetter(1))
    return lenghts[0]

def find_path_nearest(cities):
    ''' Find the closest neibour '''

    lenghts = []
    for city in cities:
        lenght = 0
        actual_cities = cities[:]
        actual_city = actual_cities.pop(actual_cities.index(city))
        path = [actual_city, ]
        # Find nearest neibour
        while actual_cities:
            min_lenght = []
            for next_city in actual_cities:
                min_lenght.append((next_city, abs(complex(city[0], city[1])
                                                 - complex(next_city[0], next_city[1]))))
            # Get closest neibor
            min_lenght.sort(key=operator.itemgetter(1))

            actual_city = min_lenght[0][0]
            lenght += min_lenght[0][1]
            actual_cities.pop(actual_cities.index(actual_city))
            path.append(actual_city)

        # Complete the trip with the first city
        path.append(city)

        lenghts.append((tuple(path), path_lenght(path)))

    # Get minimum
    lenghts.sort(key=operator.itemgetter(1))
    return lenghts[0]

if __name__ == '__main__':
    for i in range(3, 10):
        print 'Number of cities: ', i
        cities = random_cities(i)

        time1 = datetime.datetime.now()
        path2, lenght_neighbor = find_path_nearest(cities)
        time2 = datetime.datetime.now()
        print path2, lenght_neighbor
        time_neighbor = time2 - time1
        print 'Time neighbor: ', time_neighbor

        time1 = datetime.datetime.now()
        path1, lenght_brute = find_path_bruteforce(cities)
        time2 = datetime.datetime.now()
        print path1, lenght_brute
        time_brute = time2 - time1
        print 'Time brute force: ', time_brute
        print 'Diff: ', float(lenght_neighbor - lenght_brute) / lenght_brute * 100, '%'

The time spend on each is brutally different, specially as the number of cities grow. With more than 9 cities, the time grows at some point when my computer has to take more than minutes to compute the brute force approach, while the neighbor approach will still be below the 1/100 of a second. The error  also grows, being the same on small number of cities, but getting afar fast when the number of cities grow. At 9 cities, the error is about a 20-30%

$7.11 in four prices and the Decimal type


There’s an fun and not very difficult programming exercise, presented on Programming Praxis . The problem is easy to describe:

“A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.”

Ok, the problem is easy to get on a brute force approach. Just try all the combinations, see their sum and multiplication, and find the one that gets it. Whell, easy, but a lot of work to do for a modern computer. Get all the possible combination will be an amazingly great number of combinations (711 possible prices to the power of 4 gives 255,551,481,441 possibilities).

To simplify the calculations, we change the domain from 7.11 to 711, so get get the prices multiplied has to be equal to 711,000,000.

The proposed solution is to consider only the prices that are divisors of 711,000,000, reducing drastically the combinations.

I’ve tried a solution using a Python code, as follows. I added some “generic” touch and the Decimal type to avoid problems with float comparison:

def solve(dec_number, step, number_of_numbers):

integer_range = int(dec_number * 100)
all_numbers = [ Decimal(i) * step for i in range(1, integer_range) ]
multiples = 1 / reduce(operator.mul, [step] * (number_of_numbers))
correct_numbers = [ i for i in all_numbers if (dec_number * multiples % i) == 0 ]

def check(numbers):
"""Check the numbers added and multiplied are the same"""
return sum(numbers) == dec_number == reduce(operator.mul, numbers)

#it's naive to get only the combinations, but it's faster
posibilities = combinations(correct_numbers, number_of_numbers)
filter_mul = ifilter(check, posibilities)

return list(filter_mul)

t1 = time.time()
print solve(dec_number=Decimal('7.11'), step=Decimal('0.01'), number_of_numbers=4)
t2 = time.time()
print "time 7.11: ", ((t2 - t1))

and that gives an amazing time of 96 seconds! That’s clearly a lot. After that, I tried a completely different approach, just a not-so-brute solution, making a big loop with some tweaks to avoid all the combinations.

def calc():
     for w in range(711):
         for x in range(711 - w):
             for y in range(711 - w - x):
                 z = 711 - x - y - w;
                 if (w * x * y * z == 711000000):
                     print "w: %d x: %d y: %d z: %d" % (w, x, y, z)

     #Measuring time
 t1 = time.time()
 calc()
 t2 = time.time()
 print "time loop: ", ((t2 - t1))

For a total time of 34 seconds! And all the solutions! (which, BTW are the same, just reordered)

After some profiling, I’ve get the solution to this strange behavior. The use of the Decimal type.

LESSONS LEARNED:

- Decimal seems to be a “little” unefficient.

- Try to use basic types when making a lot of calculations.

- Don’t understimate the power of brute force, combined with low level languages. I’ve tried the same loop on C, and takes about 1/3 seconds.