Grasshoppers coders: now blogging

A few grasshoppers (term to designate people who visited www.linuxnewbie.org from the sensei days) and myself have started blogging about programming. Check us out at http://blog.ghcoders.net

Reddit: what Digg people will be talking about in two weeks

C++ is a horrible language, says Linus Torvalds, posted to Reddit on September 6th, 2007.

Linus Torvalds hates C++, posted to Digg on September 21st, 2007.

I usually found this “news appearance” pattern: Reddit gets it first, then Digg gets it, then Slashdot. The one exception are Apple stories where those are posted 29 times on Digg in a matter of seconds and all dugg up to the most popular stories, while Reddit gets one submission and it never reaches #1 (mostly because we’re busy upvoting xkcd)

Edit: Oh, and it seems Digg people can’t read articles. They’re all “well for a kernel, C is a better choice than C++.” They’re talking about git, not Linux!

Word numbers

I read about a programming puzzle today on programming.reddit. Here’s the problem:

“If the integers from 1 to 999,999,999 are written as words, sorted alphabetically, and concatenated, what is the 51 billionth letter?”

To be precise: if the integers from 1 to 999,999,999 are expressed in words (omitting spaces, ‘and’, and punctuation[1]), and sorted alphabetically so that the first six integers are

* eight
* eighteen
* eighteenmillion
* eighteenmillioneight
* eighteenmillioneighteen
* eighteenmillioneighteenthousand

and the last is

* twothousandtwohundredtwo

then reading top to bottom, left to right, the 28th letter completes the spelling of the integer “eighteenmillion”.

The 51 billionth letter also completes the spelling of an integer. Which one, and what is the sum of all the integers to that point?

[1] For example, 911,610,034 is written “ninehundredelevenmillionsixhundredtenthousandthirtyfour”; 500,000,000 is written “fivehundredmillion”; 1,709 is written “onethousandsevenhundrednine”.

I’ve thought about this, and I can’t think of an efficient way to solve this. In a world of infinite memory and processor power you would:

1. Generate the numbers from 1 to 999,999,999
2. Apply a number_to_words() function on every number and into a mapping of the form ([number], [number in english])
3. Sort the list on the numbers in english
4. Count characters and sum numbers until character 51,000,000,000 is reached

The problem is that this would take WAY too long and WAY too much memory. I initially thought that a lazy data structure would work, but since you need to sort the list, you need to have all the elements, so you’re kinda screwed anyhow. I made a quick test where I wrote the numbers to a file to save on memory, but I was up to 1.5 GB by the time (± 10 minutes) I reached twentymillion; needless to say I stopped the process right there.

Does anyone have a brilliant idea how this could be solved? Maybe by generating the numbers starting with 8 first, then by 5, then 4, etc.?

Habeus corpus? Not back yet

Grabbed from Reddit, there was a vote in congress to restore habeus corpus. The motion needed a 3/5 majority to be accepted, it failed to get that majority. The site has information on who voted Yea (to restore habeus corpus) and Nay. I put the informations in Vim, and did a couple manipulations. Here’s what I found out:

• Every Democrat voted Yea
• A few Republicans voted Yea
• All Nay votes were from Republicans except for one
• The last Nay vote was from Joe Lieberman

10 signs you’re a Republican congressman

A small list of signs that I, as a Canadian, think fit the republican profile quite well ;)

