Tutorial Python

Este problema es de baja dificultad. El enunciado del mismo se puede encontrar aquí .

# solucion problema OFFSIDE para spoj.pl

# lectura cantidad atacantes y defensores
atacantes, defensores= ([int(x) for x in raw_input().split()])

while (atacantes != 0):
  # lectura renglon con lista distancias atacantes
  listaata = ([int(x) for x in raw_input().split()])
  # lectura renglon con lista distancias defensores
  listadef = ([int(x) for x in raw_input().split()])

  listadef.sort()
  # segundo=listadef[1]
  if min(listaata) < listadef[1]:
    print 'Y'
  else:
    print 'N'
  atacantes, defensores= ([int(x) for x in raw_input().split()])

Diciembre 17, 2008 | Palabras Clave: acm, codigo, eficiencia, Problemas, python | Categoría: ACM en Python, Códigos | Dejar un comentario

Las excepciones en sí mismas, son distintos tipos de errores que puede generar un programa, es decir, son un comportamiento no esperado, que se produjo como consecuencia de una ejecución no planificada, dentro del programa. De aquí se deduce, que las excepciones no son un comportamiento deseado en la programación, ya que hacen que los programas se vuelvan inseguros y poco confiables, además de inestables. Por esto mismo, existe el Manejo de Excepciones que, actualmente, es implementado por muchos lenguajes diferentes.

Manejar una excepción, significa que un programa puede tolerar la ocurrencia de ciertos errores durante su corrida, y seguir ejecutándose, teniendo un comportamiento especial para cada tipo de error (y también, según la necesidad del programa o del programador, según el lugar donde ocurre). Esto hace que el programa se vuelva confiable, ya que al no interrumpirse la ejecución, hay menos posibilidad de pérdida de datos, haciendo que el software sea más estable y eficiente.

En resumen, el manejo de excepciones es una estructura de control diseñada para manejar condiciones anormales que pueden ser tratadas por el mismo programa que se desarrolla: al producirse una excepción se desciende en la pila de ejecución hasta encontrar un manejador para la excepción, el cual toma el control en ese momento.

More »

Diciembre 11, 2008 | Palabras Clave: clases, ejemplo, excepciones, except, exception, handling, jerarquía, python, try | Categoría: Programación Python | Dejar un comentario

Python es un lenguaje muy amplio que contiene muchas librerías y módulos ya desarrollados, que permiten tener un margen de acción grande, a la hora de su utilización. Algunas de estas librerías, están dedicadas a facilitar la programación web, manejo de servidores, acceso a url’s y a bases de datos -entre otras cosas- con Python. Sin embargo, para comenzar con este tipo de enfoque en Python, primero hay que tener las nociones básicas de la web, y también de algunas de las librerías básicas que se ofrecen para este tipo de tareas.

Clientes y Servidores
Un explorador es sólo un tipo de cliente web, ya que cualquier aplicacion que realiza una llamada a un servidor web, se considera cliente. Un programa cliente puede descargar datos, subir datos, manipularlos e incluso transmitirlos a otra locación; por ejemplo: al abrir un URL desde un programa python, éste está actuando como un cliente, al solicitarle un acceso al servidor que contiene a la página que se desea acceder.

More »

Diciembre 4, 2008 | Palabras Clave: librerías, programación, python, urllib, urlparse, web | Categoría: Programación Web | Dejar un comentario

El algoritmo escrito a continuación corresponde al Ordenamiento Radix Sort, el cual ordena los enteros de la lista, procesando sus dígitos por separado, conteniéndolos en urnas. A continuación, se presenta el algoritmo, con algunas funciones auxiliares para su funcionamiento:

Algoritmo de Ordenamiento Radix Sort en Python

from random import uniform

#Algoritmo escrito por Marco Lorenzotti y Melina Vidoni
#Forma no recursiva

def radixsort(lista):
    cifras=contar(lista)
    mod=10
    div=1
    for i in range(0, cifras):
        lista=ponerCola(lista, mod, div)
        mod*=10
        div*=10
    return lista

