Quest’anno sono riuscito a partecipare (me ne sono ricordato :P) all’Hacker Cup che Facebook organizza ogni anno. I problemi per le qualificazioni erano 3 e di seguito vi posto le mie soluzioni scritte in python.
Il terzo problema (Find the min) non e’ difficile, sono riuscito a risolverlo ma il tempo che ci impiega il mio algoritmo e’ molto al di sopra di quello che mette a disposizione Facebook. In realta’ bastava guardare un po output della lista che utilizzavo per memorizzare i valori per capire che da un certo punto in poi si ripeteva ( per cui non serviva tutta la potenza di calcolo che avevo immaginato 😛 ). In poche parole per gli indici della liste pari a 2k+1, i valori si ripetevano… me ne sono accorto troppo tardi ed ho finito solo i primi due step 😀
1 – Beautiful strings (20 points)
beautiful_stringstxt.txt
outputFile.txt
[sourcecode language=”python”]import sys
import math
from collections import Counter
in_file = open(sys.argv[1],"r")
exp = in_file.read()
in_file.close()
a= exp.split("\n")
b=[]
c=[]
values=[]
d={}
u={}
for i in range(1, len(a)-1) :
b.append(a[i].lower()[::-1])
flavio=1
for i in b:
d={}
values=[]
num=26
find=1
numSum=0
for k in range(0,len(i)):
#d[str(i[k])] = i.count(i[k])
if(str(i[k]).isalpha()):# or str(i[k])==’!’):
d[str(i[k])] = i.count(i[k])
for k in range(0,len(i)):
if (str(i[k]) in d):
# print i[k] + " num "+ str(num) + " # " + str(d[i[k]])
numSum += num*d[i[k]]
values.append(d[i[k]])
del d[i[k]]
num -=1
values_sorted= sorted(values, reverse=True)
num=26
numSum =0
for item in range(len(values_sorted)):
numSum += num * values_sorted[item]
num -=1
print "Case #" + str(flavio)+ ": " +str(numSum)
flavio +=1
[/sourcecode]
2 – Balanced Smileys (35 points)
balanced_smileystxt.txt
outputBalanced.txt
[sourcecode language=”python”]import sys
import math
from collections import Counter
import re
in_file = open(sys.argv[1],"r")
exp = in_file.read()
in_file.close()
b=[]
c=[]
values=[]
d={}
u={}
for i in range(1, len(a)-1) :
b.append(a[i].lower())
replacements = {":(",":)"}
for i in range(0,len(b)) :
#b[i]= b[i].replace(
b[i]= re.sub(r’\([^)]*\)’, "", b[i])
b[i]= b[i].replace(‘:(‘,”)
b[i]= b[i].replace(‘:)’,”)
def isBalanced(strInput):
"""Validate if an input string is having balanced bracket pairs
this includes bracket ordering. i.e a round bracket must be closed
by a round bracket. Emtpy strings are treated as balanced."""
#if strInput:
# list of all bracket kinds, in paired tuples
brackets = [ (‘(‘,’)’), (‘[‘,’]’), (‘{‘,’}’)]
# define fake constants – python does not support the concept of constants
kStart = 0
kEnd = 1
# internal stack used to push and pop brakets in the input string
stack = []
for char in strInput:
for bracketPair in brackets:
if char == bracketPair[kStart]:
stack.append(char)
elif char == bracketPair[kEnd] and len(stack) > 0 and stack.pop() != bracketPair[kStart]:
return False
if len(stack) == 0:
return True
#return False
flavio=1
for i in range(0,len(b)) :
if(isBalanced(b[i])):
print "Case #" + str(flavio) + ": YES"
else:
print "Case #" + str(flavio) + ": NO"
flavio +=1
[/sourcecode]
3 – Find the Min (45 points)
find_the_mintxt.txt
outputFindTheMin.txt
[sourcecode language=”python”]import os, sys
f = open(sys.argv[1], ‘r’)
T = int(f.readline())
def next(ary, start):
j = start
l = len(ary)
ret = start – 1
while j < l and ary[j]:
ret = j
j += 1
return ret
for t in range(T):
n, k = map(int, f.readline().strip().split(‘ ‘))
a, b, c, r = map(int, f.readline().strip().split(‘ ‘))
m = [0] * (4 * k)
s = [0] * (k+1)
m[0] = a
if m[0] <= k:
s[m[0]] = 1
for i in xrange(1, k):
m[i] = (b * m[i-1] + c) % r
if m[i] < k+1:
s[m[i]] += 1
p = next(s, 0)
m[k] = p + 1
p = next(s, p+2)
for i in xrange(k+1, n):
if m[i-k-1] > p or s[m[i-k-1]] > 1:
m[i] = p + 1
if m[i-k-1] <= k:
s[m[i-k-1]] -= 1
s[m[i]] += 1
p = next(s, p+2)
else:
m[i] = m[i-k-1]
if p == k:
break
if p != k:
print ‘Case #%d: %d’ % (t+1, m[n-1])
else:
print ‘Case #%d: %d’ % (t+1, m[i-k + (n-i+k+k) % (k+1)])
[/sourcecode]
Riferimenti:
https://www.facebook.com/hackercup/problems.php?round=185564241586420
Correct Solution Find The Min
http://facebook.stackoverflow.com/questions/14536384/python-too-slow-of-large-inputs
GitHub
https://github.com/flaviopace/FacebookHackerCupQualification2013
