0
$\begingroup$

The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem.

Imagine a row of commands:

A -> Perform X

B -> Perform Y

C -> Perform Z

You read the above as if the data you're looking at is A, perform X, else if it's B, perform Y ...

Now let me add more logic.

A & B -> Perform X

C & D -> Perform Y

E & F -> Perform Z

More complicated.

A & B & C -> Perform X

A & B & D -> Perform Y

A & B & E -> Perform Z

Notice in the above, if I do the normal if/else thing I would have to conditionally check A 3 times, B 3 times and C, D and E once in the case the data dictates that I must perform Z.

This can be optimized as check A & B once, then do an array lookup (or hash lookup) of the last element which will point you to the action to be performed.

Even more complex.

A & B & E -> Perform Z

A & B & C & D -> Perform X

A & D -> Perform Y

C -> Perform W

This would translate to A & B as one check, then within that condition check E or (C & D). If not that, then see if it's A & D, or if it's C.

Another way to reduce the above example could be:

let I = A & B

I & E -> Perform Z

I & !E & D -> Perform X

!I & A & D -> Perform Y

!I & C -> Perform W

I wrote it the above way because that's how I'm thinking I'll represent it in some data structure.

Another piece of info that makes this problem slightly more tractable is that while I've used symbols like A, B, C ... in reality it's something like A means 1 - 100, and let's say C may mean 101 - 200. Therefore if I see A I can safely say C is not possible.

I'm not sure how to think about this problem, but my brain is thinking subset sum, some tree traversal or like building trees of disjoint sets, and ultimately also thinking this all could be represented as perfect hashing.

Is there a name for this problem?

$\endgroup$
  • 1
    $\begingroup$ I would just call this problem "Turing machine". You should just build a decison tree as efficient as possible and use nested if-else statements to realise it. $\endgroup$ – Optidad Jan 22 '19 at 12:19
  • $\begingroup$ You say "this problem", but what exactly is the problem? I don't see a clear statement of a problem. If you're looking for an algorithm to solve some problem, you might try describing the input to the algorithm and the desired output and how they need to relate to each other. $\endgroup$ – D.W. Feb 10 '19 at 6:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.