apt-mess

Being totally new to Debian, this surely will sound funny to my future self, but still, I'm pretty confused by apt/Debian's package management.

So I want to go from stable to testing, which is easy right, it's all laid out in the docs: do an apt-setup noprobe to prepare for your install. Hm. Except that there is no apt-setup on my current system (which is Etch stable). Go look for such, with apt-cache search and dpkg -S and what not -- no luck. Then there's this Google-thing, that leads me to this nice page the content of which is a bit misleading but gives me a good kickstart. Turns out, all I have to do is replace my "stable" entries to "testing" in my source.lst file. Now, do I have to do an apt-get upgrade before my dist-upgrade or is it unnecessary. Official docs say I better do a genuine upgrade before the dist-upgrade, but hell, they even say I should use aptitude instead of apt-get and then I don't know a bit about the difference between the to.

Linux From Scratch -- Success!!

After nearly a month of fiddling with LFS I finally got it working! It's really amazing to finally see the prompt that I built. :)

This is where exactly the journey begins. But before going beyond there are some issues to cope with:

1. An 'iso-8859-1 invalid identified' error after login -- I hope this would not lead to too severe locale-related issues

2. Drives that were hdaX on my previous host system are now named sdaX in the LFS system -- this may have to do something with udev?

3. There is no working eth0 interface which is the most painful part. Maybe this has something to do with the fact that I've compiled the kernel with make defconfig?

Before really starting to do BLFS, I will investigate these issues, which will be easy since I have a snapshot inside the chroot environment with the livecd.

Linux From Scratch -- Revisited

Stuff me in a pink gown and call me Paris Hilton.
Last time my LFS build failed it wasn't even binutils but glibc! After 15 minutes of RMTFing I realized that it's called configparms not configparams, dummy.

So next on is adjusting the toolchain!

Linux From Scratch -- Failure

Oh well, binutils build has failed. I suppose it has something to do with GCC Pass 1? The wording about the first GCC compilation in the book is a bit misleading, because they are talking about bootstrapping but the make target nowhere tells it to bootstrap.
I guess I will have to come back to this one and contact the good guys on the mailing list. Of course I will do my RTFM before flooding public channels.

Linux From Scratch -- Host System

So I have downloaded the minimal LFS LiveCD and popped it into my virtual machine under VMWare Player.

As it is advertised it is definitely a valid host environment for the build process, as checked by version-check.sh

After setting up my main file systems, we need to get the source packages. There is a wget input file in the stable book download directory which comes very handy. My slow internet connection makes me have to wait for all of them to arrive.

Linux From Scratch -- Introduction

I've been a long time casual Linux/Unix user. Back before Ubuntu was hype, I got into Gentoo, but never really got too far beyond installing it and emerging some packages. At my work we use Debian, and on my Vista I sure have Cygwin cause bash and the command line stuff is awesome.

But it always bothered me that I'm not really into Linux. Not into like "I use Ubuntu for my daily browsing and document editing chores" or "I'm the sysadmin of a 50-server heterogeneous *nix farm" but somewhere in between.

I'm pretty much tied to Windows as my main working environment, and can't really afford the hassle to migrate all my stuff to Linux (yeah, going from XP 32-bit to Vista 64-bit was a big enough deal already, thank you), so what do I do?

This is where Linux From Scratch comes into play. I mean. If I just really could build a whole Linux system from scratch, well it would really mean at least something, right?

Well. Jump right into it.

Because I'm a newbie, I start with the latest stable version of the LFS book.

First of all I need a host systems which is a simple 2.6 generic Linux VMware Image created by EasyVMX! and booted up with the LFS LiveCD. Since the latest book version is 6.4 and the latest LiveCD version is 6.3 and I don't need no X and stuff, I'm gonna pick the 32-bit "-min" image.

Since I have a slow internet connection, I guess I will have to hook up on things later.

Sling Blade Runner

ITA Software could be an interesting place to work at. They sure have some interesting puzzles on their career site serving as tools for resume selection / recruitment. One of such puzzles has just gone to their archives which is a big green flag for an open discussion.

The puzzle is called Sling Blade Runner, and it is specified as follows:

"How long a chain of overlapping movie titles, like Sling Blade Runner, can you find?"

Use the following listing of movie titles: MOVIES.LST. Multi-word overlaps, as in "License to Kill a Mockingbird," are allowed. The same title may not be used more than once in a solution. Heuristic solutions that may not always produce the greatest number of titles will be accepted: seek a reasonable tradeoff of efficiency and optimality.

Let's go and try to solve it!

The General Algorithm

The task suggests a reduction to the graph-traversal domain. By translating the specification to a bit more technical level, we can lay ground for an actual implementation. The highest level description of the proposed solution is as follows:

1. Take the input of a set S of sentences

2. Build the overlap-graph D of S which is a directed graph D(V, A); where

   • V=S,
   • A = {arc(s1, s2) if s2 overlaps s1 and both elements of S}

3. Find the longest (vertex disjoint) path P in D

4. Output P

Breaking down above steps takes us more closer to an actual realization. Following are the main steps in greater detail:

1. Take the input

The input is given as a stream of sentences (titles) separated by line breaks, where

• a sentence is a non-empty sequence of words separated by non-breaking whitespace, and
• a word is a non-empty sequence of non-whitespace characters.

For simplicity we won't care too much about different character sets and encodings and casing, and let the implementation environment decide about the proper meaning of whitespaces and characters.

What we do care about is that the input can possibly containt empty sentences that we ignore and multiple instances of the same sentence which we treat as a single value. Note that a sentence does not contain any of the whitespaces which appeared in the original line of input.

2. Build the overlap-graph

The meaning of "overlapping" is outlined in the original description of the task. A more formal definition would be that the sentence s2 overlaps sentence s1 iff any of the (non-empty) suffixes of s1 (including s1) is the prefix of s2 (including s2), where s1 is not s2.

The overlap-graph D then is made up by enumerating each possible p=(s1, s2) pair of S and putting an arc (s1, s2) into D for each p if s2 overlaps s1.

3. Find longest path

An L-long vertex disjoint path in the directed graph G is a sequence of vertices v[1], v[2], ..., v[L-1], v[L] with the following properties:

• for each 1 <= i <= L, i != j it holds thats v[i] != v[j]
• for each 1 <= i < L it holds that v[i] is the predecessor of v[i+1] in G (ie. there is an arc (v[i], v[i+1]) in G)

The longest vertex disjoint path P from a source vertex v in G is found by the following BFS-like recursive algorithm:

let n = the source of the search, initially n = v
let visited = vertices already visited by the algorithm, initially empty
define function longest_path(G, n, visited) as
   if n is in visited then 
       return empty_list
   for each successor m of n do
       path_candidates[m] = longest_path(G, m, visited ++ n)
   let mpc = one of the longest paths in path_candidates
   return v ++ mpc // the list of nodes on one of the longest paths from n in G

To get the global longest path GLP in D, one of the best results of longest_path(D, n, empty_list) over each n in D must be chosen.

The "one of..." clauses are present because two distinct paths can have the same length.

4. Write output

Print vertices of GLP each vertex on a line.

5. Test

Distinct parts of the algorithm can be tested as separate units: overlap-detection, termination-of-traversal in a cyclic graph, proper graph-building, etc. -- but I'm gonna skip describing those. As far as testing the whole algorithm goes I'm only interested in two things:

• That any results fed back to the input are given back unchanged.
• That I would pick the most naive benchmark implementation and every optimization is subject give the same results as this benchmark.

These are the main concerns regarding the evolution of my implementations. I will present actual implementations in future posts, but I won't talk about testing: publishing of any code will imply a that it has passed above tests.