Instantly share code, notes, and snippets.

# marekyggdrasil/diophantine.py

Last active April 17, 2023 00:32
Show Gist options
• Save marekyggdrasil/bb953f9bfd85430c1001c294ea7108ce to your computer and use it in GitHub Desktop.
Code repository for tutorial on constraint programming available on https://mareknarozniak.com/2020/06/22/constraint-programming/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from constraint import Problem problem = Problem() problem.addVariable('x', range(1, 10)) problem.addVariable('y', range(1, 10)) problem.addVariable('z', range(1, 10)) def constraintCheck(x, y, z): if x**3 + y**2 - z**2 == 0: return True return False problem.addConstraint(constraintCheck, ['x', 'y', 'z']) solutions = problem.getSolutions() for solution in solutions: print(solution) x = solution['x'] y = solution['y'] z = solution['z']
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 from constraint import Problem import pprint pp = pprint.PrettyPrinter(indent=4) f = frozenset towns = { 'Indigo Plateau': 'a', 'Pallet Town': '', 'Viridian City': '', 'Pewter City': '', 'Cinnabar Island': '', 'Cerulean City': '', 'Saffron City': '', 'Celadon City': '', 'Lavender Town': '', 'Vermillion City': '', 'Fuschia City': '', 'Special Region': '' } V = f({ 'Indigo Plateau', 'Pallet Town', 'Viridian City', 'Pewter City', 'Cinnabar Island', 'Cerulean City', 'Saffron City', 'Celadon City', 'Lavender Town', 'Vermillion City', 'Fuschia City', 'Special Region'}) E = f({ f({'Indigo Plateau', 'Viridian City'}), f({'Pallet Town', 'Viridian City'}), f({'Viridian City', 'Pewter City'}), f({'Pewter City', 'Cerulean City'}), f({'Cerulean City', 'Saffron City'}), f({'Saffron City', 'Celadon City'}), f({'Celadon City', 'Fuschia City'}), f({'Fuschia City', 'Special Region'}), f({'Fuschia City', 'Cinnabar Island'}), f({'Vermillion City', 'Special Region'}), f({'Cinnabar Island', 'Pallet Town'}), f({'Saffron City', 'Lavender Town'}), f({'Saffron City', 'Vermillion City'}), f({'Lavender Town', 'Cerulean City'}), f({'Lavender Town', 'Special Region'}) }) G = (V, E) V = list(V) E = list(E) # print(E) # define the problem and its variables and domains problem = Problem() # every town in Kanto can have either a Pokecenter either a Gym for town in V: varname = town.lower().replace(' ', '_') problem.addVariable(varname, ['center', 'gym']) # there can be no two gyms next to each other for pair in list(E): dest_i, dest_j = tuple(pair) dest_i = dest_i.lower().replace(' ', '_') dest_j = dest_j.lower().replace(' ', '_') problem.addConstraint(lambda x, y: True if not x == y == 'gym' else False, [dest_i, dest_j]) # print(dest_i, dest_j) best_mis = [] best_mis_size = 0 best_mvc = [] best_mvc_size = len(V) + 1 # get CSP solution solutions = problem.getSolutions() # get COP solution for solution in solutions: values = list(solution.values()) nb_gyms = values.count('gym') nb_centers = values.count('center') # MVC criterion if nb_centers < best_mvc_size: best_mvc = [solution] best_mvc_size = nb_centers elif nb_gyms == best_mvc_size: best_mvc.append(solution) # MIS criterion if nb_gyms > best_mis_size: best_mis = [solution] best_mis_size = nb_gyms elif nb_centers == best_mis_size: best_mis.append(solution) assert [i for i in best_mis if i not in best_mvc] == [] print('succeedo!') print() for solution in best_mvc: pp.pprint(solution) print()