Code Jam 2011

bottrust.py

import threading, time, sys, re
inData = open('a-small.in').read().strip()
#inData = """3
#4 O 2 B 1 B 2 O 4
#3 O 5 O 8 B 100
#2 B 2 B 1"""
class Awesome(threading.Thread):
	def __init__(self, i):
		threading.Thread.__init__(self)
		self.i = i
		self.done = False
		self.st = time.time()
		self.orange = 1
		self.blue = 1
		self.turn = 0
		self.turnData = []
	def run(self):
		# parse the format
		x = re.findall("([OB] [0-9]+)+", self.i)
		x = map(lambda x: x.split(" "), x)
		blueGoal = None
		orangeGoal = None
		blueInd = None
		orangeInd = None
		procInd = []
		while self.turn <= 2000:
			turnData = ["", "", []]
			if not blueGoal:
				for k,i in enumerate(x):
					if k in procInd: continue
					if i[0] == "B":
						blueGoal = int(i[1])
						blueInd = k
						procInd.append(k)
						break
			if not orangeGoal:
				for k,i in enumerate(x):
					if k in procInd: continue
					if i[0] == "O":
						orangeGoal = int(i[1])
						orangeInd = k
						procInd.append(k)
						break
			if blueGoal == None and orangeGoal == None:
				break
			turnData[2] = [[blueGoal, blueInd], [orangeGoal, orangeInd]]
			self.turn += 1
			bluePress = False
			# make a step or skip
			if blueGoal:
				if blueGoal != self.blue:
					if blueGoal - self.blue < 0:
						self.blue -= 1
						turnData[0] = "B: Walk back 1 tile - "+str(self.blue)
					else:
						self.blue += 1
						turnData[0] = "B: Walk ahead 1 tile - "+str(self.blue)
				elif blueGoal == self.blue:
					if  blueInd < orangeInd or orangeInd == None:
						# press!
						blueGoal = None
						blueInd = None
						bluePress = True
						turnData[0] = "B: Press "+str(self.blue)
					else:
						turnData[0] = "B: Orange is blocking - "+str(self.blue)
			else:
				turnData[0] = "B: We're done here"
			if orangeGoal:
				if orangeGoal != self.orange:
					if orangeGoal - self.orange < 0:
						self.orange -= 1
						turnData[1] = "O: Walk back 1 tile - "+str(self.orange)
					else:
						self.orange += 1
						turnData[1] = "O: Walk ahead 1 tile - "+str(self.orange)
				elif orangeGoal == self.orange:
					if not bluePress and (orangeInd < blueInd or blueInd == None):
						# press!
						orangeGoal = None
						orangeInd = None
						turnData[1] = "O: Press "+str(self.orange)
					else:
						turnData[1] = "O: Blue is blocking - "+str(self.orange)
			else:
				turnData[1] = "O: We're done here"
			self.turnData.append(turnData)
		self.done = time.time()

th = []
for i in inData.split("\n")[1:]:
	th.append(Awesome(i))
	th[-1].start()
for k,i in enumerate(th):
	while True:
		if i.done:
			print "Case #%s: %s" % (k+1, i.turn)
			#if k+1 == 5:
			#	print i.turnData
			break
for i in th:
	sys.stderr.write("%s finished in %s\n"%(i.name, i.done - i.st))

magicka.py

