Problem:


Cyber Guardian

In the good old days, the Internet was free from fears and
terrorism. People did not have to worry about any cyber criminals or mad
computer scientists. Today, however, you are facing atrocious crackers 
wherever you are, unless being disconnected. You have to protect
yourselves against their attacks.

Counting upon your excellent talent for software construction and
strong sense of justice, you are invited to work as a cyber
guardian. Your ultimate mission is to create a perfect firewall system
that can completely shut out any intruders invading networks and protect
children from harmful information exposed on the Net. However, it is
extremely difficult and none have ever achieved it before. As the first 
step, instead, you are now requested to write a software simulator
under much simpler assumptions.

In general, a firewall system works at the entrance of a local network
of an organization (e.g., a company or a university) and enforces its local
administrative policy. It receives both inbound and outbound packets
(note: data transmitted on the Net are divided into small segments
called packets) and carefully inspects them one by one whether or not
each of them is legal. The definition of the legality may
vary from site to site or depend upon the local administrative
policy of an organization. Your simulator should accept data representing
not only received packets but also the local administrative policy.

For simplicity in this problem we assume that each network packet
consists of three fields: its source address, destination address, and
message body. The source address specifies the computer or appliance
that transmits the packet and the destination address specifies the
computer or appliance to which the packet is transmitted. An address
in your simulator is represented as eight digits such as 03214567 or
31415926, instead of using the standard notation of IP addresses
such as 192.168.1.1. Administrative policy is described in
filtering rules, each of which specifies some collection of
source-destination address pairs and defines those packets with the
specified address pairs either legal or illegal. 

Input

The input consists of several data sets, each of which represents
filtering rules and received packets in the following format:

n m

rule1

rule2

...

rulen

packet1

packet2

...

packetm

The first line consists of two non-negative integers n and
m. If both n and m are zeros, this means the end
of input. Otherwise, n lines, each representing a filtering
rule, and m lines, each representing an arriving packet, follow
in this order. You may assume that n and m are less than
or equal to 1,024.

Each rulei is in one of the following formats:

permit source-pattern destination-pattern

deny source-pattern destination-pattern

A source-pattern or destination-pattern is a
character string of length eight, where each character is either a
digit ('0' to '9') or a wildcard character '?'. For instance,
"1????5??" matches any address whose first and fifth digits are '1'
and '5', respectively. In general, a wildcard character matches any
single digit while a digit matches only itself.

With the keywords "permit" and "deny", filtering rules specify
legal and illegal packets, respectively. That is, 
if the source and destination addresses of a packed are matched with
source-pattern and destination-pattern, respectively, it 
is permitted to pass the firewall or the request is
denied according to the keyword. Note that a permit rule 
and a deny rule can contradict since they may share the same source
and destination address pair. For the purpose of conflict resolution,
we define a priority rule: rulei has a higher priority over
rulej if and only if i > j. For
completeness, we define the default rule: any packet is illegal unless
being explicitly specified legal by some given rule.

A packet is in the following format:

source-address destination-address message-body

Each of the first two is a character string of length eight that
consists solely of digits. The last one is a character string
consisting solely of alphanumeric characters ('a' to 'z', 'A' to 'Z',
and '0' to '9'). Neither whitespaces nor special characters can occur
in a message body. You may assume that it is not empty and that its
length is at most 50. 

You may also assume that there is exactly one
space character between any two adjacent fields in an input line
representing a rule or a packet.

Output

For each data set, print the number of legal packets in the first
line, followed by all legal packets in the same order as they occur in
the data set. Each packet must be written exactly in one line. If the
data set includes two packets consisting of the same source and
destination addresses and the same message body, you should consider
them different packets and so they must be written in different
lines. Any extra whitespaces or extra empty lines must not be
written. 

Sample Input

2 5
permit 192168?? ?12??34?
deny 19216899 012343?5
19216711 11233340 HiIamACracker
19216891 01234345 Hello
19216899 01234345 HiIamAlsoACracker
19216809 11200340 World
00000000 99999999 TheEndOfTheWorld
1 2
permit 12345678 23456789
19216891 01234345 Hello
12345678 23456789 Hello
0 0

Output for the Sample Input

2
19216891 01234345 Hello
19216809 11200340 World
1
12345678 23456789 Hello



Sample input:
2 5
permit 192168?? ?12??34?
deny 19216899 012343?5
19216711 11233340 HiIamACracker
19216891 01234345 Hello
19216899 01234345 HiIamAlsoACracker
19216809 11200340 World
00000000 99999999 TheEndOfTheWorld
1 2
permit 12345678 23456789
19216891 01234345 Hello
12345678 23456789 Hello
0 0


Sample output:
2
19216891 01234345 Hello
19216809 11200340 World
1
12345678 23456789 Hello

Submission status: Wrong Answer

Solution code:
def ipmatch(ip,iprule):
    ret=1
    for i in range(8):
        if iprule[i]!='?':
            ret*=ip[i]==iprule[i]
    return ret


def rulematch(sip,dip,rule):
    rulesip=rule[1]
    ruledip=rule[2]
    return ipmatch(sip,rulesip) and ipmatch(dip,ruledip)

