The boys at
Programming Throwdown have drawn attention to a post by
Santiago L. Valdarrama provocatively titled
Five programming problems every Software Engineer should be able to solve in less than 1 hour.
Is that one hour each or one hour altogether? Doesn't say. Anyway I'm curious because it's a chance for me to prove that I really am as clever as I think I am. That's the draw of a title like that, surely? You say: I will either solve the problems, thereby proving that other software engineers who can't solve them are idiots: or else I can't solve them, proving that the guy who posted the problem is the idiot. Either way you can't lose...
Also the Throwdown team have mentioned a substitute text shell called
Babun that they reckon is worth checking out.
This Babun shell comes with Python. I've never tried Python so this is a good excuse. I understand it is supposed to be easy to pick up, but also people do write serious systems with it. Python has been sitting in the background of the programming world for years patiently waiting for Perl to die, and now it finds that Ruby has appeared from nowhere and claimed its patch.
Anyway, the first task is to write code that works out the sum of a list of numbers three ways, by a
for loop, by a
while loop, and by
recursion.
So, here goes.
Start up Python from the fancy new shell:-
{ ~ } » python ~
Python 2.7.8 (default, Jul 28 2014, 01:34:03)
[GCC 4.8.3] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
Python 2.7 classes itself as "legacy" - the current thinking is in Python version 3. However.
Create a list of numbers with a nice easy sum:
>>> numbers = [50,25,12,7,3,2,1]
Now to use
for - well, looks like Python has several way to use a
for construction. First we can
for over a
range of consecutive numbers. Note that in Python, lists start at element zero. Thank you, note taken. The
range you specify starts at the first number and stops before the second number you specify. That makes it easy: to scan over all the elements of the array we do this:
>>> sum = 0
>>> for ix in range(0, len(numbers)):
... sum = sum + numbers[ix]
...
>>> print sum
100
Using
sum to accumulate the result each time of course.
>>> is the Python shell prompt at the top level, and
... is the prompt when you are inside a multi-line construction. Block structure is defined in the syntax
by the indentation. Bold move.
There is also a
for construction that gives you the elements in a collection without your having to pick an index, so alternatively we can say this:
>>> sum = 0
>>> for n in numbers:
... sum = sum + n
...
>>> print sum
100
>>>
To run over the list with a
while construction I'll use two index variables,
ix to step through and
iy to be the first index I don't want to see, which will be the length of the list. I set this before I go into the loop as I don't want to have to evaluate the
len() function more than once if I don't have to.
So:-
>>> sum = 0
>>> ix = 0
>>> iy = len(numbers)
>>> while ix < iy:
... sum = sum + numbers[ix]
... ix = ix + 1
...
>>> print sum
100
>>>
Yes, I derive an obscure comfort from naming variables after Z80 registers. It's a bit like making a drink in a favourite cup or taking notes with a favourite pen. You just know where you are, you see.
Now,
lst[0] corresponds to
(CAR lst) in Lisp. You get the first element from the list. In addition to writing
lst[ix] to pick a specific element you can get sub-lists. For example
lst[1:] returns the list of elements starting after the zero element in the list - so this corresponds to
(CDR lst) in Lisp. With these two in mind we can write the recursive solution that looks just like a Lisp one:
>>> def sum_list(ns):
... if ns == []:
... return 0
... else:
... return ns[0] + sum_list(ns[1:])
...
>>> print sum_list(numbers)
100
>>>
Hey, we are Python-enabled. Cool. Spam.
Did that take an hour? I don't know, I lost track of time watching Babun download.
