~Nacho/blog

Carlos shared a pretty cool link with me this morning. Codility is a platform to help recruiters and contractors to test developers before hiring them. Both the idea and the execution are beautiful. They’ve done a stunning job.

As part of my visit to the page I gave a try to the demo test. As it was funny to solve it, I’m sharing my solution here. The problem was quite easy. It reads like this:

Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0

3 is an equilibrium index, because:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6 is also an equilibrium index, because:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.

Assume the sum of zero elements is equal zero. Write a function int equi(int[] A); that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long.

They gave me 30 minutes to design, code and test my solution. Here it is (tests omitted):

import operator
 
def equi(A):
  if A is None or len(A) == 0:
    return -1
  lsum = index = 0
  rsum = reduce(operator.add, A[1:], 0)
  while True:
    if lsum == rsum:
      return index
    index += 1
    if index == len(A):
      return -1
    else:
      lsum += A[index-1]
      rsum -= A[index]

It scores 100/100 and runs in linear time (that’s tricky because O(n²) algorithms will cause performance tests to fail) :)

This introduction is followed by some Python code (function evaluate_postfix_expr) to evaluate expressions (only integers, but may be extended with ease) in Reverse Polish Notation (RPN). Some simple tests are also included in the bundle.

I agree it’s a little useless, but I thought it might be useful for someone (CS students maybe?). If you want to examine the stack in each iteration you only have to turn debugging on. That can be accomplished by changing logging.INFO to logging.DEBUG (line 7).

Copy, distribute or do whatever you want with it. It’s released in the public domain.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#!/usr/bin/env python
 
import logging
import re
import unittest
 
logging.basicConfig(level=logging.INFO)
 
operators_table = {'+': int.__add__, 
             '-': int.__sub__,
             '*': int.__mul__,
             '/': int.__div__,
             '^': int.__pow__}
 
class ExpressionError(Exception):
    def __init__(self, message):
        self._message = "Expression error: %s" % message
    def _get_message(self): 
        return self._message
    message = property(_get_message)
 
class TestEvaluation(unittest.TestCase):
    def test_correct(self):
        self.assertEqual(666, evaluate_postfix_expr("666"))
        self.assertEqual(2+3-6, evaluate_postfix_expr("2 3 + 6 -"))
        self.assertEqual(2*3+4, evaluate_postfix_expr("2 3 * 4 +"))
        self.assertEqual(2*(3+4), evaluate_postfix_expr("2 3 4 + *"))
        self.assertEqual(3**4, evaluate_postfix_expr("3   3  *     3  *      3 *"))
        self.assertEqual((7/2)**4, evaluate_postfix_expr("7 2 / 4 ^"))
        self.assertEqual((2**3)**4, evaluate_postfix_expr("2 3 ^ 4 ^"))
        self.assertEqual(5+((1+2)*4)-3, evaluate_postfix_expr("5 1 2 + 4 * 3 - +"))
 
    def test_malformed(self):
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "+")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "2 +")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "+ 2 2")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "2 2")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "2 2 + -")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "a 2 -")
 
def evaluate_postfix_expr(expr):
    atoms = re.split(r"\s+", expr)
    stack = [] 
    for atom in atoms:
        if atom in ["+", "-", "*", "/", "^"]:
            try:
                op2 = stack.pop()
                op1 = stack.pop()
            except IndexError:
                raise ExpressionError("Too few operands (unbalanced)")
            logging.debug("Calculating %d %s %d" % (op1, atom, op2))
            atom = operators_table[atom](op1, op2)
        else:
            try:
                atom = int(atom)
            except ValueError:
                raise ExpressionError("Unable to parse '%s' as integer" % atom)
 
        try:
            stack.append(atom)
        except MemoryError:
            raise ExpressionError("Too long expression")
 
        logging.debug("Pushed element %d. Stack status: %s" % (atom, stack))
 
    if len(stack) == 1:
        return stack.pop()
    else:
        raise ExpressionError("Too many operands (unbalanced)")
 
if __name__ == "__main__":
    unittest.main()

• Arquitectura y Tecnología de Computadores [+]
• Redes
• Procesadores de Lenguaje [+++]
• Inteligencia Artificial [+++]
• Ingeniería del Software I [+]
• Sistemas Electrónicos I [++]
• Informática Gráfica

[+] interesting [++] fun [+++] cool

Update (7/24): Finally 4/5, IS1 passed as well (with honors, btw).

Mwhahahaha!

Taking a look to one of the IRC channels where I’m habitual, I found an URL to a Debian wiki page, where people is adding their names because they will have problems to attend Debconf7 in the planned date. By chance I’m in this set, exams are planned for this date.

Please consider add yourself to this list if it is impossible for you attend DebConf7 in June.

Dear Rastal, here it is a funny partial hackergotchi for you:

It’s a pity that the photographer wasn’t wise taking the original picture.

Is Osnews taking the wrong way?

Sure sir, my personal computer has got about googolplex GiB RAM, and it’s ready.

Note: googolplex = 10^googol

Ya son horas más avanzadas que el post de ayer, hoy os escribo desde la charla de Ruby on Rails, la asistencia se mantiene constante, mi charla creo que ha ido bien, la gente parecía no dormirse.

Quizás echamos de menos este año también asistencia de la prensa, aunque en mi humilde opinión prefiero que no nos hagan entrevistas antes de que nos las hagan pero no reflejen nuestra opinión.

Ya estamos en el ecuador de esta sexta edición aún queda la mejor parte según mi punto de vista, mañana si me acuerdo os haré una pequeña reseña desde las Jornadas gracias a las bondades de la red Wi-Fi.

Currently writing from my new computer, running Gentoo Linux.

My domain has been added to No-www campaing. After reading their guidelines I agree with all ideas exposed in the website. In my humble opinion www subdomain, normally used to concentrate the main web content of a website, is deprecated. More information available in the campaing’s website.

At this moment, criptonita.com has been qualified as Class C domain, the most stringent compliance level.