User bio
404 bio not found
Darwin
Member since Jan 29, 2018
Posts:
Timo has not published any posts yet.
Replies:

Here is the implementation:
 

ClassMethod MaxCoverage(ByRef SourceLists, Output Solution as %List) {
    /*
    1. run through each sourcelist and generate a value - list index
     e.g. List(3) would result in a index ^||idx(5,3)="" ^||idx(8,3)="" ^||idx(9,3)=""
     also add the list to a still valid list
    2. iterate over the index find the first value with only one entry and add that list to result list, then run through the list and remove all value index entries for values contained in the list. remove the list from the still valid list.
    3. if no value only has just one list entry, pick the list with the most entries that is on the still valid list. iterate over the list and check each value against the value index, if the value is still in the index remove the value index and add list to the result list. remove the list from the still available list
    4. iterate above until either value index has no more entries, or the still valid list has no more entries.
    5. result list contains all lists required for maximum coverage
    */
    kill Solution
    kill ^||lengthIdx
    kill ^||idx
    kill ^||covered
    set idx=""
    for {
        set idx=$order(SourceLists(idx))
        quit:idx=""
        set listid=0
        set stillAvailable(idx)=""
        set ^||lengthIdx($listlength(SourceLists(idx)),idx)=idx
        while $listnext(SourceLists(idx),listid,listval) {
            set ^||idx(listval,idx)=""
        }
    }


    set listid=""
    // for loop - exit when either ^||idx has no more entries or the still valid list has no more entries
    for {
        if $data(stillAvailable)=0 {
            // no more lists to process
            quit
        }
        if $data(^||idx)=0 {
            // no more values to process
            quit
        }
        // find the first value with only one entry
        set val=""
        set found=0
        for {
            quit:found=1
            set val=$order(^||idx(val))
            quit:val=""
            set listid=""
            for {
                set listid=$order(^||idx(val,listid))
                quit:listid=""
                // found a value check now if ther eis more than one entry
                if $order(^||idx(val,listid))="" {
                    // found a value with only one entry
                    set found=1
                    quit
                }
            }
        }

        if found=0 {
            // haven't found one yet so use the one with the most entries ^||lengthIdx(
            set res=$query(^||lengthIdx(""),-1,val)
            if res'="" {
                set listid=val
            } else {
                // no more entries
                // should never hit this
                quit
            }
        }

        if listid'="" {
            // got a list now process it
            // first remove the list from the available lists
            kill stillAvailable(listid)
            kill ^||lengthIdx($listlength(SourceLists(listid)),listid)
            // iterate trhough the list, check value against the value index
            set listval=0
            w !,"found listid:"_listid,!

            set ptr=0
            set added=0
            while $listnext(SourceLists(listid),ptr,listval) {
                // check if the value is still in the index
                w !,"   checking value:"_listval
                If $INCREMENT(^||covered(listval))
                if $data(^||idx(listval)) {
                    w " - found it!"
                    // remove the value from the index
                    kill ^||idx(listval)
                    // add the list to the result list
                    if added=0 {
                        set Solution=$select($get(Solution)="":$listbuild(listid),1:Solution_$listbuild(listid))
                        set added=1
                    }
                }
            }
        }
    }
}

And the execution result:

DEV>set List(1)=$lb(3,5,6,7,9),List(2)=$lb(1,2,6,9),List(3)=$lb(5,8,9),List(4)=$lb(2,4,6,8),List(5)=$lb(4,7,9)

DEV>d ##class(Custom.codegolf).MaxCoverage(.List,.res)
found listid:2

   checking value:1 - found it!
   checking value:2 - found it!
   checking value:6 - found it!
   checking value:9 - found it!
found listid:1

   checking value:3 - found it!
   checking value:5 - found it!
   checking value:6
   checking value:7 - found it!
   checking value:9
found listid:5

   checking value:4 - found it!
   checking value:7
   checking value:9
found listid:4

   checking value:2
   checking value:4
   checking value:6
   checking value:8 - found it!

DEV>zw res
res=$lb("2","1","5","4")

DEV>zw ^||lengthIdx
^||lengthIdx(3,3)=3

DEV>zw ^||covered
^||covered(1)=1
^||covered(2)=2
^||covered(3)=1
^||covered(4)=2
^||covered(5)=1
^||covered(6)=3
^||covered(7)=2
^||covered(8)=1
^||covered(9)=3

my approach would be:

1. run through each list and generate a value - list index
     e.g. List(3) would result in a index ^||idx(5,3)="" ^||idx(8,3)="" ^||idx(9,3)=""
     also add the list to a still valid list
2. iterate over the index find the first value with only one entry and add that list to result list, then run through the list and remove all value index entries for values contained in the list. remove the list from the still valid list.
3. if no value only has just one list entry, pick the list with the most entries that is on the still valid list. iterate over the list and check each value against the value index, if the value is still in the index remove the value index and add list to the result list. remove the list from the still available list
4. iterate above until either value index has no more entries, or the still valid list has no more entries.
5. result list contains all lists required for maximum coverage
Hope that makes sense.

Certifications & Credly badges:
Global Masters badges:
Followers:
Following:
Timo has not followed anybody yet.