Categories
Software

Python II: Fibonacci Sequence

Tim’s second exercise (here’s the first):

Write a recursive function that calculates the value of Fibonacci numbers. These are your acceptance criteria:

  • Calculating fib(250) must return 7896325826131730509282738943634332893686268675876375
  • The function must use recursion. No intermediary data structures, etc.
  • The implementation must be written in pure python – no C extension modules, that’s cheating.
  • The function must calculate the 250th Fibonacci number in under one second.

    You will get extra points if:

  • You can also demonstrate a proof for the Reciprocal Fibonacci constant, meeting the following conditions
    • Your proof must also run in under one second
    • Your proof must not duplicate any of the concerns addressed by your original Fibonacci function implementation.
    • Your proof is allowed to call into the Fibonacci function though!

The Reciprocal Fibonacci constant is defined as:

P(F) = Sum[k = 1..infinity] 1/F(k) = 3.35988566…

Where F is a Fibonacci number

Here’s a couple of hints about things to look for:

  • Memoization
  • Function decorators

I haven’t tried the extra credit section yet, but this is what I came up with. Again, starting with a naive solution with some doctest tests:

#!/usr/bin/env python

"""
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
"""
def fib(n):
	if n <= 2:
		return 1
	else:
		return fib(n-2) + fib(n-1)

def _test():
   import doctest
   doctest.testmod()

if __name__ == "__main__":
   _test()

Well that seems to work OK. Now, try adding a test for the 250th number:

>>> fib(250)
7896325826131730509282738943634332893686268675876375

And wait … and wait …

No, doesn't look like that's going to return any time soon. Of course when you look at what it's doing, the complexity's increasing in the order of 2n or something, which isn't good.

OK, I guess this is where memoisation comes in. After much head-scratching on the train this morning, I came up with this:

fibs = {}

def fib(n):
	if n <= 2:
		return 1
	elif fibs.has_key(n):
		return fibs[n]
	else:
		fibs[n] = fib(n-1) + fib(n-2)
		return fibs[n]

A little tweak to allow it to be called from the command line with the value of n passed as an argument, and here's the final version:

#!/usr/bin/env python
import sys

fibs = {}

def fib(n):
	if n <= 2:
		return 1
	elif fibs.has_key(n):
		return fibs[n]
	else:
		fibs[n] = fib(n-1) + fib(n-2)
		return fibs[n]

def _test():
  import doctest
  doctest.testmod()

if len(sys.argv) > 1:
	print fib(int(sys.argv[1]))
if __name__ == "__main__":
  _test()
fib(master) $ time ./fib.py 250
7896325826131730509282738943634332893686268675876375

real	0m0.280s
user	0m0.161s
sys	0m0.047s

Sorted!

[tags]python, web21c, fibonacci[/tags]

Categories
Software

First stab at Python

Monty Python foot “It is an ex parrot. It has ceased to be.”

No, of course not. I’m talking about the other Python. Not the one with the silly walks, dead parrot and singing lumberjacks, but the one with the idiosyncratic approach to whitespace.

One of the APIs available for the Web21C SDK is Python, and there was recently some concern that we didn’t have enough expertise in the team to continue providing technical support for the Python SDK. A bunch of us have volunteered to start learning the language, and as a first step, Tim set us some homework:

Write a program that processes a list of numbers from 1 to 100. For each number, if the number is a multiple of 3, print “FIZZ”; if the number is a multiple of 5, print “BANG”; otherwise, print the number.

You are *NOT* allowed to use any *IF/ELSE* statements in your code. You can use the list-accessing ternary operator hack, but whilst I’ll accept your homework if you do, you’ll miss out on the prize (alcoholic), which goes to the most concise code (not including whitespace).

Now I have no idea what this mysterious ‘list-accessing ternary operator hack’ might be, but it sounds painful (as does missing out on an alcoholic prize), so it looks like I need to eschew ifs completely.

Since I’ve never written a line of Python in my life, I decided the easiest way to proceed would be to start off by figuring out enough syntax to solve the problem as defined by the first paragraph, then write a test which the simple code passes, then factor out the conditional logic. Normally I’d start with the test, but I think learning a new language is one of the cases where TDD isn’t really appropriate.

So here’s my first working code:

for n in range(1, 100):
	if n % 3 == 0:
		if n % 5 == 0:
			print 'FIZZBANG'
		else:
			print 'FIZZ'
	elif n % 5 == 0:
		print 'BANG'
	else:
		print n

This prints out what you would expect:

PyMate r8111 running Python 2.5.1 (/usr/bin/env python)
>>> fizzbang.py

1
2
FIZZ
4
BANG
FIZZ
7
8
FIZZ
BANG
11
FIZZ
13
14
FIZZBANG
16
...

OK, so far so good. The next step was to find out what the Pythonistas use for unit testing. As a card-carrying BDD and RSpec fan, I was initially interested to see that there’s a PySpec, but at first glance it doesn’t look that great (maybe it’s just that I’m not used to reading Python code). Then I came across the bundled DocTest, and while I’m not entirely convinced by its description on the Wikipedia BDD page as ‘BDD for Python’, it looked ideal for the task at hand.

Here’s the same code, but with the addition of a parameter to specify the number to count up to, and a DocTest test:

#!/usr/bin/env python

"""
Print numbers up to limit, replacing those divisible by 3 and/or 5 with FIZZ
and/or BANG.

>>> fizzbang(20)
1
2
FIZZ
4
BANG
FIZZ
7
8
FIZZ
BANG
11
FIZZ
13
14
FIZZBANG
16
17
FIZZ
19
BANG
"""
def fizzbang(limit):
	for n in range(1, limit + 1):
		if n % 3 == 0:
			if n % 5 == 0:
				print 'FIZZBANG'
			else:
				print 'FIZZ'
		elif n % 5 == 0:
			print 'BANG'
		else:
			print n

def _test():
   import doctest
   doctest.testmod()

if __name__ == "__main__":
   _test()

OK, now to start thinking about the hard bit – getting rid of those ifs. As a first step, I got rid of the nested logic by appending the ‘FIZZ’ and/or ‘BANG’ to a temporary string, then either printing that string, or the original number if it was empty:

def fizzbang(limit):
	for n in range(1, limit + 1):
		out = ''
		if n % 3 == 0:
			out += 'FIZZ'
		if n % 5 == 0:
			out += 'BANG'
		print out or n

At this point, I hit on the idea of using arrays to select either an empty string or the appropriate word:

def fizzbang(limit):
	for n in range(0, limit):
		print ['', '', 'FIZZ'][n%3] + ['', '', '', '', 'BANG'][n%5] or n + 1

Now all that’s left is to remove the limit parameter so the code merely satisfies the original criteria:

for n in range(100):
	print ['', '', 'FIZZ'][n%3] + ['', '', '', '', 'BANG'][n%5] or n + 1

I expect there are other more concise (and no doubt more efficient) solutions – I look forward to seeing what the other ‘pupils’ come up with!

[tags]python,web21c,fizzbang,fizzbuzz[/tags]

Categories
General nonsense Software

What’s your command-line top ten?

Here’s mine:

~ $ history|awk '{a[$2]++} END{for(i in a){printf "%5d\t%s\n",a[i],i}}'|sort -rn|head
  232	git
   82	cd
   30	ls
   20	sudo
   18	rm
   13	./script/server
   12	mate
   11	rake
    7	vi
    7	ssh

Probably slightly skewed by the fact that I was doing a git demo yesterday.

Meme via Simon Brunning.

Categories
Agile BT

InfoWorld Article on BT and Agile

Some time last year I was interviewed by Tom Hoffman for Infoworld, as part of a piece he was writing on BT’s (ongoing) transition to an agile software development model. Here’s the article:

BT: A case study in agile programming

Categories
Uncategorized

Domain Problems

As you may have noticed, kerrybuckley.com has been down for a few weeks now. This was mainly due to incompetence and laziness on my part causing the registration to expire (the hosting’s still fine), but so far the registrar has yet to respond to e-mails and messages on their 75p/min voicemail service.

For now (as you’ve obviously discovered) you can find me at kerry.ontoa.st instead (temporary feed links over on the right, assuming you’re not reading this in an RSS reader, in which case I guess you’d already figured them out). Please pass the word to anyone who might have noticed I was off-air.

