938.sagews

def getProximosEstados(lista,estadosAnteriores): #get next 'states' of the problem in the form (a,b,c) 
    posibles = []
    posible = copy(lista)
    
    if (posible[0]<10):    #si cabe mas en 'a'
        # tratar de pasar de b -> a
        posible[0] += posible[1];
        if (posible[0]>10): #se lleno 'a' antes de vaciar 'c'?
            posible[1] = posible[0] - 10
            posible[0] = 10
        else:             # se vacio b
            posible[1] = 0
            
        #agregarlo si no existe
        if (estadosAnteriores.count(posible)==0):
            posibles.append(posible)
        
        # tratar de pasar de c -> a
        posible = copy(lista)
        posible[0] += posible[2];
        if (posible[0]>10): #se lleno 'a' antes de vaciar 'c'?
            posible[2] = posible[0] - 10
            posible[0] = 10
        else:             # se vacio b
            posible[2] = 0
        
        if (estadosAnteriores.count(posible)==0):
            posibles.append(posible)
    
    posible = copy(lista)
    #si cabe mas en 'b'
    if (posible[1]<7):
        #print 'cabe en b'
        # tratar de pasar de a -> b
        posible[1] += posible[0];
        if (posible[1]>7): #se lleno 'b' antes de vaciar 'a'?
            posible[0] = posible[1] - 7
            posible[1] = 7
        else:             # se vacio a
            posible[0] = 0

        if (estadosAnteriores.count(posible)==0):
            posibles.append(posible)
        
        posible = copy(lista)
        # tratar de pasar de c -> b
        posible[1] += posible[2];
        if (posible[1]>7): #se lleno 'b' antes de vaciar 'a'?
            posible[2] = posible[1] - 7
            posible[1] = 7
        else:             # se vacio a
            posible[2] = 0
        
        if (estadosAnteriores.count(posible)==0):
            posibles.append(posible)
        
    posible = copy(lista)
    #si cabe mas en 'c'
    if (posible[2]<4):
        #print 'cabe en c'
        # tratar de pasar de a -> c
        posible[2] += posible[0];
        if (posible[2]>4): #se lleno 'c' antes de vaciar 'a'?
            posible[0] = posible[2] - 4
            posible[2] = 4
        else:             # se vacio a
            posible[0] = 0
        
        if (estadosAnteriores.count(posible)==0):
            posibles.append(posible)
        
        posible = copy(lista)
        # tratar de pasar de b -> c
        posible[2] += posible[1];
        if (posible[2]>4): #se lleno 'c' antes de vaciar 'b'?
            posible[1] = posible[2] - 4
            posible[2] = 4
        else:             # se vacio a
            posible[2] = 0
    
        if (estadosAnteriores.count(posible)==0):
            posibles.append(posible)
    #print 'devolvio posibles: ', posibles
    return posibles

def existeUnoCon2Litros(lista): # is there any container with 2 literS?
    if (type(lista)==list):
        return lista.count(2)
    else:
        return 0

def encontrar(estados,stackTrace): #find the answer.
    encontro = False

    for estado in estados:
        if (not encontro):        
            if (existeUnoCon2Litros(estado)>0):
                global encontro
                encontro = True;
                stackTrace.append(estado)
                print 'encontro, stack trace: ', stackTrace
                return encontro;
                break;
             
            if (not encontro):
                if (type(estado)==list):
                    # si no existe en el stack trace, mandarlo
                    if (stackTrace.count(estado)==0):
                        stackTrace.append(estado)
                        #print 'mando estado i: ',estado
                        encontrar(getProximosEstados(estado,estados),stackTrace)
                else:
                    #print 'mando estado: ',estados
                    stackTrace.append(estados)
                    encontrar(getProximosEstados(estados,[]),stackTrace)
                   
    return encontro

print encontrar ([0,7,4],[])

encontro, stack trace: [[0, 7, 4], [7, 0, 4], [10, 0, 1], [3, 7, 1], [4, 7, 0], [10, 1, 0], [6, 1, 4], [6, 5, 0], [2, 5, 4]] True

# Problema 5

def FloydWarshal(M):
    if M.is_square():
        n = len(M.columns())
        for k in range (0,n):
            for i in range (0,n):
                for j in range (0,n):
                    fila = copy(M[i])
                    fila[j] = min(M[i][j] , M[i][k] + M[k][j])
                    M[i] = fila
                    #M[i][j] = min (M[i][j] , 40)
        return M
    else:
        return False

M5 = matrix([[0,50,10000,40,25,10],[50,0,15,20,10000,25],[10000,15,0,10,20,10000],[40,20,10,0,10,25],[25,10000,20,10,0,55],[10,25,10000,25,55,0]]);

print latex(M5)

print M5 ,'\n'

print FloydWarshal(M5)

\left(\begin{array}{rrrrrr} 0 & 50 & 10000 & 40 & 25 & 10 \\ 50 & 0 & 15 & 20 & 10000 & 25 \\ 10000 & 15 & 0 & 10 & 20 & 10000 \\ 40 & 20 & 10 & 0 & 10 & 25 \\ 25 & 10000 & 20 & 10 & 0 & 55 \\ 10 & 25 & 10000 & 25 & 55 & 0 \end{array}\right) [ 0 50 10000 40 25 10] [ 50 0 15 20 10000 25] [10000 15 0 10 20 10000] [ 40 20 10 0 10 25] [ 25 10000 20 10 0 55] [ 10 25 10000 25 55 0] [ 0 35 45 35 25 10] [35 0 15 20 30 25] [45 15 0 10 20 35] [35 20 10 0 10 25] [25 30 20 10 0 35] [10 25 35 25 35 0]

latex(M5)

\left(\begin{array}{rrrrrr} 0 & 35 & 45 & 35 & 25 & 10 \\ 35 & 0 & 15 & 20 & 30 & 25 \\ 45 & 15 & 0 & 10 & 20 & 35 \\ 35 & 20 & 10 & 0 & 10 & 25 \\ 25 & 30 & 20 & 10 & 0 & 35 \\ 10 & 25 & 35 & 25 & 35 & 0 \end{array}\right)