neingeist

Auch Julian liess sich von der süßen Katze aus Kil… äh Shrek 2 über’s Ohr hauen und postete ein Movie-Wallpaper. Da will ich nichts nachstehen, und hier ist mein SüßeKatzenMovieWallpaper.

Nachdem wir am Samstag kurzfristig für einen ausgefallenen Sendungsmacher auf Querfunk (Freies Radio Karlsruhe) eingesprungen sind, und so unsere erste Sendung improvisiert haben, möchten wir nun eine “echte Sendung” machen. Nochmals Danke an ein paar Heidelberger die uns am Samstag unterstützt haben!

Das Thema soll das nächste Mal die Videoüberwachung sein. Aktuell gibt es Bestrebungen in Karlsruhe, eine solche am Europaplatz und drumherum einzuführen. Hierüber möchten wir informieren und vielleicht ein paar Leute
überzeugen, dass das keine gute Idee ist.

Ich suche noch Musik zum Thema, also zögert nicht zu kommentieren!

• Entropia Wiki: ChaosradioVideoUeberwachung
• MP3 der Sendung am Samstag (Achtung, Improvisation! >50 MB)

Und noch ein wenig Lisp-Code, diesmal eine Übungsaufgabe für meine Vorlesung Kognitive Systeme. Es ging darum, das Wort mit der größten Ähnlichkeit zu *word-from* aus der Liste *words-to* herauszufinden. Höherer Score bedeutet hier eine höhere Ähnlichkeit, in den Vorlesungen Info II und Info IV war das andersherum definiert (Editierabstand) und die Matrix anders initialisiert.

(defparameter *word-from* "DAABBCADBBA")
(defparameter *words-to* '("DDABCBA" "BAAATTCDBA" "DAABCCACBBA" "DAABBAABB" "AABDBCDBBC"))
(defparameter *word-to* nil)
(defparameter *matrix* nil)

(defun run ()
(declare (special *word-to*))
(dolist (*word-to* *words-to*)
(setf *matrix* (make-array (list (1+ (length *word-from*)) (1+ (length *word-to*))) :initial-element nil))
(init-matrix)
(do-score)
(show-matrix)))

(defun init-matrix ()
(dotimes (x (array-dimension *matrix* 0))
(setf (aref *matrix* x 0) 0))
(dotimes (y (array-dimension *matrix* 1))
(setf (aref *matrix* 0 y) 0)))

(defun show-matrix ()
(format t "        ")
(dotimes (x (length *word-from*))
(format t "~G   " (subseq *word-from* x (1+ x))))
(format t "~%")
(dotimes (y (array-dimension *matrix* 1))
(if (zerop y)
(format t "  ")
(format t "~G " (subseq *word-to* (1- y) y)))
(dotimes (x (array-dimension *matrix* 0))
(format t "~3D " (aref *matrix* x y)))
(format t "~%"))
(format t "~%"))

(defun score (x y)
(apply #'max
(list           (if (equal (subseq *word-from* (1- x) x)
(subseq *word-to* (1- y) y))
(+ (aref *matrix* (1- x) (1- y)) 2)
(+ (aref *matrix* (1- x) (1- y)) -1))
(+ (aref *matrix* (1- x) y) -3)
(+ (aref *matrix* x (1- y)) -2))))

(defun do-score ()
(loop for y from 1 to (length *word-to*) do
(loop for x from 1 to (length *word-from*) do
(setf (aref *matrix* x y) (score x y)))))

There’s a nice Web developer extension to Firefox which greatly helps when debugging web sites with
neat features like:

• Display, live edit and validate CSS of a webpage
• Find broken images, images without alt-tags
• Lots of validation options
• Web form helpers

So, that’s the third extension (besides the language menu and
the session saver) I’ll use.

This blog finally validates as XHTML 1.0 Transitional. I wish web browsers just wouldn’t display invalid pages…

Another toy problem from the ITA software page is the Add-A-Gram:

An “add-a-gram”
is a sequence of words formed by starting with a 3-letter word, adding
a letter and rearranging to form a 4-letter word, and so on. For example,
here are add-a-grams of the words “CREDENTIALS” and “ANACHRONISM”:

ail + s =
sail + n =
nails + e =

aliens + t =
salient + r =
entrails + c =
clarinets + e =
interlaces + d =
CREDENTIALS (length 11)

(…) given the dictionary found
here (1.66MB), what is the longest add-a-gram?

Running my code to get the longst add-a-gram is left as an exercise to the reader 😉 I also did some basic performance testing and compared the results
of my Lisp version to those of the versions on the site in
Perl
and Python. Looks like Lisp isn’t so slow after all. Timings and Lisp code follow:
Read the rest of this entry »

Another nice toy problem I found on

the career page of ITA Software (which has some more problems for breakfast 😉 is the “Nine Nines” problem:

Combining nine 9s with any number of the operators +, -, *, /, (, ) , what is the smallest positive integer that cannot be expressed?

I already had a look on
the Lisp solution by Luke Gorrie by way of the Small-cl-src
mailing list, a mailing list intended for small Common Lisp source snippets, so my solution might look a little like his. But I tried not to copy his code, maybe that’s the reason why mine is quite a bit slower (actually, it’s a lot slower…). I guess
it’s because of my excessive use of lists and the pushnew statement instead of
a hash table, as he uses one. Maybe the Lisp wizards in the neighbourhood will enlighten me sometime, and I’ll post a new faster version.

(defun nines (n)
"Gives the solution to the n-nines problem."
(let ((solutions (make-array (1+ n) :initial-element nil)))
(setf (aref solutions 1) '(9))
(do ((k 2 (1+ k)))
((> k n))
(format t "solve for ~G ~%" k)
(solve solutions k))
(find-first-missing-integer solutions n)))

(defun solve (solutions n)
"Find all possible combinations for n nines, using the already
calculated combinations of 1 to n-1 nines"

(do ((k 1 (1+ k)))
((> k (/ n 2)))
(format t "inner loop ~G ~G ~%" n k)
(dolist (solution (combine (aref solutions k) (aref solutions (- n k))))
(pushnew solution (aref solutions n)))))

(defun find-first-missing-integer (solutions n)
"Find the first missing integer, our solution."

(do ((k 1 (1+ k)))
((not (member k (aref solutions n))) k)))

(defun combine (a b)
"Gives arithmetic combinations of the members of a and b"

(let ((foo nil))
(dolist (x a)
(dolist (y b)
(pushnew (+ x y) foo)
(pushnew (abs (- x y)) foo)
(pushnew (* x y) foo)
(unless (zerop y) (pushnew (/ x y) foo))
(unless (zerop x) (pushnew (/ y x) foo))))
foo))

Other solutions which I found on the web: Luke’s Haskell version, Karl Zilles’ port to ML and Nicolas Minutillo’s solution in Java (22 pages!).

This is more of a dirty little helper than a clean solution, but it suits me well. I only know of one other tool for synchronizing bookmarks between multiple computers: The Bookmarks Synchronzier (FTP) uses FTP to do the job, but I prefer CVS (or any other version control system in the future) because I already use that for various tasks.

The main problems with synchronizing bookmarks via CVS are conflicts, which come up naturally (changed bookmark properties) or because of some flags (like last visit or last modification date for folders). To reduce the latter, I use this dirty little script:


#!/bin/bash
bookmarks=`echo ~/.firefox/default/*/bookmarks.html`

cd `dirname $0`
sed -e ‘s/LAST_VISIT=”[0-9]\+” //‘ \
-e ‘s/LAST_MODIFIED=”[0-9]\+” //‘ < $bookmarks > bookmarks.html
cvs update

It first copies the bookmarks.html, removes the conflict-prone LAST_VISIT and LAST_MODIFIED tags and then updates from the CVS repository. Then you got to manually resolve all remaining conflicts (look for “>>>” in bookmarks.html). Finally I use another script to commit the changes and copy back the new – synchronized – bookmarks file. All that has to be done while Firefox is closed. (It’s a good idea to close Firefox from time to time anyway, holy memory leak…)


#!/bin/bash
bookmarks=`echo ~/.firefox/default/*/bookmarks.html`

cd `dirname $0`
cvs commit -m foo
cp bookmarks.html $bookmarks

Alex Wenger, den Entropianern unter uns allen bekannt, hat nun Das Coffein unter den Blogs aufgemacht.

Da fällt mir ein: Es ist Zeit für meinen Fünfuhrkaffee!

Ich nenne meinen iPod künftig nur noch körpergebundene Kleinanlage für die hochwertige Wiedergabe von Hörereignissen. (via heise.)