Escribe una función qeq(a, b, c) que, dados tres valores enteros a, b, y c devuelva las dos soluciones de la ecuación de segundo grado ax2 + bx + c = 0
Escribe una función roman_to_int(r) que, dada una cadena de texto que representa un número romano (por ejemplo, r="XIV") devuelva su valor entero decimal.
Escribe una función fit(X, Y) que, dados dos vectores de valores X e Y devuelva la pendiente a y la ordenada en el origen b de la recta y = ax + b que mejor se ajusta a los datos (regresión lineal).
Curso 2015-2016
Fecha límite de entrega: 2 de noviembre, hasta las 15.00. Escribe una función hyphenate(palabra) que devuelva una palabra en castellano dividida en las sílabas que la componen. Por ejemplo, si la palabra es "cambio" debe devolver la cadena de texto "cam-bio", y si es "edad", devolverá "e-dad". Para ello, debe tener en cuenta que una sílaba debe contener al menos una vocal y que el carácter siguiente a dicha vocal inaugura una nueva sílaba sólo en ciertos casos: cuando la vocal es abierta y el nuevo carácter es también una vocal abierta; cuando es una consonante seguida de vocal; cuando es una consonante doble ("ch", "rr" o "ll"); o cuando es una consonante fuerte seguida de "r" o "l" (por ejemplo, "tr", "pl").
Fecha límite de entrega: 16 de noviembre, hasta las 15.00. Implementa una función llamada bin_search que calcule el valor de x para el que una función real monótona (creciente o decreciente) se aproxima más a un valor y dado. La función bin_search tomará 5 parámetros:
La función f que debe evaluarse.
El límite inferior xmin del rango de búsqueda.
El límite superior xmax del rango de búsqueda.
La precisión epsilon para determinar el valor de x.
El valor objetivo ytarget.
La función devolverá el valor x, con precisión epsilon, para el que f(x) se aproxima más a ytarget. Comprueba, por ejemplo, que sin(x) se aproxima a 2^(-0.5) si x se acerca 0.25*pi.
Fecha límite de entrega: 21 de diciembre, hasta las 15.00. Se nos ha encargado implementar una función -denominada rentabilidad(nombre_de_archivo)- que calcule la tasa interna de rentabilidad (TIR o rentabilidad promedio) de una cartera de inversiones.
Las transacciones se guardan en una hoja de cálculo cuya primera columna contiene la fecha en que se realizó (en formato ISO 8601), la segunda el número de unidades compradas o vendidas, la tercera una descripción breve del activo, y la cuarta el valor de compra o de venta (negativo en el segundo caso). Supondremos que la última línea contiene la fecha y en la cuarta columna
el valor actual de todos los activos en propiedad (comprados pero no vendidos).
El número de años transcurridos se calculará como la razón entre el número de días y 365,25.
Se supondrá que el dinero desinvertido no produce ninguna rentabilidad, es decir, que se gasta o no se invierte.
Dado que el valor es una función monótonamente creciente con la rentabilidad, su valor se obtendrá mediante búsqueda binaria en el rango [-1.0, 1.0] con precisión 0.001.
Este documento proporciona más detalles sobre cómo calcular la rentabilidad.
Unexcel de ejemplo con rentabilidad aproximada 0.07666.
Curso 2014-2015
Criptografía. Fecha de entrega: 21 de octubre, hasta las 15.00.
Escribe una función char_freq_in_string(s) que dada un texto s (es decir, una variable de tipo string) devuelva un mapa de los caracteres que aparecen en s y sus frecuencias absolutas. Implementa otra función char_freq_in_file(f) que haga lo mismo a partir de un archivo de texto f (es decir, f es una variable de tipo file). Calcula las frecuencias relativas de las letras del castellano y del inglés (sin distinguir mayúsculas y minúsculas) y explica qué diferencias notables observas entre sus letras más frecuentes. La función debe estar en un archivo p1.py y el informe en otro llamado p1.pdf. Puedes utilizar,por ejemplo, este archivo de texto en inglés y su traducción al castellano para hacer pruebas. Nota: los textos usan la codificación más habitual para texto, UTF8. Para que las letras con acentos diacríticos (por ejemplo, á) se vean correctamente puedes aplicar la siguiente función a cada línea de texto: linea_descodificada = linea_original.decode('UTF8'). Si utilizas otros textos, debes comprobar cuál es la codificación que usan y sustitutir UTF8 por la que corresponda (por ejemplo Windows-1252). Parte opcional: para reemplazar caracteres con diacríticos puedes usar, por ejemplo "ábc".replace(u'á', 'a') (observa la u, abreviatura de Unicode, antes de la á).
Pasatiempos. Fecha de entrega: 3 de noviembre, hasta las 15.00.
Se nos pide que preparemos un programa para resolver problemas de asignación de dígitos distintos (entre 1 y 9) a variables como, por ejemplo, abcd * e = dcba. Para ello, escribe una función test(a, b, c, d, e) que compruebe si los enteros a, b, c, d y e satisfacen la ecuación anterior. Después escribe una función search() que devuelva la primera solución que encuentre al problema. Escribe otras funciones test2(s,e,n,d,m,o,r,y) y search2() para el problema siguiente: send + more = money.
Inteligencia artificial (Mastermind). Fecha de entrega: 24 de noviembre.
Debemos adivinar una secuencia X de 4 símbolos distintos con su orden correcto. La secuencia se ha construido seleccionando aleatoriamente valores de entre 6 disponibles (A, B, C, D, E, F), no permitiéndose la repetición de valores en la misma secuencia. Para encontrar X, debemos formular hipótesis y el sistema nos dirá cuántos de los valores se corresponden con la secuencia oculta. Por ejemplo, si X = ('A', 'B', 'F', 'E'), la hipótesis H = ('E', 'B', 'D', 'A') contiene un valor correcto (B),y dos mal ubicados (E y A). Escribe un función check(X, H) que dados los vectores X y H (la incógnita y la hipótesis), devuelva un par de enteros (m, n) donde m es el número de caracteres que coinciden en X y H (es decir, con valor y posición idénticos) y n es el número de caracteres de X que se hallan en H incorrectamente ubicados. Por ejemplo, si X = ('A', 'B', 'C', 'D'), entonces:
check(X, ('B','A','C','C')) devuelve (1, 2)
check(X, ('C','C','C','C')) devuelve (1, 0)
check(X, ('D','D','B','A')) devuelve (0, 3)
Implementa otra función llamada check_candidate(candidate, results) que devuelta True si (y sólo si) el vector candidate es compatible con todos los resultados guardados en el diccionario results. El diccionario contiene, para aquellas secuencias h propuestas anteriormente, el resultado de check(X, h), es decir, results[h] puede ser None indefinido) o check(X, h). Por ejemplo, results = {('B','A','C','C'):(1,2), ('C','C','C','C'):(1,0), ('D','D','B','A'):(0,3)} entonces check_candidate(('B','A','C', 'C'), results) devuelve False mientras que check_candidate(('A','B','D', 'C'), results) devuelve True.
Utiliza las funciones anteriores para escribir una tercera función, guess(results), que devuelva una hipótesis (tupla) de cuatro componentes teniendo en cuenta los resultados anteriores guardados en el diccionario results). Procura que la hipótesis propuesta permita que el programa pueda adivinar el vector incógnita X en el menor número de intentos posible.
Cifras y letras. Fecha de entrega: 22 de diciembre.
Una de las pruebas del concurso cifras y letras consistía en obtener, a partir de unas cifras dadas y operaciones aritméticas básicas (sumas, restas, multiplicaciones y divisiones enteras), un valor predeterminado. No es obligatorio usar todas las cifras, pero estas no pueden usarse más de una vez (aunque sí podría ocurrir que haya alguna repetida, en cuyo caso se puede usar como máximo el número de veces que aparece repetida). Escribe una función build(numbers, goal) que devuelva True si (y sólo si) el entero goal puede obtenerse aplicando operaciones aritméticas sencillas a los números de la lista numbers.
Por ejemplo, si numbers=[2, 7, 9, 1] y goal = 15, la respuesta será True porque (2 * 7) + 1 = 15; en cambio si goal = 29 la respuesta es False dado que no hay ninguna forma de obtener ese resultado a partir de (algunos o todos) los valores de la lista.
La implementación de build debe hacer lo siguiente:
Si goal está en la lista numbers termina y devuelve True.
En caso contrario, para todos los pares de números x e y en la lista numbers hace lo siguiente:
Calcula el resultado r de (x + y), |x - y|, x * y y, si el resultado de la división es entero también x / y (o y / x, cuando y > x).
Para cada resultado posible r, llama recursivamente a la función build con una nueva lista (más pequeña) donde x e y han sido sustituidos por el resultado r.
Si (y solo si) alguna de las llamadas recursivas devuelve True, entonces build responde True.
OPCIONAL: Escribe otra función operations(numbers, history, goal) que devuelva una cadena que describa una secuencia de operaciones que permite obtener goal (y None si esto no es posible). Por ejemplo, si goal= 527 y numbers = [7, 6, 5, 5, 6, 4] puede devolver '(6+(5*5))*(4+(7+6)))'. Nota: history es una lista que almacena cadenas de texto que describen las operaciones que han permitido obtener cada valor de la lista numbers. En el último ejemplo, history es, inicialmente, ['7', '6', '5', '5', '6', '4'] y se actualiza en cada llamada recursiva. Si, por ejemplo, se multiplican las dos primeras cifras numbers pasa a ser ['42', '5', '5', '6', '4'] y history es ['(7*6)', '5', '5', '6', '4'].
Problemas de cursos anteriores
Curso 2013-2014
Cuadrados mágicos. Fecha de entrega: 11 de octubre, hasta las 15.00.
Escribe una función magic(M) que, dada una matriz M determine si es un cuadrado mágico, es decir, que devuelva True si la suma de cada una de sus filas, columnas y diagonales principales es constante y False en caso contario. Las matrices se escribirán como listas de listas de valores numéricos enteros, por ejemplo, A = [[4, 9, 2], [3, 5, 7], [8, 1, 6]] es una matriz de tamaño 3 por 3 con constante mágica 15. El programa se pondrá en marcha así: python pr1.py. El programa esperará (sin preguntar nada) a que escribamos con el teclado la matriz en el formato explicado de listas de listas, por ejemplo, [[4, 9, 2], [3, 5, 7], [8, 1, 6]]. Tras apretar la tecla de salto de línea, el programa escribirá en la pantalla cierto o falso según sea M mágica o no.
Números primos. Fecha de entrega: 18 de noviembre, hasta las 15.00.
En un programa llamado pr2.py, escribe una función primes(m) que devuelva una lista con todos los números primos desde 1 hasta m. Después implementa otra función split(L, a, b, n) que, dada la lista de valores L (no necesariamente ordenada) y un número de segmentos n, calcule cuántos valores de L hay en cada uno de los n subintervalos que resultan de dividir el intervalo comprendido [a,b] y devuelva el resultado como una lista de n enteros. Por último, programa una función plot(m, n) que dibuje un histograma que represente cuántos números primos comprendidos hay en cada uno de los n intervalos de tamaño m/n que van desde 1 hasta m.
Damas y caballos. Fecha de entrega: 2 de diciembre, hasta las 15.00. En un archivo llamado pr3.py escribe una función recursiva place(T, q, ka) que simule la colocación de damas de ajedrez en un tablero sin que se amenacen mutuamente. Debes tener en cuenta que:
El parámetro T representa el tablero como una lista de enteros en la que el valor de T[i] es la columna donde se sitúa la dama de la fila i o -1 si la dama de esa fila aún no ha sido colocada. Importante: a diferencia del ejercicio realizado en clase, ahora el tablero T podrá tener cualquier tamaño nxn.
El parámetro q es un entero que identifica la primera fila vacía en el tablero, comenzando por 0, es decir, la dama número 0 es la primera que hay que colocar.
El parámetro ka (knight attack) es una variable booleana. Si ka es falso. las damas sólo amenazan las casillas accesibles según los movimientos clásicos de la dama de ajedrez (todas las casillas en la misma fila, columna o diagonal); en cambio, si ka es cierto, también amenazarán las casillas según el movimiento de un caballo (knight).
La función place no devolverá nada ni imprimirá nada en pantalla, solo guardara en la variable global sols el número de soluciones distintas encontradas.
La leyenda de Teseo y el Minotauro. Fecha de entrega: 20 de diciembre, hasta las 23:59.
La princesa Ariadna enamorada de Teseo le propuso, con su ayuda, derrotar a su hermano (el Minotauro) y a cambio se casaría con él. Teseo aceptó. La ayuda de Ariadna consistió en dar a Teseo un ovillo de hilo que éste ató por uno de los extremos a la puerta del laberinto mientras que él conservó el otro extremo. De este modo podría guiarse por el laberinto. Teseo entró así en el laberinto, donde finalmente encontró y derrotó al Minotauro. A continuación, Teseo, recogió el hilo y así pudo salir del laberinto. Aquí está el punto de partida de nuestra práctica.
Describimos un laberinto como una lista de listas, es decir, una matriz, donde cada celda contendrá un carácter que podrá ser uno de estos:
@ Representa a Teseo, así podemos saber si ya ha visitado una celda del laberinto.
* Representa una pared, en este caso no se puede visitar ni atravesar esa celda.
' ' (Espacio en blanco) Indica que esa celda se puede visitar.
E Representa la salida del laberinto (`exit`).
Por ejemplo:
# Laberinto con solucion: Salida en (y=1, x=10), Entrada en (y=7, x=0).
M= [
['*','*','*','*','*','*','*','*','*','*','*'],
['*','*','*','*','*','*','*','*','*',' ','E'],
['*','*','*',' ','*','*','*','*',' ','*','*'],
['*','*',' ','*',' ','*','*',' ','*','*','*'],
['*','*',' ','*','*',' ',' ','*','*','*','*'],
['*','*',' ','*','*','*','*','*','*','*','*'],
['*',' ','*','*','*','*','*','*','*','*','*'],
[' ','*','*','*','*','*','*','*','*','*','*']
]
Una posible solución es:
* * * * * * * * * * *
* * * * * * * * * @ E
* * * @ * * * * @ * *
* * @ * @ * * @ * * *
* * @ * * @ @ * * * *
* * @ * * * * * * * *
* @ * * * * * * * * *
@ * * * * * * * * * *
Con todo esto se pide escribir en un archivo llamado pr4.py una función recursiva que tenga este nombre y estos parámetros y que devuelva la primera solución que encuentre: def solve ( i, M ):
Donde los parámetros 'i' y 'M' son:
i La tupla de coordenadas '(y,x)' que representa la celda de entrada al laberinto.
M La lista de listas que representa al laberinto.
La función solve devuelve una lista de tuplas '(y,x)' que representa un camino que desde la entrada 'i' llega a la celda con una 'E' en el laberinto 'M'. Si no hay ningún camino, será una lista vacía. Ten en cuenta que la tupla de entrada 'i' puede referirse a una celda con un espacio (' ') o a una celda con una pared ('*') pero no a la celda de salida ('E').
Un caso de llamada para este ejemplo: print solve ( (7,0), M )
Produciría esta salida:
[(7, 0), (6, 1), (5, 2), (4, 2), (3, 2), (2, 3), (3, 4), (4, 5), (4, 6), (3, 7), (2, 8), (1, 9), (1, 10)]
En el fichero pr4.py a entregar sólo debes escribir la función 'solve', nada más, no debe tener un programa principal. Si usas un programa principal de prueba antes de entregarlo debes borrarlo.
Curso 2012-2013
Multiplicación de matrices. Fecha límite de entrega: 18 de octubre, hasta las 15.00.
Implementa un programa llamado matrix.py que multiplique dos matrices A y B. Las matrices (tanto las que hay que multiplicar como el resultado) se escribirán como listas de listas de valores numéricos (enteros, reales o complejos), por ejemplo, A = [[2, 4, 3.5], [1, 3.3, 6]] es una matriz de tamaño 2 por 3.
El programa se pondrá en marcha así:
python matrix.py
Sin preguntar nada esperará que escribamos con el teclado la primera matriz en el formato de explicado de listas de listas, por ejemplo,
[ [1, 2] , [3, 4] ]
A continuación (también sin preguntar nada), esperará que escribamos la segunda matriz, por ejemplo,
[[3], [7]]
Si se pueden multiplicar las matrices, el programa llevará a cabo la multiplicación e imprimirá el resultado mostrando la matriz resultado fila por fila y los elementos de cada fila separados por un espacio en blanco. así, para las matrices A y B del ejemplo veremos:
17
37
En cambio, si para la primera matriz escribimos
[ [2, 3, 4] , [1, 4, 5], [3, 1, 7] ]
y la segunda matriz es
[ [1, 2] , [3, 4] , [5, 6] ]
entonces, el resultado exactamente (aunque lo pueda parecer no hay lningún espacio en blanco al principio ni al final de cada línea):
31 40
38 48
41 52
Si las matrices no se pueden multiplicar el programa mostrará por pantalla la cadena: "error" (sin las comillas).
Medias móviles. Fecha límite de entrega: 10 de noviembre hasta las 14.30.
Dado un archivo de texto prima.txt como el siguiente, que contiene una lista de fechas y valores asociados
2012-01-01 33.5
2012-01-02 55.7
2012-01-04 27.3
...
Escribe un programa ma.py que represente gráficamente los valores como puntos en función de la fecha, así como la media móvil de los últimos n días. Por ejemplo, para la lista de valores [33.5, 55.7,27.3] anterior, las medias móviles con n = 2 son [33.5, 44.6, 41.5]. Puedes descargar un archivo de prueba de esta dirección.
El nombre del archivo y el parámetro n se tomarán de la entrada estándar, es decir, el programa se ejecutará, por ejemplo, ma.py prima.txt 3. También se podrá solicitar varias medias móviles superpuestas, por ejemplo, ma.py prima.txt 7 30 365.
Prepara tu programa para que funcione correctamente tanto si las fechas están ordenadas ascendentemente como descendentemente o en cualquier otro orden.
Programas para el cálculo del área de una curva. Fecha límite de entrega: 5 de diciembre hasta las 14.30.
En una archivo llamado integral.py, escribe una función simpson(f, xmin, xmax, N) que calcule el valor del área bajo una curva f(x)en el intervalo [xmin,xmax] por el procedimiento de Simpson : para todos los valores de xmin + nh con h = (max - xmin) / N y n = 1,3,5,..., N - 1, añade (f(x-h)+4*f(x)+f(x+h))*h/3 al resultado. Escribe otra función montecarlo(f, xmin, xmax, N) que calcule el valor del área bajo una curva f(x) en el intervalo [xmin,xmax] por el siguiente procedimiento: genera N valores al azar entre xmin y xmax con distribución uniforme, calcula el promedio de f(x) para los N valores y devuelve el producto del promedio de f(x) y (xmax-xmin).
Opcional: haz que el programa principal lea el método, la función, los límites y el número de puntos de la entrada estándar. Por ejemplo, se escribirá python integral.py simpson math.sin(x) -1 1 1000. No te olvides de poner en la cabecera import math, para poder utilizar las funcioens matemáticas como math.sin, math.sqrt, etc. Si se implementa esta parte opcional, incluye un comentario en la primera o segunda linea del archivo que diga # Implementada la lectura de la entrada estándar.
Ordenación por mezcla. Fecha límite de entrega: 21 de diciembre, hasta las 15.00. Un método muy rápido para ordenar (de menor a mayor) una lista de enteros consiste en partir la lista en dos mitades, ordenar cada una de ellas y luego mezclar las dos sublistas:
def msort(L, i, j): # sort sublist L[i:j]
if j - i == 1: # trivial case
return L[i:j]
else:
k = i + (j - i) / 2 # k is central point between i and j
R1 = msort(L, i, k)
R2 = msort(L, k, j)
return merge(R1, R2)
Implementa la función merge(R1, R2) en un archivo msort.py que, dadas dos listas ordenadas de enteros, devuelve una lista con los elementos de R1 y R2 ordenados. Para ello, no puedes usar las funciones sort que porporciona el lenguaje de programación. Procura que el tiempo de cálculo de la función merge sea proporcional a len(R1) + len(R2). Naturalmente, la lista puede contener elementos repetidos.
Otros problemas prácticos de programación
Una fundación debe repartir equitativamente N bienes entre dos socios. Para ello se crearán dos lotes de valor idéntico con una parte de los bienes y el resto se enajenará para repartir su valor en efectivo. Dado que cada venta implica algunos costes financieros, se desea maximizar el valor repartido en especie.
Escribe una función llamada reparto(data) (en un archivo reparto.py) que devuelva el valor máximo de los bienes que pueden agruparse en dos lotes de valor idéntico. La entrada es una cadena que contiene enteros separados por espacios en blanco y que representan los valores w1,...,wN.
Por ejemplo, si la entrada es [15, 5, 46, 37, 6, 1] la salida correcta es 104, pues 52=46+6=37+15.
Para el entrada [14, 17, 26, 97, 30, 30, 23, 91, 16, 44], la salida correcta es 388.
[Instrucciones]. Escribe un programa que lea una lista de enteros (separados por espacios en blanco) y devuelve el valor máximo de todos ellos. Modifica el programa para que lea una lista de números (enteros o reales), escriba cuál es su máximo, su promedio y su desviación típica.
[Gráficos] Escribe un programa que lea el nombre de un fichero y escriba las características de la recta que mejor se ajusta a los puntos dados. El fichero contendrá pares de números reales separados por espacios (un par en cada línea) y el resultado debe mostrar una línea de texto con los valores de a (la pendiente) y b (la ordenada en el origen) del mejor ajuste. Modifica el programa anterior para que dibuje en un gráfico en la pantalla del ordenador los puntos y la recta resultado.
[Estructuras de datos]. Escribe un programa que lea todas las palabras contenidas en un fichero y las muestre por orden alfabético (una por línea) junto al número de veces que aparece cada una. Haz que le programa anterior muestre una gráfica de frecuencias ordenadas de mayor a menor en escala logarítmica y el mejor ajuste lineal (según la ley de Zipf).
[Simulación]. Escribe un programa para simular el efecto distributivo de la lotería.
[Programación recursiva]. Escribe un programa que resuelva un tablero del juego sudoku almacenado en el archivo cuyo nombre lea de la entrada. El archivo contiene 9 líneas de longitud 9 con el valor de cada posición o un 0 si es desconocido.
[Programas voraces]. Escribe un programa que lea una lista de enteros que representan una cantidad de dinero (entre 0 y 99) seguida de las denominaciones disponibles de una moneda (también entre 0 y 99). El resultado debe mostrar el número medio de monedas necesario para realizar un pago (o devolución) cuando todos los valores entre 0 y 99 son equiprobables. El número de monedas se obtendrá mediante un método voraz.
[Programación dinámica]. Modifica el programa anterior para que calcule el número óptimo de monedas, sea cual sea la estructura de denominaciones. Determina el promedio teniendo en cuenta la ley de Benford y compara el sistema europeo (1,2,5,10, 20, 50) con el de los E.U.A (1, 5, 10, 25, 50). Estudia posibles estrategias para determinar el número óptimo de denominaciones.
[Programación dinámica]. Escribe un programa para resolver el problema de la asignación óptima de tareas.
[Ramificación y poda] Escribe un programa para la encontrar la forma óptima de iluminar calles en una ciudad.