1. You say that gay people live an immoral and sinful life, but you enjoy the occasional bathroom reach-around.
2. You argue that every life is precious to justify your opposition to abortion, yet you support death penalty and oppose stem-cell research which could potentially save thousands of people.
3. You support the war in Iraq, but you found a way to avoid going to Viet-Nam when it was your time to fight for your country.
4. You present yourself as a pro-family candidate, but you cheat on your wife with the underage babysitter.
5. You speak of America as a beacon of freedom and liberty, but you support every bill that takes away those freedoms and liberties in the name of the global war against terrorism and national security.
6. You say the penalties for consuming marijuana should be more severe, even though you smoked plenty of pot in your youth.
7. Despite overwhelming evidence to support it, you don’t believe in evolution. You do, however, believe in creationism, even if there is not a shred of evidence to support it.
8. You do not hire the best and the brightest, you give jobs to your friends and people who share your point of view.
9. You were opposed to the war in Kosovo during the Clinton administration, citing the lack of clear objectives or an exit strategy and the tragedy to American families, yet you fail to see the irony about the war in Iraq (which you support, as already mentioned.)
10. You think getting a blowjob is grounds for impeachment, but illegal wiretapping, lying to the American people, torture, etc. are just fine and dandy.

Django patch

I wrote and submitted a patch for a ticket in Django’s trac. The newforms library automatically adds a semi-colon to your label names if you use the as_* methods (as_p(), as_table(), as_ul()). I have no idea why this behavior was in there, but this patch, which will hopefully be accepted, adds a suffix parameter to the Form class, so that you can specify which character to use.

A Django template tag for the current active page

An important part of a usable web site is a well-designed navigation bar. Something that any navigation bar should have is an indication of where the user is. Common practices for this include using a bold face for the link, a different color or adding a small icon next to the current section link. To do that, you could include your navigation code in every page and use an “active” class name on the a element to distinguish it from the other links.

<div id="navigation">
    <a href="/">Home</a>
    <a href="/services/">Services</a>
    <a class="active" href="/contact/">Contact</a>
</div>

Writing this in every template quickly becomes a pain in the neck. With Django, an easy solution would be to move this section to a different file, _nav.html for instance, and include it in every page. Another, even better way, would be to make sure that every template extends a base template (a very common practice with Django) and to add the navigation to that base template.

We face a little problem however: how do we know which page we’re on? If you use the render_to_response shortcut, you can give an extra keyword argument, context_instance. If you use the RequestContext class, you can pass more data to the template (the generic views use RequestContext by default, so you don’t have to worry about them.) Here’s how to do it:

## settings.py
TEMPLATE_CONTEXT_PROCESSORS = (
    'django.core.context_processors.request',
)

## views.py
from django.template import ContextRequest

def home(request):
    return render_to_request('home.html', {}, context_instance=RequestContext(request))

You can now use the request template variable in home.html and its parent templates, which should include your base template. The HttpRequest object has an attribute, path, which contains the current URL (starting after the host name). We can now add the active class to the link for the current section:

<div id="navigation">
    <a class="{% ifequal request.path "/" %}active{% endifequal %}" href="/">Home</a>
    <a class="{% ifequal request.path "/services/" %}active{% endifequal %}" href="/services/">Services</a>
    <a class="{% ifequal request.path "/contact/" %}active{% endifequal %}" href="/contact/">Contact</a>
</div>

This code has two problems: (1) it’s really ugly (it’s probably all that should matter to make you want to rework this code), and (2) imagine that there are subsections under the services section, /services/web-hosting/, /services/tech-support/, etc. When you’re under one of those subsections, the link to the services section will not be highlighted. We’ll fix that by using a custom template tag that will check if request.path begins with a given string.

## tags.py
@register.simple_tag
def active(request, pattern):
    if request.path.startswith(pattern):
        return 'active'
    return ''

<!-- navigation -->

{% load tags %}
<div id="navigation">
    <a class="{% active request "/" %}" href="/">Home</a>
    <a class="{% active request "/services/" %}" href="/services/">Services</a>
    <a class="{% active request "/contact/" %}" href="/contact/">Contact</a>
</div>

Ah, the code is much nicer and now if we go to /services/web-hosting/, the services link will still be highlighted. Another link will be highlighted unfortunately: the home link will ALWAYS be highlighted, because every path begins with a slash. Let’s change the implementation of the active tag slightly to use regular expressions and we’ll also change the calls to {% active %}

## tags.py
@register.simple_tag
def active(request, pattern):
    import re
    if re.search(pattern, request.path):
        return 'active'
    return ''