Categories
Agile Rants Software

Government IT waste

Money down the drainThere’s an article in today’s Guardian called Not fit for purpose: £2bn cost of government’s IT blunders, with the following summary:

The cost to the taxpayer of abandoned Whitehall computer projects since 2000 has reached almost £2bn – not including the bill for an online crime reporting site that was cancelled this week, a survey by the Guardian reveals.

I have no doubt whatsoever that the government wastes a vast amount on IT contracts, but I think that, by concentrating on the cost of cancelled projects, the article misses the point slightly.

If a project is clearly never going to deliver, it’s far better to cancel it than to fall into the trap of the sunk cost fallacy, and keep pouring money in in the hope that eventually everything will turn out OK in the end.

The real questions for me are ‘are the government’s IT needs being met at the most cost-effective manner?’ and ‘why does it take so long to realise that a project is doomed?’

I don’t know anything about the projects discussed in the article, or about how government IT contracts are handled in general, but I’d be willing to bet that the following guesses aren’t too wide of the mark:

  • Someone decides that a new system is required, and produces a huge list of everything they think it needs to do. This goes out to tender, and the job goes to whoever manages to produce the lowest quote while still giving a reasonably credible impression that they can actually complete the work in the specified time.
  • The contractor goes off and starts work. They talk to the civil servants who are responsible for specifying the system, but probably not to the people who will actually have to use it. They then go off and produce a design, get it signed off, and set up teams to work on all the identified subsystems.
  • Every few months they deliver a progress report, assuring the client that everything’s progressing according to plan. After a year or so the schedule probably slips a bit, but they assure everyone that it’s jsut a blip, and the final delivery won’t be significantly affected (we can always trim the testing phase a little, right?)
  • Because the contract fixed time, cost and scope, there’s only one thing that can be adjusted to keep the project profitable when the estimates turn out to have been optimistic: quality. Of course this ripples forward, with more and more time spent chasing problems caused by poor quality work in existing parts of the system.
  • When (eventually) the first version of the system is delivered, there are integration problems, it doesn’t quite do what the people specifying it actually wanted, and it turns out that large parts of the specification weren’t that important, but some vital features have been missed out altogether. Depending on just how big a disaster it all was, one of two things happens:
    • The project gets cancelled. The contractor moves on to the next lucrative contract, and an enquiry’s set up to investigate the specific reasons for the project failure, completely missing the big picture.
    • The problems are slowly ironed out, and the missing features are added to the requirements for the next release. The contractor rubs its collective hands at the thought of the massive fees they can charge for the change requests, and a huge amount of time is wasted arguing about whether each change is a new feature or a bug request.

I’m not (quite) naive enough to suggest that all these problems could be solved by wholesale adoption of XP, but I get the impression that the government (and the media reporting on these fiascos) isn’t even aware that there is a better way. With major companies adopting an agile approach now (or at least pretending to), how long before the people responsible for spending our taxes wake up?

[tags]government,it,waste,agile[/tags]

Categories
Web 2.0

Valuing Openness

An interesting insight from, of all places, a clip of CSI, where they’re looking at someone’s Twitter feed:

Greg: “Some people just don’t value privacy.”

Archie: “They don’t expect privacy. They value openness.”

I came across the clip purely by accident – it was in the ‘what’s related’ box on Youtube for a clip of psd asking Evan Williams a question at LeWeb.

And on a completely unrelated note, finding Evan’s site for the link above (via his Twitter profile, naturally), I see his comment on Twitter’s elusive business model:

I agree with Fred on this issue. It’s not that we don’t care about the business model or aren’t thinking about it, but, as Fred says: “But every ounce of time, energy, money, and brainpower you spend on thinking about how to monetize will take you away from the goal of getting to scale. Because if you don’t get to scale, you don’t have a business anyway.”

Which kind of ties in nicely with this tweet from JP.

Oh, and looking for that tweet, it appears Twitter now don’t SMS you @replies from people you follow to people you don’t. Maybe it’s worked like that for ages, but I hadn’t noticed before. Which relates slightly to my previous post, and also brings us neatly back to Paul’s question, which is where we came in.