def contar(lista):
    max=mayor(lista)
    largo=0
    while ((max/10)!=0) :
      max=int(max/10)
      largo+=1
    return largo

def mayor(lista) :
  max=0
  for i in range(0,len(lista)) :
    if (max<lista[i]) :
      max=lista[i]
    return max

def ponerCola(lista, mod, div):
    colas = [ [], [], [], [], [], [], [], [], [], [] ]
    temp = []
    for i in range(0, len(lista)):
        colas[lista[i] % mod / div].append(lista[i])
    for i in range(0, 10):
        temp.extend(colas[i])
    return temp

Explicación:
Éste método también se denomina generalización clasificación por urnas, ordena una secuencia de n elementos, siempre que se conozca algo del tipo de las claves que se están ordenando (la cantidad máxima de cifras en los números). Éste algoritmo publicado, funciona sólo para números enteros positivos, dejando los negativos en la parte final de la lista, sin importar su valor absoluto.
Consiste en hacer diversos montones de valores, cada uno de los cuáles se caracteriza por tener sus componentes un mismo digito en la misma posición. Luego, une todos esas pilas en orden ascendente, y las reparte de nuevo en montones, según el siguiente dígito de la clave.
Es un algoritmo muy eficiente.

Recursos de Interés
Ordenamiento RadixSort (wikipedia)

Noviembre 6, 2008 | Palabras Clave: algoritmo, iterativo, no recursivo, ordenamiento, python, radix, radixsort, sort, sorting | Categoría: Códigos | Dejar un comentario

A continuación se encuentra el codigo Python para el problema el Mundo de bloques publicado anteriormente.

# Problema: El Mundo de Bloques.

# Se importa el modulo STRING para utilizar la funcion 'split'.

from string import split

# LISTA QUE REPRESENTA EL MUNDO DE BLOQUES.

mundo = []

# --- 

# FUNCIÓN PRINCIPAL: Lee el archivo de entrada y
# escribe el archivo de salida.

def mundoBloques():
    # Abrir el archivo de entrada en modo lectura.
    entrada = open('entrada.txt', 'r')

    # Crea la lista leyendo la primera linea que determina el tamaño.
    crearMundo(int(entrada.readline()))

    for linea in entrada:
        ejecutar(linea) # Procesar cada linea.

    entrada.close()     # Cierra el archivo de entrada.
    escribirSalida()    # Escribe en el archivo el estado resultado.

# ---

# FUNCIONES AUXILIARES:

# Función auxiliar que crea los elementos de la lista.

def crearMundo(tamanio):
    for i in range(0, tamanio):
        mundo.append([i])

# Función auxiliar que desglosa la linea de comando
# y ejecuta el comando correspondiente.

def ejecutar(linea):
    if not (linea == 'terminar'):     # Si es el comando 'terminar' finaliza el programa.
        listaCom = split(linea, ' ')  # Se divide cada linea de texto.
        bloqueA = int(listaCom[1])
        bloqueB = int(listaCom[3])
        if validar(bloqueA, bloqueB):
            comando = listaCom[0]
            subCom = listaCom[2]
            if comando == 'mover':
                if subCom == 'en':
                    moverEn(bloqueA, bloqueB)     # Ejecutar 'mover .. en .. '
                else:
                    moverSobre(bloqueA, bloqueB)  # Ejecutar 'mover .. sobre .. '
            else:
                if subCom == 'en':
                    pilaEn(bloqueA, bloqueB)    # Ejecutar 'pila .. en .. '
                else:
                    pilaSobre(bloqueA, bloqueB) # Ejecutar 'pila .. sobre .. '

# Función auxiliar que valida los argumentos del comando.
# Los bloques argumentos no pueden ser iguales, ni estar en la misma pila.

def validar(a, b):
    if (a == b) or (buscar(a) == buscar(b)):
        return False
    else:
        return True

# Función auxiliar que abre y escribe el archivo de salida.

def escribirSalida():
    salida = open('salida.txt', 'w')
    for i in range(0, len(mundo)):
        salida.write(str(i) + ': ')
        for j in range(0, len(mundo[i])):
            salida.write(str(mundo[i][j]) + ' ')
        salida.write('\n')
    salida.close()

