Google Code Jam-Qualification Round

さりげなく参加してた。この手のイベントは初めて。TopCoderとかも参加したことがない。

Qualification Round,AがLarge含めてOK,Cはshortのみで43点で通過。ただ他の人のコードと比べてもコードが酷い。否応なしにコードの酷さとか理解できるので勉強するにはいい場ですね。一方で問題提出してそれがOKでると自分の努力をちょびっと認められた気分になってうれしいです。

A

与えられた文字列がエイリアンの言語にいくつマッチしてるか数える。(,)を[,]に変えて正規表現で比較するだけ。あまりにあっさり解けすぎてLarge合ってるかどうか心配だった・・問題を理解するのに95%くらい時間がかかった気がする。

B

水の流れる範囲でマップを色分けする。「高いとこから降りてきたときに、既にラベルのついてるセルに来たら"その回の一番上のセルから全て"そのラベルに付け直す」っていう処理が無かったんだと思う。多分。

C

"wweellccoommee to code jam"のような文字列が与えられたとき、"welcome to code jam"と文字列を取り出す方法は何通りあるか数える問題。バカ正直に一個ずつ一致するかどうか見ていったらLargeが時間超えまくりで駄目だった。多分検索とかでよく知られてるやり方があるんだろうなぁ。

あと問題解いてるときにいろいろ覚えたこと。

• doctestまじ便利。
• tuple受け取り使えそう。(a,b,c) = str.splitみたいに。
• 空白区切りはsplit()でok
• cでいう(char)('c'+ i)ってどうやるんだ？
• 二重配列でyの高さ求める式は？len(result)でいいの？

ソース

A

q1.py

#Read input file
import sys
from searchword import searchword

def main(fileName):
	setting, known, testData = fileOpen(fileName)
	i = 0
	for t in testData:
		i += 1
		count = searchword(known,t)
		print "Case #%d: %d" % (i,count)

def fileOpen(fileName):
	f = open(fileName)
	i = 0
	setting = {}
	known = []
	testData = []
	for line in f:
		if i == 0:
			#parse first line
			setting = parseFirstLine(line[:-1])
		elif i < int(setting["D"]+1):
			#known alien language
			known.append(line[:-1])
		elif i < int(setting["N"])+int(setting["D"]+1):
			testData.append(line[:-1])
		i += 1
	return setting, known, testData

def parseFirstLine(str):
	"""
		>>> parseFirstLine("3 5 4")
		{'N': 4, 'L': 3, 'D': 5}
	"""
	result={}
	(result["L"],result["D"],result["N"]) = str.split()
	for i in result.keys():
		result[i] = int(result[i])
	return result 

if __name__ == "__main__":
	if len(sys.argv) > 1:
		main(sys.argv[1])
	else:
		import doctest
		doctest.testmod(verbose=True)
		#"usage: exefile inputfile"

searchword.py

"""
	abc-> 1 hit
	>>> searchword(['abc','bca','dac','dbc','cba'],'abc')
	1
	>>> searchword(['abc','bca','dac','dbc','cba'],'(abc)(abc)(abc)')
	3
"""
import re
def searchword(known,testWord):
	count = 0
	testWord = testWord.replace("(","[")
	testWord = testWord.replace(")","]")
	#print testWord
	p = re.compile(testWord)
	for k in known:
		if p.match(k):
			count += 1
	return count

def _test():
	import doctest
	doctest.testmod(verbose=True)

if __name__ == "__main__":
	_test()

C

q3.py

#Read input file
import sys
from searchword import searchword

def main(fileName):
	setting, data = fileOpen(fileName)
	i = 1
	for d in data:
		result = searchword(d)
		print "Case #%d: %04d" % (i ,result)
		i += 1
		if i > setting:
			break

def fileOpen(fileName):
	f = open(fileName)
	i = 0
	data = []
	for line in f:
		if i == 0:
			#parse first line
			setting = int(line[:-1])
		else:
			data.append(line[:-1])
		#print line
		i += 1
	return setting,data

if __name__ == "__main__":
	if len(sys.argv) > 1:
		main(sys.argv[1])
	else:
		#import doctest
		#doctest.testmod(verbose=True)
		print "usage: exefile inputfile"

searchword.py

"""
find "wweellccoommee to .." -> "welcome to .."
"""
def print_d(str):
	#print str
	pass

def searchword(input,checkword="welcome to code jam"):
	
	index = [0 for i in range(len(checkword))]
	pos = 0 # position of checkword
	count = 0 # success count for search word
	while True:
		findFlag = False
		matchFlag = False
		c = checkword[pos]
		for p in range( index[pos], len(input) ):
			print_d("compare " + c + " with " + input[p] + " p:" + str(p))
			if c == input[p]:
				print_d("ok")
				# if success for search, count += 1
				if pos >= len(checkword)-1:
					count = (count + 1) % 10000 
					index[pos] = p+1
					matchFlag = True
					print_d("match")
				else:
					print_d( "pos:" + str(pos))
					index[pos]   = p
					index[pos+1] = p+1
					pos += 1
					findFlag = True
				break

		if findFlag == False and matchFlag == False:
			# if don't find, pos -1 and index[pos] += 1
			print_d("return")
			pos -= 1
			index[pos] += 1
			if pos < 0:
				break
	return count

def _test():
	import doctest
	doctest.testmod(verbose=True)

if __name__ == "__main__":
	#print searchword("abbc","abc")
	print searchword("welcome to code jaam") #1
	print searchword("wweellccoommee to code qps jam") #256
	print searchword("welcome to codejam") #0
	print searchword("ewl") #0
	print searchword("wweellccoommee to code qps jjaamm") #2048?