coding_contests/facebook_high_security.python at master · codemonkey3045/coding_contests · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
__author__ = 'codemonkey3045'

nGames = int(raw_input())

def segment(li):
	start = 0
	length = 0
	segments = []
	for ind, c in enumerate(li):
		if c == 'X':
			s = [length, start, start + length-1, 'A']
			segments.append(s)
			start = ind + 1
			length = 0
		elif ind == len(li)-1:
			t = [length+1, start, start + length, 'A']
			segments.append(t)
			start = ind + 1
			length = 0
		else:
			length = length + 1
		# print "ind %d had start %d and length %d" % (ind, start, length)
	return segments

def removeEmptySegments(s):
	rets = []

	for tup in s:
		if tup[0] == 0:
			tup[3] = 'REMOVE'

	for tup in s:
		if tup[3] != 'REMOVE':
			rets.append(tup)

	return rets

def removeGuards(s1, other):
	rets = []
	for tup in s1:
		# print tup
		if tup[0] == 1:
			# print "single"
			for o in other:
				if tup[1] >= o[1] and tup[2] <= o[2] and o[3] == 'A':
					# print "useless guard"
					o[3] = 'T'
					tup[3] = 'REMOVE'
				# else:
					# print "useful"
	for tup in s1:
		if tup[3] != 'REMOVE':
			rets.append(tup)
	return rets

def solve(col, l1, l2):
	r1 = list(l1)
	r1s = segment(r1)

	r2 = list(l2)
	r2s = segment(r2)

	r1s = removeEmptySegments(r1s)
	r2s = removeEmptySegments(r2s)

	# print "\ncheck me\n%s\n%s\n" % (r1s, r2s)
	# start squashing guards covered by other row
	r1s = removeGuards(r1s, r2s)
	r2s = removeGuards(r2s, r1s)

	return len(r1s) + len(r2s)

counter = 0
for game in range(0, nGames):
	counter = counter + 1
	columns = raw_input()
	line1 = raw_input()
	line2 = raw_input()
	# print "Case #%d: \n%s\n%s\n" % (counter, line1, line2)
	nGuards = solve(columns, line1, line2)
	# print "Case #%d: %d\n%s\n%s\n" % (counter, nGuards, line1, line2)
	print "Case #%d: %d" % (counter, nGuards)