while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0 and m==0:
        break
    else:
        rules=[]
        for i in range(n):
            rulei=raw_input().split()
            rules.append(rulei)
        for i in range(m):
            message=raw_input().split()
            sip=message[0]
            dip=message[1]
            for j in range(-1,-n-1,-1):
                if rules[j][0]=='deny':
                    if rulematch(sip,dip,rules[j]):
                        break
                else:
                    if rulematch(sip,dip,rules[j]):
                        print sip,dip,message[2]
                        break

Submission status: Wrong Answer

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	if n == 0: break
	P = []; D = []
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		r = re.compile(s+d)
		if p[0] == "p":
			P.append(r)
		else:
			D.append(r)
	for i in range(m):
		s,d,name = raw_input().split()
		tf = any(r.search(s+d) for r in P) and not any(r.search(s+d) for r in D)
		if tf:
			print s,d,name

Submission status: Wrong Answer

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	P = []; D = []
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		r = re.compile(s+d)
		if p[0] == "p":
			P.append(r)
		else:
			D.append(r)
	for i in range(m):
		s,d,name = raw_input().split()
		tf = any(r.search(s+d) for r in P) and not any(r.search(s+d) for r in D)
		if tf:
			print s,d,name

Submission status: Wrong Answer

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	P = []; D = []
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		r = re.compile(s+d)
		if p[0] == "p":
			P.append(r)
		else:
			D.append(r)
	ans = []
	for i in range(m):
		s,d,name = raw_input().split()
		if any(r.search(s+d) for r in P) and not any(r.search(s+d) for r in D):
			ans.append([s,d,name])
	print len(ans)
	for s,d,name in ans:
		print s,d,name

Submission status: Accepted

Solution code:
# AOJ 1111: Cyber Guardian
# Python3 2018.7.15 bal4u

import re

while True:
	n, m = map(int, input().split())
	if (n|m) == 0: break
	rule, ans = [], []
	for i in range(n):
		g, s, d = input().split()
		rule.append((g[0] == 'p', s.replace("?", "[0-9]"), d.replace("?", "[0-9]")))
	for i in range(m):
		s, d, m = input().split()
		for G, S, D in rule[::-1]:
			if re.match(S, s) and re.match(D, d):
				if G: ans.append((s, d, m))
				break
	print(len(ans))
	for a in ans: print(*a)

Submission status: Accepted

Solution code:
# AOJ 1111: Cyber Guardian
# Python3 2018.7.15 bal4u

import re

while True:
	n, m = map(int, input().split())
	if (n|m) == 0: break
	rule, ans = [], []
	for i in range(n):
		g, s, d = input().split()
		rule.append((g[0] == 'p', \
		             re.compile(s.replace("?", "[0-9]")), \
		             re.compile(d.replace("?", "[0-9]"))))
	for i in range(m):
		s, d, m = input().split()
		for G, S, D in rule[::-1]:
			if re.match(S, s) and re.match(D, d):
				if G: ans.append((s, d, m))
				break
	print(len(ans))
	for a in ans: print(*a)

Submission status: Accepted

Solution code:
# AOJ 1111: Cyber Guardian
# Python3 2018.7.15 bal4u

import re
while True:
	n, m = map(int, input().split())
	if (n|m) == 0: break
	rule, ans = [], []
	for i in range(n):
		g, s, d = input().split()
		rule.append((g[0] == 'p', re.compile((s+d).replace("?", "[0-9]"))))
	for i in range(m):
		s, d, m = input().split()
		sd = s+d
		for G, SD in rule[::-1]:
			if re.match(SD, sd):
				if G: ans.append((s, d, m))
				break
	print(len(ans))
	for a in ans: print(*a)

Submission status: Accepted

Solution code:
# AOJ 1111: Cyber Guardian
# Python3 2018.7.15 bal4u

import re

while True:
	n, m = map(int, input().split())
	if (n|m) == 0: break
	rule, ans = [], []
	for i in range(n):
		g, s, d = input().split()
		rule.append((g[0] == 'p', re.compile((s+d).replace("?", "\d"))))
	for i in range(m):
		s, d, m = input().split()
		sd = s+d
		for G, SD in rule[::-1]:
			if re.match(SD, sd):
				if G: ans.append((s, d, m))
				break
	print(len(ans))
	for a in ans: print(*a)

Submission status: Accepted

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if (N, M) == (0, 0):
        break
    rules = []
    for _ in xrange(N):
        f, p1, p2 = raw_input().split()
        rules += [(f, p1+p2)]
    rules = rules[::-1]
    def check(s):
        def match(pattern, address):
            for p, a in zip(pattern, address):
                if p == "?":
                    continue
                if p != a:
                    return False
            return True
        a1, a2, _ = s.split()
        for flag, pattern in rules:
            if flag == "permit" and match(pattern, a1+a2):
                return True
            if flag == "deny" and match(pattern, a1+a2):
                return False
    ans = filter(check, [raw_input() for _ in xrange(M)])
    print len(ans)
    if len(ans) != 0:
        print "\n".join(ans)

Submission status: Accepted

