1

This is a math problem with software limitations.

I am forced to work with a very inflexible tool and must check 5 fields, each of which can be one of 4 values (or left unset), to ensure that 1 and only 1 field is set with any of the 4 values. I cannot directly compare two fields, nor can I compare a field to null/0/unset. The interface is a horrible web based page, that only allows extremely simple logic to be input, via drop down menus, line by line.

The only pseudo logic I can use is as follows:

if <field> <equals/not equals> <val> [<and/or>] 
if <field> <equals/not equals> <val> [<and/or>]
...

Where:
<field> is limited to field1, field2, ..., field5
<val> is limited to val1, val2, val3, val4
[<and/or>] is optional and would lead in to the following line

Each single line of "if" statement is one entry. I know very little about the backend, but what I have gathered from testing is that "and" seems to be a higher precedence than "or". There is also an arbitrary limit (that I have no idea what it is) on the number of lines, so the fewer lines the better.

This "ruleset" is basically one giant "if" statement that will be run through, and eventually return true or false. The actions of true or false are determined outside of this ruleset, so the only thing I need to focus on here is the minimum number of steps to ensure that 1 and only 1 field has a value set, and a way to calculate how many entries are needed for that single ruleset given X fields with Y values. My goal is to calculate all of this out, so I can mathematically prove that doing this is a waste of time and the backend needs to be fixed. I have to make dozens of rulesets like this, all with different numbers of fields and values.

It seems to me that the only way to use this logic would be to check:

if field1 = val1 and 
if field2 = val1 or
if field1 = val1 and 
if field2 = val2 or
...
if field1 = val1 and
if field2 = val4 or
if field1 = val2 and
if field2 = val1 or
...

This is walking across all of the fields and values to to check if any two pairs of fields both have some value set. When this whole ruleset returns true, it means that more than one field had a value set. I believe the equation that models this is as follows:

((4*4*4)+(3*4*4)+(2*4*4)+(1*4*4))*2 = 320

This is walking each pair of fields without repeating since order does not matter, (1&2, 1&3, 1&4, 1&5, 2&3, 2&4, 2&5, 3&4, 3&5, 4&5), and comparing one value against the other 4, 4 times per pair of fields (one for each possible value). The *2 at the end is because this math is assuming that comparing one field value to another is a single step, while in reality that requires two steps to do.

I do not believe there is any faster way to walk through all of the values, and I believe my math is correct. If either of these or wrong, or can be optimized, please let me know.

As brought up in the comments, this could be scripted, yes. However, there are a vast number of things wrong with this setup as a whole and I would rather objectively show that it needs to be fixed, rather than working around it.

11
  • Can you copy the field value and manipulate the copy?
    – The Masked Avenger
    Jun 12, 2015 at 2:45
  • If you had internal variables, you could get away with 25 comparisons.
    – The Masked Avenger
    Jun 12, 2015 at 2:58
  • @TheMaskedAvenger No, unfortunately the tool I am working with is not able to do this. The only operations I can perform are as I said in the question. The configuration of it is through a graphical interface. My goal is to find the least number of steps to accomplish what needs to be done, and the function to calculate the number of steps needed. Jun 12, 2015 at 3:24
  • Too bad. If you can't set variables, you can't do things like 'if field1 has value1 then set var1 to var1+1', which would cut down on the number of tests needed.
    – The Masked Avenger
    Jun 12, 2015 at 3:37
  • Are you allowed to do anything? As written, there is an if test, but nothing specifying what you are allowed to do after the test passes. Do you need to do this with a single big if test, or can you nest them?
    – Cort Ammon
    Jun 12, 2015 at 5:33

1 Answer 1

2

I think your answer is as cheap as it can be done. However, in the process of trying to work out the logic, I found I needed to come up with a more standard definition of the problem and the language you face, so I wanted to include it here. It may be helpful, so I included it here before the answer.

Consider if I modeled the data you are receiving as a grid:

        blank  val1  val2  val3  val4
       +-----------------------------+
field1 | X                           |
field2 |              X              |
field3 | X                           |
field4 | X                           |
field5 |                          X  | <--// error - 2 fields set
       +-----------------------------+

What do we know about this setup:

  • No row can contain more than one X, because a field can only have one value
  • Your field = value and field != value tests are identical to querying the state of one square on the board.
  • The goal is to verify that all fields are blank, except for one of them.

Now the grammar you have access to is important. We're not just looking for positions, we're looking for a minimal set of rules expressed in this grammar to test those positions. I will assume, from your comments, that the grammar is a Sum of Products (SoP) form where "and" takes precedence over "or," and there are no parenthesis to create nested expressions.

For brevity, I'm going to invent a shorter syntax, using x13 to means "is there an x for field 1, val3." This just makes it shorter to write, and is perfectly translatable into if field1 = val3. Let's also use !x13 to means if field1 != val3, which is the typical meaning of ! in C based programming languages. I will use SoP notation so x12*x23 + !x34 means:

if field1 = val2 <and>
if field2 = val3 <or>
if field3 != val4

This also has a huge advantage of now using typical mathematical operator precedence, so I can avoid wasting lots of space with parenthesis (though I may use them where convenient). However, as a side effect of the limits in your language, blanks have to be tested by negation, so I can never test x30, I must instead test !x31*!x32*!x33*!x34. This will be important later

So now your example of

if field1 = val1 and 
if field2 = val1 or
if field1 = val1 and 
if field2 = val2 or
...
if field1 = val1 and
if field2 = val4 or
if field1 = val2 and
if field2 = val1 or
...

can be written as [(f11*f21) + (f11*f22) + ... + (f11*f24)] + [(f12*f21) + (f11*f22) + ... + (f11*f24)], with parenthesis and brackets provided for clarity. Now we know something important with this: any other valid notation must be logically equivalent to this one. We also know that the equation must be in SoP form. There's a lot of solutions available if we could do a bigger hierarchy than this.

I recommend this notation, because doing SoP optimization is standard hat for microelectronics engineers. We've been doing it a long time, so we know all of the tricks.

Now, with that notation aside, to solve the problem

Consider the following information:

  • Any one query (field = value) cannot contain enough information to detect a failure, because legally any field can have any value.
    • It takes a minimum of two terms to detect a failure. They will always be d together because it is in SoP form.
    • No new information is gathered by combining 3 terms with . For any 3 terms linked with , any non-failing input would have not-failed with fewer terms. Any failing input would have failed with 2 terms because the third term is a 'dont-care.'
  • <and> takes precedence, meaning you must build a list of failure-detection expressions, and then <or> them together to detect the failures.
  • These rules put together points out that an answer which only ever combines 2 queries (like your answer) will always be more efficient than an answer involving 3 queries.
    • Thus we only have to consider if there is a combination of rules in the form (x1*y1)+(x2*y2)+(x3*y3)+... which can be more efficient than your set.

The only possible way to detect a failure with this form is to have both x1 and y1 be terms that query a field that was not-blank. The only possible way to catch that is to test every possible pair. It is trivial to show that, if you skip a pair, you can miss an invalid input.

The only thing we can mix to possibly beat more value out of SoP is negation. So far we've only talked about testing for equality. Unfortunately, due to the language you have, it doesn't help. If I negate any test, such as !x32, that is identical to x30 + x31 + x33 + x34. Unfortunately, there is no where in your logic where it is helpful to lump a blank like x30 in with values like x31 using . Thus the only negation that would be useful to you is !x30, but as you mentioned, you can't test a blank, so the only useful negation is not possible.

All of this suggests that there are other ways to do it, but they will all require the same amount of steps that your solution requires, or worse.

1
  • Awesome. Its been a little while since I've done any kind of math like this, but the way you put it together makes a good bit of sense. Jun 12, 2015 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.