[tags]twitter, privacy, openness, csi, psd, jp[/tags]

Categories
Web 2.0

Modes of Conversation

Tower of BabelThis post has been languishing in my drafts for a while, but JP’s musings on ‘asymmetric tweeting’ reminded me to get it finished.

Before the Internet came along, there was a fairly clear boundary between publishing and conversation. You could reply to a newspaper article via the letters page if you felt strongly enough, but the publisher decided whether to print your comments, and the relationship was still heavily one-sided. Conversations, in turn, could be largely divided into synchronous (face-to-face, telephone etc) and asynchronous (letters, fax and so on).

The more traditional internet communication tools follow a similar pattern: publish a web site; converse synchronously (instant messaging) or asynchronously (e-mail). A new addition was the many-to-many conversation – again either synchronous (IRC) or asynchronous (newsgroups; mailing lists).

With the advent of what I’ll call ‘Web 2.0’ for want of a better term, things start getting a whole lot stranger.

Let’s start with blogs. At first glance a blog is just published content, but what sets it apart is comments and links. Anyone can reply to a blog post, either by commenting on the post itself, or by writing a response on their own blog, and using trackbacks. If it’s a popular blog, you often end up with conversations between commenters which don’t even involve the original poster. With trackbacks, it’s not always obvious to people reading an article that it’s a response to another, so you can end up with several conversations on the same post: one in the comments, and the others in ‘the blogosphere’, held together loosely by hyperlinks. People will read later contributions without necessarily even realising that they’re part of a conversation of sorts. There’s no guarantee that the original poster will even read everything that links back to his post, and reading links to links is even less likely. Similarly many people comment on a blog and never get round to going back to look for replies to their comment (bloggers: please provide RSS feeds for comments on individual posts!)

Then we have the weird and wonderful world of ‘social networks’. Facebook, for example, provides several ways to converse with your friends. There’s personal messaging, which is basically a walled-garden, non-standard e-mail service and not especially interesting. You can write on people’s walls (not to mention superwalls, funwalls and who-knows-what-else-walls), and have ‘wall-to-wall’ conversations. Even ignoring the fact that they’re hidden from the Web at large, these are only semi-public, in that only people who are friends with both of you can see the whole conversation – non-mutual friends can only see one half. Or people can have more ephemeral conversations just using their statuses, which can look very odd to those who are only privy to part of the conversation, or who come in late when the statuses no longer make sense together.

Twitter, for such a simple service, also leads to a surprising variety of conversations. There’s the original simple broadcast “what are you doing?”, and direct private messages (again, not much different from e-mail or SMS), but things get interesting when people use the @username syntax to reply to other messages. As observed by Phil and discussed by JP, this can get confusing (and annoying) when you aren’t following the person being replied to (although watching who your friends reply to can be a good way of finding new people to follow). On the other side of the coin, if you reply to a tweet from someone who doesn’t follow you, they won’t even see your reply, unless they happen to look in the replies tab on the Twitter website (or subscribe to their replies using RSS).

And as if that weren’t complicated enough, what happens when all these tools meet up? Lots of people automatically post their tweets to their Facebook status, or create Facebook links to their blog posts, or aggregate just about everything to Jaiku, and inevitably some people will reply to the link or the second-hand message rather than going back to the source.

So can we cope with all these semi-visible, partly-asymmetrical, multi-homed conversations? We seem to be managing so far, and at least we have the choice. I was reading something recently that I wrote in my student days (when mobiles were for yuppies, and student houses didn’t generally have phones, let alone internet access). A bunch of us from various places were going camping in Wales for the weekend, and apparently there was confusion because someone had sent a letter saying they didn’t know where the campsite was, but it hadn’t arrived in time to send a reply. Life was simpler then, but sometimes the simplicity made things more complicated.

[tags]conversation, facebook, twitter, blogosphere[/tags]

Categories
Java Software

Java ‘Good for Nothing’?

In Language Explorations, Ola Bini (of JRuby fame) suggests that there won’t be any more ‘big languages’, but instead more of a mix-and-match approach, with different languages used for different parts of an application according to their strengths, all running on the JVM (or presumably .NET if you’re on the dark side).

An interesting opinion (which I’ve slightly mischievously taken out of context here) from the article:

