Solution to a fun little programming problem given here: http://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html#comment-1165807320

gistfile1.txt

Tom Moertel <[email protected]>
2013-12-16

We are given the following problem:

    Given a text file with 999,999 lines, one number per line,
    numbers in random order from 1 to 1,000,000 but a single number is
    missing, figure out what number is missing.

    Source: http://blog.moertel.com/posts/2013-12-14-great-old-timey-game-programming-hack.html#comment-1165807320

My solution, in Haskell:

> main :: IO ()
> main = interact $ show . missing 1000000 . map read . lines

The `main` function just reads lines from the standard input, converts
them into a list of Ints, calls (missing 1000000) on the list to find
the missing number, and finally prints the number.  The `missing`
function is where the real work happens.

> missing :: Int -> [Int] -> Int
> missing n xs = n * (n + 1) `div` 2 - sum xs

How does it work?

Recall that we are given, in some undisclosed order, all of the
numbers between 1 and 1 million, but that one number is missing.
Assume that it was *not* missing.  What would the sum of the
numbers be?  Letting

    S(N) = 1 + 2 + 3 + ... + N,

the sum would be S(1000000).  This sum has a nice closed-form formula:

    S(N) = N * (N + 1) / 2.

(We can prove the formula correct by induction over the natural
numbers.)

Now let's revisit that missing number.  Let's call it X.  If we add up
the numbers we are given, we must get S(1000000) less X.  That is,

    T = S(1000000) - X.

Solving for X, we have

    X = S(1000000) - T.

Thus we can find the missing number by computing the total T of the
numbers we are given and then subtracting T from S(1000000).

This is what the `missing` function does, just generalized for any
value of N.  For example, if N = 5 and we were given the sequence
[1, 4, 2, 5], we could find the missing number (3) like so:

    Prelude> missing 5 [1, 4, 2, 5]
    3

And that's my solution.