Tech Tuesday: Algorithms (Implementations)

Last week in Tech Tuesday, we continued our introduction to algorithms by looking at a first implementation.  As a reminder we are trying to find out whether a sequence of integers contains a number that is repeated four times in a row. Here is that Python code together with a bug fix for dealing with empty number sequences:

# numbers = [1, 15, 7, 3, 8, 8, 19, 5, 12, 8, 2, 6, 8]
numbers = [1, 15, 8, 8, 8, 8, 7, 3, 19, 5, 12, 2, 6]

counter = 1
if len(numbers) > 0:
    prev = numbers.pop()

while len(numbers) > 0 and counter < 4:
    next = numbers.pop()
    if prev == next: 
        counter = counter + 1
    else:
        counter = 1
        prev = next

if counter == 4: 
    print "Found four times repeated number"
else: 
    print "No four times repeated number found"

I will now show implementations in a number of different languages.  These have been written specifically to stay as close as possible to the original English language description of the algorithm.  Or put more starkly: these are not the best possible code in any of these programming languages (including the Python example).  There are ways to solve the problem that are more idiomatic for the respective language.  But for now the main goal is to show that understanding which algorithm solves a problem is more important than any particular language.

From Python I decided to go to Javascript next.  Obviously that required some syntactic changes, such as adding var to define variables, semicolons at the end of lines and parentheses to enclose blocks of code (the first two of these are somewhat optional in Javascript)

# var numbers = [1, 15, 7, 3, 8, 8, 19, 5, 12, 8, 2, 6, 8];
var numbers = [1, 15, 8, 8, 8, 8, 7, 3, 19, 5, 12, 2, 6];

var counter = 1;
var index = 0;
var prev, next;
if (numbers.length > 0) { 
    prev = numbers[index++];
}

while (index < numbers.length && counter < 4) {
    next = numbers[index++];
    if (prev == next) { 
        counter++;
    }
    else {
        counter = 1;
        prev = next;
    }

if (counter == 4) { 
    print("Found four times repeated number");
}
else { 
    print("No four times repeated number found");
}

You can see this code running here.  In addition to the syntactic changes, because Javascript doesn’t have a list data type, I chose to use an array which required introducing an additional index variable to let us move through that array (note: arrays are available in Python as well of course and so we could go back and make the Python code work that way as well).

From Javascript, the next language I decided to use was PHP.  That turns out to be an easy change: just switch the var declarations to a $ preceding the variable name and use array() to initialize the number sequence (run it)

# $numbers = [1, 15, 7, 3, 8, 8, 19, 5, 12, 8, 2, 6, 8];
$numbers = [1, 15, 8, 8, 8, 8, 7, 3, 19, 5, 12, 2, 6];

$counter = 1;
$index = 0;
$prev, next;
if (count($numbers) > 0) { 
    prev = $numbers[$index++];
}

while ($index < count($numbers) && $counter < 4) {
    $next = $numbers[$index++];
    if ($prev == $next) { 
        $counter++;
    }
    else {
        $counter = 1;
        $prev = $next;
    }
}

if ($counter == 4) { 
    print("Found four times repeated number");
}
else { 
    print("No four times repeated number found");
}

Next up I decided to provide an implementation in C.  I went back and based that on the Javascript code because most of what I had to do was replace the var declarations with int (see the discussion of data types).  Here is the C code (run it)

int numbers[13] = {1, 15, 7, 3, 8, 8, 19, 5, 12, 8, 2, 6, 8};
/* int numbers[13] = {1, 15, 8, 8, 8, 8, 7, 3, 19, 5, 12, 2, 6}; */
   
int counter = 1;
int index = 0;
int prev, next;
int length = sizeof(numbers)/sizeof(int);

if (length > 0) { 
    prev = numbers[index++];
}
 
while (index < length && counter < 4) {
    next = numbers[index++];
    if (prev == next) counter++;
    else {
        counter = 1;
        prev = next;
    }
}
 
if (counter == 4) 
    printf("Found four times repeated number");
else 
    printf("No four times repeated number found");

The only other salient change is that in C we have to explicitly state up front how many numbers we will be looking at when we initialize the array.  I then use sizeof to find the length of that array so that if the array were to come from some other initialization process the remaining code would do just fine.

So far the syntax and reserved words of the languages used are amazingly similar and our code looks and feels much the same.  Again that’s because I purposefully avoided idioms from the respective languages.  Now just for the fun of it here is an implementation of this algorithm in Lisp.  This is written in completely non-idiomatic Lisp and without obvious shortcuts to follow the English language outline closely. I want to bring home the point that an understanding of how computation works is far more important than learning any one particular language.  So here is the Lisp code (run it)

; (setq numbers '(1 15 7 3 8 8 19 5 12 8 2 6 8))
(setq numbers '(1 15 8 8 8 8 7 3 19 5 12 2 6))

(setq counter 1)
(if (> (list-length numbers) 0) 
    (progn (setq prev (car numbers)) 
           (setq numbers (cdr numbers))))

(loop
    while (and (> (list-length numbers) 0) (< counter 4))
    do
        (setq next (car numbers))
        (setq numbers (cdr numbers))
        (if (eql prev next) 
            (setq counter (+ counter 1))
            (progn (setq counter 1) (setq prev next))))

(if (eql counter 4)
    (print "Found four times repeated number")
    (print "No four times repeated number found"))

It will take a second to get past the syntax of parenthesis and the somewhat odd keywords (car and cdr? see if you can figure out from the code what they do).  But then the code is actually is quite easy to follow because it mimics what all the other code examples do closely.

In upcoming posts we will learn more about different ways to approach this same problem.  By that I mean both other algorithms and more idiomatic implementations.  The key take away though for now should be that for a company to say that they are looking for a “python programmer” is a lot like saying they are looking for a “Black & Decker furniture maker.”

Enhanced by Zemanta

Posted: 13th November 2012Comments
Tags:  tech tuesday programming algorithms implementation

Newer posts

Older posts

blog comments powered by Disqus
  1. pressbreaktest reblogged this from continuations
  2. awasim reblogged this from continuations
  3. continuations posted this

Newer posts

Older posts