Solution code:
import re
while True:
    N, M = map(int, raw_input().split())
    if (N, M) == (0, 0):
        break
    rules = []
    for _ in xrange(N):
        f, p1, p2 = raw_input().replace("?", "\d").split()        
        rules += [(f, re.compile(p1+p2))]
    rules = rules[::-1]
    def check(s):
        a1, a2, _ = s.split()
        a = a1 + a2
        for f, r in rules:
            if f == "permit" and r.match(a):
                return True
            if f == "deny" and r.match(a):
                return False
    ans = filter(check, [raw_input() for _ in xrange(M)])
    print len(ans)
    if len(ans) != 0:
        print "\n".join(ans)

Submission status: Accepted

Solution code:
def ipmatch(ip,iprule):
    ret=1
    for i in range(8):
        if iprule[i]!='?':
            ret*=ip[i]==iprule[i]
    return ret


def rulematch(sip,dip,rule):
    rulesip=rule[1]
    ruledip=rule[2]
    return ipmatch(sip,rulesip) and ipmatch(dip,ruledip)

while(1):
    [n,m]=[int(x) for x in raw_input().split()]
    if n==0 and m==0:
        break
    else:
        anssum=0
        ansmes=[]
        rules=[]
        for i in range(n):
            rulei=raw_input().split()
            rules.append(rulei)
        for i in range(m):
            message=raw_input().split()
            sip=message[0]
            dip=message[1]
            for j in range(-1,-n-1,-1):
                if rules[j][0]=='deny':
                    if rulematch(sip,dip,rules[j]):
                        break
                else:
                    if rulematch(sip,dip,rules[j]):
                        anssum+=1
                        ansmes+=[[sip,dip,message[2]]]
                        break
        print anssum
        for mm in ansmes:
            print mm[0],mm[1],mm[2]

Submission status: Accepted

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	R = []
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		r = re.compile(s+d)
		R.append([r,(1 if p[0] == "p" else 0)])
	ans = []
	for i in range(m):
		s,d,name = raw_input().split()
		for r,p in R[::-1]:
			if r.search(s+d):
				if p:ans.append([s,d,name])
				break
	print len(ans)
	for s,d,name in ans:
		print s,d,name

Submission status: Accepted

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	R = [0]*n
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		R[i] = [re.compile(s+d), 1 if p[0] == "p" else 0]
	ans = []
	for i in range(m):
		s,d,name = raw_input().split()
		for r,p in R[::-1]:
			if r.search(s+d):
				if p:ans.append([s,d,name])
				break
	print len(ans)
	for s,d,name in ans:
		print s,d,name

Submission status: Accepted

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	if n == m == 0: break
	R = [0]*n
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		R[i] = [re.compile(s+d), p[0] == "p"]
	ans = []
	for i in range(m):
		s,d,name = raw_input().split()
		for r,p in R[::-1]:
			if r.search(s+d):
				if p: ans.append([s,d,name])
				break
	print len(ans)
	for s,d,name in ans:
		print s,d,name

Submission status: Runtime Error

Solution code:
import re
while 1:
	n,m = map(int,raw_input().split())
	P = []; D = []
	for i in range(n):
		p,s,d = raw_input().replace("?","[0-9]").split()
		r = re.compile(s+d)
		if p[0] == "p":
			P.append(r)
		else:
			D.append(r)
	for i in range(m):
		s,d,name = raw_input().split()
		tf = any(r.search(s+d) for r in P) and not any(r.search(s+d) for r in D)
		if tf:
			print s,d,name

Submission status: WA: Presentation Error

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if (N, M) == (0, 0):
        break
    rules = []
    for _ in xrange(N):
        f, p1, p2 = raw_input().split()
        rules += [(f, p1+p2)]
    rules = rules[::-1]
    def check(s):
        def match(pattern, address):
            for p, a in zip(pattern, address):
                if p == "?":
                    continue
                if p != a:
                    return False
            return True
        a1, a2, _ = s.split()
        for flag, pattern in rules:
            if flag == "permit" and match(pattern, a1+a2):
                return True
            if flag == "deny" and match(pattern, a1+a2):
                return False
    ans = filter(check, [raw_input() for _ in xrange(M)])
    print len(ans)
    print "\n".join(ans)

Submission status: WA: Presentation Error

Solution code:
answers = ""
while True:
    N, M = map(int, raw_input().split())
    if (N, M) == (0, 0):
        break
    rules = []
    for _ in xrange(N):
        f, p1, p2 = raw_input().split()
        rules += [(f, p1+p2)]
    rules = rules[::-1]
    def check(s):
        def match(pattern, address):
            for p, a in zip(pattern, address):
                if p == "?":
                    continue
                if p != a:
                    return False
            return True
        a1, a2, _ = s.split()
        for flag, pattern in rules:
            if flag == "permit" and match(pattern, a1+a2):
                return True
            if flag == "deny" and match(pattern, a1+a2):
                return False
    ans = filter(check, [raw_input() for _ in xrange(M)])
    answers += str(len(ans)) + "\n"
    answers += "\n".join(ans) + "\n"
print answers.strip()