# -*- coding: utf-8 -*-

import math

def Buscar_Subcadena(patron, texto): #Si no encuentra el patron, retorna -1.
	match = -1
	for i in range(len(texto)):
		if texto[i]==patron[0]: #Verifica que un caracter del texto coincida con el primer caracter del patron.
			match=i
			for j in range(len(patron)): #Verifica coincidencia con el resto del patron.
				if texto[i+j]!= patron[j]:
					match=-1
					break
		if match > -1: #Si hay una coincidencia, deja de buscar.
			break
	return match #En caso de no encontrar coincidencia alguna, retorna -1.

def CribaEratostenes(n):
	criba=[False,False]+[True]*(n-1) #Inicializa una lista de booleanos con las 2 primeras entradas falsas
	i = 2
	while i <= math.sqrt(n): #Recorre la lista hasta la raiz cuadrada de n
		j=2
		if criba[i]== True: #Recorre todos los multiplos de un primo, haciendolos falsos.
			while i*j <= n:
				criba[i*j]=False
				j+=1
		i+=1
	prime=[] #Esta es la lista de numeros primos
	for k in range(len(criba)): #Agrega a la lista todos indices de criba[] que sean verdaderos
		if criba[k]==True:
			prime.append(k)
	return prime
	
def Goldbach(n):
	if n%2 != 0 or n<=2: #Si n no es par o es menor a 2 imprime un mensaje de error y retorna nan (Not A Number)
		print "El numero introducido no es par o es menor a 2"
		return float('nan')
	else:
		primes=CribaEratostenes(n) #Crea una lista con todos los primos menores a n
		j=len(primes)-1
		for i in range(len(primes)): #Recorre la lista de primos buscando algun par de primos cuya suma sea n.
			while primes[j]+primes[i]>= n:
				if primes[j]+primes[i]==n:
					return [primes[i], primes[j]]
				else:
					j-=1

def fsign(f): #Retorna 1 o -1 de acuerdo al signo f
	if f == 0:
		return 0
	elif f < 0:
		return -1
	else:
		return 1

def HornerIt(c, x): #Implementacion iterativa del metodo de Horner
	f=c[0]
	for i in range(len(c)-1):
		f=c[i+1]+x*f
	return f

def ReglaFalsa(a,b,f,e): #Implementacion de regla falsa
	if fsign(HornerIt(f, a))*fsign(HornerIt(f, b)) > 0:
		print "Los signos de f(a) y f(b) son iguales"
		return float('nan')
	c = b - float(HornerIt(f, b)*(b-a))/float(HornerIt(f,b)-HornerIt(f,a)) #Esta linea difiere de la anterior implementacion de biseccion
	j=0
	while ((HornerIt(f, c)!= 0 and abs(b-a)/2 > e/2) or abs(HornerIt(f, c)) > e/2) and j<1000*(len(f)+1): #Se divide el valor de e (tolerancia) entre 2 para obtener mayor precision
		if fsign(HornerIt(f, a))*fsign(HornerIt(f, c)) < 0:
			b = c
		else:
			a = c
		c = b - float(HornerIt(f, b)*(b-a))/float(HornerIt(f,b)-HornerIt(f,a)) #Esta linea difiere de la anterior implementacion de biseccion
		j+=1
	return c

def Ordenamiento_ParImpar(L):
	ordenado = False
	while ordenado == False:
		ordenado = True
		i=0
		while i < len(L)-1: #Itera sobre las posiciones pares-impares y hace el cambio de ser necesario
			if L[i] > L[i+1]:
				ordenado = False #Si se hizo algun cambio, la lista no esta ordenada aun
				L[i], L[i+1] = L[i+1], L[i]
			i+=2
		i=1
		while i < len(L)-1: #Itera sobre las posiciones impares-pares y hace el cambio de ser necesario
			if L[i] > L[i+1]:
				ordenado = False #Si se hizo algun cambio, la lista no esta ordenada aun
				L[i], L[i+1] = L[i+1], L[i]
			i+=2
	return L

def ExpIter(a,b): 
	if b < 0: #Si b es menor a 0, imprime un mensaje de error y retorna nan
		print "b debe ser positivo"
		return float("nan")
	if a == 0 and b !=0: #Si a es 0 y b es distinto de 0, retorna 0 inmediatamente
		return 0
	if a == 0 and b == 0: #Si a y b son iguales a 0, imprime un mensaje de error y retorna nan
		print "0**0 no esta definido"
		return float("nan")
	ans = 1
	while b !=0: #Este ciclo combierte b a binario y multiplica las potencias de a
		if b%2 != 0:
			b -= 1
			ans *= a
		a*=a
		b/=2
	return ans

#Note que en el metodo anterior no habia necesidad de convertir b a binario y luego calcular la potencia, 
#ambas cosas se pueden hacer en un mismo ciclo.

def Producto_Matrices(A,B):
	for i in range(len(A)-1): #Verifica si A es una matriz y en caso se no serlo imprime un mensaje de error y retorna nan
		if len(A[i])!=len(A[i+1]):
			print "A no es una matriz"
			return float('nan')
	for i in range(len(B)-1): #Verifica si B es una matriz y en caso se no serlo imprime un mensaje de error y retorna nan
		if len(B[i])!=len(B[i+1]):
			print "B no es una matriz"
			return float('nan')
	if len(A[0])!=len(B): #Verifica que las dimensiones de A y B sean adecuadas y en caso se no serlo imprime un mensaje de error y retorna nan
		print "Las dimensiones de A y B no son adecuadas"
		return float('nan')
	C=[] #Esta será la matriz producto
	for i in range(len(A)): #Recorre las filas de A
		D=[] #Arreglo auxiliar
		for j in range(len(B[0])): #Recorre las columnas de B
			d=0 #Variable auxiliar
			for k in range(len(B)): #Recorre una fila A y una columna de B
				d += A[i][k]*B[k][j] #Calcula el elemnto que estara en la posicion C[i][j]
			D.append(d)
		C.append(D)
	return C