IEEExtreme 2009 competition registration opens today, 1st of September.
This competition seems very interesting, and some kamibu members are thinking about participating!
Languages supported are: Microsoft Visual C++/C#, C/C++, C# and some “surprises”.
I would really like to see some functional programming language getting on to that list, like Common Lisp, Haskell or my favourite: Scheme!
Functional programming may be very handy some times, and a lot of fun!
For example, I tried solving last year’s “Merging IP’s” problem (see IEEEXtreme 2008 Competition booklet, pdf) using Scheme.
The goal is to merge a list of IP intervals (e.g. 192.168.1.1 – 192.168.1.60), so that you only keep a list of the minimum required intervals.
Example Input:
3.0.0.0 – 3.100.0.0
3.99.0.0 – 3.255.0.0
10.1.0.0 – 10.200.0.0
10.2.0.1 – 10.5.99.99
10.200.0.1 – 10.225.225.0
Example Output:
3.0.0.0 – 3.255.0.0
10.1.0.0 – 10.225.225.0
Let’s build the main loop for the program (without input and output functions).
Suppose we have 2 functions ready: (should-merge int1 int2) that is true only if intervals int1 and int2 should be merged (one of them starts in the middle of the other and ends after it), and (precedes int1 int2) only if both addresses of interval1 “precede” interval2 (e.g. 5.0.0.0 – 6.0.0.0 precedes 6.0.0.5-7.0.0.0).
Now, we can write a function (merge-intervals intervals merged) that will recursively merge all intervals. Intervals parameter should be a list of intervals that have to be merged, sorted by their first address.
Merged should be a list of intervals that are always totally merged. In the beginning it should be an empty list, and in the end the solution of the problem.
(define (merge-intervals intervals merged)
; important! intervals must be sorted
(cond ((null? intervals) merged) ; all intervals are merged. return merged list
((null? merged)
; just started, merged is empty
; remove first of intervals and add it to the merged list
merge-intervals (cdr intervals) (list (car intervals)))
((should-merge (car intervals) (car merged))
; the two intervals should be merged
(merge-intervals (cdr intervals)
(cons
(merge (car intervals) (car merged))
(cdr merged))))
((precedes (car merged) (car intervals))
; add the first of intervals to the top of merged
(merge-intervals (cdr intervals) (cons (car intervals) merged)))
(else
; the first of intervals starts after the last merged
; and ends before the last merged ends
; ignore it
(merge-intervals (cdr intervals) merged))))
; We also used the merge function, that has a pretty straightforward definition
; returns an interval that starts at the start of int1 and ends at the end of int2
(define (merge int1 int2)
(interval-create
(interval-start int1)
(interval-end int2)))
Of course, there are no built-in functions to handle intervals in Scheme, you have to write them (interval-create etc) on your own. A pair is perfect for representing an interval.
Notice that an iterative implementation would not (or at least it shouldn’t) be faster than the recursive impementation used here, as Scheme implements tail-recursion.
For those not familiar with Scheme or Lisp,
(car l) can be interpreted as returning the first item of list l
(cdr l) as returning all the items but the first of list l, and
(cons item l) as pushing item to the beginning of the list l,
although that’s not exactly what they do.
Implementing should-merge and precedes function is a piece of cake if you represent the IP addresses as an integer (like ip2long of PHP or python iptools).
Bring Scheme to IEEExtreme 2009!
Bring functional programming to IEEExtreme 2009!
P.S.: Thanks to Ted for pointing out IEEExtreme to the team 
). So I want to write a few lines for some optimizations we started implementing in the new version.
