Martin Pool's blog

Mail me RSS Bazaar distcc Canonical is hiring! flickr

Quick quiz

Ken Silverman says that "sub eax, 128" -> "add eax, -128" is his favorite optimization. Why is it neat?

Also, John Carmack on what makes a good programmer.

posted Tue 20 Apr 2004 in /software/puzzles | link

programming puzzle 1

Sample problems from the DevX contest linked on Slashdot:

1. Problem 1

Problem 2

Problem 3

I did a rough solution to problem 1 in Scheme (dquads.scm). I feel like it took me a long time for the supposedly "easy" problem, though a lot of it was being unfamiliar with the tools. I still have to think a lot about how to express control structures that would come naturally in Python, Java or C. On the other hand, some of the expressions eventually turn out rather more concise than they would in those other languages.

I did a lot of these kinds of things when I was at high school for the Australian and South-East Asian Computing Competitions. It feels like a long time ago now. I think I did many of them in BASIC, which looking back seems incredibly difficult. I did some of them in C, which has the advantage of pointers and structs but really debugging pointer errors under time pressure is quite unnecessary.

One thing I notice is that its harder to put inline comments into Scheme, because (what seems to me to be) the idiomatic layout gets interrupted by fullline comments more than in C, which is basically one statement per line.

It seems that one pleasant thing about Scheme is that it's pretty easy to hoist code out into smaller functions. I suspect some of these cases would not have been easy enough to make it worthwhile in C because of the conceptual and visual overhead of passing a function pointer.

Performance is pretty reasonable, although I wrote it without much of a view to speed, and it potentially has to do a lot of calculation for the largest examples.

(use-modules (ice-9 slib))
(use-modules (srfi srfi-1))

;; "Flights" is (just) the input format.  It is a list with one
;; element for each node.  Each node gives a list of the numbers of
;; nodes that there are edges to.  Edges are directed and may be
;; duplicated.

;; This is transformed into a list of edges for internal use.  This is
;; simply a list of duples giving the from-node and to-node for each.
;; Again, there may be repeated edges.

;; A path is a list of edges, such that the to-node and from-nodes
;; connect up in order.

;; A quad is a path of length 4 that starts and ends at the same node.

;; Return a list of edges from FROM-NODE to each node in TO-LIST
(define (make-edge-list from-node to-list)
  (map (lambda (to) (list from-node to))
       to-list))

;; extract-edges FLIGHTS -> EDGES
;; Given a list of flights, return all the edges described.
(define (flights->edges flights)
  (let ((from-node 0)
	(edges '()))
    (for-each (lambda (to-list)
		(set! edges
		      (append (make-edge-list from-node to-list)
			      edges))
		(set! from-node (1+ from-node)))
	      flights)
    (reverse edges)))
		 

;; starts-from?
;;
(define (starts-from? node edge)
  (equal? (car edge) node))

;; Select from EDGES the ones starting from NODE
(define (edges-from node edges)
  (let ((f (lambda (e) (starts-from? node e))))
    (filter f edges)))

;; Return a list of paths that extend PATH by adding each of STEPS
(define (add-steps path steps)
  (map (lambda (s) (append path (list s)))
       steps))

;; Return a list of paths with all possible next steps chosen from
;; edges.
(define (next-steps path edges)
  (let* ((current-node (second (last path)))
	 (steps (edges-from current-node edges)))
    (add-steps path steps)))

;; Check if any element of L is equal to another element.  Dumb
;; O(n**2) algorithm.
(define (has-duplicates? l)
  (and (not (null? l))
       (or (member (car l) (cdr l))
	   (has-duplicates? (cdr l)))))

;; Check that the path does not revist any nodes.  Of course it is OK
;; for the last edge to go back to the start, since NODES doesn't list
;; it twice.
(define (revisit-ok? path)
  (not (has-duplicates? (path->nodes path))))

;; Return a list being the concatenation of lists built from FN
;; applied to each member of L.
(define (map-splicing fn l)
  (if (null? l)
      l
      (append (fn (car l)) (map-splicing fn (cdr l)))))
      

;; paths-starting-with FIRST EDGES
;;
;; Generate a list of all connected quads starting with FIRST and
;; continuing through EDGELIST.  Does not apply the diagonal test.
(define (quads-starting-with first edges)
  (let* ((generate-next (lambda (p) (next-steps p edges)))
	 (expand-steps (lambda (pathlist) (map-splicing generate-next pathlist)))
	 (init-pathlist (list (list first))))
    (filter revisit-ok?
	    (filter closed-path?
		    (expand-steps (expand-steps (expand-steps init-pathlist)))))))

;; make-paths EDGES -> PATHLIST
;;
;; Generate a list of all connected paths.  We try each edge as an
;; initial edge, and find all quads that start from there.
(define (make-quads edges)
  (if (< (length edges) 4)
      ;; Obviously no quads here
      '()
      (append
       ;; Find all paths starting with FIRST
       (quads-starting-with (car edges) (cdr edges))
       (make-quads (cdr edges)))))

;; Check that all the edges connect up, but not that this is a closed
;; loop.
(define (connections-ok? path)
  (or (null? (cdr path))
      (and (equal? (cadar path)		; goes to
		   (caadr path))	; comes from
	   (connections-ok? (cdr path)))))

;; Check that all the edges join up and the first one is the last
(define (closed-path? path)
  (equal? (caar path)
	  (cadr (last path))))

;; Return the nodes visited by a path
(define (path->nodes path)
  (map car path))

;; Check that there is no edge in either direction between the second
;; and third node in the path.
(define (diagonal-ok? path edges)
  (let* ((nodes (path->nodes path)))
    (not (any (lambda (x) (or (equal? x (list (first nodes) (third nodes)))
			      (equal? x (list (third nodes) (first nodes)))
			      (equal? x (list (second nodes) (fourth nodes)))
			      (equal? x (list (fourth nodes) (second nodes)))))
	       edges))))

(define (find-solutions flights)
  (let* ((edges (flights->edges flights))
	 (diag-check? (lambda (p) (diagonal-ok? p edges))))
    (filter diag-check? (make-quads edges))))

;; count-dquads FLIGHTS -> COUNT
(define (count-dquads flights)
  (length (find-solutions flights)))

I heard the idea recently that to keep developing as a programmer you ought to learn one new language every year. So I was wondering how I was doing against that:

2003

Scheme? (finally?)

2001

Python

2000

PHP

1998

Java

1997

Perl

There seem to be some gaps but maybe I was learning something else of similar complexity those years. I think I learnt a bit about the kernel in 1999 (when I should have been doing my Management subject homework. :-/).

Thinking back, it's hard to put an exact date on them, because for many of these languages there was a few false starts before being really confident. (Does that sound kind of lame for something as apparently simple as Python? Perhaps, though being really Pythonic is not quite trivial.) I suppose also the implementations improve over time and make them more welcoming: Java was terribly slow when I first used it on a ~100MHz machine, and I think Guile is only becoming friendly now.

posted Sun 18 May 2003 in /software/puzzles/devx/2003 | link

Copyright (C) 1999-2007 Martin Pool.