LAB 05 - Listas generalizadas
Contents
!wget --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/20192.L3/master/init.py
import init; init.init(force_download=False); init.get_weblink()
import init
from local.lib.rlxmoocapi import submit, session
import inspect
student = session.Session(init.endpoint).login( course_id=init.course_id,
session_id="UDEA",
lab_id="lab_05" )
LAB 05 - Listas generalizadas¶
En estos ejercicios usaremos las clases Node y L. Ejecuta la siguiente celda para cargar sus definiciones
class Node:
def __init__(self, value, next=None):
assert next is None or isinstance(next,Node), "next must be Node, not %s"%(type(next))
self.value = value
self.next = next
def __repr__(self):
return str(self.value)
class L(object):
def __init__ (self, first_node=None):
assert first_node is None or isinstance(first_node,Node), "first must be Node, not %s"%(type(first_node))
self.first_node = first_node
def __getitem__(self, idx):
k = self.first_node
for i in range(idx):
assert k.next is not None, "index %s out of range"%(str(idx))
k = k.next
return k.value
def __len__(self):
k = self.first_node
if k is None:
return 0
i=1
while k.next is not None:
i+=1
k = k.next
return i
def __repr__ (self):
if self.first_node is None:
return "[]"
s = "[ %s"%self.first_node
k=self.first_node
while (k.next is not None):
s += ", %s"%k.next
k = k.next
return s+" ]"
Ejercicio 1¶
Implementa el método __getitem__ para que funcione con índices positivos y negativos. Por ejemplo:
> W = L1(Node(10, Node(20, Node(30))))
> print W
[ 10, 20, 30 ]
> print W[0], W[1], W[2]
> print W[-1], W[-2], W[-3]
10 20 30
30 20 10
Ten en cuenta los casos en los que el índice excede el tamaño de la lista, bien positivo bien negativo. En estos casos has de generar un assertion error.
En el ejemplo anterior, W[3] y W[-4] deben de generar un AssertionError
class Node:
def __init__(self, value, next=None):
assert next is None or isinstance(next,Node), "next must be Node, not %s"%(type(next))
self.value = value
self.next = next
def __repr__(self):
return str(self.value)
class L(object):
def __init__ (self, first_node=None):
assert first_node is None or isinstance(first_node,Node), "first must be Node, not %s"%(type(first_node))
self.first_node = first_node
def __len__(self):
k = self.first_node
if k is None:
return 0
i=1
while k.next is not None:
i+=1
k = k.next
return i
def __repr__ (self):
if self.first_node is None:
return "[]"
s = "[ %s"%self.first_node
k=self.first_node
while (k.next is not None):
s += ", %s"%k.next
k = k.next
return s+" ]"
def L1(*args,**kwargs):
class L1_class(L):
def __getitem__(self, idx):
return <... TU CODIGO AQUI ...>
return L1_class(*args,**kwargs)
comprueba manualmente tu código
W = L1(Node(10, Node(20, Node(30))))
W = L1(first_node=Node(10, Node(20, Node(30))))
print(W)
W.first_node == None
print(W[0], W[1], W[2])
print(W[-1], W[-2], W[-3])
print(W[3])
print (W[-4])
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_01");
r = teacher.run_grader_locally("grader_01", source_functions_names_01, source_variables_names_01, locals())
from IPython.display import HTML
print ("grade", r[0])
HTML(r[1])
Ejercicio 2¶
Implementa una función __setitem__ que también soporte índices negativos. Por ejemplo:
W = L2(Node(10, Node(20, Node(30))))
print W
[ 10, 20, 30 ]
W[1]=25
print W
[ 10, 25, 30 ]
W[-1]=35
print W
[ 10, 25, 35 ]
def L2(*args,**kwargs):
class L2_class(L):
def __getitem__(self, idx):
<... TU CODIGO AQUI ...>
def __setitem__(self, idx, value):
<... TU CODIGO AQUI ...>
return L2_class(*args,**kwargs)
W = L2(Node(10, Node(20, Node(30))))
print(W)
W[1]=25
print(W)
W[-1]=35
print(W)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_02");
Ejercicio 3¶
Implementa la función clone_node que duplica. Si el nodo tiene un next también lo duplica
Sugerencia: implementa el siguiente pseudocódigo recursivo
function clone_node(node)
si node es NULL
devuelve NULL
devuelve nuevo_nodo(node.value, clone_node(node.next))
def clone_node(node):
r = <... TU CODIGO AQUI ...>
return r
comprueba manualmente tu código. Los valores han de ser iguales pero los id no, señalando que son verdaderamente objetos distintos
n = Node(10, Node(20, Node(30)))
print(n, id(n))
print(n.next, id(n.next))
print(n.next.next, id(n.next.next))
print(n.next.next.next, id(n.next.next.next))
k = clone_node(n)
print( k, id(k))
print( k.next, id(k.next))
print( k.next.next, id(k.next.next))
print( k.next.next.next, id(k.next.next.next))
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_03");
Ejercicio 4¶
Implementa clone que duplica una lista. Pon atención, ya que si hay sublistas, éstas han de ser duplicadas también. Entiende la implementación de la siguiente función, que muestra recursivamente los id de cada nodo de una lista según tu propia implementación del ejercicio 2
def show_ids(M, level=0):
k = M.first_node
while k is not None:
print (" "*2*level, id(k))
if (str(k.value.__class__.__name__) == str(M.__class__.__name__)):
show_ids(k.value, level+1)
k = k.next
W=L2(Node(10, Node(L2(Node(14, Node(15, Node(L2(Node(16, Node(17))))))), Node(20, Node(30)))))
show_ids(W)
Desarrolla tu solución de la siguiente manera:
Primero copia los nodos de la lista actual (
self)Crea una lista nueva con los nodos copiados
Recorre los nodos de la lista nueva verificando el campo
valueSi este campo es también una lista (usa
isinstancecomo en la funciónshow_ids) entonces llama aclonede esa lista y sustituye el valor.
def L4(*args,**kwargs):
class L4_class(L):
def clone(self):
def clone_node(node):
return <... TU CODIGO AQUI ...>
r = <... TU CODIGO AQUI ...>
return r
return L4_class(*args,**kwargs)
comprueba tu código, ambas listas han de tener el mismo contenido, pero distintos id
W=L4(Node(10, Node(L4(Node(14, Node(15, Node(L4(Node(16, Node(17))))))), Node(20, Node(30)))))
W
W.__class__.__name__
K = W.clone()
K
show_ids(W)
show_ids(K)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_04");
Ejercicio 5¶
Implementa el método ´__add__´ para que concatene una lista con otra creando una nueva lista. Usa los métodos desarrollados en los ejercicios anteriores.
Sugerencia de implementación: copia primero las dos listas originales y luego concaténalas haciendo apuntar el next del último elemento de la copia de la primera lista al primer elemento de la copia de la segunda lista.
def L5(*args,**kwargs):
class L5_class(L):
def clone(self):
return <... TU CODIGO AQUI ...>
def __add__(self, M):
return <... TU CODIGO AQUI ...>
return L5_class(*args,**kwargs)
W = L5(Node(10, Node(20, Node(30))))
Z = L5(Node(3, Node(2)))
print (W)
print (Z)
print (W + Z + L5())
esto ahora debería de funcionar (recuerda que en las Notas correspondientes existía un problema)
X = W + Z + W
print (X)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_05");
Ejercicio 6¶
Implementa la función de igualdad.
Sugerencia de implementación: haz una función que recorra simultáneamente los nodos de ambas listas (self y other) y devuelva False en cuanto encuentre que el campo value de los dos nodos sea distinto (!=). Pon especial atención a que si value es a su vez una lista, el método será recursivo.
def L6(*args,**kwargs):
class L6_class(L):
def __eq__(self, other):
return <... TU CODIGO AQUI ...>
def __ne__(self, other):
return not self==other
return L6_class(*args,**kwargs)
W=L6(Node(10, Node(L6(Node(14, Node(15, Node(L6(Node(16, Node(17))))))), Node(20, Node(30)))))
Z=L6(Node(10, Node(L6(Node(14, Node(15, Node(L6(Node(16, Node(17))))))), Node(20, Node(30)))))
Y=L6(Node(10, Node(L6(Node(14, Node(15))), Node(20, Node(30)))))
print (W)
print (Z)
print (Y)
print (W==W)
print (Z==Z)
print (Y==Y)
print (W==Z)
print (W==Y)
print (Y==Z)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_06");
Ejercicio 7¶
Realiza una función que evalúe un VarTerm dado un diccionario vals. Asume que este diccionario contendrá un valor para la variable del término. Por ejemplo
> vals = {"x": 1, "y":2, "z": 3}
> vt = VarTerm(9,"y", 2)
> print vt, "=", evaluate_vterm(vt, vals)
9 y^2 = 36
> vt = VarTerm(2,"z", 3)
> print vt, "=", evaluate_vterm(vt, vals)
2 z^3 = 54
def VarTerm7(*args,**kwargs):
class VarTerm7_class():
def __init__(self, coef, var, exp=1):
assert (isinstance(coef, float) or isinstance(coef,int)) and \
isinstance(exp, int) and isinstance(var, str) and len(var)==1
self.coef = coef
self.var = var
self.exp = exp
def get_math_representation(self):
s = ("%s"%str(self.coef) if self.coef!=1 else "") +\
(" %s"%self.var if self.exp==1 else (" %s^%d"%(self.var, self.exp) if self.exp!=0 else ""))
return s
def __repr__(self):
return self.get_math_representation()
def evaluate(self, vals):
return <... TU CODIGO AQUI ...>
return VarTerm_class(*args,**kwargs)
vals = {"x": 1, "y":2, "z": 3}
vt = VarTerm7(9,"y", 2)
print(vt, "=", vt.evaluate(vals))
vt = VarTerm7(2,"z", 3)
print(vt, "=", vt.evaluate(vals))
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_07");
Ejercicios de refuerzo (no obligatorios)¶
crea una función que evalúe un
VarPol, según definido en las notas.analiza la complejidad computacional de tus implementaciones
¿Podrías enriqueces
Nodepara mejorar la complejidad computacional?
Ejercicio 8¶
Realiza una función que evalúe un VarPol dado un diccionario vals. Asume que vals contendrá valores para todas las variables presentes en el polinomio.
Sugerencia de implementación
evalua el
VarTermasociado con el polinomio.recorre la lista del polinomio (desde
self.first_node) sumando el valor de cada nodo de forma que:si el nodo es un
VarTermllama a la funciónevaluate_vtermsi el nodo es un
VarPolllama a la funciónevaluatedel dicho polinomio
Observa que este último paso hace el algoritmo recursivo, por tanto, pon atención al mismo.
class Pol(L):
def get_math_representation(self):
if self.first_node is None:
return Math("")
k = self.first_node
s = k.value.get_math_representation()
while (k.next is not None):
s += "+"+k.next.value.get_math_representation()
k = k.next
s = s.replace("+-", "-")
return s
def show(self):
from IPython.display import Math, HTML, display
display(HTML("<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=default'></script>"))
return Math(self.get_math_representation())
class VarTerm():
def __init__(self, coef, var, exp=1):
assert (isinstance(coef, float) or isinstance(coef,int)) and \
isinstance(exp, int) and isinstance(var, str) and len(var)==1
self.coef = coef
self.var = var
self.exp = exp
def get_math_representation(self):
s = "" if self.coef==0 else \
("%s"%str(self.coef) if self.coef!=1 else "") +\
(" %s"%self.var if self.exp==1 else (" %s^%d"%(self.var, self.exp) if self.exp!=0 else ""))
return s
def show(self):
from IPython.display import Math, HTML, display
display(HTML("<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=default'></script>"))
return Math(self.get_math_representation())
def __repr__(self):
return self.get_math_representation()
class VarPol(Pol):
def __init__(self, first_node, vterm=VarTerm(1,"k",0)):
super(VarPol, self).__init__(first_node)
assert vterm is not None and isinstance(vterm, VarTerm), "must specify a VarTerm"
self.vterm = vterm
def get_math_representation(self):
return self.vterm.get_math_representation()+"("+super(VarPol, self).get_math_representation()+")"
p1 = VarPol( vterm=VarTerm(1,"x",3), first_node=Node(VarTerm(2,"y", 2), Node(VarTerm(5,"y"))))
p2 = VarPol(first_node=Node(VarTerm(7,"y",2)), vterm=VarTerm(1,"x",1))
p3 = VarPol(first_node=Node(p1, Node(p2)), vterm=VarTerm(1,"z", 2))
p4 = VarPol( vterm=VarTerm(1,"x",2), first_node=Node(VarTerm(5,"y", 1)))
p5 = VarPol( first_node=Node(p4, Node(VarTerm(4,"x",1))), vterm=VarTerm(1,"z",1))
p6 = VarPol( vterm=VarTerm(1,"x",3), first_node=Node(VarTerm(4,"y", 2)))
p7 = VarPol(first_node=Node(VarTerm(9,"y", 0), Node(VarTerm(8,"y",1))))
p8 = VarPol(first_node=Node(p3, Node(p5, Node(p6, Node(p7)))))
p8.show()
class VarPol(Pol):
def __init__(self, first_node, vterm=VarTerm(1,"k",0)):
super(VarPol, self).__init__(first_node)
assert vterm is not None and isinstance(vterm, VarTerm), "must specify a VarTerm"
self.vterm = vterm
def get_math_representation(self):
return self.vterm.get_math_representation()+"("+super(VarPol, self).get_math_representation()+")"
def evaluate(self, vals):
def evaluate_vterm(vterm, vals):
return vterm.coef*vals[vterm.var]**vterm.exp
vt = evaluate_vterm(self.vterm, vals)
vpol = 0
k = self.first_node
while k is not None:
vpol += evaluate_vterm(k.value, vals) if isinstance(k.value, VarTerm) else \
k.value.evaluate(vals) if isintance(k.value, VarPol) else 0
k = k.next
return vt*vpol
p1 = VarPol( vterm=VarTerm(1,"x",3), first_node=Node(VarTerm(2,"y", 2), Node(VarTerm(5,"y"))))
p2 = VarPol(first_node=Node(VarTerm(7,"y",2)), vterm=VarTerm(1,"x",1))
p3 = VarPol(first_node=Node(p1, Node(p2)), vterm=VarTerm(1,"z", 2))
p4 = VarPol( vterm=VarTerm(1,"x",2), first_node=Node(VarTerm(5,"y", 1)))
p5 = VarPol( first_node=Node(p4, Node(VarTerm(4,"x",1))), vterm=VarTerm(1,"z",1))
p6 = VarPol( vterm=VarTerm(1,"x",3), first_node=Node(VarTerm(4,"y", 2)))
p7 = VarPol(first_node=Node(VarTerm(9,"y", 0), Node(VarTerm(8,"y",1))))
p8 = VarPol(first_node=Node(p3, Node(p5, Node(p6, Node(p7)))))
p8.show()
vals = {"x": 1, "y":2, "z": 3}
print (p1.evaluate(vals))
p1.show()
Ejercicios de refuerzo (no obligatorios)¶
crea una función que evalúe un
VarPol, según definido en las notas.analiza la complejidad computacional de tus implementaciones
¿Podrías enriqueces
Nodepara mejorar la complejidad computacional?