Coding Challenge

[Alex Tweedly]

Hi Malte. Hope I'm not too late to the party :-)

Here's some sample code that appears to work on my small sample data. 
It's not easy to come up with good test data here - nothing obvious 
could generate realistic test data by program.

Summary is

1. deal with all equality cases first. For every set of equal-age names, 
we use the same name (first one alphabetically) for the 'younger' 
relationship table.

2. normalize the realtionships (always younger, replace by same-age 
equivalent

3. for each name, keep two lists - those older and still to be handled, 
and those older but already dealt with

4. repeatedly, take a name from the first list and try to move it to the 
second. If this name itself has nothing left on its 'still-to-do' list 
then we have completely moved this name - remove it from the still-to-do 
list.

This should be reasonably efficient, though there are possible 
optimizations by keeping back-pointers - so let me know if this is too 
slow when you start using thousands of names,

-- Alex.
>
> global gSameAge   -- array of those who are the same age
> global gRelate -- array of direct (i.e. defined) relationships
> global gOlder -- array containing (one per line) all those who are 
> known older than the key
> global gOlderStillToDo
>
> on c
>    put URL "file:~/data.txt" into tData
>
>    put empty into gSameAge
>    put empty into gOlder
>    put empty into gOlderStillToDo
>    -- deal with all the equal age info
>    -- for each group of same-age people, we will use the first 
> alphabetically
>    -- step 1. normalize each individual equality to be alphabetocal
>    -- step 2. sort the set of equality facts to be alphabetical
>    -- step 3. for each subsequent name, store the earliest equal one
>    repeat for each line  L in tData
>       if word 2 of L = "=" then
>          if word 1 of L < word 3 of L then
>             put word 1 of L && word 3 of L & CR after tEqual
>          else
>             put word 3 of L && word 1 of L & CR after tEqual
>          end if
>       end if
>    end repeat
>    -- sort these to handle cases like a=b and b=d
>    sort lines of tEqual
>    repeat for each line L in tEqual
>       if gSameAge[word 1 of L] is not empty then
>          put gSameAge[word 1 of L] into gSameAge[word 2 of L]
>       else
>          put word 1 of L into gSameAge[word 2 of L]
>       end if
>    end repeat
>
>    -- now normalize the direct relationships
>    put empty into gRelate
>    repeat for each line  L in tData
>       if word 2 of L = "<" then
>          put sample(word 1 of L) into t1
>          put sample(word 3 of L) into t2
>          put t1 && t2 & CR after tUnequal
>       end if
>    end repeat
>
>    -- first the direct relationships
>    repeat for each line L in tUnequal
>       put word 2 of L & CR after gOlderStillToDo[word 1 of L]
>    end repeat
>
>    repeat 10000 timeS -- forever, but avoid infinite loops
>       put 0 into tNeedToDoAgain
>       put the keys of gOlderStillToDo into tKeys
>       -- for each one that still has something to do
>       repeat for each line K in tKeys
>          put empty into tNewlyFound
>          put empty into tStillToDo
>          repeat for each line L in gOlderStillToDo[K]
>             if L is not among the keys of gOlderStillToDo then
>                -- add this older one, *and* all names known to be 
> older than it
>                put L & CR after gOlder[K]
>                put gOlder[L] & CR after tNewlyFound
>             else -- this one hasn't yet been done, so we may need 
> another iteration
>                put L & CR after tStillToDo
>                add 1 to tNeedToDoAgain
>             end if
>          end repeat
>          if tStillToDo is empty then
>             delete variable gOlderStillToDo[K]
>          else
>             put tStillToDo into gOlderStillToDo[K]
>          end if
>          repeat for each line L in tNewlyFound
>             if L = K then   -- there is a loop in age info - i.e. bad 
> input !!
>                ask "loop" && L && K
>                exit to top
>             end if
>             if L is not among the lines gOlder[K] and L is not among 
> the lines of gOlderStillToDo[K] then
>                put L & CR after gOlderStillToDo[K]
>                add 1 to tNeedToDoAgain
>             end if
>          end repeat
>       end repeat
>       if tNeedToDoAgain = 0 then exit repeat
>    end repeat
>    repeat for each key K in gOlder
>       put K & "--->" & CR after field "F"
>       put gOlder[K] after field "F"
>
>    end repeat
> end c
>
> function sample pA
>    if gSameAge[pA] is not empty then
>       return gSameAge[pA]
>    else
>       return pA
>    end if
> end sample
>



On 08/03/2011 18:49, Malte Brill wrote:
> Thanks for the head ups folks,
>
> Björnke and Mark: I do not have the exact ages to sort by. All I do have is relations:
>
> Malte is older than Björnke
> Mark is older than Malte
>
> And now I need to compute if it is valid to say:
> - Björnke is older than Mark  (obviously not)
> - Björnke is the same age as Mark (obviously not)
> - Björnke is younger than Mark. (That´s the one)
>
> What comes easy to the human brain in fact appears to be a lot more difficult when having to be tackled computationaly.
>
> Chris: Yes, I want such a list in the end. But in order to finally get this I will need to tell the machine which relations are legal first (the user tells which relations there are) and ideally filter out the data for relations that make no sense. Now I wish it was easy to tell the machine to just use logic and make sense itself :D This comparison has to be done for thousands of entities (children in this case).
>
> Cheers,
>
> Malte
>
>
> _______________________________________________
> use-livecode mailing list
> use-livecode at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-livecode
>