Programación de restricciones con python-constraint

    Introducción

    Lo primero que tenemos que entender al tratar con la programación con restricciones es que la forma de pensar es muy diferente de nuestra forma habitual de pensar cuando nos sentamos a escribir código.

    La programación de restricciones es un ejemplo del paradigma de programación declarativa , a diferencia del paradigma imperativo habitual que usamos la mayor parte del tiempo.

    ¿Qué es un paradigma de programación?

    Un paradigma significa “un ejemplo” o “un patrón” de algo. Un paradigma de programación se describe a menudo como una “forma de pensar” o “forma de programar”. Los ejemplos más comunes incluyen programación procedimental (por ejemplo, C), programación orientada a objetos (por ejemplo, Java) y programación funcional (por ejemplo, Haskell).

    La mayoría de los paradigmas de programación se pueden clasificar como miembros del grupo de paradigmas imperativos o declarativos.

    ¿Cuál es la diferencia entre programación imperativa y declarativa?

    • La programación imperativa , en pocas palabras, se basa en que el desarrollador describe la solución / algoritmo para lograr un objetivo (algún tipo de resultado). Esto sucede al cambiar el estado del programa a través de declaraciones de asignación, mientras se ejecutan las instrucciones paso a paso. Por lo tanto, hace una gran diferencia el orden en que se escriben las instrucciones.
    • La programación declarativa hace lo contrario: no escribimos los pasos sobre cómo lograr un objetivo, describimos el objetivo y la computadora nos da una solución. Un ejemplo común con el que debería estar familiarizado es SQL. ¿Le dice a la computadora cómo darle los resultados que necesita? No, usted describe lo que necesita; necesita los valores de alguna columna, de alguna tabla, donde se cumplen algunas condiciones.

    Instalación del módulo de restricción de python

    En este artículo trabajaremos con un módulo llamado python-constraint(Nota: hay un módulo llamado “restricción” para Python, eso no es lo que queremos), que tiene como objetivo llevar la idea de programación de restricciones a Python.

    Para instalar este módulo, abra el terminal y ejecute:

    $ pip install python-constraint
    

    Conceptos básicos del uso de restricción de python

    Este es el esqueleto generalizado de los programas escritos usando este módulo (Nota: usamos import constrainty no import python-constraint)

    • importar constraint
    • definir una variable como nuestro problema
    • agregar variables y sus respectivos intervalos a nuestro problema
    • agregar restricciones integradas / personalizadas a nuestro problema
    • buscar las soluciones
    • revise las soluciones para encontrar las que necesitamos

    Como se mencionó anteriormente, la programación de restricciones es una forma de programación declarativa. El orden de las declaraciones no importa, siempre y cuando todo esté ahí al final. Por lo general, se usa para resolver problemas como este:

    Ejemplo A
    Find all (x,y) where x ∈ {1,2,3} and 0 <= y < 10, and x + y >= 5
    

    Si nos fijamos en esta frase, podemos ver una serie de condiciones (llamémosles limitaciones) que xy ytienen que cumplir.

    Por ejemplo, xestá “restringido” a los valores 1,2,3, ydebe ser menor que 10y su suma debe ser mayor o igual que 5. Esto se hace en unas pocas líneas de código y en unos minutos mediante la programación de restricciones.

    Mirando el problema anterior probablemente pensaste “¿Y qué? Puedo hacer esto con 2 ciclos for y media taza de café en Python en menos de 10 minutos”.

    Tiene toda la razón, aunque a través de este ejemplo podemos tener una idea de cómo se ve la programación de restricciones:

    import constraint
    
    problem = constraint.Problem()
    
    problem.addVariable('x', [1,2,3])
    problem.addVariable('y', range(10))
    
    def our_constraint(x, y):
        if x + y >= 5:
            return True
    
    problem.addConstraint(our_constraint, ['x','y'])
    
    solutions = problem.getSolutions()
    
    # Easier way to print and see all solutions
    # for solution in solutions:
    #    print(solution)
    
    # Prettier way to print and see all solutions
    length = len(solutions)
    print("(x,y) ∈ {", end="")
    for index, solution in enumerate(solutions):
        if index == length - 1:
            print("({},{})".format(solution['x'], solution['y']), end="")
        else:
            print("({},{}),".format(solution['x'], solution['y']), end="")
    print("}")
    

    Salida:

    (x,y) ∈ {(3,9),(3,8),(3,7),(3,6),(3,5),(3,4),(3,3),(3,2),(2,9),(2,8),(2,7),(2,6),(2,5),(2,4),(2,3),(1,9),(1,8),(1,7),(1,6),(1,5),(1,4)}
    

    Repasemos este programa paso a paso. Teníamos dos variables xy y. Los hemos agregado a nuestro problema con sus respectivos rangos aceptables.

    Esas dos líneas significan lo siguiente:

    I'm adding a variable x that can only have values [1,2,3], and a variable y that can only have values [0,1,2,..,9]
    

    A continuación, definimos nuestra restricción personalizada (es decir, x + y >= 5). Se supone que los métodos de restricción regresan Truesi una combinación de valores de variable es aceptable y Nonesi no lo es.

    En nuestro our_constraint()método, decimos “La única situación aceptable es cuando x + y >= 5, de lo contrario, no incluya esos valores de (x,y)en las soluciones finales”.

    Después de definir nuestra restricción, tenemos que agregarla a nuestro problema. La estructura del .addConstraint()método es:

    addConstraint(which_constraint, list_of_variable_order)
    

    Nota : en nuestro caso, no importa si escribimos [x,y]o [y,x]como nuestro segundo parámetro, pero el orden sí importa en la mayoría de los casos.

    Después de eso, obtuvimos las soluciones con problem.getSolutions()(devuelve una lista de todas las combinaciones de valores de variables que satisfacen todas las condiciones) y las iteramos.

    Nota : Si, por ejemplo, quisiéramos buscar solo combinaciones donde x /= y, agregaríamos una restricción incorporada antes de buscar las soluciones:

    problem.addConstraint(constraint.AllDifferentConstraint())
    

    Puede encontrar la lista de todas las restricciones integradas aquí. Eso es casi todo lo que necesitas saber para poder realizar cualquier tarea de este tipo.

    Ejemplos de calentamiento

    Ejemplo B

    Aquí hay un tipo de programación de restricción de problemas que es divertido de usar, llamado rompecabezas criptográfico . En la siguiente forma de rompecabezas criptográfico, cada carácter representa un dígito diferente (los caracteres principales no pueden ser 0):

    TWO + TWO = FOUR
    

    Piense en cómo resolvería esto usando Python normal. De hecho, le animo a buscar la solución para este problema que utiliza programación imperativa.

    También debería darte todo el conocimiento que necesitas para resolver el Ejemplo D por tu cuenta.

    Tenga en cuenta que ‘T’ y ‘F’ no pueden ser cero, ya que son los caracteres principales, es decir, el primer dígito de un número.

    import constraint
    
    problem = constraint.Problem()
    
    # We're using .addVariables() this time since we're adding
    # multiple variables that have the same interval.
    # Since Strings are arrays of characters we can write
    # "TF" instead of ['T','F'].
    problem.addVariables("TF", range(1, 10))
    problem.addVariables("WOUR", range(10))
    
    # Telling Python that we need TWO + TWO = FOUR
    def sum_constraint(t, w, o, f, u, r):
        if 2*(t*100 + w*10 + o) == f*1000 + o*100 + u*10 + r:
            return True
    
    # Adding our custom constraint. The
    # order of variables is important!
    problem.addConstraint(sum_constraint, "TWOFUR")
    
    # All the characters must represent different digits,
    # there's a built-in constraint for that
    problem.addConstraint(constraint.AllDifferentConstraint())
    
    solutions = problem.getSolutions()
    print("Number of solutions found: {}n".format(len(solutions)))
    
    # .getSolutions() returns a dictionary
    for s in solutions:
        print("T = {}, W = {}, O = {}, F = {}, U = {}, R = {}"
            .format(s['T'], s['W'], s['O'], s['F'], s['U'], s['R']))
    

    Al ejecutar este código, nos saludan las posibles soluciones:

    Number of solutions found: 7
    
    T = 7, W = 6, O = 5, F = 1, U = 3, R = 0
    T = 7, W = 3, O = 4, F = 1, U = 6, R = 8
    T = 8, W = 6, O = 7, F = 1, U = 3, R = 4
    T = 8, W = 4, O = 6, F = 1, U = 9, R = 2
    T = 8, W = 3, O = 6, F = 1, U = 7, R = 2
    T = 9, W = 2, O = 8, F = 1, U = 5, R = 6
    T = 9, W = 3, O = 8, F = 1, U = 7, R = 6
    
    Ejemplo C
    You recently got a job as a cashier. You're trying to convince your friend that it's hard work, there are just SO many ways to give someone their change back! Your "friend" shakes his head, obviously not believing you. He says "It can't be that bad. How many ways can there POSSIBLY be to give someone their change back, for like 60 cents?".
    
    Your response is, of course, to sit and quickly write a program that would prove your point. You have a decent amount of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), and a lot of kinda suspicious coins worth 3 cents each. Calculate in how many ways you can return change for 60 cents.
    

    Nota : El orden en el que se imprime nuestro resultado no es necesariamente el mismo que el orden en el que agregamos las variables. Es decir, si el resultado es ( a,b,c,d,e) no sabemos si tenemos amonedas de 1 céntimo, bde 3 céntimos, etc.

    Entonces, deberíamos imprimir explícitamente la variable y su valor. Una consecuencia de esto es que no podemos utilizar el built-in .ExactSumConstraint()en su forma de dos parámetros, ExactSumConstraint(50,[1,3,5,10,20]).

    El segundo parámetro aquí es el “peso” de cada variable (cuántas veces debe multiplicarse), y no tenemos garantía de cuál de nuestras variables tendrá qué peso.

    Es un error común suponer que las ponderaciones se asignarán a las variables en el orden en que se agregaron, en su lugar usamos la forma de tres parámetros de esta restricción incorporada en el siguiente código:

    import constraint
    
    problem = constraint.Problem()
    
    # The maximum amount of each coin type can't be more than 60
    # (coin_value*num_of_coints) <= 60
    
    problem.addVariable("1 cent", range(61))
    problem.addVariable("3 cent", range(21))
    problem.addVariable("5 cent", range(13))
    problem.addVariable("10 cent", range(7))
    problem.addVariable("20 cent", range(4))
    
    problem.addConstraint(
        constraint.ExactSumConstraint(60,[1,3,5,10,20]),
        ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"]
    )
    # Where we explicitly give the order in which the weights should be allocated
    
    # We could've used a custom constraint instead, BUT in this case the program will
    # run slightly slower - this is because built-in functions are optimized and
    # they find the solution more quickly
    # def custom_constraint(a, b, c, d, e):
    #     if a + 3*b + 5*c + 10*d + 20*e == 60:
    #         return True
    #     problem.addConstraint(o, ["1 cent", "3 cent", "5 cent","10 cent", "20 cent"])
    
    
    # A function that prints out the amount of each coin
    # in every acceptable combination
    def print_solutions(solutions):
        for s in sols:
            print("---")
            print("""
            1 cent: {0:d}
            3 cent: {1:d}
            5 cent: {2:d}
            10 cent: {3:d}
            20 cent: {4:d}""".format(s["1 cent"], s["3 cent"], s["5 cent"], s["10 cent"], s["20 cent"]))
            # If we wanted to we could check whether the sum was really 60
            # print("Total:", s["1 cent"] + s["3 cent"]*3 + s["5 cent"]*5 + s["10 cent"]*10 + s["20 cent"]*20)
            # print("---")
    
    solutions = problem.getSolutions()
    #print_solutions(solutions)
    print("Total number of ways: {}".format(len(solutions)))
    

    Ejecutar este fragmento de código producirá:

    Total number of ways: 535
    
    Ejemplo D
    CRASH + ERROR + REBOOT = HACKER
    

    Los ejemplos B y D son casi idénticos cuando se usan restricciones, solo unas pocas variables hacia arriba y hacia abajo y restricciones más detalladas. Eso es algo bueno de la programación de restricciones: buena escalabilidad, al menos cuando se trata de tiempo dedicado a la codificación. Solo hay una solución para este rompecabezas y es A = 3 B = 7 C = 8 E = 2 H = 6 K = 0 O = 1 R = 5 S = 9 T = 4.

    Ambos tipos de tareas (especialmente la cripto-taritmética) se utilizan más por diversión y para una demostración sencilla de cómo funciona la programación con restricciones, pero hay ciertas situaciones en las que la programación con restricciones tiene un valor práctico.

    Podemos calcular el número mínimo de emisoras para cubrir un área determinada, o averiguar cómo configurar los semáforos para que el flujo de tráfico sea óptimo. En términos generales, las restricciones se utilizan cuando hay muchas combinaciones posibles.

    Estos ejemplos son demasiado complejos para el alcance de este artículo, pero sirven para mostrar que la programación de restricciones puede tener usos en el mundo real.

    Ejemplos más difíciles

    Ejemplo E
    You wish to pack chocolates for your mother. Luckily you work in a chocolate factory that has a lot of leftover chocolate. You have a few chocolate types at your disposal.
    
    Your goal is to bring her the sweetest chocolate possible, that you can pack in your bag and sneak through security, and that wouldn't pass a certain net value for which you'd go to prison if you got caught.
    
    Security most likely won't get suspicious if you bring less than 3kg. You can fit 1 dm^3 of chocolate in your bag. You won't go to jail if you steal less than $300 worth of chocolate.
    

    Chocolate Nombre Peso (g) Dimensiones (cm) Dulzura Valor ($)

    Chocolate A1008 × 2.5 × 0.5208
    Chocolate B457 × 2 × 0.5166.8
    Chocolate C103 × 2 × 0.594
    Chocolate D253 × 3 × 0.573

    Ahora arremangémonos y comencemos. No debería ser demasiado difícil si ha entendido los ejemplos anteriores.

    Primero averiguaremos cuánto de cada chocolate podemos tener si SOLAMENTE trajimos ese tipo, para que podamos tener el límite superior de nuestros intervalos. Por ejemplo, para el Chocolate A, según el peso podemos traer como máximo 30 barras, según el valor podemos aportar 37 como máximo, y según el volumen podemos aportar 100.

    El menor de estos números es 30, y ese es el número máximo de Chocolate A que podemos traer. Los mismos pasos nos dan la cantidad máxima del resto, B -> 44, C -> 75, D -> 100 .

    import constraint
    
    problem = constraint.Problem()
    
    problem.addVariable('A', range(31))
    problem.addVariable('B', range(45))
    problem.addVariable('C', range(76))
    problem.addVariable('D', range(101))
    
    # We have 3kg = 3,000g available
    def weight_constraint(a, b, c, d):
        if (a*100 + b*45 + c*10 + d*25) <= 3000:
            return True
    
    # We have 1dm^3 = 1,000cm^3 available
    def volume_constraint(a, b, c, d):
        if (a*8*2.5*0.5 + b*6*2*0.5 * c*2*2*0.5 + d*3*3*0.5) <= 1000:
            return True
    
    # We can't exceed $300
    def value_constraint(a, b, c, d):
        if (a*8 + b*6.8 + c*4 + d*3) < 300:
            return True
    
    problem.addConstraint(weight_constraint, "ABCD")
    problem.addConstraint(volume_constraint, "ABCD")
    problem.addConstraint(value_constraint, "ABCD")
    
    maximum_sweetness = 0
    solution_found = {}
    solutions = problem.getSolutions()
    
    for s in solutions:
        current_sweetness = s['A']*10 + s['B']*8 + s['C']*4.5 + s['D']*3.5
        if current_sweetness > maximum_sweetness:
            maximum_sweetness = current_sweetness
            solution_found = s
    
    print("""
    The maximum sweetness we can bring is: {}
    We'll bring:
    {} A Chocolates,
    {} B Chocolates,
    {} C Chocolates,
    {} D Chocolates
    """.format(maximum_sweetness, solution_found['A'], solution_found['B'], solution_found['C'], solution_found['D']))
    

    Ejecutar este fragmento de código producirá:

    The maximum sweetness we can bring is: 365.0
    We'll bring:
    27 A Chocolates,
    2 B Chocolates,
    16 C Chocolates,
    2 D Chocolates
    

    Nota : Podemos almacenar toda la información relevante para cada tipo de chocolate en un diccionario, por ejemplo weight_dictionary = {'A' : 100, 'B' : 45, 'C' : 10, 'D' : 25}, y acceder a valores de esa manera, en lugar de codificarlos en funciones. Sin embargo, en aras de la legibilidad, la longitud del código y el enfoque en las cosas más importantes de este tutorial, prefiero codificar las funciones de restricción en sí mismas.

    Nota : Probablemente notó que tomó un tiempo calcular este resultado, esto es un inconveniente de la programación de restricciones.

    Ejemplo F

    Ahora, para algo más divertido, hagamos un solucionador de sudoku (clásico 9×9). Leeremos el rompecabezas de un archivo JSON y encontraremos todas las soluciones para ese rompecabezas en particular (asumiendo que el rompecabezas tiene una solución).

    Si olvidó las reglas para resolver sudoku:

    • Las celdas pueden tener valores del 1 al 9
    • Todas las celdas de la misma fila deben tener valores diferentes
    • Todas las celdas de la misma columna deben tener valores diferentes
    • Todas las celdas de un cuadrado de 3×3 (nueve en total) deben tener valores diferentes

    Uno de los problemas de este programa es: ¿cómo almacenamos los valores? No podemos simplemente agregar una matriz como variable a nuestro problema y hacer que Python descubra mágicamente lo que queremos.

    Usaremos un sistema en el que trataremos los números como nombres de variables (eso está permitido) y pretendemos que tenemos una matriz. Los índices parten de (1,1) en lugar del habitual (0,0). Usando eso, accederemos a los elementos del tablero de una manera a la que estamos acostumbrados.

    A continuación, debemos hacer la parte fácil de decirle a Python que todas esas celdas pueden tener valores entre 1 y 9.

    Luego notamos que las celdas en la misma fila tienen el mismo primer índice, por ejemplo (1, x) para la primera fila. Podemos recorrer fácilmente todas las filas y decir que todas las celdas deben contener valores diferentes. Lo mismo ocurre con las columnas. El resto se comprende más fácilmente al mirar el código.

    Echemos un vistazo a un archivo JSON de ejemplo:

    [[0, 9, 0, 7, 0, 0, 8, 6, 0],
     [0, 3, 1, 0, 0, 5, 0, 2, 0],
     [8, 0, 6, 0, 0, 0, 0, 0, 0],
     [0, 0, 7, 0, 5, 0, 0, 0, 6],
     [0, 0, 0, 3, 0, 7, 0, 0, 0],
     [5, 0, 0, 0, 1, 0, 7, 0, 0],
     [0, 0, 0, 0, 0, 0, 1, 0, 9],
     [0, 2, 0, 6, 0, 0, 0, 5, 0],
     [0, 5, 4, 0, 0, 8, 0, 7, 0]]
    
    # 1 - - - - - - - - -
    # 2 - - - - - - - - -
    # 3 - - - - - - - - -
    # 4 - - - - - - - - -
    # 5 - - - - - - - - -
    # 6 - - - - - - - - -
    # 7 - - - - - - - - -
    # 8 - - - - - - - - -
    # 9 - - - - - - - - -
    #   1 2 3 4 5 6 7 8 9
    
    import constraint
    import json
    
    problem = constraint.Problem()
    
    # We're letting VARIABLES 11 through 99 have an interval of [1..9]
    for i in range(1, 10):
        problem.addVariables(range(i * 10 + 1, i * 10 + 10), range(1, 10))
    
    # We're adding the constraint that all values in a row must be different
    # 11 through 19 must be different, 21 through 29 must be all different,...
    for i in range(1, 10):
        problem.addConstraint(constraint.AllDifferentConstraint(), range(i * 10 + 1, i * 10 + 10))
    
    # Also all values in a column must be different
    # 11,21,31...91 must be different, also 12,22,32...92 must be different,...
    for i in range(1, 10):
        problem.addConstraint(constraint.AllDifferentConstraint(), range(10 + i, 100 + i, 10))
    
    # The last rule in a sudoku 9x9 puzzle is that those nine 3x3 squares must have all different values,
    # we start off by noting that each square "starts" at row indices 1, 4, 7
    for i in [1,4,7]:
        # Then we note that it's the same for columns, the squares start at indices 1, 4, 7 as well
        # basically one square starts at 11, the other at 14, another at 41, etc
        for j in [1,4,7]:
            square = [10*i+j,10*i+j+1,10*i+j+2,10*(i+1)+j,10*(i+1)+j+1,10*(i+1)+j+2,10*(i+2)+j,10*(i+2)+j+1,10*(i+2)+j+2]
            # As an example, for i = 1 and j = 1 (bottom left square), the cells 11,12,13,
            # 21,22,23, 31,32,33 have to be all different
            problem.addConstraint(constraint.AllDifferentConstraint(), square)
    
    file_name = input("Enter the name of the .json file containing the sudoku puzzle: ")
    try:
        f = open(file_name, "r")
        board = json.load(f)
        f.close()
    except IOError:
        print ("Couldn't open file.")
        sys.exit()
    
    # We're adding a constraint for each number on the board (0 is an "empty" cell),
    # Since they're already solved, we don't need to solve them
    for i in range(9):
        for j in range(9):
            if board[i][j] != 0:
                def c(variable_value, value_in_table = board[i][j]):
                    if variable_value == value_in_table:
                        return True
    
                # Basically we're making sure that our program doesn't change the values already on the board
                # By telling it that the values NEED to equal the corresponding ones at the base board
                problem.addConstraint(c, [((i+1)*10 + (j+1))])
    
    solutions = problem.getSolutions()
    
    for s in solutions:
        print("==================")
        for i in range(1,10):
            print("|", end='')
            for j in range(1,10):
                if j%3 == 0:
                    print(str(s[i*10+j])+" | ", end='')
                else:
                    print(str(s[i*10+j]), end='')
            print("")
            if i%3 == 0 and i!=9:
                print("------------------")
        print("==================")
    
    if len(solutions) == 0:
        print("No solutions found.")
    

    Salida (cuando usamos nuestro archivo JSON de ejemplo como entrada):

    ==================
    |295 | 743 | 861 |
    |431 | 865 | 927 |
    |876 | 192 | 345 |
    ------------------
    |387 | 459 | 216 |
    |612 | 387 | 594 |
    |549 | 216 | 783 |
    ------------------
    |768 | 524 | 139 |
    |923 | 671 | 458 |
    |154 | 938 | 672 |
    ==================
    ==================
    |295 | 743 | 861 |
    |431 | 865 | 927 |
    |876 | 192 | 345 |
    ------------------
    |387 | 459 | 216 |
    |612 | 387 | 594 |
    |549 | 216 | 738 |
    ------------------
    |763 | 524 | 189 |
    |928 | 671 | 453 |
    |154 | 938 | 672 |
    ==================
    ==================
    |295 | 743 | 861 |
    |431 | 865 | 927 |
    |876 | 192 | 543 |
    ------------------
    |387 | 459 | 216 |
    |612 | 387 | 495 |
    |549 | 216 | 738 |
    ------------------
    |763 | 524 | 189 |
    |928 | 671 | 354 |
    |154 | 938 | 672 |
    ==================
    

    Nota : Es muy fácil pasar por alto la parte del código que se asegura de que no toquemos los valores que ya están en el rompecabezas.

    Si intentáramos ejecutar el código sin esa parte, el programa intentaría crear TODOS LOS PUZZLES DE SUDOKU IMAGINABLES. Que bien podría ser un bucle sin fin.

    Conclusión e inconvenientes

    Tan divertida y diferente como es la programación de restricciones, ciertamente tiene sus inconvenientes. Cada problema resuelto mediante la programación de restricciones se puede escribir en estilo imperativo con un tiempo de ejecución igual o (como en la mayoría de los casos) mejor.

    Es natural que el desarrollador comprenda el problema mejor de lo que puede describirlo python-constraint. Una nota muy importante a hacer es que la programación de restricciones puede, en algunas situaciones, ahorrar horas y horas de tiempo de desarrollo a cambio de un tiempo de ejecución ligeramente peor.

    Recientemente tuve un ejemplo de esto en la vida real. Una amiga mía, alguien que se enteró de la existencia de Python unos meses antes, necesitaba resolver un problema para un proyecto de investigación de química física en el que estaba trabajando.

    Ese amigo necesitaba que se resolviera el siguiente problema:

    Generate all combinations (that have a length equal to the number of keys) of values stored in a dictionary (the order of output doesn't matter). The dictionary is {String : List_of_Strings}. In such a way that every combination has exactly one value from the List_of_Strings of a key.
    
    You don't know the number of keys in the dictionary in advance, nor do you know how long a List_of_String is, every List_of_String can be of different length. I.e. the dictionary is dynamically generated via user input.
    
    Example input: dictionary = {"A" : [1,2], "B" -> [4], "C" -> [5,6,7], "D" -> [8,9]}
    Example output: (1,4,5,8), (1,4,5,8), (1,4,6,8), (1,4,6,9), (1,4,7,8)....
    

    Intente pensar cómo resolvería esto usando programación imperativa.

    Ni siquiera se me ocurrió una idea de una buena solución en imperativo. Al menos no en los 5 minutos que me tomó resolver su problema en la programación de restricciones, literalmente en unas pocas líneas de código.

    import constraint
    
    # input example
    generated_dictionary = {'A' : [1,2], 'B' : [4], 'C' : [5,6,7], 'D' : [8,9]}
    
    problem = constraint.Problem()
    
    for key, value in generated_dictionary.items():
        problem.addVariable(key, value)
    
    solutions = problem.getSolutions()
    
    for solution in solutions:
        print(solution)
    

    Eso es. Simplemente no agregamos ninguna restricción y el programa generó todas las combinaciones aceptables para nosotros. En su caso, la mínima diferencia en el tiempo de ejecución de este programa no importa ni remotamente tanto como qué tan rápido fue escrito y qué tan legible es.

    Una cosa más a tener en cuenta es que python-constraintpuede hacer más que simplemente probar si una combinación se ajusta a todas las restricciones sin pensar.

    Se implementan capacidades de retroceso (y retroceso recursivo), así como también un solucionador de problemas basado en la teoría de conflictos mínimos. Estos se pueden pasar como un argumento al .Problem()método, por ejemplo .Problem(BacktrackingSolver), el resto se hace de la misma manera que en los ejemplos anteriores.

    Lista de restricciones integradas

    Nombre de la restricciónDescripción de la restricciónTodoDiferenteConstraintAllEqualConstraintMaxSumConstraintExactSumConstraintMinSumConstraintInSetConstraintNotInSetConstraintSomeInSetConstraintSomeNotInSetConstraint

    Hace que los valores de todas las variables dadas sean diferentes
    Hace que los valores de todas las variables dadas sean iguales
    Hace cumplir que los valores de las variables dadas suman una cantidad determinada
    Hace que los valores de las variables dadas sumen exactamente una cantidad determinada
    Restricción que impone que los valores de las variables dadas sumen al menos una cantidad determinada
    Restricción que impone que los valores de las variables dadas estén presentes en el conjunto dado
    Restricción que impone que los valores de las variables dadas no estén presentes en el conjunto dado
    Restricción que impone que al menos algunos de los valores de las variables dadas deben estar presentes en un conjunto dado
    Restricción que impone que al menos algunos de los valores de las variables dadas no deben estar presentes en un conjunto dado

    Al usar restricciones que pueden tomar una lista de multiplicadores como parámetro (Me gusta ExactSumo MinSum), tenga cuidado de decir explícitamente el orden o las variables si es necesario, como hicimos en el Ejemplo E

    Conclusión

    La programación de restricciones es sorprendente en lo que respecta a la legibilidad y la facilidad de desarrollo de ciertos programas, pero lo hace a costa del tiempo de ejecución. Depende del desarrollador decidir qué es más importante para él / ella para un problema en particular.

    Etiquetas:

    Deja una respuesta

    Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *