Irreal

The other day, I presented two Elisp coding challenges. I specified Elisp because Irreal readers tend to like Emacs related posts. The down side of that is that several of you worried about bignums and other Emacs limitations. That wasn’t my intent—I just thought the problems were interesting and might even come in handy someday in an interview.

In any event, here are my solutions. All the commenters who gave an answer for problem 1 (Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm to find the missing integer.) gave the same O(n)/O(1) algorithm for time/space, namely just sum the integers up and subtract the sum from (n² + n) / 2 to find the missing number.

The solution to the second problem (Given a list of integers from 1 to n but with one of the integers missing and another repeated, find an efficient algorithm to find the missing and repeated numbers.) is similar except the we sum the numbers and their squares. If we let delta₁ be the difference between the sum of the integers and the sum of the integers from 1 to n, and delta₂ be the difference between the sum of the squares of the integers and the sum of the squares of the integers from 1 to n, we have:

• repeated – missing = delta₁ and
• repeated² – missing² = delta₂.

From there, some very easy algebra (the quadratic terms drop out) we get

• repeated = (delta₂ + delta₁²) / 2 delta₁
• missing = (delta₂ – delta₁²) / 2 delta₁

Now it’s easy to write an algorithm that’s linear in time and constant in space (modulo some increase in size for bignums if we’re using a language that supports them).

(require 'cl)
(defun solve (n repeat missing)
  (let ((numbers (cons repeat
                       (delete missing (loop for i from 1 to n collect i))))
        (sum-1-to-n (/ (* n (1+ n)) 2))
        (sumsq-1-to-n (/ (* n (1+ n) (+ n n 1)) 6))
        (units 0)
        (squares 0))
    (dolist (i numbers)
      (incf units i)
      (incf squares (* i i)))
    (let ((delta1 (- units sum-1-to-n))
          (delta2 (- squares sumsq-1-to-n)))
      (message "repeated number is %d, missing number is %d"
               (/ (+ delta2 (* delta1 delta1)) (* 2 delta1))
               (/ (- delta2 (* delta1 delta1)) (* 2 delta1))))))

I didn’t bother to randomize the list because I don’t make any use of the fact that it’s (almost) in numerical order. Some readers calculated the length of the list but I assumed that n was given as part of the problem. If not, it’s simple to count them up as we sum the numbers and their squares and then calculate sum-1-to-n and sumsq-1-to-n afterwards.

When we run solve, we get the expected answer

ELISP> (solve 100 35 78)
"repeated number is 35, missing number is 78"
ELISP> 

I ran across a couple of nice interview questions and an interesting story over at Tanya Khovanova’s Math Blog. The two questions are:

1. Given a list of integers from 1 to n but with one of the integers missing, write an efficient algorithm for finding the missing integer.
2. Given a list of integers from 1 to n but with one of the integers missing and another integer repeated, write an efficient algorithm for finding the missing and repeated integers.

In both problems the numbers in the list are in no particular order.

So the challenge is to write the two algorithms in Emacs Lisp. The interviewer expected a O(n log n) algorithm for time for the second problem. Can you do better?

Don’t go over to Khnovanova’s blog until you have solved the problems because there are spoilers in the comments. After you solve the problem, though, be sure to read her story about “hiring the smartest people in the world.”

The latest Programming Praxis Exercise is interesting. Back in 1973, Luis Trabb Pardo and Don Knuth published an algorithm that was meant to assess the power of a programming language. The algorithm was

Ask for 11 numbers to be read into a sequence S
Reverse S
For each number in S
  Call some function to do a mathematical operation on the number
  If the result overflows
    Alert the user
  else
    Print the result

That seems simple enough but notice how it involves arrays (lists would be more natural in Lisp but the intent was to use arrays), indexing, I/O, iteration, general functions, mathematical functions, and error detection. Be implementing the algorithm in a language you get a good feel for how the language handles common programming tasks.

Naturally, I had to try it out in Lisp. I used Emacs Lisp as a sort of minimal Lisp but still got a very nice and concise implementation.

(require 'cl)
(let ((s (make-vector 11 0)))
  (dotimes (i 11)
    (aset s i (read-number "Enter a number: ")))
  (coerce (reverse (coerce s 'list)) 'vector)
  (mapc (lambda (n)
          (print (condition-case nil (expt 2 n) ((overflow-error) "OVERFLOW"))))
        s))

If I had used a list instead of an array, I wouldn’t have needed the two calls to coerce but I would have needed two reverses if I filled the list in the most natural way.

The condition-case is like try/except from other languages. It performs the exponentiation and returns the result unless an overflow error occurs in which case it returns OVERFLOW. Whatever is returned is then printed. The only problem I had was getting an overflow. Generating an overflow is hard in most Lisps because of their bignum facilities. Emacs Lisp doesn’t use bignums but it does handle overflows in the interpreter. A sexpr like (expt 10 1000) just returns 0. If you use (expt 10.0 1000) it returns 1.0e+INF. Division by zero does generate an error but its an arith-error not an overflow-error. If anyone knows how to generate an overflow in Elisp, leave a comment.