Sesión 1: Conceptos básicos

Esta sección está orientada a resolver un problema algorítmico de teoría de números y revisa algunos conceptos básicos de la sintaxis y semática de Python. Hay dos soluciones al problema, una que explota características propias de la aritmética de precisión arbitraria implementada en Python. La otra, una solución que requiere algo de ingenio. Del lenguaje se abordan los conceptos de constante, variable, asignación, condicionales e iteración (con for y con while).

El problema

El problema se encuentra en la arena de programación competitiva UVa y es el siguiente:

10127 - Ones

Este problema puede ser formalizado de la siguiente manera:

Entrada: un número entero n, con n impar y no divisible por 5
Salida: longitud del mínimo entero positivo m divisible por n y tal que m contiene únicamente el dígito 1

Un número que tiene a 1 como su único dígito se llama (en inglés) repunit (de repetitive unit). Aunque el enunciado del problema no lo hace explícito, dadas las condiciones sobre n, hay un teorema que garantiza la existencia de m. Es decir, este es un problema de búsqueda con certeza.

Estrategia de solución

Dado que el problema es una búsqueda con certeza y que Python tiene artimética de precisión arbitraria, este problema acepta una solución muy sencilla. La idea es la siguiente: iterativamente construir los números 1, 11, 111, 1111, etc. hasta que encontremos uno múltiplo de n (ese sería el testigo m por el cual pregunta el problema). Note que esta estrategia no es posible, en general, al usar un lenguaje de programación como C que tiene tipos numéricos de precisión limitada.

Con base en la estrategia anterior, es necesario conocer los siguientes elementos del lenguaje:

asignaciones
iteraciones
operaciones aritméticas básiscas:
- suma
- multiplicación
- test de divisibilidad
leer de la entrada estándar
imprimir a la salida estándar
definición de funciones (así podemos organizar mejor el código del programa)

Tutoriales y documentación

En esta sección usaremos documentación externa para revisar los elementos del lenguaje necesarios para resolver el problema. En particular, visitaremos parte de la sección 3 de The Python Tutorial y practicaremos con material para aprender Python del sitio After Hours Programming.

Visite la sección 3.1.1 de The Python Tutorial para familiarizarse con algunos conceptos básicos de números en Python.
Lleve a cabo los siguientes tutoriales en el sitio After Hours Programming (no es necesario registrarse):

Adicionalmente hay que mencionar lo siguiente. Como se pudieron dar cuenta, Python ofrece asignaciones simultáneas, i.e., asignaciones en donde más de una variable puede ser afectada. Sin embargo, para aquellas personas que estamos acostumbradas a este tipo de funcionalidad es lenguajes algorítmicos, es importante resaltar que las asignaciones simultáneas en Python NO son asignaciones en paralelo. La semántica adoptada por Python para este tipo de asignaciones es una semántica de evaluación secuencial que en algunos casos difiere de una semántica pura de asignación en paralelo.

Para entender esta situación y su explicación pueden visitar:

Simultaneous assignment semantics in Python

Solución (versión 1)

La solución la presentamos en dos partes: (1) lectura de datos de entrada e impresión de datos de salida, y (2) solución algorítmica del problema.

Lectura e impresión de datos

Los datos se leen de la entrada estándar de la siguiente manera:

mientras que haya una línea por leer, esta se lee en la variable, digamos l (cada l es una cadena que representa un número entero)
el valor de l se convierte a un número entero y se almcena en la variable entera n
se invoca la función solve con parámetro n (esta función será implementada por nosotros a continuación)
se imprime la respuesta calculada en el numeral 3

El código de lectura, transformación de datos y de impresión hacen parte de una función main (esta función puede llamarse como uno quiera, no necesariamente main).

La estructura de la solución y la implementación de la función main se presentan a continuación:

from sys import stdin

def solve(n):

  pass

def main():

  for l in stdin.readlines():

    n = int(l)

    print(solve(n))

main()

Por favor cerciórese de entender la estructura del código y cómo interactúan sus principales componentes. Por favor consulte la documentación del comando pass.

Solución algorítmica del problema

La solución algorítmica del problema está implementada en la función solve y está basada en la estrategia descrita al inicio de la sesión: iterativamente construir los números 1, 11, 111, 1111, etc. hasta que encontremos uno múltiplo de n.

def solve(n):

  m,r = 1,1

  while m%n!=0:

    m,r = m*10+1,r+1

  return r

La variable m representa el testigo y r la cantidad de dígitos de m (invariante). Inicialmente m y r son asignadas el valor 1 (note que 0 es múltiplo de 2 y por ende no hace parte de la entrada del problema). El ciclo mantiene el invariante al aumentar m en un dígito y actualizando r con una unidad más. El ciclo termina cuando el resídulo al dividir m por n es 0, i.e., cuando m es múltiplo de n. El número de dígitos de m está almacenado en r, que corresponde al valor retornado por la función solve.

El código completo de la solución lo llamaremos ones_v1.py y es el siguiente:

from sys import stdin

def solve(n):

  m,r = 1,1

  while m%n!=0:

    m,r = m*10+1,r+1

  return r

def main():

  for l in stdin.readlines():

    n = int(l)

    print(solve(n))

main()

Ejecución y pruebas

Considere un archivo ones_test1.in con el siguiente contenido:

Al ejecutar la solución construída, se obtienen el siguiente resultado (el mismo del enunciado del problema).

$ python3 ones_v1.py < ones_test1.in

Solución (versión 2)

La primera versión de la solución es cortesía de la implementación de aritmética arbitraria en Python. Sin embargo, también explicamos inicialmente, algunos lenguajes de programación no cuentan con esta funcionalidad (al menos, como parte de su distribución básica). La buena noticia es que, bajo los supuestos iniciales del problema, la primera versión de la solución puede ser modificada ligeramente, sin alterar su sencillez y elegancia, para obtener una equivalente que no usa aritmética de precisión arbitraria.

Considere la guarda del ciclo en la función solve: m no es divisible por n (i.e., m%n!=0). Fíjese que para hacer la comprobación basta con fijarse en el resíduo de dividir m por n; en particular no nos interesa el valor del cociente de dividir m por n. Entonces es suficiente con almacenar el resíduo de dividir m por n (i.e., m módulo n) y no el valor de m.

El código que implementa esta observación hace parte de la función solve y se presenta a continuación:

def solve(n):

  m,r = 1%n,1

  while m!=0:

    m,r = m*10+1,r+1

    m = m%n

  return r

Note que el enunciado del problema indica que el varlor máximo de n es 10000. Por ende, esta versión 2 de la solución se puede implementar en un entero de 32 bits como (int en C y Java, por ejemplo) sin posibles efectos de desborde de tipo.

Tarea

Modifique el código de cualquiera de las versiones para imprimir, además de la longitud de m, el valor de m. Siga el formato de impresión del archivo ones_test3.out que corresponde a la salida correcta para la entrada en ones_test3.in. Verifique que su implementación es correcta con respecto al archivo de entrada ones_test4.in y de salida ones_test4.out. Una forma conveniente de resolver el problema es con tuple.
Implemente una solución para el problema 10359 - Tiling. Para validar su solución use los archivos tiling_test1.in y tiling_test1.out.
Lea la sección 3.1.2 sobre cadenas de The Python Tutorial y lleve a cabo el tutorial sobre cadenas de After Hours Programming.