Coding Challenge

[Nonsanity]

On Fri, Mar 11, 2011 at 1:54 PM, Nonsanity <form at nonsanity.com> wrote:

> Try this. I haven't tested, but the logic looks sound enough...


Actually, don't try that, try this. That one had flaws this one should fix.
(But again, not tested at ALL.)



private function resolveRelation pPers1,pPers2,pRelation
   put sRelations[pPers1][pPers2] into relationship

   -- if the relationship is a direct match, return true
   if relationship = pRelation then
      return true
   -- else if there is a direct relationship, but not the one we're testing
for, then fail
   else if relationship is not empty and relationship is not pRelation then
      return false
   end if

   -- make a reversed copy of our target relationship
   put pRelation into Rel
   if pRelation is "<" then put ">" into Rel
   else if pRelation is ">" then put "<" into Rel

   -- otherwise, there is no direct relationship, so look for an indirect
one
   -- to find one, we first find other items related to both inputs that
have the same relationship exactly
   -- then iterate through the tree looking for further >= or <=
relationships
   local tOther
   put the keys of sRelations[pPers1] into tOther
   repeat for each line personB in tOther
      if sRelations[pPers1][personB] = pRelation then
         get traverseList(pPers1,personB,pRelation,Rel)
         if it is true then
            set sRelations[pPers1][pPers2] to pRelation
            set sRelations[pPers2][pPers1] to Rel
            return true
         end if
      end if
   end repeat

   -- test for the other direction, reverse everything
   put the keys of sRelations[pPers2] into tOther
   repeat for each line personB in tOther
      if sRelations[pPers2] = Rel then
         get traverseList(pPers2,personB,Rel,Rel)
         if it is true then
            set sRelations[pPers1][pPers2] to pRelation
            set sRelations[pPers2][pPers1] to Rel
            return true
         end if
      end if
   end repeat

   return false
end resolveRelation


-- pPersV varies as we move through the tree
-- pPersX is our target person
private function traverseList pPersV,pPersX,pRelation,pRevRel
   -- are the two people of the correct relationship and/or equal?
   if sRelations[pPersV][pPersX] = pRelation or sRelations[pPersV][pPersX] =
"=" then
      return true
   end if
   local tOther
   put the keys of sRelations[pPersV] into tOther
   repeat for each line personB in tOther
      -- only follow branches leading to the same relationship we are
testing (<= or >=)
      -- So if: A<B and B<C and C=D and D<E then "A<E" must be true
      if sRelations[pPersV][personB] = pRelation or
sRelations[pPersV][personB] = "=" then
         if traverseList(personB,pPersX,pRelation) then
            -- save this data directly for future speed
            set sRelations[pPersV][pPersX] to pRelation
            set sRelations[pPersX][pPersV] to pRevRel
            return true
         end if
      end if
   end repeat
   return false
end traverseList


 ~ Chris Innanen
 ~ Nonsanity