I'm pretty sure I'm being stupid here (phrase "led like a puppy in tow" comes to mind), but I don't mind. I kinda asked for it 
Originally Posted by
Mario F.
Let me rephrase:
I'm assuming the 'trick' is that there is no scalar solution. We have
michael >= michel
mikel >= michael
michel <= michael
michel = 13.8 m/s
mikel = 13.9 m/s
which is satisfied with
michael = [ 13.8 m/s .. 13.9 m/s ]
which could also be written as
13.8 m/s <= michael <= 13.9 m/s
In other words, we don't know the exact speed Michael had, but if it was between 13.8 m/s and 13.9 m/s, inclusive, it satisfies the requirements.
I tried to write out the algorithm description, but it went on and on an on. So, instead, here's a proof of concept Python code for the simplest variants: only ≤ rules (as the third rule is the same as the first one), no rules between unknowns, and no contradictory rules:
Code:
#!/usr/bin/python
class Span:
def __init__(self):
self.min = float("-inf")
self.max = float("+inf")
def __str__(self):
if self.min == self.max:
return "%.1f" % self.min
elif self.min < self.max:
return "[ %.1f .. %.1f ]" % (self.min, self.max)
else:
return "No solution"
def notgreaterthan(self, value):
value = float(value)
if value < self.max:
self.max = value
return True
return False
def notlessthan(self, value):
value = float(value)
if value > self.min:
self.min = value
return True
return False
notless = [ ( 'michael', 'michel' ), ( 'mikel', 'michael' ) ]
known = { 'michel': 13.8, 'mikel': 13.9 }
unknown = { 'michael' }
solution = {}
for name in unknown:
solution[name] = Span()
changes = True
while changes:
changes = False
# Apply each rule to each tentative solution.
# If there are any changes to the tentative solution,
# set changes to True.
for rule in notless:
if (rule[0] in solution) and (rule[1] in known):
if solution[rule[0]].notlessthan(known[rule[1]]):
changes = True
elif (rule[1] in solution) and (rule[0] in known):
if solution[rule[1]].notgreaterthan(known[rule[0]]):
changes = True
for name in solution:
print("%s = %s\n" % (name, solution[name]))
Technically, the solver itself should be a separate class, having it written out like above is a no-no. Possibly the rules should be a separate class (a subclass of tuple), too.
I'd hafta get a nap to let my subconscious munch on the issues, before I'd like to suggest the interface for the solver; that's why the above is just a raw'n'ugly proof-of-concept. (It could be that the solver would be easier/better if the entire problem set was treated as a set of equalities and inequalities instead, with the result being a set of sets of equalities and inequalities.) Also, it's Saturday, and I did have a couple of beers.
For example, considering the type of the problem statements, each inequality or rule should be tested against the existing rules, so that the first contradictory rule stated raises an error.
For more complicated rules, a simple span is not going to cut it; it'd have to be a set of spans and scalars. With ≤ ≥ < > -based rules, each unknown is limited to a half space, thus a continuous span (with < > comes the added problem of end points not being within the span, though); with ≠ and conditional rules, the span may be split into multiple spans.
The nastiest cases to think of is when a span (or a set of spans) limits another span -- this happens when we have a rule that applies to two unknowns. I believe the correct option is to return the maximal set, so that the caller can fix any single variable within the spans specified, and obtain the subspace of the solutions by applying the solver again.
Also note that I completely ignore information not relevant to the solution. (The problem statement used phrases like "X had speed Y during time interval Z", where the Z are completely irrelevant to the problem at hand.)
I did like this problem -- even if I'm making a donkey out of myself -- because I can see it having some use case in the real world. Large collections of inequalities are nasty to manage in my opinion, and they do occur sometimes in the real world (underspecified problems), so I can see the benefit of having a tool that helps untangle them.
