Problem 22 (Project Euler) python 2.7.x solution

One of my favorite online resources for programming challenges is called Project Euler . More than certain you’ve heard about it, otherwise what would be the reason to visit this page.

Problem 22 is a simple to medium challenge . In order to solve it you’ll need basic programming knowledge: reading a line from a file, apply some functions on a string, lambda functions and python list comprehension .

Here is the requirment:

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?

And this was my “condensed” solution:

There’s no need for additional comments, the code is pretty straight-forward.

Credit Card Validation (Python 3.x)

If you ever wondered how Credit Card Numbers, IMEI Numbers or Canadian Social Insurance Numbers are validated you can take a look at this Programming Praxis article . It’s all about a simple, tiny, patented (now public domain) algorithm invented by IBM’s computer scientist Hans Peter Luhn .

The validation is pretty simple, and works this way:

1. Given a number we will consider the last digit a check-digit .
2. Starting from the check digit backwards we will multiply by 2 every even digit .
3. We will sum all digits (both doubled and undoubled) .
4. If the sum is a multiple of 10 then the number is valid, else is invalid .


5 4 3 2 9 8 3 7 6
5 8 3 4 9 (1+6) 3 (1+4) 6 = 50 (which is a muliple of 10, thus the number is valid)

I’ve written the implementation of this simple algorithm using python 3.x . The solution can become rather elegant if we use the functional programming features that python offers us:

And the output:

Observations: Read More

Bytelandian gold coins

A nice programming challenge (easy/medium difficulty) comes from and it is being called: “Bytelandian gold coins”.

From this exercise I’ve learnt that the most elegant solutions are recursive .

In this challenge our task is to resolve the currency issues in a imaginary country, Byteland:

Each Bytelandian gold coin has an integer number written on it. A coin n
can be exchanged in a bank into three coins: n/2, n/3 and n/4.
But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange
rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars
you can get for it?

The input will contain several test cases (not more than 10). Each
testcase is a single line with a number n, 0 < = n <= 1 000 000 000. It is the number written on your coin. For each test case output a single line, containing the maximum amount of American dollars you can make.

(…more here)

My first attempt (which seemed natural at that point) was working “flawlessly” on my local machine but codechef was insistingly reporting Time Limit Exceed: Read More

RPN Calculator (using Scala, python and Java)

1. Description

One of the earliest Programming Praxis challenges is called RPN Calculator . Our task is to write a RPN module capable of evaluating simple RPN expressions and return the right result . The exact requirment:

Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3 / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds with 85.2974. The program should read expressions from standard input and print the top of the stack to standard output when a newline is encountered. The program should retain the state of the operand stack between expressions.

Programming Praxis

The natural algorithm to resolve this exercise is stack-based :

The first step is to tokenize the expression .If the expression is “19 2.14 + 4.5 2 4.3 / – *” after the tokenization the resulting structure will be an array of operands and operators, for example an array of Strings {“19”, “2.14”, “+”, “4.5”, “2”, “4.3”, “/”, “-“, “*”} .
At the second step we iterate over the array of tokens .If the token:

  • Is an operand (number, variable) – we push in onto the stack .
  • Is an operator (we apriopri know the operator takes N arguments), we pop N values from the stack, we evaluate the operator with those values as input parameters, we push the result back onto the stack .
If the RPN expression is valid, after we apply the previous steps, the stack would contain only one value, which is the result of the calculation .

2. Implementation

I will implement the solutions for this challenge using three different languages: Scala, python and Java .

2.1 Scala Solution

And if we compile and run the above code: Read More

How to get the active process list on a Linux machine using python

To retrieve the active process list on a Linux machine we will use the subprocess module . This module will allow us to create new subprocesses, connect to their input / output / error pipes, and eventually retrieve their exit codes .

It offers us a higher level and cleaner approach by defining only one class: subprocess.Popen(), intended to replace the functionality offered by methods such as: os.system(), os.popen() or os.popen2() .

To obtain the active processes and their associated information (USER, PID, CPU, MEM, TTY, STAT, TIME, COMMAND, etc.) we will spawn a ps aux subprocess, connect to its output pipe and parse the results .

But first let’s analyze a little the output of ps aux :

Our first step will be to create a data structure capable of encapsulating the above information . We will write the Proc class that will wrap all the process meta-information present in the ‘ps aux‘ output :

A list of Proc objects will probably do the job . Read More