Author Archives: Stefan Geens

The de Bruijn Code

Posted on by
36

Instead of doormen, Stockholm apartment buildings have a little keypad at the front door, into which you key a 4-digit code to gain access to the lobby. The code is known to residents, and is liberally shared with acquaintances, workmen, postmen, and no doubt sold to an underworld of snail-mail spammers and worseI’d love to see a database of Stockholm door codes, though, if only to gain a little humint on what are the most popular 4-digit combinations..

The keypad is unusual in that there is no enter key. Instead, it remembers the last 4 digits you have pressed, and compares those to the code which unlocks the door. In other words, if you key in the sequence 123456, you’ll have tried codes 1234, 2345 and 3456. If the correct code is 2345, you’ll have opened the door after keying in the first 5 digits in the above sequence.

This is different from how a bank machine keypad operates, where you need to key in four digits (and then enter) for every PIN code number you try. If you were to forget your code, you’d have to go through a maximum of 40,000 key punches (not counting the mathematically boring enter key): 10,000 combinations of 4 keys each (0000, 0001 … 9998, 9999).

On a door-code keypad, however, it’s clear that you can cycle through every combination in far fewer than 40,000 key punches: If I key in just the sequence 1234567890, for example, I have already tried 7 different 4-digit combinations with just 10 key punches. On a bank machine keypad, it would have taken me 28 key punches to try 7 different 4-digit combinations.

This is interesting information for all those of us who think it within the bounds of possibility they might one day find themselves standing somewhat stupefied in the snow outside their Stockholm apartment at 3am on a Sunday in January, with the mercury all shrivelled up, not a soul in sight and not a code in mind. Deciding beforehand on the right contingency strategy for such a situation could shave hours off the frigid poking at that dumb but durable little keypad which would then have to follow.