import threading, time, sys, re
inData = open(sys.argv[1]).read().strip()
#inData = """5
#0 0 2 EA
#1 QRI 0 4 RRQR
#1 QFT 1 QF 7 FAQFDFQ
#1 EEZ 1 QE 7 QEEEERA
#0 1 QW 2 QW"""
class Awesome(threading.Thread):
	def __init__(self, i):
		threading.Thread.__init__(self)
		self.i = i
		self.done = False
		self.st = time.time()
	def run(self):
		data = self.i.split(" ")
		combine = {}
		explode = {}
		combineCnt = 0
		explodeCnt = 0
		step = 0
		for k,v in enumerate(data):
			if k == 0 and step == 0:
				combineCnt = int(v)
				step = 1
				if combineCnt <= 0:
					step = 2
				continue
			elif combineCnt > 0 and step == 1:
				if v[0] not in combine:
					combine[v[0]] = {}
				combine[v[0]][v[1]] = v[2]
				if v[1] not in combine:
					combine[v[1]] = {}
				combine[v[1]][v[0]] = v[2]
				combineCnt -= 1
				if combineCnt <= 0:
					step = 2
					continue
			elif step == 2:
				explodeCnt = int(v)
				step = 3
				if explodeCnt <= 0:
					step = 4
				continue
			elif step == 3 and explodeCnt > 0:
				if v[0] not in explode:
					explode[v[0]] = []
				explode[v[0]].append(v[1])
				if v[1] not in explode:
					explode[v[1]] = []
				explode[v[1]].append(v[0])
				explodeCnt -= 1
				if explodeCnt <= 0:
					step = 4
					continue
			elif step == 4:
				if re.match("^([0-9]+)$", v):
					step = 5
			elif step == 5:
				stack = []
				stackturn = []
				for a, x in enumerate(v):
					stack = stack[:len(stack)]
					if len(stack) > 0:
						if stack[-1] in combine and x in combine[stack[-1]]:
							stack.append(combine[stack[-1]][x])
							del stack[-2]
						elif x in explode:
							for kaboom in explode[x]:
								if kaboom in stack:
									stack = []
									stackturn.append("BOOM appending "+x+" to "+kaboom)
									break
							if len(stack) > 0:
								stack.append(x)
						else:
							stack.append(x)
					else:
						stack.append(x)
					stackturn.append([a,x,stack])
				step = 6
			else:
				break
		self.explode = explode
		self.combine = combine
		self.stackturn = stackturn
		self.out = `stack`.replace("'", "")
		self.done = time.time()

th = []
for i in inData.split("\n")[1:]:
	th.append(Awesome(i))
	th[-1].start()
for k,i in enumerate(th):
	while True:
		if i.done:
			print "Case #%s: %s" % (k+1, i.out)
			#if k == 2:
			#	print i.stackturn
			break
for i in th:
	sys.stderr.write("%s finished in %s\n"%(i.name, i.done - i.st))

splitting.py

# During code jam competition, this code was running under
# Mac OS X 10.6.7 2011 MacBook Pro, pypy 1.5.0-alpha0 GCC 4.0.1
# Python 2.7.1 measured 250946 pystones/sec
import threading, subprocess, time, sys, re, math, multiprocessing
from itertools import combinations
inData = open(sys.argv[1]).read().strip()
#inData = """3
#5
#1 2 3 4 5
#3
#3 5 6
#2
#5 5"""
def noobAdd(x, y):
	if y > x:
		x2 = y
		y2 = x
		y = y2
		x = x2
	x = bin(x).split("b")[1][::-1]
	y = bin(y).split("b")[1][::-1]
	out = ""
	for k,v in enumerate(x):
		try:
			d = int(v) + int(y[k])
			if d >= 2: d = 0
		except IndexError:
			d = int(v)
		out += str(d)
	out = out[::-1]
	return int(out, 2)
class ComGen(threading.Thread):
	def __init__(self, i, data):
		threading.Thread.__init__(self)
		self.i = i
		self.done = False
		self.st = time.time()
		self.out = -1
		self.data = data
	def run(self):
		i = self.i
		p = combinations(self.data, i+1)
		aVal = []
		for x in p:
			#notIn = filter(lambda o: o not in x, data)
			notIn = self.data[:]
			for z in x:
				if z in notIn:
					del notIn[notIn.index(z)]
			if len(notIn) == 0: continue
			patrick = reduce(lambda o,p: noobAdd(o, p), notIn)
			patrickCnt = reduce(lambda o,p: noobAdd(o, p), x)
			if patrickCnt != patrick:
				continue # reject
			elif len(x) > len(notIn):
				sean = reduce(lambda o,p: o+p, x)
				aVal.append(sean)
		if len(aVal) > 0:
			self.out = max(aVal)
		if not self.out:
			self.out=-1
		self.done=True
