programming praxis

Credit Card Validation (Python 3.x)

April 9, 2011September 10, 2013 Andrei Ciobanu Leave a comment

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 .

Example:

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:

def luhn_check(num):
    ''' Number - List of reversed digits '''
    digits = [int(x) for x in reversed(str(num))]
    check_sum = sum(digits[::2]) + sum((dig//10 + dig%10) for dig in [2*el for el in digits[1::2]])
    return check_sum%10 == 0

if __name__ == "__main__":
    print(luhn_check(543298376))

def luhn_check(num):

''' Number - List of reversed digits '''

digits = [int(x) for x in reversed(str(num))]

check_sum = sum(digits[::2]) + sum((dig//10 + dig%10) for dig in [2*el for el in digits[1::2]])

return check_sum%10 == 0

if __name__ == "__main__":

print(luhn_check(543298376))

And the output:

True

True

Observations: Read More

RPN Calculator (using Scala, python and Java)

January 3, 2011September 10, 2013 Andrei Ciobanu 1 Comment

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

import scala.collection.mutable.Stack
import scala.io.Source
import java.lang.Double.parseDouble

/**
* RPN Calculator .
*
* @author Andrei Ciobanu
* @date JAN 2, 2011
**/

object RPNCalc {
	// Maps an operator to a function .
	val ops = Map("+" -> ((_:Double) + (_:Double)),
				  "-" -> (-(_:Double) + (_:Double)),
				  "*" -> ((_:Double) * (_:Double)),
				  "/" -> (1/(_:Double) * (_:Double)))

	// Evaluate RPN expr (given as string of tokens)
	def evalTokens(tokens: Array[String]) : Double = {
		val stack = new Stack[Double]
		tokens.foreach(tok => {
			if (ops.contains(tok)) stack.push(ops(tok)(stack.pop, stack.pop))
			else stack.push(parseDouble(tok))
		})
		stack.pop
	}

	// Main	function
	def main(args: Array[String]) = {
		// Read line by line from stdin + tokenize line + evaluates line
		Source.fromInputStream(System.in).getLines.foreach(l =>
			printf("exp=%2.2fn", evalTokens(l.split(" "))))
	}
}

import scala.collection.mutable.Stack

import scala.io.Source

import java.lang.Double.parseDouble

/**

* RPN Calculator .

* @author Andrei Ciobanu

* @date JAN 2, 2011

**/

object RPNCalc {

// Maps an operator to a function .

val ops = Map("+" -> ((_:Double) + (_:Double)),

"-" -> (-(_:Double) + (_:Double)),

"*" -> ((_:Double) * (_:Double)),

"/" -> (1/(_:Double) * (_:Double)))

// Evaluate RPN expr (given as string of tokens)

def evalTokens(tokens: Array[String]) : Double = {

val stack = new Stack[Double]

tokens.foreach(tok => {

if (ops.contains(tok)) stack.push(ops(tok)(stack.pop, stack.pop))

else stack.push(parseDouble(tok))

})

stack.pop

}

// Main function

def main(args: Array[String]) = {

// Read line by line from stdin + tokenize line + evaluates line

Source.fromInputStream(System.in).getLines.foreach(l =>

printf("exp=%2.2fn", evalTokens(l.split(" "))))

}

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

ROT13 (Caesar Cipher)

October 5, 2010September 10, 2013 Andrei Ciobanu Leave a comment

In this ProgrammingPraxis challenge we have to build a simple Caesar Cipher with a special property, called rot13 :

ROT13 (“rotate by 13 places“, sometimes hyphenated ROT-13) is a simple substitution cipher used in online forums as a means of hiding spoilers, punchlines, puzzle solutions, and offensive materials from the casual glance. ROT13 has been described as the “Usenet equivalent of a magazine printing the answer to a quiz upside down”.ROT13 is an example of the Caesar cipher, developed in ancient Rome. (Wikipedia)

Applying ROT13 to a piece of text merely requires examining its alphabetic characters and replacing each one by the letter 13 places further along in the alphabet, wrapping back to the beginning if necessary. A becomes N, B becomes O, and so on up to M, which becomes Z, then the sequence continues at the beginning of the alphabet: N becomes A, O becomes B, and so on to Z, which becomes M. Only those letters which occur in the English alphabet are affected; numbers, symbols, whitespace, and all other characters are left unchanged. Because there are 26 letters in the English alphabet and 26 = 2 × 13, the ROT13 function is its own inverse. (Wikipedia)

Write a function that takes a string and returns the ROT13 version of the string; you may assume that the character set is ascii. What is the meaning of “Cebtenzzvat Cenkvf vf sha!” .

The transition table for rot13:

Examples of transitions:

The Wall	Gur Jnyy
Smoke on the water	Fzbxr ba gur jngre

Initially I wanted to resolve the challenge in a functional programming language. Given the fact that my Haskell skills are very low, I’ve tried to write a functional approach in python . The results… lesser readability, fewer lines of code & fewer minutes:

from string import letters, lowercase, uppercase

numlet=26
num=13
llist = lambda let : [[let[x], let[(x + num) % numlet]] for x in range(numlet)]
shifted = dict(llist(uppercase) + llist(lowercase))

def get_shifted(text):
    return "".join([shifted[s] if s in letters else s for s in text])
if __name__ == '__main__':
    print get_shifted("Cebtenzzvat Cenkvf vf sha!")

from string import letters, lowercase, uppercase

numlet=26

num=13

llist = lambda let : [[let[x], let[(x + num) % numlet]] for x in range(numlet)]

shifted = dict(llist(uppercase) + llist(lowercase))

def get_shifted(text):

return "".join([shifted[s] if s in letters else s for s in text])

if __name__ == '__main__':

print get_shifted("Cebtenzzvat Cenkvf vf sha!")

And the output: