Finally using Lisp at work

I wrote my first Lisp program for work today.   Its a short program that traverses a huge file system (about 1 TB) and finds duplicate files and then prints a nice report showing file names, counts, space consumed, etc.   Ok, it does a little more than that but I can’t talk about the specifics .    Anyway, I had a lot of fun writing it and I finally got a good grasp of working with pathnames, which can be a little confusing in Lisp.  I also got to use quite a bit of my existing utility code like my table printer.

I hope to be able to write more Lisp code at work.  Its unlikely that I will be able to do anything big with it but the quick one-offs are very easy to sneak in without too much resistance!

Learn Lisp in 5 easily written steps

Learning Lisp has been a very enlightening experience for me. But getting the development environment up and running can be quite a chore, especially for a newbie. This can very discouraging if you are used to batteries-included programming languages like Python, Perl, Ruby and even C#. All I can say is be patient, learning Lisp is good for you!

1. Install Linux – If you already use Linux then you will likely not have much trouble with the rest of the steps. If you don’t use Linux, why not?? It’s free! Go download Ubuntu Linux or vanilla Debian. Learn to use the package manager. I’m suggesting Linux because it supports all of the open source Common Lisp implementations. Windows has great support for commercial implementations and very poor support (but getting better) for the open source CL’s. I know others use MacOS but I can’t comment since I don’t own a Mac (yet!).
2. Learn Emacs – I mean *really* learn it. Learn how to use the help system. Learn Elisp. Learn how to customize it but don’t try to turn Emacs into Notepad or Visual Studio or Vi(m) or whatever your old favorite editor is. Use it the way it was meant to be used. Steal relentlessly and unapologetically from other people’s .emacs config files. In addition to Lisp, Emacs supports just about every other language. Try using it as your primary development environment.
3. Use Slime – Slime stands for Superior Lisp Interaction Mode for Emacs. It is simply the best way to develop Lisp code. It has code completion (intellisense), context sensitive help, and includes one of the best debuggers I’ve ever worked with.
4. Read some Lisp books – Practical Common Lisp by Peter Seibel is a great starter book. The examples are, as the book title indicates, very practical and additionally easy to follow. Paul Graham’s ANSI Common Lisp is another good beginner’s book which includes a bonus language reference in the back.
5. After going though all of the exercises in one or two Lisp books, write a medium-large program using Lisp. Pick something you have done before in another language, or something totally new. The best way to learn a language is to write code!

And that’s it! Easy right? Learning Lisp can tough but it is well worth the effort. I’m so spoiled with it now that I go through severe withdrawals when I have to use Java or C++.

Solving The Knight’s Tour

I really enjoy solving computer programming puzzles. They are great for exercising the brain and learning new programming languages. One of my all time favorites is The Knight’s Tour, which was given to me as an assignment in college back in ‘93.

The basic idea is this: Place a knight on a standard chessboard in a random starting position. Move the knight using normal L-shaped knight moves to every position on the board without moving to any position twice. There is more than one solution for a given starting point. The smallest solvable board size is 6×6. If you are solving this by hand then it is best to mark the traveled positions with a number. For example, here’s a solved puzzle:

1 |16|31|56|3 |18|21|50
--+--+--+--+--+--+--+--
30|55|2 |17|48|51|4 |19
--+--+--+--+--+--+--+--
15|32|57|54|45|20|49|22
--+--+--+--+--+--+--+--
58|29|44|47|52|63|42|5
--+--+--+--+--+--+--+--
33|14|53|64|43|46|23|40
--+--+--+--+--+--+--+--
28|59|34|37|62|41|6 |9
--+--+--+--+--+--+--+--
13|36|61|26|11|8 |39|24
--+--+--+--+--+--+--+--
60|27|12|35|38|25|10|7

Back in college I wrote two solutions: a brute force solution and what I call the “look ahead” solution. On an 8×8 chessboard the brute force solution, written in C++, took 14 days to solve on a 486 DX2. The “look ahead” method can solve it in microseconds. The brute force method travels to every possible position until it finds a solution while the look-ahead method chooses the best move from the next possible moves. The best move is determined by “looking ahead” at the next 2 moves and choosing the move with the least number possible moves. Don’t ask me why it works, it just does!

I’ve written Knight’s Tour solutions in just about every language I’ve learned since ‘93 including Java, Python, Ruby and Common Lisp. The Common Lisp solution I wrote is by far the most elegant, not necessarily because its written in Common Lisp. It is mostly because I’m now more experienced as a developer and at solving this particular problem

