1

The goal is to take a binary space, say 64 bits, and make certain parts of it "valid" and certain parts "invalid", then increment, starting at 0, through that space, avoiding the invalid areas.

Space is made "invalid" by applying an arbitrary number of arbitrary rules. For instance "if bits 2 and 49 are set, that number is invalid", etc..

Space unaffected by rules is considered "valid".

The easy way to do this is simply apply all the rules every time you increment. But this is unrealistic for a 64 bit space with even a few rules, it takes forever. For larger bit spaces and or alot of/complex rules, same problem.

So a much more efficient method is needed. Something that takes very few instructions and the end result is essentially only incrementing to numbers that are in valid space.

I would imagine this has already been figured out in a thesis somewhere and is probably used every day in file systems or something common.

Not Really
  • 19
  • 1
  • Update: Its not necessary to increment sequentially through the resultant "valid" space, but it is important to know when you have incremented through all of it. – Not Really Jul 23 '17 at 04:47
  • I'm assuming this is an interview question? One approach (and probably the one that the interviewer was looking for) is to use [function composition](https://en.wikipedia.org/wiki/Function_composition_(computer_science)) (or, in an OO world, [decorator](https://en.wikipedia.org/wiki/Decorator_pattern) objects). – kdgregory Jul 23 '17 at 17:59
  • Its not an interview question, its an experimental program I'm working on to generate logic circuits that match an arbitrary truth table. I will look up function composition and decorator. – Not Really Jul 24 '17 at 02:32
  • Look at space subsets, and try to condense a subset "constant" across spaces into a single bit suitable for enumeration. – Frank Hileman Jul 24 '17 at 22:14

1 Answers1

2

You're looking for an automated way to transform a set of arbitrary validation rules into a set of arbitrary incrementing rules that only produce valid numbers.

If such a thing existed we'd have no trouble predicting prime numbers. Since we do, it doesn't.

This doesn't mean that valid incrementing rules don't exist for some validation rules. Odd numbers for example. But they certainly don't exist for every arbitrary set of validation rules.

candied_orange
  • 102,279
  • 24
  • 197
  • 315
  • Besides odd numbers, lets say I add a second arbitrary rule, like "every 4th odd number gets skipped". Now I need a counter and a rule checker, but I am only doing the work of checking 1 rule (is it 4th odd?), when two are being applied (odd + skip every 4th). So this leads me to believe that this problem could be modified in some way to result in significantly less work being done than the number of effective rules in place. Also, a solution to this problem doesnt have to be pure incrementing, it just need to be alot more efficient than brute force rule checking of the entire space. – Not Really Jul 23 '17 at 04:33
  • Also, lets say I do something like make an arbitrary rule that happens to line up with a very efficient intrinsic machine property, like every 256th odd number gets skipped. Now I can apply a rule like that using a byte rollover,without doing any work, etc.. – Not Really Jul 23 '17 at 04:34