-
Notifications
You must be signed in to change notification settings - Fork 0
/
jarrow.dlx2.py
159 lines (142 loc) · 4.94 KB
/
jarrow.dlx2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
# Takes a description of a Japanese Arrows puzzle and
# build a model to run with Knuth's dlx2 solver.
#
# Usage: python jarrow.dlx2.py < jarrow.txt > model.dlx
import itertools
import functools
DIR = {
"^": (-1, 0),
"v": (1, 0),
"<": (0, -1),
">": (0, 1)
}
def collect_targets(n, directions, numbers, j, i):
jj, ii = DIR[directions[j][i]]
pj = j + jj
pi = i + ii
cell = []
seen = set()
while 0 <= pi < n and 0 <= pj < n:
cell.append((pj, pi))
if numbers[pj][pi] != '.':
seen.add(int(numbers[pj][pi]))
pj += jj
pi += ii
minsize = max(1, len(seen)) if len(cell) else 0
maxsize = sum(1 for jj, ii in cell if numbers[jj][ii] == ".") + len(seen)
if numbers[j][i] != '.':
minsize = maxsize = int(numbers[j][i])
return (seen, cell, minsize, maxsize)
def create_grid(n, func, *args):
f = functools.partial(func, *args)
directions = []
for j in xrange(n):
line = []
for i in xrange(n):
line.append(f(j, i))
directions.append(line)
return directions
def iter_grid(n):
for j in xrange(n):
for i in xrange(n):
yield (j, i)
def collect_arrows(n, targets, j, i):
cell = []
for jj, ii in iter_grid(n):
for tj, ti in targets[jj][ii][1]:
if tj == j and ti == i:
cell.append((jj, ii))
return cell
def encode(x):
return chr(ord('a') + x)
def encode_pos(j, i, *more):
return (encode(j), encode(i)) + tuple(more)
def collect_cells(n, targets, arrows, numbers):
for j, i in iter_grid(n):
minsize = targets[j][i][2]
maxsize = targets[j][i][3]
for size in xrange(minsize, maxsize + 1):
option = ["#C%s%s" % encode_pos(j, i)]
option.append("c%s%s:%s" % encode_pos(j, i, encode(size)))
for x in xrange(0, 10):
option.append("i%s%s%d:%d" % encode_pos(j, i, x, int(x == size)))
for arrow in arrows[j][i]:
option.append("h%s%s%d:1" % encode_pos(arrow[0], arrow[1], size))
yield " ".join(option)
if len(targets[j][i][1]):
choices = set(range(0, 10)) - set(targets[j][i][0])
combs = itertools.combinations(choices, size - len(targets[j][i][0]))
else:
combs = [[0]]
for comb in combs:
all_choices = set(comb).union(set(targets[j][i][0]))
option = ["#H%s%s" % encode_pos(j, i)]
option.append("c%s%s:%s" % encode_pos(j, i, encode(size)))
for k in xrange(0, 10):
option.append("h%s%s%d:%d" % encode_pos(j, i, k, int(k in all_choices)))
yield " ".join(option)
def collect_greater(n, targets, directions):
for j, i in iter_grid(n):
for tj, ti in targets[j][i][1]:
if directions[tj][ti] == directions[j][i]:
minsize = targets[j][i][2]
maxsize = targets[j][i][3]
for s1 in xrange(minsize, maxsize + 1):
for s2 in xrange(targets[tj][ti][2], s1 + 1):
option = ["G%s%s%s%s" % (encode_pos(j, i) + encode_pos(tj, ti))]
option.append("c%s%s:%s" % encode_pos(j, i, encode(s1)))
option.append("c%s%s:%s" % encode_pos(tj, ti, encode(s2)))
yield " ".join(option)
def collect_empty(n, targets):
for j, i in iter_grid(n):
for k in xrange(0, 10):
if targets[j][i][1] and k > 0:
option = ["E%s%s%d" % encode_pos(j, i, k)]
option.append("h%s%s%d:0" % encode_pos(j, i, k))
for jj, ii in targets[j][i][1]:
option.append("i%s%s%d:0" % encode_pos(jj, ii, k))
yield " ".join(option)
for jj, ii in targets[j][i][1]:
option = ["E%s%s%d" % encode_pos(j, i, k)]
option.append("h%s%s%d:1" % encode_pos(j, i, k))
option.append("i%s%s%d:1" % encode_pos(jj, ii, k))
yield " ".join(option)
elif k == 0 and not targets[j][i][1]:
option = ["E%s%s0" % encode_pos(j, i)]
option.append("h%s%s0:1" % encode_pos(j, i))
yield " ".join(option)
def collect_primary(options):
items = set()
for option in options:
for item in option.split():
if item[0].isupper() or item[0] == "#":
items.add(item)
return items
def collect_secondary(options):
items = set()
for option in options:
for item in option.split():
if item[0].islower():
items.add(item.split(":")[0])
return items
def print_targets(n, targets, arrows):
for j in xrange(n):
for i in xrange(n):
print j, i, "target", targets[j][i]
print j, i, "arrow", arrows[j][i]
def main():
n = int(raw_input())
directions = [raw_input().strip() for _ in xrange(n)]
numbers = [raw_input().strip() for _ in xrange(n)]
targets = create_grid(n, collect_targets, n, directions, numbers)
arrows = create_grid(n, collect_arrows, n, targets)
options = []
options.extend(collect_cells(n, targets, arrows, numbers))
options.extend(collect_greater(n, targets, directions))
options.extend(collect_empty(n, targets))
primary = collect_primary(options)
secondary = collect_secondary(options)
print "%s | %s" % (" ".join(primary), " ".join(secondary))
for option in options:
print option
main()