# Función que busca en que pila se encuentra un bloque.

def buscar(a):
    for i in range(0, len(mundo)):
        if not (mundo[i].count(a) == 0):
            return i

# Función que devuelve los bloques encima del
# bloque argumento a sus posiciones originales.

def remover(a):
    pos = buscar(a)
    temp = subLista(a, pos)
    mundo[pos].append(temp[0])
    for i in range(1, len(temp)):
        mundo[temp[i]].append(temp[i])

# Funcion que retorna una sublista y la borra de la pila.

def subLista(a, pos):
    i = 0
    encontrado = False
    while not encontrado:
        if mundo[pos][i] == a:
            encontrado = True
        else:
            i += 1
    temp = []
    for j in range(i, len(mundo[pos])):
        temp.append(mundo[pos][i])
        mundo[pos].remove(mundo[pos][i])
    return temp

# ---

# COMANDOS PRINCIPALES:

# Para realizar las funciones de los comandos principales se utilizan combinaciones
# de las funciones auxiliares.

# COMANDO: MOVER EN:

def moverEn(a, b):
    remover(b)
    moverSobre(a, b)

# COMANDO: MOVER SOBRE:

def moverSobre(a, b):
    posA = buscar(a)
    remover(a)
    mundo[buscar(b)].append(a)
    mundo[posA].remove(mundo[posA][-1])

# COMANDO: PILA EN:

def pilaEn(a, b):
    remover(b)
    pilaSobre(a, b)

# COMANDO: PILA SOBRE:

def pilaSobre(a, b):
    mundo[buscar(b)].extend(subLista(a, buscar(a)))

# --- FIN DEL PROGRAMA ---

Octubre 31, 2008 | Palabras Clave: bloques, Códigos, Problemas, vectores | Categoría: Códigos | Dejar un comentario

El algoritmo desarrollado a continuación es la implementación iterativa (no recursiva) del famoso Ordenamiento Rápido, también denominado Quicksort, que fue desarrollado por Tony Hoare. La forma no recursiva es bastante más larga y complicada de entender que la recursiva, y necesita del uso de clases. Sin embargo, sigue siendo tan rápido y eficiente como su versión recursiva, sólo que su código pierde elegancia:

Algoritmo de Ordenamiento Quicksort No Recursivo en Python

#Algoritmo escrito por Melina Vidoni
#Forma no recursiva

class Pila () :
  inferior=0
  superior=0

def quicksortNoRec (lista) :
  """Ordena la lista siguiendo el algoritmo quicksort
  o de ordenación rapida. Forma no recursiva"""
  qs(lista,0,len(lista)-1)
  return lista

def qs (lista,inicial,final) :
  p=1
  "declaramos la pila de estructuras"
  pila=[20]
  for m in range(0,20) :
    pila=Pila()
  "ahora se comienza a ordenar"
  pila[p].inferior,pila[p].superior=inicial,final
  while p :
    inicial,final=pila[p].inferior,pila[p].superior
    p-=1
    izdo,dcho=inferior,superior
    while inferior<dcho :
      izdo,dcho=inferior,superior
      mitad=lista[izdo+((dcho-izdo)/2)]
      while izdo<=dcho :
        while lista[izdo]<mitad and izdo<final : izdo+=1
        while mitad<lista[dcho] and dcho>inicial : dcho-=1
        if izdo<=dcho :
          lista[izdo],lista[dcho]=lista[dcho],lista[izdo]
          izdo+=1
          dcho-=1
      if izdo<final :
        p+=1
        pila[p].inferior,pila[p].superior=izdo,final
      final=dcho
  return lista

Explicación:
Para comenzar, se declara una clase pila que contiene un valor inferior y uno superior, ambos inicializados en cero. La función principal recibe como argumento solamente a la lista en cuestión, y desde ahí llama a la función de ordenamiento, con los valores correspondientes.
En la función qs primero se declara un array de varios elementos, los cuales son del tipo Pila definido previamente. Con esto, se comienza una iteración por los elementos de la lista a ordenar, dividiéndola en sectores, cuyos índices superior e inferior se almacenan en un elemento de la Pila. Esto ocurre hasta que la lista se encuentra ordenada en su totalidad.
La versión no recursiva (o iterativa) es tan eficiente como la versión recursiva (la más común), pero desarrollo es un poco más compleja. Al igual que la otra, es muy útil para ordenar listas con elementos muy dispersos, o con números negativos entre sus valores.