class Awesome(multiprocessing.Process):
	def __init__(self, i, i2, t):
		multiprocessing.Process.__init__(self)
		self.i = i
		self.done = False
		self.st = time.time()
		self.out = i2
		self.time = t
	def run(self):
		data = map(lambda x: int(x), self.i.split(" "))
		maxValue = reduce(lambda x,y:x+y, data)
		aVal = []
		if len(data) == 2:
			if data[0] == data[1]:
				self.out.value = data[0]
		th = []
		for i in range(int(math.ceil(len(data)//2)), len(data)-1):
			th.append(ComGen(i, data))
			th[-1].start()
		for i in th:
			while True:
				if i.done:
					sys.stderr.write(self.name+": thread "+i.name+" is done ("+str(len(th))+")\r")
					aVal.append(i.out)
					break
		if len(aVal) == 0:
			self.out.value = -1
		else:
			self.out.value = max(aVal)
		self.time.value = time.time() - self.st

if __name__ == "__main__":
	"""no = 1
	for k,i in enumerate(inData.split("\n")[1:]):
		sys.stderr.write(str(no)+"\r")
		if len(i.split(" ")) == 1:
			continue
		th = Awesome(i)
		th.run()
		print "Case #%s: %s" % (no, th.out)
		no += 1
	exit()"""
	th = []
	running = 0
	for i in inData.split("\n")[1:]:
		if len(i.split(" ")) == 1:
			continue
		th.append(Awesome(i, multiprocessing.Value("i"), multiprocessing.Value("f")))
		th[-1].start()
		sys.stderr.write(str(len(th))+"\r")
		while True:
			running = 0
			for i in th:
				if not i.out.value:
					running += 1
			if running <= 8:
				break
			time.sleep(0.1)
	sys.stderr.write("Thread assigned\r")
	for k,i in enumerate(th):
		while True:
			if i.out.value:
				v = i.out.value
				if v == -1:
					v = "NO"
				print "Case #%s: %s" % (k+1, v)
				#if k == 2:
				#	print i.stackturn
				break
			time.sleep(0.1)
	for i in th:
		sys.stderr.write("%s finished in %s\n"%(i.name, i.time.value))

submitted-splitting.py

# During code jam competition, this code was running under
# Mac OS X 10.6.7 2011 MacBook Pro, pypy 1.5.0-alpha0 GCC 4.0.1
# Python 2.7.1 measured 250946 pystones/sec
import threading, time, sys, re, math
from itertools import combinations
inData = open(sys.argv[1]).read().strip()
#inData = """1
#2
#5 5"""
def noobAdd(x, y):
	if y > x:
		x2 = y
		y2 = x
		y = y2
		x = x2
	x = bin(x).split("b")[1][::-1]
	y = bin(y).split("b")[1][::-1]
	out = ""
	for k,v in enumerate(x):
		try:
			d = int(v) + int(y[k])
			if d >= 2: d = 0
		except IndexError:
			d = int(v)
		out += str(d)
	out = out[::-1]
	return int(out, 2)
class Awesome(threading.Thread):
	def __init__(self, i):
		threading.Thread.__init__(self)
		self.i = i
		self.done = False
		self.st = time.time()
		self.out = "NO"
	def run(self):
		data = map(lambda x: int(x), self.i.split(" "))
		maxValue = reduce(lambda x,y:x+y, data)
		aVal = []
		if len(data) == 2:
			if data[0] == data[1]:
				self.out = data[0]
		for i in range(int(math.ceil(len(data)//2)), len(data)-1):
			p = combinations(data, i+1)
			for x in p:
				notIn = filter(lambda o: o not in x, data)
				notIn = data[:]
				for z in x:
					if z in notIn:
						del notIn[notIn.index(z)]
				if len(notIn) == 0: continue
				patrick = reduce(lambda o,p: noobAdd(o, p), notIn)
				patrickCnt = reduce(lambda o,p: noobAdd(o, p), x)
				if patrickCnt != patrick:
					continue # reject
				elif len(x) > len(notIn):
					sean = reduce(lambda o,p: o+p, x)
					aVal.append(sean)
		if len(aVal) > 0:
			self.out = max(aVal)
		self.done = time.time()

"""no = 1
for k,i in enumerate(inData.split("\n")[1:]):
	sys.stderr.write(str(no)+"\r")
	if len(i.split(" ")) == 1:
		continue
	th = Awesome(i)
	th.run()
	print "Case #%s: %s" % (no, th.out)
	no += 1
exit()"""
th = []
for i in inData.split("\n")[1:]:
	if len(i.split(" ")) == 1:
		continue
	th.append(Awesome(i))
	th[-1].start()
	sys.stderr.write(str(len(th))+"\r")
sys.stderr.write("\nThread assigned\n")
for k,i in enumerate(th):
	while True:
		if i.done:
			print "Case #%s: %s" % (k+1, i.out)
			#if k == 2:
			#	print i.stackturn
			break
for i in th:
	sys.stderr.write("%s finished in %s\n"%(i.name, i.done - i.st))