In fact, I’m not sure if Java the language is good enough for anything, anymore.

Categories
Software

Happy New Year

JanusSo, that’s 2007 over with. Is it just me getting old, or did the past year go by even quicker than normal?

Amongst other things, 2007 was (for me at least) the year of Ruby. Obviously Rails had already been around for a while, and the language itself even longer, but they both seemed to be popping up all over the place last year, and gaining acceptance where they had previously been ignored as not mature or “enterprisey” enough. It’ll probably still be a while before large companies look at Ruby and Rails in the same way they currently look at Java and J2EE, but at least in my little corner of a large company I was able to spend the whole year writing Rails apps. It doesn’t look like there’s going to be any slacking of the pace in 2008 either, with the last few weeks of 2007 seeing the release of Rails 2.0, RSpec 1.1, Ruby 1.9 and JtestR (the last of which should be cool for Ruby people still stuck in a Java world).

It was also the year of ‘social networking’ websites in general, and Facebook in particular. Halfway through the year they introduced their developers’ API, and the web was awash with people praising their openness. Over the following months people started to realise that that ‘openness’ was very much one way, intended to get your applications running on their platform rather than allowing users to expose their data on the Web, and much of the shine wore off. Of course, most of us still use it now and again (if only to play Scrabulous), and there are a few signs that they’re starting to open the door to the Web ever-so-slightly in the other direction, so we’ll see what happens. There’s also OpenSocial to keep an eye on, of course, with Google so far managing to stay just on the right side of the good/evil line (all-seeing eye notwithstanding).

At the lighter end of the social networking scale, the star of 2007 was undoubtedly Twitter. Never has something so simple and apparently pointless been so intriguing and useful. Their business model (at least in the UK) is still a mystery though.

Some would say that 2007 was the year when Agile Software Development finally crossed into the mainstream. Unfortunately I tend to side more with Simon and Gus, and call it the year of compromised agile. It seems that for many large companies ‘agile’ has just become another buzzword. They talk about ‘enterprise scale agile’ and introduce a few of the easier, non-technical practices (daily stand-ups, retrospectives and so on), and put off making the real changes that are required for a truly agile organisation (co-located self-organising teams, daily customer involvement, devolution of decision-making, genuine focus on business value, an emphasis on technical excellence, test-driven development etc), while persisting with anti-agile behaviours such as outsourcing development, big up-front design, ivory tower architecture and fixed time, scope and budget. Baby steps are great, but there’s an implicit assumption that you take lots of them, instead of a few large ones.

Last but not least, 2007 was, of course, the year of the lolcat!


So what does 2008 hold in store? Unfortunately I didn’t get a crystal ball for Christmas, but here are a few guesses and hopes.

Will 2008 really be the year of Erlang? It seems to be building up the same kind of following (amongst many of the same people) that Ruby had 18 months ago, so who knows? It’s an interesting language, but I still find that the syntax grates.

Perhaps this will be the year when everyone finally realises that ‘Web 2.0’ has become so overloaded as to be meaningless. Sadly, even if that happens we’ll probably just see the buzzword bandits start calling something ‘Web 2.1’ or ‘Web 3.0’, so that’s a battle that’s never likely to be won.

Finally, could it be the year of OpenID and OAuth? If it weren’t for my poor security practices when it comes to personal site registrations, I’d have no chance of remembering account details for the myriad sites I’ve registered on, so wider adoption of OpenID would be nice. Similarly, it’s a pain finding and adding friends in yet another ‘social network’ application. I don’t really want to be handing out my GMail password left right and centre, and OAuth would (amongst other things) provide a neat way to request friends lists from other sites (and of course using OpenID would make it easier to identify people). Personally, I’d prefer it if everywhere just exposed my friends list publicly like Twitter does, or at least gave me that option. If they all used FOAFXFN, so much the better.

Anyway, I ought to post this while it’s still New Year’s Day. Whatever technologies 2008 has in store, I hope it’s a good year for you.

[tags]ruby, rails, rspec, jtestr, facebook, agile, enterprise, compromised agility, lolcats, erlang, new year, 2007, 2008, web 2.0, openid, oauth, foaf[/tags]