Recursos de Interés:
Ordenamiento Quicksort (wikipedia)
Ordenamiento Quicksort Recursivo en Python
Ejemplo de Creación de Clases en Python
“Algoritmos de Ordenación”, de Sebastián Gurin

Octubre 30, 2008 | Palabras Clave: iterativo, no, ordenamiento, python, quick, quicksort, rápido, recursivo | Categoría: Códigos | Dejar un comentario

El algoritmo escrito a continuación, es la implementación más conocida del Ordenamiento Rápido, más conocido como Quicksort. Fue denominado de esta forma por su creador Tony Hoare, y hasta ahora es el algoritmo (en la práctica) más corto, elegante y eficiente de ordenación. Su implementación recursiva es muy popular, y recibe como parámetro sólo la lista a ordenar, necesitando por eso de una función auxiliar, que realiza la ordenación propiamente dicha:

Algoritmo de Ordenamiento Quicksort Recursivo en Python

#Algoritmo escrito por Melina Vidoni
#Forma recursiva

def quicksort (lista) :
  """Ordena la lista siguiendo el algoritmo quicksort
  o de ordenación rápida"""
  ordena_quicksort(lista,0,len(lista)-1)
  return lista

def ordena_quicksort (lista,izdo,dcho) :
  if izdo<dcho :
    pivote=lista[(izdo+dcho)/2]
    i,d=izdo,dcho
    while i<=d :
      while lista[i]<pivote : i+=1
      while lista[d]>pivote : d-=1
      if i<=d :
        lista[i],lista[d]=lista[d],lista[i]
        i+=1
        d-=1
    if izdo<d : ordena_quicksort(lista,izdo,d)
    if i<dcho : ordena_quicksort(lista,i,dcho)
  return lista

Explicación:
Este método divide en dos partes a la lista a ordenar, y va dejando en la primera mitad los elementos menores y en la otra los mayores, luego, se llama recursivamente con la primera mitad repitiendo el proceso sucesivamente, hasta volverlo a hacer con las segundas mitades.
Es sumamente rápido y es útil para ordenar listas con elementos muy dispersos, y funciona correctamente hasta con la inclusión de números negativos en el arreglo a ordenar. Ésta velocidad de operación se debe a que necesita de la ejecución de pocas operaciones para ordenar el arreglo.
Para dividir el arreglo en dos, utiliza un pivote quese puede elegir al azar, o simplemente el elemento que se encuentra en la mitad del mismo. La versión presentada corresponde a la elección del elemento del medio, ya que es la más eficiente y rápida de las dos versiones recursivas.

Recursos de Interés
Ordenamiento Quicksort (wikipedia)

Octubre 30, 2008 | Palabras Clave: algoritmo, ordenamiento, python, quicksort, rápido, recursivo | Categoría: Códigos | Commentarios (1)

El algoritmo de Ordenamiento por Inserción (también llamado Insertion Sort), se encarga de ir buscando los elementos en el orden correspondiente, para luego ir insertándolo en la posición que corresponda, según el valor del mismo. Una ordenación parecida es el ShellSort.
Hay dos versiones, iterativa y recursiva, expuestas a continuación:

Algoritmo de Ordenamiento por Inserción Iterativa en Python
En cada pasada, estable un elemento como punto comparativo, y de acuerdo a ese, se van insertando los demás en la posición correcta, para luego repetir el ciclo, hasta que la lista se encuentre ordenada. Recibe un sólo parámetro, que es la lista en cuestión:

#Algoritmo escrito por Melina VIdoni
#Forma no recursiva

def insercion (lista) :
  """Ordena la lista con el algoritmo InsertionSort
  o por Inserción, de forma no recursiva"""
  for i in range(1,len(lista)) :
    aux=lista[i]
    j=i
    while j>0 and aux<lista[j-1] :
      lista[j]=lista[j-1]
      j-=1
    lista[j]=aux
  return lista