<!-- navigation -->

{% load tags %}
<div id="navigation">
    <a class="{% active request "^/$" %}" href="/">Home</a>
    <a class="{% active request "^/services/" %}" href="/services/">Services</a>
    <a class="{% active request "^/contact/" %}" href="/contact/">Contact</a>
</div>

Nice! Now it’s how we want it. Home will be highlighted only when we’re viewing the / URL, the subsections still work and the code is still pretty cute.

I’m #1!

Yay! Thanks to all the star-struck reddit people who made my last post the top post on WordPress.com :-)

Celebs of Reddit

One reason I prefer Reddit to Digg is because it seems people know each other better in the comment sections, especially in the section I hang out the most in, the programming section. More than that, some known developers hang there and shoot the breeze with the rest of us. Here’s an incomplete list of those developers:

• jacobian: Jacob Kaplan-Moss, co-lead developer of Django, a Python web framework
• mr_chromatic: chromatic, a well-known Perl hacker and author, currently involved in the Parrot project
• slava_pestov: Slava Pestov, the initial developer of jEdit and current lead developer of the Factor language
• dons: Don Stewart, one of the developer of xmonad, a tiling window manager written in Haskell
• paulgraham: Paul Graham, the author of two Common Lisp book, the founder of ViaWeb and partner at Y Combinator. Currently writing a programming language, Arc
• jrockway: Jonathan Rockway, lead developer of Catalyst, a Perl web framework
• avibryant: Avi Bryant, lead developer of Seaside, a Smalltalk web framework and of DabbleDB, an online spreadsheet-database application
• augustss: Lennart Augustsson, a well-known Haskell hacker, winner of 3 IOCCC and of the 1999 ICFP Judge’s Prize for which he was declared an extremely cool hacker
• xkcd: Randall Munroe, not known for a program he wrote, rather for the very popular XKCD comic, a favorite among redditors

What other celebrities hang on reddit?

Update:
Contributed by others:

• effbot: Frederik Lundh, Python hacker responsible for the Python Imaging Library and ElementTree.
• zzzeek: Mike Bayer, creator of the Python ORM SQLAlchemy and of the Mako templating language.
• mjd: Mark Jason Dominus, well-known Perl hacker responsible for many CPAN modules and author or the book Higher-Order Perl
• spolsky: Joel Spolsky, a well-known author of programming litterature and blogger, he worked on Microsoft Excel in the early nineties.

Page navigation in Django

Django is cool, it gives you free pagination: you say “I just want 20 articles per page” and it’ll split your result set in sets of 20 objects. The thing that’s missing is a template tag to add navigation between these pages. I wrote a small sub-template, which depends on two of my own template tags, to automatically add page navigation. First, here are the template tags needed:

@register.simple_tag
def pagination_get_string(get_dict, page_num):
    import copy
    get = copy.deepcopy(get_dict)
    get['page'] = page_num
    return '?' + get.urlencode()

@register.filter
def range1(n):
    try:
        return range(1, int(n) + 1)
    except ValueError:
        return []

Quick note about these two. pagination_get_string copies the current GET string and adds page=x to it. This ensures that if your pagination occurs in a search view with several parameters, moving between pages keeps the same parameters. range1 is pretty self-documenting, it returns a list from 1 to n (inclusively). Now, here is the sub-template:

{% load wsftags %}
Page:
{% for page_num in pages|range1 %}
    {% ifequal page_num page %}
        {{ page_num }}
    {% else %}
        <a href="{% pagination_get_string request.GET page_num %}">{{ page_num }}</a>
    {% endifequal %}
{% endfor %}

Just save this in a template directory and be sure to change the {% load %} statement to reflect the name of your own custom template tag file. You know, I think I should make this an inclusion_tag… Bah, another day. Anyway, to use it, just add this line to the template you wish to be paginated:

{% include "pagination.html" %}

Et voilà!