My CL solution is 63 lines of code with comments. If you find a bug you win a free one year subscription to my blog!

#|
The Knight's Tour
Author: Anthony Fairchild
|#

(defun make-chessboard (size-xy)
  "creates a two dimensional array representing a chessboard"
  (make-array (list size-xy size-xy)))

(defun is-valid-move (board pos-x pos-y)
  "Returns true if the given move is valid.  A move is valid if it is
   within the board dimensions and it is not taken by another position."
  (and (< pos-x (array-dimension board 0))
       (< pos-y (array-dimension board 1))
       (>= pos-x 0)(>= pos-y 0)
       (zerop (aref board pos-x pos-y))))

(defun next-valid-moves (board curx cury)
  "returns next 8 possible valid moves"
  (loop for pair in '((-1 2)(-2 1)(1 -2)(2 -1)(-1 -2)(-2 -1)(1 2)(2 1))
        for newx = (+ (first pair) curx)
        for newy = (+ (second pair) cury)
        when (is-valid-move board newx newy)
        collect (list newx newy)))

(defun next-optimized-moves (board curx cury)
  "Sorts the next valid moves with the best moves first.  The best move is
   determined by looking ahead at the next 2 moves and choosing the move
   with the least number of possible moves"
  (sort (next-valid-moves board curx cury)
        #'(lambda (move-a move-b)
            (< (length (next-valid-moves board (first move-a) (second move-a)))
               (length (next-valid-moves board (first move-b) (second move-b)))))))

(defun solve-knights-tour (board posx posy move-num next-moves-fun)
  "Solves the knight's tour recursively. Uses next-move-fun function
to determine next move. Both brute force and optimized methods use
this function as a base."
  (setf (aref board posx posy) move-num)
  (cond ((= move-num (* (array-dimension board 0)
                        (array-dimension board 1))) board)
        ((loop for move in (funcall next-moves-fun board posx posy)
               when (solve-knights-tour board (first move)
                                        (second move) (1+ move-num)
                                        next-moves-fun)
               return t) board)
        (t (setf (aref board posx posy) 0) nil)))

(defun solve-optimized (board posx posy move-num)
  "Solves the knight's tour intelligently by finding the most likely
good position to move to."
  (solve-knights-tour board posx posy move-num #'next-optimized-moves))  

(defun solve-brute-force (board posx posy move-num)
  "Solves the knight's tour using brute force.  This means travel to every
possible position."
  (solve-knights-tour board posx posy move-num #'next-valid-moves))

(defun knights-tour (&key (optimized t)(size-xy 8)(start-x (random size-xy))(start-y (random size-xy)))
  "Return a solution for the knight's tour or nil if no solution could be found"
  (if optimized
      (solve-optimized (make-chessboard size-xy) start-x start-y 1)
      (solve-brute-force (make-chessboard size-xy) start-x start-y 1)))

CL-USER> (time (print-table (knights-tour)))
9 |6 |11|44|27|4 |29|34
--+--+--+--+--+--+--+--
12|43|8 |5 |46|33|26|3
--+--+--+--+--+--+--+--
7 |10|45|48|55|28|35|30
--+--+--+--+--+--+--+--
42|13|54|63|32|47|2 |25
--+--+--+--+--+--+--+--
53|64|49|56|1 |58|31|36
--+--+--+--+--+--+--+--
14|41|62|59|50|19|24|21
--+--+--+--+--+--+--+--
61|52|39|16|57|22|37|18
--+--+--+--+--+--+--+--
40|15|60|51|38|17|20|23

Evaluation took:
  0.006 seconds of real time
  0.004001 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  1,043,200 bytes consed.

A New Toy

I purchased a new toy yesterday that I’m pretty excited about, a Treo 700p. I’ve been using Palms devices since they were made by 3COM. The main reason I stuck with them for so long is they are very well supported in Linux. Palm also makes a 700w which runs the Windows embedded OS. My friend Keven tells me he read a review that said the 700p has a more intuitive interface over the 700w.

So this Treo is 3 devices in one: a phone, a camera and a palm pilot. Those items purchased separately would probably run about $399, which is what the Treo cost me. Having them all in one device really beats the alternative, which surely involves some kind of fanny pack

Today I installed an open source SSH client on the Treo and was able to connect to my Debian server and run Emacs/Slime on the tiny 320×320 screen. My Treo is now a little Lisp Machine