Algoritmo de Ordenamiento por Inserción Recursiva en Python
La función se llama a sí misma con el largo-1, hasta encontrarse con la lista de un sólo elemento, en la cual llama a la subfunción insertar, donde realmente se produce la comparación de elementos, y el intercambio de los mismos. Luego, la función va volviendo en la cadena de llamados, hasta concluir. REcibe como argumento la lista en cuestión, y el largo-1 de la misma:

#Algoritmo escrito por Melina Vidoni
#Forma recursiva
#Ejemplo de llamada: insercionRec(nombre_lista,(len(nombre_lista)-1))

def insercionRec (lista, largo) :
  """Ordena la lista con algoritmo InsertionSort
  o por Inserción, de forma recursiva"""
  if (largo-1)>=0 :
    insercionRec(lista,largo-1)
    insertar(lista,largo)
  return lista

def insertar (lista, largo) :
  pivote=lista[largo]
  i=largo-1
  while i>=0 and lista[i]>pivote :
    lista[i+1]=lista[i]
    i-=1
  lista[i+1]=pivote

Recursos de Interés
Ordenamiento Insertion Sort (wikipedia)
“Algoritmos de Ordenación y Búsqueda”, de Sebastián Gurin

Octubre 30, 2008 | Palabras Clave: algoritmo, insercion, iterativa, ordenamiento, python, recursiva | Categoría: Códigos | Commentarios (1)

El algoritmo de Ordenamiento por Selección (o Selection Sort), se encarga de seleccionar el elemento más pequeño de la lista pasada como argumento, e insertarlo en la primer posición, para luego continuar con el elemento más pequeño de los elementos restantes.
Hay dos versiones, ambas expuestas a continuación: iterativa y recursiva:

Algoritmo de Ordenamiento por Selección Iterativa en Python
Ordena un vector de números reales o enteros. en cada pasada i, explora los elementos del arreglo, en busca del menor de ellos, para luego intercambiarlo por la posición lista[i]. Es el algoritmo de ordenación más fácil de codificar:

#Algoritmo escrito por Melina Vidoni
#Forma no recursiva

def seleccion (lista) :
  """Ordena la lista pasada como parámetro, con el algoritmo
  SelectionSort, o por Selección. Forma no recursiva"""
  for i in range(0, len(lista)-1) :
    indiceMenor=i
    for j in range(i+1, len(lista)) :
      if lista[j]<lista[indiceMenor] :
        indiceMenor=j
    if i!=indiceMenor :
      lista[i],lista[indiceMenor]=lista[indiceMenor],lista[i]
  return lista

Algoritmo de Ordenación por Selección Recursiva en Python
La forma recursiva de éste algoritmo, ordena de la misma forma que la versión iterativa, sólo que recorre una sóla vez la lista, y luego la función se llama a sí misma, con el resto de la lista que aún no ha sido ordenada. Por esto mismo, la función recibe como parámetros a la lista propiamente dicha, y un entero que es el indice inicial:

#Algoritmo Escrito por Melina Vidoni
#Forma recursiva
#tipo de llamada: seleccionRec(lista,0)

def seleccionRec (lista, indiceInicial) :
  """Ordena la lista pasada como parámentro con el algoritmo
  SelectionSort o por Seleción. Forma Recursiva"""
  if indiceInicial<(len(lista)-1) :
    indiceMenor=indiceInicial
    for i in range(indiceInicial+1,len(lista)) :
      if lista[i]<lista[indiceMenor] :
        indiceMenor=i
    lista[indiceInicial],lista[indiceMenor]=lista[indiceMenor],lista[indiceInicial]
    seleccionRec(lista,indiceInicial+1)
  return lista

Recursos de Interés
Ordenamiento SelectionSort (wikipedia)
Algoritmos de Ordenación (Sebastian Gurin)

Octubre 30, 2008 | Palabras Clave: algoritmo, iterativa, ordenamiento, python, recursiva, selección | Categoría: Códigos | Dejar un comentario