← Back to branch summary

~ubuntu-branches/ubuntu/karmic/pypy/karmic

« back to all changes in this revision

Viewing changes to pypy/objspace/test/problems.py

  • Committer: Bazaar Package Importer
  • Author(s): Alexandre Fayolle
  • Date: 2007-04-13 09:33:09 UTC
  • Revision ID: james.westby@ubuntu.com-20070413093309-yoojh4jcoocu2krz
Tags: upstream-1.0.0
Import upstream version 1.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
pypy/objspace/test/problems.py
 
1
 
 
2
def dummy_problem(computation_space):
 
3
    ret = computation_space.var('__dummy__')
 
4
    computation_space.set_dom(ret, c.FiniteDomain([]))
 
5
    return (ret,)
 
6
 
 
7
def send_more_money(computation_space):
 
8
    #FIXME: this problem needs propagators for integer finite domains
 
9
    #       performance is terrible without it
 
10
    cs = computation_space
 
11
 
 
12
    variables = (s, e, n, d, m, o, r, y) = cs.make_vars('s', 'e', 'n', 'd', 'm', 'o', 'r', 'y')
 
13
 
 
14
    digits = range(10)
 
15
    for var in variables:
 
16
        cs.set_dom(var, c.FiniteDomain(digits))
 
17
 
 
18
    # use fd.AllDistinct
 
19
    for v1 in variables:
 
20
        for v2 in variables:
 
21
            if v1 != v2:
 
22
                cs.add_constraint([v1, v2],
 
23
                                  '%s != %s' % (v1.name, v2.name))
 
24
 
 
25
    # use fd.NotEquals
 
26
    cs.add_constraint([s], 's != 0')
 
27
    cs.add_constraint([m], 'm != 0')
 
28
    cs.add_constraint([s, e, n, d, m, o, r, y],
 
29
                                   '1000*s+100*e+10*n+d+1000*m+100*o+10*r+e == 10000*m+1000*o+100*n+10*e+y')
 
30
    cs.set_distributor(di.DichotomyDistributor(cs))
 
31
    print cs.constraints
 
32
    return (s, e, n, d, m, o, r, y)
 
33
 
 
34
def conference_scheduling(computation_space):
 
35
    cs = computation_space
 
36
 
 
37
    dom_values = [(room,slot) 
 
38
          for room in ('room A','room B','room C') 
 
39
          for slot in ('day 1 AM','day 1 PM','day 2 AM',
 
40
                       'day 2 PM')]
 
41
 
 
42
    variables = [cs.var(v, FiniteDomain(dom_values))
 
43
                 for v in ('c01','c02','c03','c04','c05',
 
44
                           'c06','c07','c08','c09','c10')]
 
45
    for conf in ('c03','c04','c05','c06'):
 
46
        v = cs.find_var(conf)
 
47
        cs.tell(make_expression([v], "%s[0] == 'room C'" % conf))
 
48
 
 
49
    for conf in ('c01','c05','c10'):
 
50
        v = cs.find_var(conf)
 
51
        cs.tell(make_expression([v], "%s[1].startswith('day 1')" % conf))
 
52
 
 
53
    for conf in ('c02','c03','c04','c09'):
 
54
        v = cs.find_var(conf)
 
55
        cs.tell(make_expression([v], "%s[1].startswith('day 2')" % conf))
 
56
 
 
57
    groups = (('c01','c02','c03','c10'),
 
58
              ('c02','c06','c08','c09'),
 
59
              ('c03','c05','c06','c07'),
 
60
              ('c01','c03','c07','c08'))
 
61
 
 
62
    for group in groups:
 
63
        for conf1 in group:
 
64
            for conf2 in group:
 
65
                if conf2 > conf1:
 
66
                    v1, v2 = cs.find_vars((conf1, conf2))
 
67
                    cs.tell(make_expression([v1, v2], '%s[1] != %s[1]'% (v1.name(),v2.name())))
 
68
    cs.tell(AllDistinct(variables))
 
69
 
 
70
    return variables
 
71
 
 
72
def sudoku(computation_space):
 
73
    cs = computation_space
 
74
    import constraint as c
 
75
 
 
76
    variables = [cs.var('v%i%i'%(x,y)) for x in range(1,10) for y in range(1,10)]
 
77
 
 
78
    # Make the variables
 
79
    for v in variables:
 
80
        cs.set_dom(v, c.FiniteDomain(range(1,10)))
 
81
    # Add constraints for rows (sum should be 45)
 
82
    for i in range(1,10):
 
83
        row = [ v for v in variables if v.name[1] == str(i)]
 
84
        cs.add_constraint(row, 'sum([%s]) == 45' % ', '.join([v.name for v in row]))
 
85
    # Add constraints for columns (sum should be 45)
 
86
    for i in range(1,10):
 
87
        row = [ v for v in variables if v.name[2] == str(i)]
 
88
        cs.add_constraint(row, 'sum([%s]) == 45' % ', '.join([v.name for v in row]))   
 
89
    # Add constraints for subsquares (sum should be 45)
 
90
    offsets = [(r,c) for r in [-1,0,1] for c in [-1,0,1]]
 
91
    subsquares = [(r,c) for r in [2,5,8] for c in [2,5,8]]
 
92
    for rc in subsquares:
 
93
        sub = [cs.find_var('v%d%d'% (rc[0] + off[0],rc[1] + off[1])) for off in offsets]
 
94
        cs.add_constraint(sub, 'sum([%s]) == 45' % ', '.join([v.name for v in sub]))
 
95
        for v in sub:
 
96
            for m in sub[sub.index(v)+1:]:
 
97
                cs.add_constraint([v,m], '%s != %s' % (v.name, m.name))
 
98
    #print cs.constraints
 
99
    return tuple(variables)
 
100