SRM480 - div2 - level two

srm480_div2_level2.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-

"""SRM480 - div2 - level two

TopCoder Security Agency (TSA, established today) is going 
to search for dangerous content in the internet.

There are N candidate websites numbered 0 through N-1. Each 
website has an address given as address[i]. It also has one 
or more keywords associated with it. The i-th element of 
keyword is a String describing all keywords associated with 
the i-th website. It is formatted as a single space separated 
list of keywords without leading or trailing spaces, where 
each keyword consists only of lowercase letters.

It is known to TSA that some keywords are dangerous. These 
keywords are given in String[] dangerous, where each element 
is a single dangerous keyword. For all other keywords it is 
not initially known whether they are dangerous or not.

TSA uses the following algorithm to identify all dangerous websites:

    Initially, all websites are considered to be safe.
    
    While there exists a website W such that it's considered safe and
        at least threshold of its keywords are known to be dangerous

        Website W becomes dangerous
        All keywords associated with W become dangerous   

    End While

Return a String[] containing the addresses of all dangerous 
websites found by the algorithm described above sorted in 
increasing order of website numbers. Return an empty String[] 
if no dangerous website is found.

Definition:
    Class: InternetSecurity
    Method: determineWebsite
    Parameters: String[], String[], String[], int
    Returns: String[]
    Method signature: String[] determineWebsite
        (String[] address, String[] keyword, 
            String[] dangerous, int threshold)
Notes
    - The address of a website is just a String used to 
      uniquely identify it. It doesn't necessarily adhere to 
      any common format of naming websites.
"""

class InternetSecurity(object):
    """Chicken Oracle

    Constraints:
        - address will contain between 1 and 50 elements, 
          inclusive.
        - Each element of address will contain between 1 and 
          50 characters, inclusive.
        - Each character in address will be a '.', '_' or a 
          lowercase letter ('a'-'z').
        - All elements of address will be distinct.
        - keyword will contain the same number of elements 
          as address.
        - Each element of keyword will contain between 1 
          and 50 characters, inclusive.
        - Each character in keyword will be a ' ' or a lowercase 
          letter ('a'-'z').
        - Each element in keyword will be formatted as 
          described in the statement above.
        - For each website, the keywords associated with it 
          will be distinct.
        - dangerous will contain between 1 and 50 elements, 
          inclusive.
        - Each element of dangerous will contain between 1 
          and 50 characters, inclusive.
        - Each character in dangerous will be a lowercase 
          letter ('a'-'z').
        - All elements of dangerous will be distinct.
        - threshold will be between 1 and 25, inclusive.

    >>> internetsecurity = InternetSecurity()
    >>> print internetsecurity.determineWebsite(
    ...     ["www.topcoder.com", 
    ...      "www.sindicate_of_evil.com", 
    ...      "www.happy_citizens.com", ], 
    ...     ["hack encryption decryption internet algorithm", 
    ...      "signal interference evil snake poison algorithm", 
    ...      "flower baloon topcoder blue sky sea, ", ], 
    ...     ["hack","encryption","decryption","interference","signal","internet", ], 
    ...     3)
    ['www.topcoder.com', 'www.sindicate_of_evil.com']
    >>> print internetsecurity.determineWebsite(
    ...     ["brokenlink","flowerpower.net","purchasedomain.com", ], 
    ...     ["broken","rose tulips","cheap free domain biggest greatest", ], 
    ...     ["biggest","enemy","hideout", ], 
    ...     2)
    []
    >>> print internetsecurity.determineWebsite(
    ...     ["a..a.ab.","...aa.b", ], 
    ...     ["a bc def","def ghij klmno", ], 
    ...     ["a","b","c","d","e", ], 
    ...     1)
    ['a..a.ab.', '...aa.b']
    >>> print internetsecurity.determineWebsite(
    ...     ["www.tsa.gov", ], 
    ...     ["information assurance signal intelligence research", ], 
    ...     ["signal","assurance","penguin", ], 
    ...     2)
    ['www.tsa.gov']
    """

    def __init__(self):
        pass

    def determineWebsite(self, address, keyword, dangerous, threshold, res=[]):
        for i in range(len(address)):
            words = [w.strip() for w in keyword[i].split(" ") if w]
            if len([w for w in words if w in dangerous]) >= threshold\
                    and address[i] not in res:
                res.append(address[i])
                dangerous += words
                res += self.determineWebsite(
                        address, keyword, dangerous, threshold, res)
        return [a for a in address if a in res]

if __name__ == '__main__':
    import doctest
    doctest.testmod()