Se compone de los siguientes ejercicios:
Sobre los 80 puntos hay que alcanzar un mínimo de 50 puntos para pasar la prueba de nivel. Se tendrá en cuenta que la solución sea corta y robusta.
Se espera por parte de los participantes un compromiso de honestidad. Las respuestas son sencillas y cortas pero no hay una única solucion posible a todas ellas. Se verificará que el trabajo realizado por cada uno es individual. Si hay sospechas de que ese trabajo no es individual, dicho trabajo no pasará la prueba de nivel.
Fecha de entrega 23:59h del 17 de Abril
Lista balanceada: Tenemos una lista de tokens compuesta de paréntesis abiertos, paréntesis cerrados y enteros de 1 a 9. Una lista está bien formada si los paréntesis están balanceados y cada entero indica el número de pares de paréntesis que rodean a dicho valor.
Implementar bien_formada, que toma una lista de tokens y devuelve True si y solo si la lista de tokens está bien formada.
> print bien_formada(list('(1)'))
True
> print bien_formada(list('(2)'))
False
> print bien_formada(list('((2)((3)))'))
True
> print bien_formada(list('((3)((2)))'))
False
> print bien_formada(list('(((3)((4))(3))(2)((3)))'))
TrueUsa el siguiente código de partida:
def bien_formada(s, depth=0):
try:
first = s.pop(0)
if first != '(':
return depth == int(first)
In [135]:
def bien_formada(s,depth=0):
try:
st = list()
balanced = True
number = 0
i = 0
while i < len(s) and balanced:
first = s[i]
if first == "(":
st.append(first)
depth += 1
elif first.isdigit():
number = int(first)
check = int(depth)
if check!=number:
balanced = False
else:
balanced = True
else:
depth -= 1
st.pop(0)
i = i + 1
if balanced and len(st)==0:
return True
else:
return False
except ValueError:
print "Error, valor no válido"
# Pruebas
print bien_formada(list('(1)'))
print bien_formada(list('(2)'))
print bien_formada(list('((2)((3)))'))
print bien_formada(list('((3)((2)))'))
print bien_formada(list('(((3)((4))(3))(2)((3)))'))
Diccionario invertido: La función invertir toma un diccionario y devuelve un diccionario nuevo donde los valores son claves y las claves se convierten en una lista de valores. Si un valor no puede convertirse en clave se descarta.
> print(invertir({'a':5, 'b':3, 'c':2, 'd':3}))
{2: ['c'], 3: ['b', 'd'], 5: ['a']}
> print(invertir({'a':5, 'b':3, 'c':[2], 'd':3}))
{3: ['b', 'd'], 5: ['a']}
In [136]:
import collections
def invertir(d):
r = {}
for k, v in d.iteritems():
if isinstance(v, collections.Hashable):
r[v] = r.get(v, [])
r[v].append(k)
return r
# Pruebas
print(invertir({'a':5, 'b':3, 'c':2, 'd':3}))
print(invertir({'a':5, 'b':3, 'c':[2], 'd':3}))
Generador no único: La función generadora no_unico toma cualquier iterable como argumento y devuelve un iterador sobre todos los elementos no únicos en el orden en el que se detecta que no son únicos.
> list(no_unico([1, 3, 2, 2, 5, 3, 4, 1]))
[2, 3, 1]
In [137]:
def no_unico(l):
s = set()
r = []
for i in l:
if i in s:
r.append(i)
else:
s.add(i)
return r
# Prueba
list(no_unico([1, 3, 2, 2, 5, 3, 4, 1]))
Out[137]:
Clase musical: Crea una clase denominada Cancion que tenga un método playque escriba en pantalla las estrofas de una canción que se le haya pasado en el constructor.
> cancion = Cancion(["Cumpleaños feliz", "Cumpleaños feliz", "Te deseamos todos", "Cumpleaños feliz"])
> cancion.play()
Cumpleaños feliz
Cumpleaños feliz
Te deseamos todos
Cumpleaños feliz
In [138]:
class Cancion:
def __init__(self, song):
self.toplay = song
def play(self):
for i in self.toplay:
print i
# Prueba
cancion = Cancion(["Cumpleaños feliz", "Cumpleaños feliz", "Te deseamos todos", "Cumpleaños feliz"])
cancion.play()
Carrera Vertical: Un corredor participa en una carrera vertical de n escalones pudiendo subir 1, 2 ó 3 escalones cada vez. Implementa una función que cuente todas las formas posibles de subir n escalones.
> print staircaseCount(1)
1
> print staircaseCount(2)
2
> print staircaseCount(3)
4
> print staircaseCount(4)
7La función debe ser capaz de computar en milisegundos cuantas formas posibles hay de subir 2500 escalones.
> print staircaseCount(2500)
25995141303821807172626236125906607615866791331561915620894574816921166800783923163332957535456271118463859873532852472723081575732040959420569217974251649035410975341213005762974633863697137749526890977505439660087436608713532914323869402616134445658944972896728120963411762122409556001067164509550348737157978465715896564604789452958067810550967263935696654067812304084042952611890333378496696245046542645295156787769713726767193263664300047841280740907689056815793889572131230684861580654047165401179620363687057859687709472816310747945105347461038894919004972392012629651907230981574199275727359628753065632760532058527830684202805216236662454100846575950215
In [140]:
# Tecnica "Memoization", se guardan valores en "cache" para no repetir llamadas.
stair_memo = {}
def staircaseCount(n):
# Si esta en el diccionario de "cache" lo tomamos de ahí.
if n >= 0 and stair_memo.get(n,0) != 0:
return stair_memo.get(n,0)
# Si el numero de escalones es menor que 0 (un error), no hay manera de subirlos.
if n < 0:
return 0
# Si el número de escalones es 0, solo hay una manera de subirlos.
elif n == 0:
stair_memo[n] = 1
return 1
else:
currentSteps = 0
# Si se tiene el resultado de n-1, se puede calcular directamente del diccionario.
if stair_memo.get(n-1,0)!=0:
currentSteps += stair_memo.get(n-1,0) + stair_memo.get(n-2,0) + stair_memo.get(n-3,0)
# Si se tiene el resultado de n-2, se puede calcular parte del diccionario y parte recursivamente.
elif stair_memo.get(n-2,0)!=0:
currentSteps += stair_memo.get(n-3,0) + stair_memo.get(n-2,0) + staircaseCount(n-1)
# Si se tiene el resultado de n-3, se puede calcular parte del diccionario y parte recursivamente.
elif stair_memo.get(n-3,0)!=0:
currentSteps += stair_memo.get(n-3,0) + staircaseCount(n-2) + staircaseCount(n-1)
# Si no se tiene el resultado de n-3, no se puede calcular directamente del diccionario.
else:
currentSteps += staircaseCount(n-3) + staircaseCount(n-2) + staircaseCount(n-1)
stair_memo[n] = currentSteps
return currentSteps;
# Prueba
print staircaseCount(2500)
In [ ]: