Job programming puzzles

Lately, I've been taking to job programming puzzles, to help my brain atrophy a bit less. :-P There are a couple of ones I've looked at so far: Justin.tv, and Weebly. I found both of these companies through the Hacker News job board. I look forward to doing more puzzles as I come across them. I'll probably store all my answers, and just submit them when my Green Card arrives and I can start applying for some of these jobs.

The Weebly one is easy. I solved that one in 15 minutes (and could have done it somewhat faster if not for a couple of false starts). In so saying, I didn't have to write any JavaScript code at all, I just used standard Unix tools, so perhaps that's cheating (as far as timing goes—I could have done using only client-side JavaScript code, but it would have taken me a little longer). :-P

---

The Justin.tv one is more challenging. I had some code from my OMGWTF 2007 submission that handled operator precedence (yes, my calculator was written to behave like a scientific calculator, and even provided buttons for parentheses so you could override the precedence), but I wanted to do it ‘the right way’, so I read up Wikipedia on parsing. I ended up using the shunting yard algorithm to do this (if you aren't familiar with this algorithm, I'd advise you to learn it from Dijkstra's paper, rather than from the Wikipedia article).

The extra-credit reduction option I implemented in a fairly conservative way, that does not reorder the values, nor change the evaluation order (even when such reordering would provide a correct final result). It does squash consecutive applications of the same operator into one function call (such that it would work as expected in Scheme), and it does so knowing that addition and multiplication are associative.

My implementation is written in Perl, by the way (and I use operator overloading on the S-expression class so that printing nested S-expressions requires very little code). It's written in a functional style, allowing easy translation to Ruby once I know the language better. And as an extension, it supports the exponentiation operator, **, which has higher precedence than * and /, and the output could even be fed to Scheme (with SRFI-1 support) if you had this function defined:

(define (** . args)
  (reduce-right expt 1 args))

---

Here is the test set I used (the first five are from the Justin.tv website, and the last four involve negative numbers, which are outside the spec, so change them appropriately if your implementation can't deal with negative numbers):

3
1 + 1
2 * 5 + 1
2 * ( 5 + 1 )
3 * x + ( 9 + y ) / 4
a + b + c + d
a + b + ( c + d )
a + ( b + c ) + d
a + ( b + c + d )
w - x - y - z
w - x - ( y - z )
w - ( x - y ) - z
w - ( x - y - z )
-1 + 0 - 1 * 2 * 3 - 4 - 5
-1 + 0 - 1 * 2 * 3 - 4 - 5 / 6 / 7 - 8 + 9
-1 + ( 0 - 1 * 2 * 3 - 4 - 5 / 6 - 7 / 8 ) + 9
-1 + ( 0 - 1 * 2 * 3 - 4 - 5 / 6 + 7 / 8 ) + 9

Results, without reduction:

3
(+ 1 1)
(+ (* 2 5) 1)
(* 2 (+ 5 1))
(+ (* 3 x) (/ (+ 9 y) 4))
(+ (+ (+ a b) c) d)
(+ (+ a b) (+ c d))
(+ (+ a (+ b c)) d)
(+ a (+ (+ b c) d))
(- (- (- w x) y) z)
(- (- w x) (- y z))
(- (- w (- x y)) z)
(- w (- (- x y) z))
(- (- (- (+ -1 0) (* (* 1 2) 3)) 4) 5)
(+ (- (- (- (- (+ -1 0) (* (* 1 2) 3)) 4) (/ (/ 5 6) 7)) 8) 9)
(+ (+ -1 (- (- (- (- 0 (* (* 1 2) 3)) 4) (/ 5 6)) (/ 7 8))) 9)
(+ (+ -1 (+ (- (- (- 0 (* (* 1 2) 3)) 4) (/ 5 6)) (/ 7 8))) 9)

Results, with reduction:

3
(+ 1 1)
(+ (* 2 5) 1)
(* 2 (+ 5 1))
(+ (* 3 x) (/ (+ 9 y) 4))
(+ a b c d)
(+ a b c d)
(+ a b c d)
(+ a b c d)
(- w x y z)
(- w x (- y z))
(- w (- x y) z)
(- w (- x y z))
(- (+ -1 0) (* 1 2 3) 4 5)
(+ (- (+ -1 0) (* 1 2 3) 4 (/ 5 6 7) 8) 9)
(+ -1 (- 0 (* 1 2 3) 4 (/ 5 6) (/ 7 8)) 9)
(+ -1 (- 0 (* 1 2 3) 4 (/ 5 6)) (/ 7 8) 9)