A rundown of the options, then:

  • Going through the combinations bank-machine style. Pros: Counting from 1 to 10,000 is easy; you’re guaranteed to hit your code eventually Cons: 40,000 key punches at around 2 per second will take just over 5 1/2 hours. With luck, your code is 0012 — but nobody is ever lucky at 3am on Sundays.
  • Going at it randomly. Pros: No thinking required whatsoever. Cons: Looks pathetic; generating truly random patterns is nearnigh impossible for humans, especially drunk ones; you might actually never type in the correct code.
  • Calculating beforehand the shortest possible sequence that cycles through all possible codes, writing it down and keeping it in your parka in case of just this kind of emergency. Pros: Should get you into any warm lobby in no time, relatively speaking. Cons: The “beforehand” part of the first sentence in this paragraph.

    • The rest of this post concerns itself with exploring the possibility of making this third option a viable one for Stockholmers. To that end, I have been wondering: (1) What is the minimum amount of door-code keypad punches needed to try every possible combination? (2) Is it possible to run through every possible combination without being forced to repeat any combination? (3) Is there a unique such solution? (4) If not, how many solutions are there? And finally, (5) How likely am I to spontaneously generate the shortest possible sequence if I pursue the second, random strategy described above?

    If the answer to (2) is yes, it’s easy to see that the answer to (1) is 10,003. That’s because after three punches, every subsequent key I press adds a new 4-digit combination to the sequence, and there are 10,000 combinations to go through. In this best-case scenario, at 2 presses per second, we’d go through every combination in under 84 minutes.

    As I started looking into this, it felt like the answer to (2) should be yes, but I lacked the mathematical tools to back up my hunch. So I decided to try to simplify the problem and then apply brute force. Instead of looking for the shortest sequence that contains all possible 4-digit combinations without repetitions, I decided to try to find one that contains all 2-digit combinations without repetitions — the shortest sequence that would unlock a door-code keypad with a 2-digit code.

    I printed out a 10×10 grid with all 100 combinations (00, 01 … 98, 99) and headed for a café in Kungsholmen. After a café latte’s worth of trying to connect the numbers, I’d found a sequence 101 digits long that contained all the combinations exactly once — showing that (2) is true, at least for 2 digits:

    00112131415161718191022324252627282920334353637383930445464748494055657585950667686960778797088980990

    I can’t help it, but I happen to feel that that’s a pretty cool sequence — it feels so dense, so efficient. Just from inspection, some other things become clear:

  • There are many distinct such shortest possible sequences. For example, you can make some others just by moving the 00 at the start of the sequence to wherever else there is a 0, just by moving the first 0 next to any other 0. This means the answer to question (3) is No, there is no unique solution; not for two digits, and by extension, not for four digits, because here too we’d be able to insert the specific combination 0000 anywhere we find 000 in the sequence. The same holds for shortest sequences containing all combinations of any length.
  • The last digit and the first digit are repeated. That’s because every digit except the first and last does “double duty” in belonging to a combination, and since there is an equal total number of digits in the combinations 00, 01 … 98,99 (twenty 0s, twenty 1s, twenty 2s etc… for a total of 200 digits), the first and last digit have to be the same. This is the case for any shortest sequence containing all 2-digit combinations.
  • Since the last digit and the first digit are always the same, you can fuse them into one digit that does “double duty”, in the process turning this sequence into a great big circle of 100 digits. This is even more elegant; you can start anywhere you like in the sequence and loop around it, and you’ll have gone through every combination when you’ve made a complete loop. A better way to denote our sequence, then, would be

    • …0011213141516171819102232425262728292033435363738393044546474849405565758595066768696077879708898099…

  • You can go in either direction around this loop. That’s because every combination has its own unique mirror image: 91 maps to 19, 34 maps to 43, etc… And palindromes map to themselves.

    • It felt like these observations should apply by extension to shortest sequences for combinations of any length, but I still could not demonstrate to my satisfaction that the shortest circular sequence containing all combinations of x digits had to be of length 10x — in the case of our door-code keypad problem, a loop of 10,000 digits. Also, I was nowhere near being able to count the number of such shortest sequences.

    I thought I’d simplify the problem further, then — by reducing the base from 10 to 2. We can do that, because we’ve really just been using digits as stand-ins for distinct objects, and combinations as ordered collections of these objects. For that matter, you could think of our 4-digit codes as being equivalent to 4-letter words, made from an alphabet comprised of 10 letters. In base 2, there are only two letters, if you will: I and O.

    In base 2, then, what do the shortest circular sequences containing all 2-letter words“codes” / “combinations” / “words” / “cyphers” / “strings” / “stretches” / “ordered collections”… — it’s all the exact same thing. look like?

    …0011…

    That’s it, actually (1001, 1100 and 0110 are all shifted versions of the same circular sequence)For completeness’s sake, the shortest circular sequence containing all 1-letter words in base 2 is …01…, and it’s unique, obviously.. Notice that the length is 4, or 22. How about the shortest sequences containing all eight 3-letter words, in base 2?

    …00010111… = …00011101…

    There are two, though they are each other’s mirror image; proceeding clockwise on the first is equivalent to proceeding counterclockwise on the second. Length: 23 = 8.

    Shortest sequences containing all 16 4-letter words, base 2?

    …0000100110101111… = …0000111101011001…

    …0000100111101011… = …0000110101111001…

    …0000101001101111… = …0000111101100101…

    …0000101001111011… = …0000110111100101…

    …0000101100111101… = …0000101111001101…

    …0000101101001111… = …0000111100101101…

    …0000101111010011… = …0000110010111101…

    …0000110100101111… = …0000111101001011…

    That’s 16 sequences of 16 letters each, including mirror images.

    To find these sequences, I had to resort to drawing crude graphs, with all the possible words connected by arrows indicating which word could lead to which as we create a sequence (think “continue punching away at the keypad”). For example, both 1010 and 0010 can be followed by 0100 or 0101, in the exact same way that on the door-code keypad, the codes 1001, 2001, … 9001 and 0001 can be followed by 0011, 0012, … 0019 or 0010, depending on which key you choose to punch next.

    The trick is to visit each word only once by following the arrows. Here, for example, is a graph with all possible 2-letter words in base 2 as nodes:

    dBG[2,2].gif

    This is a much prettier version, made later, after I got some help online. Notice how there is only one way of cycling through all the nodes once.

    Here is a graph with all possible 3-letter words in base 2 as nodes, again made much prettier after the fact:

    dBG[2,3].gif

    In all these graphs, I’ve also labelled the arrows, because they represent a unique relationship between two words. For example, the arrow from node 011 to 110 is labelled 0110, because that is the 4-letter word created when these 3-letter words follow one another in our sequence.

    This hints at a very profound relationship between these graphs: Every arrow on the smaller graph corresponds to a node on the larger graph. Therefore, trying to find a path that cycles through every arrow on the smaller graph is the same as finding a path that cycles through every node on the larger graph. And visually, at least, it is a lot easier to find all the ways to cycle through every arrow on the smaller graph than it is to find all the ways to cycle through every node on the larger graph. Hence I never needed to draw a graph with all 4-letter words as nodes in order to find the 16 shortest circular sequences containing all 4-letter words listed earlier — instead, I just found all the ways to cycle through all the arrows on the larger graph above.

    This is as far as I got on my own. It began to feel like I was trying to reinvent the wheel, badly, so I decided to seek professional help. After rummaging about on Mathworld for a while, I hit paydirt: It turns out a loop sequence of letters or digits is called a necklace. The shortest possible such sequence containing all possible words of a certain length is called a de Bruijn sequence. The graph associated with a de Bruijn sequence is called a de Bruijn graph. The path along such a graph that uses every arrow (edge) exactly once is called a Eulerian circuit (and all graphs that allow such a circuit are called Eulerian graphs, making de Bruijn graphs a subset of Eulerian graphs). The path that uses every node (vertex) exactly once is called a Hamiltonian circuit (and you can guess what a Hamiltonian graph is).

    It turns out that Leonard Euler provided us with the crucial link that shows why the answer to question (2), “Is it possible to run through every possible combination without being forced to repeat any combination?” is always yes, regardless of alphabet or word size. According to the Mathworld page on Eulerian graphs,

    “Euler showed (without proofI don’t know if someone has supplied a proof of this, in the meantime. Something to look up.) that a connected graph is Eulerian if and only if it has no graph vertices of odd degree. […] A directed graph is Eulerian if and only if every graph vertex has equal indegree and outdegree.”

    In other words, if on a graph connected by arrows every node has as many arrows coming in as arrows going out, you will always be able to make at least one Eulerian circuit — you will always be able to find a way to cycle through all the arrows without ever getting stuck at a node. This makes sense, intuitively: Take the larger graph above, the de Bruijn graph for base 2, order 3 (which means the nodes represent 3-letter words): every node has an equal number of arrows going out, because the alphabet (base) from which to choose the next letter as you proceed along your circuit is the same at every node. The same goes for arrows coming in, which represent the letter being dropped as we progress along our circuit — it too has to be a member of the same alphabet.

    But what about generating a bona fide de Bruijn sequence for our door-code keypad? Well, Mathworld is linked to the math program Mathematica (the brainchild of Stephen Wolfram), and the page on de Bruijn sequences mentions that Mathematica has an algorithm for generating such sequences for any given alphabet and word length. Although Mathematica is perhaps one of the most impressive applications ever made, it also costs 25,000kr., and hence I’ve never managed to justify buying it. Fortunately, there is a 15-day free trial, so I hurriedly downloaded it, and got to work. Here is a trial run, a de Bruijn sequence for 3-digit combinations in base 10:

    …9798787770760750740730720710980970960950940930920910108908708608508408308208889998988081009909008007006005004003002000190180170160150140130120119118117116115114113112912812712612512412312213913813713613513413313214914814714614514414314215915815715615515415315216916816716616516416316217917817717617517417317218918818718618518418318219919819719619519419319212111029028027026025024023022922822722622522422392382372362352342332492482472462452442432592582572562552542532692682672662652642632792782772762752742732892882872862852842832992982972962952942932322202103903803703603503403393383373363353349348347346345344359358357356355354369368367366365364379378377376375374389388387386385384399398397396395394343330320310490480470460450449448447446445945845745645546946846746646547947847747647548948848748648549949849749649545444043042041059058057056055955855755695685675665795785775765895885875865995985975965655505405305205106906806706696686679678677689688687699698697676660650640630620610790780779778978879…

    Again, I love the density of these sequences. When it came to generating a de Bruijn sequence for 4 digits in base 10, though, Mathematica took its time — 2 hours and 45 minutes, to be exact. By then I had grown restless and had been googling “de Bruijn sequence”, only to find a most surprising page among the results: A Swedish blogger! Hakan Kjellerstrand has a page up with a much faster algorithm for generating de Bruijn sequences. He even singles out the specific solution for Stockholm door-code keypads. So click on that link, print out the result and keep it handy whenever you have a door-code keypad blocking your way.

    But two of the five original questions remained unanswered: First, how many such sequences are there? Hakan and Mathematica both provide one sample de Bruijn sequence, not a counting function for de Bruijn sequences for a given alphabet and word length.

    It turns out the answer wasn’t even known for sure until 2002, when Vladimir Rosenfeld at the University of Haifa published a proof for the general formula in a paper titled “Enumerating de Bruijn Sequences.” It’s not online, as far as I can tell, but he does talk about his results in another paper of his, Enumerating Kautz Sequences (original link).

    According to Rosenfeld, in 1946 Dutch mathematician N.G. De Bruijn proved a formula for counting the number of shortest circular sequences containing all q-letter words using a 2-letter alphabet (base 2). Here it is:

    total number = 22(q-1)–q

    Indeed, for q = 3 the result is 2 and for q = 4 the result is 16, as shown earlier. This made him famous, and led to this entire class of sequences being named after him, though it doesn’t seem like he proved a generalized formula for any given alphabet size (base). In 2002, Rosenfeld did just that, apparently. For an alphabet size s and word length size q, the number of circular de Bruijn sequences of length sqis! means factorial. 4! = 4x3x2x1:

    (s!)s(q-1)s–q

    Making s=10 and q=4 gives us 10!1000/10000, or 5.79×106555Update 2004-10-09: Well, you can’t trust the internet for anything, can you? The paper by Rosenfeld misprints the formula for the number of circular de Bruijn sequences (I’ve corrected the main text now). The relationship between the number of circular de Bruijn sequences and the number of linear de Bruijn sequences didn’t look right when I read the paper — I thought the difference between these two formulas should be a factor of s^q, because every circular de Bruijn sequence seemed to me to contain that many starting points for linear de Bruijn sequences. But hey, I didn’t prove the results, and my blog doesn’t have “expert anonymous reviewers,” so what would I know? Today, though, I found a different formula for the number of circular de Bruijn sequences in Stephen Wolfram’s New Kind of Science and this one confirms my hunch. And so far, Wolfram has never failed me. (The formula for the linear de Bruijn sequence remains the same, though.)
     
    Update 2004-10-21:Vladimir sent me his original paper, Enumerating de Bruijn sequences [PDF] and indeed there the formula is correct. And an interesting read.    , sequences. If we want to tally up the more real-world situation, where you need to key in 10,003 digits into the door-code keypad, then the formula is slightly modified:

    (s!)s(q-1)

    which gives 10!1000 or 5.79×106559 linear de Bruijn sequences. That’s our answer for question (4).

    Which leaves us only question (5): “How likely am I to spontaneously generate the shortest possible sequence if I pursue the second, random strategy described above?” To answer this, all we need is to divide the total number of linear de Bruijn sequences (which we just counted) into the total number of sequences that are 10,003 digits long (which is just 1010,003). The answer: 1 in 5.79×103444 times. Given that the number of stars in the universe is about 7×1022, it’s a safe bet to say that every pig will need to fly before anyone ever achieves this feat.

    Postscript: De Bruijn sequences are actually useful, and crop up in several seemingly unrelated fields. They provide the mathematical underpinning for DNA manipulation tools — DNA being nothing but sequences of words composed of the letters G, A, T and C. Rosenfeld’s paper, too, aimed to provide mathematical tools for understanding “minimal generating sequences” in DNA, that is, “the sequence of minimal length that produces all possible amino acids.” Also, de Bruijn sequences seem to get mentioned a lot in connection with cryptography, especially by Stephen Wolfram in the footnotes to A New Kind of Science, though how or why is something I think I need to look into next.

    A liberal dose

    Posted on by
    6

    Another week, another libertarian/classical liberal blogger joins the Swedish blogosphere. It’s an unmistakable trend that both JKL Blog and Media Culpa [English] pick up on today. We now have, in no particular order, Johan Norberg [mainly in English], Johnny Munkhammar [Some English], Henrik Alexandersson, PJ Anders Linder, Dick ErixonPer Gudmundson is a part-time participant., The group blog Smorgasbord [in English] and Tobias Henriksson all blogging from an ideological pole near the Timbro Institute, a Swedish think tank in favor of free markets or else a right wing capitalist cabal, depending on your sensibilities.

    Those on the left drawn to conspiracy theories might wonder whether the Ludwig von Mises Institute hasn’t been issuing marching orders; but if the left has such thoughts, they have nowhere to blog it. That’s because the one thing more remarkable than the advent of liberal blogging in Sweden is the near-complete absence of credible socialist/social democrat bloggers pushing back.

    What these liberal blogs have in common is that they all stay focused, stay on message, and collectively guarantee that no left-wing political shenanigans go unpunished, at least in the Swedish blogosphere. And sometimes, blogging critically about Sweden’s left-wing is less like shooting fish in a barrel than shooting a barrelful of fishIf I have a gripe, it’s that with the exception of the last two on the above list, Sweden’s liberal bloggers don’t allow commenting, which is lame. It’s not as if any of them are Andrew Sullivan yet. But even if they were, that’s is no reason to turn comments off; look at Kos. Oh, and get RSS feeds..

    Why no groundswell of left-wing or even just social democrat blogs? My hunch is that in a society where one political perspective has the hegemony, blogging acts as an assymetric weapon in the war of ideas. Blogging is essentially free, scalable, competitive yet freely associative — right up Liberalism’s alley, in fact. Meanwhile, social democrats and the left are sticking to those big old media guns that got them to the top of the pile in the first place. They have yet to adapt.

    But the lack of intelligent social democratic countervetting makes the Swedish blogosphere poorer for it. I have yet to read (or find a link to) a good critique of Catherine Hakim’s new book and its reasons for the marked differences between men and women’s salaries in Scandinavian countries (and I can think of some responses, but this is not my battle, and I’d like to read the book first); and where is the serious response to Johan Norberg’s survey of Swedish libraries showing bias in the purchasing of political booksTo be honest, I don’t think a credible retort is possible in the case of library bias.?

    In other cases, incisive left critique would do liberal blogs some good, lest they get all flabby and incestuous. For example, Norberg today approvingly quotes a (still permalinkless) Munkhammar post listing a litany of statistics pointing out how Sweden will effectively cease to exist in 2033I’m sure he’s kidding about the 2033 date, but does that mean we are supposed to take all the other data with a grain of salt?. First off, the post is completely unlinked and unsourced, leaving us fact checkers to do all the hard work; second, some of the quoted statistics are old news and have already been parsed to death elsewhere; third, the one new piece of information to me — “In 1999, Sweden was no 4 in the international investment league, in 2002 it had fallen to no 27” — is tendentiously presented. UNCTAD’s week-old 2002 foreign direct investment (FDI) league tables for this notoriously volatile indicator places Sweden 23rd out of 140 nations, far ahead of the EU norm and handily outperforming that Hayekian paradise – the US, in 92nd place – if these things matter to youWhen it comes to outward investment, Sweden came 8th. Belgium is first globally in both tables, but I’m not taking credit for that..

    Furthermore, statistics can prove any point. For example, did you know Sweden is actually one of the world’s best places to do business? The World Bank’s month-old report “Doing Business in 2005 — Removing Obstacles to Growth,” ranks Sweden ninth, globally, for ease of doing business. Only two EU members make it into the top ten: Sweden and the United Kingdom. How so? Among EU members, Sweden, together with Finland, has the lowest number of required procedures to start up a business — three. It has among the EU’s lowest start-up costs, at 0.7% of per capita income (only Denmark is lower). Registering property takes one procedure and two days — easily making it the EU’s top performer. Sweden is also the cheapest place in the EU to enforce contracts, at 5.9% of the value of the debt (vs. an EU mean of 12.1%). I’ll leave out the fact that payroll costs are at the EU norm, just to heighten the effect. No wonder Sweden ranks so high in terms of FDIAnd I’ll spare you the stellar results Sweden had in the World Economic Forum’s 2003-2004 Global Competitiveness Report.
    Update 2004-10-13: Rankings for 2004-2005.    .

    But I shouldn’t be doing this work — a left-leaning patriotic Swede should, because, basically, I agree with the liberals. It’s just that it takes two sides for political blogging to get truly fun.

    Sleepwriting

    Posted on by
    3

    Must. Stay. Awake. For. The. Debate. This effort is very much being helped along by Marc in Berlin who insisted I read over his article on tropical rainforests in zeppelin hangarsHere is the article. when he finished writing it, but who then instead proceeded to procrastinate over on MemeFirst. I did manage to get a gift certificate for iTunes out of it, however, and this soon led to the purchase of a maddeningly boppy song, “I’d rather dance with you” by Bergen’s own Kings of Convenience.

    Check out the whole video on iTunes — I am finding it hard to resist the urge to join in with the silly steps, and since the alternative is catatonic sleep, I am grateful.

    But the song doesn’t just work at the gut level. The lyrics wink at you as they seduce:

    I’d rather dance with you than talk with you
    So why don’t we just move into the other room
    There’s space for us to shake, and hey, I like this tune

    Even if I could hear what you said
    I doubt my reply would be interesting for you to hear
    Because I haven’t read a single book all year
    And the only film I saw, I didn’t like it at all

    …

    The music’s too loud and the noise from the crowd
    Increases the chance of misinterpretation
    So let your hips do the talking
    I’ll make you laugh by acting like the guy who sings
    And you’ll make me smile by really getting into the swing

    See, because even though he’s saying how he’d rather not talk, he is talking; and even though he denies being interesting, she doubts it; and though he pretends to describe, he is actually telling her what to do. Somehow, at 3am, that comes across as profound.

    Top ten things I hate about Stockholm, IX

    Posted on by
    10

    The ninth in an occasional series.
     
    Ten: Predatory seating
    Nine: Culinary relativism
    Eight: Preëmptive planning
    Seven: Premature mastication
    Six: Irrational discalceation
    Five: Radiotjänst i Kiruna AB
    Four: Temporal engineering
    Three: Tunnelbana vision    Two: Simölacra

    I’ve learned a few lessons in life I’d like to pass on.

    Don’t drink British wine. Don’t drink Italian beer. Don’t drink cosmopolitans in dive bars, don’t drink Rolling Rock in diva bars. Do as the locals.

    Don’t drink decaffeinated coffee. Don’t drink de-alcoholized beer. Don’t eat vegetarian food made to look like meat. Seek out authentic things.

    But what to do if these two prescriptions for life clash? What if the locals seek out simulacra? I am referring, of course, to that sad abomination of an acoholic beverage, lätt öl [Swedish], a Swedish class of barely beers, “light” on taste, alcohol and point, a straight-to-bladder production that not even the state alcohol dispensing monopoly, Systembolaget, could be bothered regulating.

    And yet Swedes don’t get the hint about what that implies. Every day, at luncheon places all over Sweden, hundreds of thousands will optimistically ask once again for lätt öl by name, just in case that, over night, it might suddenly have developed into something substantive.

    It’s hard to describe the lack of taste it has. You know how sometimes, when you buy a coke from a concession stand and the dispenser has almost run out of syrup, you get to drink something with a hint of coke that is actually far worse than just water? Lätt öl is the beer equivalent.

    To be honest, I don’t understand why Swedish beer is drunk at all. Sweden has worldbeating vodkas and aquavits and wonderful traditions involving punsch and mulled wine. Swedish beer, on the other hand, is atrocious.

    Yes it is, and you know it — there is a reason why you don’t export it. I’m not necessarily saying only Belgians can make good beer — the Germans produce competent brews, even if their restrictive Reinheitsgebot guarantees they’re boring; the Americans have some excellent microbreweries; give them a few more generations as they chisel away at the rough edges, and they will have something that approaches the complexity of the palate of an Orval. But as for Swedish beer, there is no hope, and the whole enterprise should just be put out of its misery.

    At least lätt öl consumption has fallen by half over the past ten years, for which we have the EU to thank. Price-sensitive consumers have been getting more booze for their buck by nipping over the border and carting home something realI’ve described the role alcohol plays in Sweden’s social life before.. This upgrading of Swedish drinking habits is encouraging, but Swedish alcohol consumption still ranks below the EU mean — so if Swedes want to bolster their until-now entirely undeserved international reputation as a drinking nation, there is still much work to be done.

    I suggest refocusing on core Nordic competencies — bring back Viking meadAnd if you hire Absolut’s marketing geniuses you’ll have another runaway export success on your hands.. Read up on Norse drinking culture, convert Spendrups‘s breweries into meaderies, then start enjoying an alcoholic heritage that is both local and authentic.

    NetNewsWire 2 vs. Shrook 2

    Posted on by
    3

    For the last few days I’ve been playing with the public beta of NetNewsWire 2, the successor to the first popular newsfeed reader for the Mac and new competitor to Shrook 2, the current favorite in the fieldA Newsfeed reader lets you collect, manage and display newsfeeds, which are stripped-down versions of the most recent stories published by websites such as newspapers, wire services and blogs. A site’s newsfeeds are updated whenever the site is updated; they come in standardized formats (such as RSS), and are fetched regularly by the newsfeed reader, making it possible to keep tabs on hundreds of websites automatically, instead of having to visit these sites individually to see what’s new..

    I have taken an instant liking to NNW2. While I was impressed by the features of Shrook 2 when that application came out, I found it to have too many quirks for me to use it as the predominant way of being apprised of what’s new on my favorite sites. Instead, I returned to hunting and pecking at websites with my conventional browser, these days Camino.

    NNW2 has quirks too, and it is still beta, but the frustrations I have with this application are of a different kind. NNW2 is so good that I can now see how I will surf the web in a year or two; it’s just that it’s not quite there yet.

    How will I surf the web in a year or two? The application I will use will be a browser, with tabs, history, bookmarks, pop-up blocking and what-have-you, but also with souped-up feed management and display tools much like what NNW2 and Shrook 2 offer today.

    Both these newsfeed readers now let you toggle between the stripped down version of a story and the much prettier browser version, rendered inside the application. But whereas Shrook 2 does this as a feature, it is much more central to NNW2, which has a back button, an address bar, tabs even! It feels so natural to begin using NNW2 as a starting point for one’s net adventures that it comes as a shock when you instinctively look for but can’t find a google search bar on the top right, or a browse history, or a home button, or lack the ability to access your non-feed shortcuts.

    But I now know what I want. And if you read NNW2’s feature request/bug report page, you can see that other beta users are also screaming for a full-fledged in-line browser. The future lies not with newsfeed readers that also render websites but with browsers that also manage and display newsfeedsApple’s next iteration of Safari, shown in the preview of OS X 10.4, lets you collect and display newsfeeds, though it is far from clear how impressive the newsfeed management system is..

    What’s more, my future browser will have a system for organizing my feeds that is a hybrid of how Shrook 2 and NNW2 do it today. Simply put, Shrook 2 uses the iTunes library/playlist metaphor, NNW2 uses the email folder metaphor. Both have drawbacks — Like iTunes, Shrook 2’s system is not hierarchical; like Mail or Microsoft Entourage, NNW2’s system does not allow aliases of the same item in different foldersSure, in NNW2 you can subscribe to the same feed as many times as you want and put these shortcuts in different folders, but that is not efficient on many levels..

    I want hierarchical folders like NNW2 has. If I highlight my top-level folder called “Sweden”, I get to see all new stories contained by all the feeds in all the subfolders (NNW2 calls these folders “groups.”) If I expand that folder and highlight a subfolder, say, “Politics/media,” I get to see new stories from just the feeds therein. In Shrook 2, on the other hand, you can’t expand folder/playlists in the left-most column — a whole extra column is required to see what’s in them, leading to a four-column layout that I find unwieldy. And, unlike with folders, playlists (Shrook calls them “channels”) can’t contain subplaylists. I have no idea why not, actually.

    But I also want to be able to scatter multiple instances of a newsfeed across folder/channels, like Shrook 2 allows. For example, I’d like www.kimthew.com to show up both in my “Friends” folder/channel and “New York” folder/channel. However, should I decide I want to banish my friend forever, it should take but a single swipe from a master library. NNW2 doesn’t let me do this.

    And then there are features I want that neither application has yet: For example: hierarchical smart foldersSmart folders are folders that are dynamically populated by news items that meet specific criteria, such as, say, those containing the text fragments “swed” or “svensk” or “sverige”.. Current implementations of these smart folders are a bit crude: You have to choose between matching any criteria or all criteria. You can’t currently make a smart folder that displays items containing either the text “SvD” or “DN” or “Expressen” or “Aftonbladet” but which must also contain the text “Stefan Geens”, for example. In other words, you can’t mix and match the logical OR and AND operators. One solution would be to allow hierarchical smart folders — A top level smart folder would look for the mention of Swedish daily newspapers, a sublevel smart folder would look for my name among those results.

    Many of the features in NNW2 were first introduced by Shrook 2. But a couple of them are unique to NNW2, to my knowledge:

    NNW2 can compare the current newsfeed’s contents to the previous one. The results can be highly amusing:

    gizmodo.gif

    NNW2 let’s you save a search in Feedster, Daypop or Blogdigger — they’re like Googles for newsfeeds — as a virtual newsfeed. The most recent news items that include your search term are in it. If you want to know if anyone at all is blogging “Belgium”, even if you don’t subscribe to their newsfeed or have never heard of them, this is the way to do it.

    Other clever ideas include connecting scripts to a virtual newsfeed, so you can go scrape websites that have no newsfeeds themselves; a customizable toolbar that provides excellent access to quick toggling of viewing styles; and a tool for finding “dinosaur” newsfeeds, which haven’t been updated in a while. There is also something that is supposed to share your newsfeed collection with others, but it doesn’t work yet in the beta.

    Update 2004-09-28: Ranchero have now announced they too will support syncing and bandwidth use managment in NNW2.Shrook 2, meanwhile, still has a much better solution in place for managing bandwidth issues: Their distributed checking feature is truly clever, whenever it works. They also let you access your newsfeed collection via any browser, so you can keep up when you are travelling.

    A list of other Mac newsreaders can be found here.So if you have already shelled out $25 for Shrook 2, your investment is safe, but if you have yet to adopt a newsreader as your own, take a very good look at same-priced NetNewsWire 2 when it comes out of beta.

    Skype

    Posted on by
    15

    As a consequence of the need to tend to several work-related projects, the presence of a looming urge to redesign this blog, a spurt of blogging over at MemeFirst and a rather heavy post on Leopold II last week to come down from, you will now be served a few posts blissfully free of any import or presumption: A roundup of recent Mac software I’ve used and can recommend. Today:

    A voice chat application for both PC and Mac that lets you talk to other users for free but also make cheap calls to real phones.Skype: This second beta for the Mac, out since a week ago, now works seamlessly. I actually only use one of Skype’s features, SkypeOut, but what a feature it is: 2-eurocent a minute “voice chat” to real phones in the US, Europe and Australia from anywhere I can plug my PowerBook to the internet — and with the same sound quality as a normal phone call.

    This changes everything. Consider my setup: Because I’ve been moving frequently these past few years, I haven’t bothered getting landlines, relying instead on my mobile phone to make calls, even if calling out is expensive, at 1 euro per minute to the US. Today the 10 euro credit I bought on Skype will let me talk 500 minutes, as opposed to the 10 minutes I would have gotten via Telia on my mobile. That’s also far cheaper than using landlines or calling cards.

    Friends in New York who are all avid Vonage users have asked me why they should use Skype instead. They shouldn’t. Unlike Vonage, Skype can’t receive calls from real phones. But Vonage, inexplicably for the business they’re in, only takes credit cards with US addresses (trust me, I tried); Skype takes all comers. And since I already have a mobile phone on which I can receive calls for free, I don’t miss Skype’s inability to do so.

    If you live in Europe, have broadband and still initiate long distance phone calls using landlines, you are being fleeced. Help kickstart the voice-over-internet-protocol (VoIP) revolution and get Skype. (Did I mention it’s made in Sweden?)

    Fredagsfyran: Vad heter din blogg?

    Posted on by
    4

    1. Vad heter din blogg?
    Det finns blog@stefangeens.com, MemeFirst, Swedish Research News och Oog som jag känner mig ansvarig för, men den sista har faktiskt blivit min fars fotoblogg.

    2. Hur valde du detta namn och avspeglar det på något sätt syftet med din blogg?
    blog@stefangeens.com och Swedish Research News är jättetråkiga som namn, men de har fördelen att namnen är ärliga. När jag började blog@stefangeens.com behövde Blogger (som jag använde då) en titel, och jag hade ingen inspiration. Kanske också anade jag att om jag gav min blogg en kvick titel (t.ex. New York State of Mind, Ceçi n’es pas un Belge eller Stockholm Syndrome), jag skulle tröttna på den innan att jag tröttnar på min blogg.

    MemeFirst är en helt annan berättelse. När jag var på semester med några kompisar var det så tråkigt bara sitta på stranden att vi bestämde oss vi skulle skriva och regissera en kortfilm, “Beaver Me First,” och därinne fanns en kult som hette “Me First”. Kultmedlemmar var egoistiska, självklart. När några av oss senare ville starta upp en gruppblogg som skulle befordra argumentationer, insåg vi att det skulle angå bada konflikter mellan individer (me first), och konflikter mellan memer (meme first). Jag tycker fortfarande om namn.

    Oog betyder öga på flamländska. Bra namn för en fotoblogg, tycker jag.

    3. Bästa svenska bloggnamn? Media Culpa

    4. Bästa utländska bloggnamn? Memepool.

    A trial for Leopold II

    Posted on by
    10

    lii2.jpgIf King Leopold II were alive today, there is no doubt he would be on trial alongside Milosevic at The Hague for genocide and crimes against humanity. You might have heard about Leopold II’s exploits in the Congo at the cusp of the 19th and 20th centuries — perhaps from Adam Hochschild’s book King Leopold’s GhostExcerpts from Hochschild’s book are available in PDF format here. It’s essential reading., or else White King, Red Rubber, Black Death, a BBC documentary that enraged the Belgian royal family when it was shown in Belgium earlier this year.

    Many Belgians have never heard the story. Among the allegations, briefly: The Congo Free State, the personal property of King Leopold II, suffered a decline in population from 20 million to 10 million in the decades straddling 1900 as the king, in constant need of cash, had his colonial agents implement a brutal regime of forced labor on the native population. The process went thus: Belgian agents would enter a village and hold the women and children hostage; to secure their release, the men would have to head into the forest, find rubber trees, tap them, and return with superhuman quotas of sap. Many were worked to death, or else killed. If agents killed those held to ransom, they might chop off (right) hands, to prove that the bullets used hadn’t been wasted on game.

    If you were the King, or Milosevic, how would you structure your defence? The numbers are exaggerated? They died from other causes? You never ordered such barbaric acts? You weren’t aware this was going on? It wasn’t systemic, but the actions of isolated individuals? You were framed? The natives did it more than you?

    Of course you would. And now, a document [MS Word] published by the Belgian Embassy in LondonDon’t get me started — here is a PDF version I made. in the wake of the BBC documentary mounts a defence of Leopold II precisely along these lines. I have no idea why it even exists — why should government resources be expended defending the personal projects of a long-dead king from the work of historians and documentary filmmakers, irrespective of the accuracy of the claims? Can’t this matter be settled among academics? The Belgian constitution does not grant the current king policy making powers, so I don’t see why royal hissy fits should turn into national policy stances.

    It’s a bizarrely defensive document, and stiffly phrased. For example, it doesn’t start, “Yes, King Leopold II’s actions are indefensible, certainly by today’s standards and even by the standards of his contemporaries, but the context in which he acted is more nuanced than a portrayal by a BBC documentary…” Instead, we get nuggets such as these:

    About the allegations:

    Translation: ‘Weakened,’ ‘some even killed;’ doesn’t sound so bad. And they call this genocide?These media claim that numerous deaths and cruelties ought to be ascribed to the system of licensing that King Leopold II had set up for the exploitation of rubber. The indigenous people were claimed to have been weakened and some even killed by forced labour for the exploitation of rubber in Congo. The reign of Leopold II is described as “genocidal”.

    Some excerpts from the defence:

    Translation: It wasn’t systemic, and in any case, the locals were doing it too. Bonus gratuitous swipe: They’re still doing it.It was not a practice ordered or imposed by Congo Free State or by Leopold II, but was the result of individual acts, based upon prior existing local customs. Mutilations were not introduced by the Belgians, but already existed (and still do) in some parts of Africa — they occurred not only in the Congo, but for instance also recently in Liberia and Sierra Leone. Taking the “scalp” of the enemy is not even peculiar to Africa.

    Translation: There weren’t enough Belgians in the Congo to kill that many (even though they tried). And anyway, of the agents implementing Leopold II’s regime of forced labor, many weren’t Belgian. This reflects well on Leopold II, for some reason.3. Another reason why the accusation of “genocide” is out of proportion and unrealistic, is the fact that only 175 agents were in charge of the exploitation of rubber in Congo at the beginning of the 1890s. Most of them were not Belgian and a considerable number of them quickly succumbed to tropical diseases.

    Translation: Some natives died before Leopold’s agents could exploit them. Surely he can’t be held responsible for that?4. […] The alleged deaths for the whole of Congo cannot be ascribed to the Belgians, simply because at the beginning of the colonisation, they were not even present or active in the whole of Congo. (their emphasis)

    ‘Demographic changes’!! My nomination for euphemism of the year. Translation for ‘Migration’: Apparently some Congolese didn’t like living in Congo Free State. ‘Tropical diseases’: Who would have guessed that exhausted, malnourished and mistreated workers have lowered immune systems? And re the slave trade, which Leopold II made ‘great efforts’ to ‘completely eradicate’: Well, if it contributed to a depopulation of the Congo, how successful were the efforts then? Even if demographic changes would have taken place in certain regions of Congo, they cannot solely by [sic] attributed to the reign of Leopold II. Other factors that have to be taken into account are: migration, tropical diseases and slave trade (which had been taking place in many parts of Congo before the reign of King Leopold II and which he made great efforts to completely eradicate).

    Now, all this is just so tactless. Even the one narrow point I am willing to concede is made practically unpalatable by the smug logic the authors use to underpin it:

    First of all, the use of the term Îgenocide’ is debatable in this context. ÎGenocide’ can only be used if there is a clear intention to destroy a population on nationalistic, ethnic, racial or religious grounds. Neither King Leopold II nor his administrators ever ordered the extermination of the Congolese population, or of some groups of it. On the contrary, the Congo administration needed the local labour for the cultivation of rubber and therefore had no interest in decimating it.

    How enlightened. That practically sounds like sustainable development. Au contraire, the rubber quotas demanded by Leopold II were so large that rubber trees died from overexploitation, requiring desperate Congolese to head further and further into the jungle in bids to secure the release of their kin.

    A brief aside here: I don’t believe in holding historical figures to modern moral standards — Vikings just didn’t know any better than to rape and pillage; they were never aware of modern moral alternatives to such methods (like joining the EU, for example) and so cannot be held to task for not choosing them. I do believe in holding rulers to the moral standards of their contemporaries, however, especially if there was widespread condemnation already then on moral grounds. In Leopold II’s case, he was the target of a sustained campaign to stop the abuses in the Congo. People like E.D. Morel, Mark Twain, Arthur Conan Doyle and Joseph Conrad made it impossible for the king not to be aware that his rule was morally bankrupt. And yet he did not change. This is what makes the moral indictment stick, in my mind.But, yes, according to the narrow legal definition of genocide, Leopold II did not perpetrate that. He just didn’t give a damn about the Congolese, despite knowledge of the effect his policies were having. The mass depopulation of the Congo was the consequence of his policies, not the aim. In our moot court, however, this makes not an iota of difference to his culpability for crimes against humanity.

    The authors, meanwhile, seem to believe that their defense brings his actions back to within the norm of acceptable behavior for a turn-of-the-century monarch — making him someone whom Belgians can continue to honor and respect. But even if everything in the document were true, these defences are so pathetic that Leopold II would still emerge as one of the vilest statesmen of the 20th century. He would still be a vain, racist philanderer whose colonial ambitions led directly to the deaths, estimated far too conservatively then, of at least a million Congolese; and he knew it.

    lii.jpgYet he was king of Belgium, and so there are statues of him around Brussels today. There is one on the Place du TrŸne, around the corner from the Royal Palace and a stone’s throw from EU headquarters. Leopold II is buried in the royal crypt on the grounds of Laeken, a palace he rebuilt entirely with Congo profits, and in which the current royals live.

    If you are a soldier or civil servant, put in enough years and you will get a medal with his name on it. Thirty years after becoming an officer, for example, you get to be Commander in the Order of Leopold II. Today.

    I find that disgraceful. It’s clear to me that this man needs to be unambiguously disowned by the Belgian state, regardless of the wishes of the royal family. His statues need to come down, his medals need to be replaced (may I propose the Order of Patrice Lumumba?) and, in a gesture of contrition, Laeken needs to be sold to fund thousands of scholarships for Congolese students, so that these ill-gotten gains can finally do some good. (The king has another lovely palace in the center of town where he can live.)

    There will soon be an opportunity for all this to happen. In 2005, Belgium’s Africa Museum, founded by Leopold II and which for a century has neglected to tell the story of his rule, will be hosting an academic conference, in order to ascertain the “historic truth” behind Hochschild’s story. An exhibit will accompany it. Sound promising?

    The Belgian government admits that individual abuses took place in Congo, but rejects the accusations that circulate in the press. That is the reason why next year the Africa Museum in Tervuren is organising an exhibition, which will portray an independent and realistic picture of Congo under colonial rule.

    I guess not.

    Fredagsfyran

    Posted on by
    2

    Frågor kommer från här.1. Vilken författare, död eller levande, skulle du vilja se som bloggare?
    Utan tvivel, JM Coetzee. Även om det var bara en av hans rena, minimalistiska paragrafer varannan vecka. Jag tror förresten att han inte skriver hans romaner snabbare än det. Jag undrar därför om det betyder att Coetzee inte skulle orka skriva fler böcker om han började blogga.

    2. Borde fler bloggare försöka ge ut sina anteckningar i bokform (se”Supermamman“)?

    Ja, så länge det inte är deras blogg innehåll som blir förlagt som bok; bloggar och böcker är helt annorlunda litterära former och jag tror att det som passar bra i en blogg blir mindre i en bok. Förresten är bloggkompetenser helt annorlunda som romanförfattarekompetenser. En kompis sa en gång, “bloggers are novelists with ADD.” Jag håller med. Det finns människor som kan båda, men det är inte självklart.

    Vi kommer att se hur Belle de Jour gör det. Om hennes roman dokumentär blir en sexy version av Bridget Jones’s Diary kan det funka. Men Helen Fielding skrev aldrig hennes bok kronologiskt, som en verklig dagbok. En roman blir bra om berättelsen har en stor struktur (en “dramatic arch”), och det klarar man inte genom att skriva på ett rent kronologiskt sätt, som på en blogg (utan att vara ett geni).

    Jag utesluter inte att man får publicera en novellsamling av blogginlägg, men noveller inte heller är vad flesta bloggare skriver på deras bloggar.

    Förresten: Jag tycker faktiskt inte om att man tar bort blogginläggen från webben när de blir förlagt som en bok. Det är mot min bloggaretik. Bättre att skriva nya grejor för boken.

    3. Skulle DIN blogg kunna redigeras om till bok?
    Nej, tack.

    4. Vore en bok skriven i bloggform (en post = ett kapitel), en bra idé?
    Ja, om författare har skrivit och redigerad mesta av innehållet innan att hon börjar publicerar det som en blogg, så att vi läsare kan nöja oss av en riktig handling. Till slut, det är mycket svårare för en blogg att bli en bra bok än för en bok att bli en bra blogg.