Some code of mine from 2004
I wrote this in response to a programming challenge back in 7/2004. Looking back on it, I can’t really remember doing it or how I was thinking, but I had fun going back to read it.
This is one of the more interesting challenges in the GEEK setting, because it’s got a strong academic feel. The skyline problem isn’t easy to solve quickly, and the traditional methods aren’t terribly elegant. I solved the challenge once a long time ago with a method that ran in O( n log n) time, but I don’t have that code and OSI reset. :)
So, I decided since I have been trying to learn lisp, why not do it in Common Lisp? The solution I did is in two parts. The first solves the skyline problem, and the second (in C++) does the checksumming. Because I don’t know enough CLisp to actually lock down the variable types, I can’t do the checksumming in Clisp just yet. :)
First, I had to write a generic routine to split the incoming string. I wrote a routine that could do it about as generically as I could want:
(defun separatorp (x)
(char= ## x))
(defun split (string crit start)
(if (<= (length string) start)
()
(let ((eor (position-if crit string :start start)))
(if eor
(cons (subseq string start eor) (split string crit (1+ eor)))
(list (subseq string start (length string)))))))
It isn’t tail recursive, but it was easy to write. :) The separatorp function just returns yes if the character is a sharp. I might later write “split-if-equal” which would be a subset of this, but split worked well enough for now.
My algorithm is a bit different from the traditional method. Instead of building a long array (as long as the biggest record), I actually just evaluate the building height where it could possibly change. I do this by making start and end records in a list, which I sort by their x value (and starts go before ends). My algorithm only tracks buildings by height, because that’s the only significant criterion. Building color would be a different story. :)
So I made a structure and a function to sort it:
(defstruct bmark kind height pos)
(defun bmark< (bm1 bm2)
(if (= (bmark-pos bm1) (bmark-pos bm2))
(< (bmark-kind bm1) (bmark-kind bm2))
(< (bmark-pos bm1) (bmark-pos bm2))))
(defun startp (x) (= (bmark-kind x) 0))
I should have made kind break on symbols, not on numbers, but I’m a lisp newbie, okay? So, now a function to turn my split string into a list of these structures, and a function to put this and the initial split together:
(defun make-initial (x &optional (target 'b-mark-list))
(let ((lst (split x #'(lambda (c) (eq #, c)) 0)))
(set target (append (list (make-bmark :kind 0
:height (parse-integer (second lst))
:pos (parse-integer (first lst))))
(list (make-bmark :kind 1
:height (parse-integer (second lst))
:pos (parse-integer (third lst))))
(eval target)))))
(defun parse-into-forms (x &optional (target 'b-mark-list))
(dolist (ent (split x #'separatorp 0))
(make-initial ent target))
(sort (eval target) #'bmark<))
That one looks longer than it has to be, because I kept the spacing sane. So now I could just drop a string in and have it parsed and ready for my algorithm. But the actual algorithm? Surprisingly short, in fact it’s barely longer than the code to actually do the parsing:
(defun make-skyline-rep ()
(let ((priq '(0)))
(dolist (bm b-mark-list)
(let ((tmp (car priq))
(bpos (bmark-pos bm)))
(if (startp bm)
(emit-change (car (sort (push (bmark-height bm) priq) #'>)) tmp bpos)
(emit-change (car (setf priq (remove (bmark-height bm) priq :count 1))) tmp bpos ))))))
(defun emit-change (cur prev pos)
(if (not (eq cur prev))
(push (list pos cur) s-mark-list)))
This function, to keep it shorter, is much scarier, I know. :) “emit-change” is the easiest one. It just says, “If the current height is different from the previous one, put a pair onto my result list.” This is corresponding to the “1#11” result list, but it’ll go on backwards.
“make-skyline-rep” is the meat of it. It makes a list that has 0 at the “bottom” Then it goes through each of my aforementioned structures, and follows a simple algorithm. For each entry, it checks to see if its a start or a stop entry. If it is a start entry, it places the height on the priority list, and sorts it. It then calls emit changed with the new value on top of the priority list, the previous value on top, and the x position of the current entry. If the entry is instead a fail entry, it removes the first occurrence of that height from the priority list, then calls emit-change as in the previous option.
It’s really that simple, though. Now, if I had a heap (which can do the priority list thing in O(log n) time), then I’d be mimicking my old C program that did this in O( n log n ) time, but since I don’t, I get a hefty overhead for sorting that list on every insert. I think it makes my algorithm O( n log n ^2) as a result (or somewhere in that area).
One note though, unlike most implementations, my algorithm only examines areas where there are changes, specifically where a building starts or ends. This means my N is much smaller than that of my other competitors (who’s N is basically the same as the endpoint of the greatest building), which makes a huge difference with polynomial time algorithms. For the challenge input, I only handled 1000 things, whereas most people handled 2000 things. If I could just get rid of the sort on every insert entry, I’d probably lose at least half of that. Clisp ran this and said the following once I compiled the functions:
Real time: 0.287368 sec. Run time: 0.28 sec. Space: 854944 Bytes GC: 2, GC time: 0.06 sec.
Not bad for less than 90 lines of code with an obvious bottleneck on an interpreted language, eh?