I've run into a mildly interesting problem that some of my readers may be able to solve. (The rest of you will get about two sentences in and go, "Huh?" That's fine!)
Here's the problem: a universe of numbers 0-99999, of which only about 6500 are used at any time. I need a function that maps that sparse universe into a dense universe, and vice versa. (Yes, this sounds like a hash table problem: maybe, maybe not, keep reading.) One function converts the sparse universe number into its dense universe counterpart; the other function converts the dense universe counterpart to its sparse universe counterpart.
If this were a one-time use, or if the numbers actually used in the sparse universe did not change, this would be an obvious hash table solution. The problem is that while the total size of the dense universe does not change appreciably, which numbers are used in the sparse universe does change with some regularity, as some numbers are released, and others, previously released, commit some new crime, and come back into use. There is no practical way to store the translation, and it is important that the conversion from sparse to dense be consistent, and that we do not reuse numbers in the dense universe.
Now, it is entirely possible that there is no such solution. It strikes me as I write this that the requirement that we not reuse numbers in the dense universe means that it will almost certainly have to be as large as sparse universe. But I would be curious to see if anyone has an elegant solution to this.
The core problem is that there is not much space for a bar code containing the offender's five digit number. Narrow bar codes require the prisoners get close enough to the prisoner to hold the bar code up to the reader--and some prisoners really don't like correctional officers that close. (And some prisoners, of course, you do not want to get that close to, either.)