Friday, October 16, 2009

Ugly numbers in a heap

As I was saying, a good solution to finding ugly numbers would be to somehow enumerate only numbers which are known to be ugly, removing them from memory after they have been read. I couldn't think of the way to do that. Internet to the rescue.

Here's what you do:
  1. Store the number 1 in a set.
  2. Consider the smallest item, "n" in the set. That is counted as the next ugly number.
  3. Add the numbers n*2, n*3, and n*5 to the set.
  4. Remove n from the set.
  5. Repeat steps 2-4 until you reach the desired ugly count (1500).
Each time you search for the next ugly number, you remove one number from the set but add three more, for a net gain of two. Thus, the set of numbers you are storing on each step i is (2*i-1). That's a manageable memory size. But there's still a snag.

Sets are unordered lists, and we want to always find the smallest number of the set as efficiently as possible. How do we do that? We can't just read every number in the set, or the problem scope quickly becomes O(n2). Can't have that.

Turns out there is an ideal data structure for handling this kind of thing, but it's something I haven't looked at since I was an undergrad. It's called a min-heap.

A heap is a special kind of binary tree, where every level of the tree is filled to maximum density. For instance, in a heap with 8 elements, you know that the top level has one node with exactly two children; each of those two children has two children (that makes 7), and the leftmost node at the third level has one child on the left.

The neat thing about using a heap is that because of its predictable structure, you can represent it using an expandable one-dimensional array. You don't have to mess with pointers or the other headaches of data structures. If you are looking for root.left.right, you just calculate the spot in the array and access element 4.

A min-heap is constructed in such a way that the children of each node are guaranteed to be larger than the parent node. In other words, the smallest value is guaranteed to be at the root, and each child of the root is itself a min-heap with the smallest element of that at the root.

(If I'm going too fast for you, speak up. I don't believe I've ever done a post specifically on binary trees, so maybe I should.)

In any case... you can do two things with a min-heap: add a new element, which is rapidly sorted to the right place; and remove the root element, which then moves the next smallest element into the root and fixes the rest of the heap so that it is still a min-heap.

This is exactly what we need. It keeps the cost of searching for the smallest known ugly number to O(log n), where n is the number of elements currently in the list.

So to recap:
  1. Write your own min-heap class, which is the fun part. ;)
  2. Add the number 1 to the heap.
  3. Inspect the root of the heap, and count that number ("r") as ugly.
  4. Add 2r, 3r, and 5r to the heap.
  5. Delete the root.
  6. Repeat steps 3-5 until you reach the desired ugly count (1500).
Actually it turned out that wasn't quite the answer, because you can get duplicate ugly numbers on the heap. For instance, in the second pass you add 2*3, while in the third pass you add 3*2, which results in multiple 6's on the heap. But that's easy to fix. All we have to do is change step 5 to: "Keep deleting the root until it is no longer equal to the last recorded ugly number."

And there you go. Small storage space, quick execution time, ignores non-ugly numbers, and finishes in 3 seconds easily.

SPOILER:

In case you wondered, the answer is 859,963,392.
Posted by at
Labels: , , ,

2 comments:

  1. BeamStalkOctober 16, 2009 at 3:47 PM

    I like that. I have been out of programming for so long it is almost foreign to me. I need to get back into it.

    ReplyDelete
  2. CodeWeaverApril 3, 2010 at 1:38 PM

    Hi, Russell. I once commented long ago about your Sudoku solver, and on checking back in, I find this delightful little puzzle. I really must come back here more often.

    I thought maybe about striking up a conversation on the utility of the various kinds of heaps, including priority heaps, as they have come up more than a few times in some puzzles I've solved. But I thought instead I'd hit you with a double-whammy of passing interest.

    I wish I could take total credit for the following, but its based on a solution to a related number set generating problem I found. Here's my variation in Haskell, which I've decided to learn recently:

    -------------



    dirtyMultiples :: [Int] -> Int -> [Int]
    dirtyMultiples ds x = [x*y | y<-ds]

    mergeUnique :: [Int] -> [Int] -> [Int]
    mergeUnique u@(x:xs) v@(y:ys) = case compare x y of
    LT -> x : mergeUnique xs v
    GT -> y : mergeUnique u ys
    otherwise -> x : mergeUnique xs ys

    dirtyList :: Int -> [Int]
    dirtyList x =
    let
    dirtyList' = 1:((dirtyMultiples dirtyList' 2) `mergeUnique` (dirtyMultiples dirtyList' 3) `mergeUnique` (dirtyMultiples dirtyList' 5))
    in
    take x dirtyList'

    dirtyNumber :: Int -> Int
    dirtyNumber x = head $ drop (x-1) $ dirtyList x

    -------------

    The result of evaluating

    dirtyNumber 1500

    is in fact your answer, so thanks for posting a verification. :)

    But what is more interesting is what you can take back with you to your own language. (I'm not really intending this to be an advocacy of Haskell). This program runs in O(n).

    The basic idea here is that there are three 'streams' of data describing the sequential generation of the sets of the multiples of 2, 3, and 5 respectively. These three streams are merged into a new fourth stream that describes the set of dirty numbers (and as a consequence, as they're being merged, the duplicates are removed).

    Of course, there's a mutual dependency here. The fourth stream, the dirty numbers, is what the first three streams need to generate their values. However, the rate at which the dirty numbers are generated by the three streams of multiples is faster than the rate they are needed by the three streams of multiples. So by seeding the dirty number stream, I end up with all four streams mutually supporting each other.

    In Haskell, these streams are represented by lists, and all four lists are infinite in length. The 'dirty stream' is generated by the dirtyList function.

    I can get away with this because Haskell only evaluates as much of any value as is needed to finish the immediate computation (lazy evaluation), so as long as I don't ask for the entire list of dirty numbers, I'm fine. The function dirtyNumber does this by asking for the head of the infinite list that results when I drop the first x-1 values. 'drops' are handled by the garbage collection whenever the expressions have evaluated far enough not to need part of the list.

    The merge itself is being done on the three list of multiples which themselves are infinite lists -- but it only asks for as much of each of the list of multiples as is necessary to continue the merge.

    In Java or C++ you would probably construct list generator objects to do the work to evaluate on demand. Depending on your implementation, you might get away with just one actual linked list (the dirtyList), plus the generator multiples which can give you the next multiple as you need it. Cleaning up elements you 'don't need' in a non garbage collected language would take a little care.

    Anyway, by seeing some of your other posts on teaching programming to young ones, I thought you might appreciate the perspective one can gain by looking at a problem from another language. :)

    Darn, now I have to go and implement this solution in C++. Back in a moment.

    ReplyDelete

Subscribe to: Post Comments (Atom)