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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202import time
class Seg:
def __init__(self, length):
self.length = length
self.placements = []
def __repr__(self):
return '<Seg:len=' + str(self.length) + ',placements=' + str(self.placements) + '>'
class Bar:
def __init__(self, axis, index, segs, length):
self.segs = segs
self.complete = False
self.dirty = False
self.axis = axis
self.index = index
self.length = length
self.full_space = sum([seg.length for seg in self.segs]) + len(self.segs) - 1
def is_full(self):
return self.full_space == self.length
def __repr__(self):
return '<Bar:axis=' + str(self.axis) + ',index=' + str(self.index) + ',len=' + str(
self.length) + ',full_space=' + str(
self.full_space) + ',segs=' + str(self.segs) + ',dirty=' + str(self.dirty) + '>'
def __lt__(self, other):
return self.index - other.index
def load():
with open("../data/up.txt") as f:
lines = f.readlines()
lines = [line.strip() for line in lines if (not line.startswith('#')) and len(line.strip()) != 0]
raw = [list(map(int, line.split())) for line in lines]
assert sum(raw[0]) == len(raw) - 1
return raw[1:raw[0][0] + 1], raw[raw[0][0] + 1:]
def print_board(board):
m = {1: '#', 0: ' ', None: '?'}
print("\n".join([''.join([m[ele] for ele in row]) for row in board]))
def calc_space(segs):
return sum([seg.length for seg in segs]) + len(segs) - 1
def calc_placement(bars):
for bar in bars:
for i in range(len(bar.segs)):
seg = bar.segs[i]
start = calc_space(bar.segs[:i]) + 1
end = bar.length - calc_space(bar.segs[i + 1:]) - seg.length
seg.placements = list(range(start, end))
def update_board(board, bar, i, value):
if board[bar.axis][bar.index][i] == value:
return False
board[bar.axis][bar.index][i] = value
board[1 - bar.axis][i][bar.index] = value
return True
def mark_overlaps(board, bars):
for bar in bars:
for seg in bar.segs:
for i in range(seg.placements[-1], seg.placements[0] + seg.length):
if update_board(board, bar, i, 1):
bars[(1 - bar.axis) * h + i].dirty = True
def validate_placement(board, bar, iseg, placement):
seg = bar.segs[iseg]
# if the previous pixel is 1
if placement > 0 and board[bar.axis][bar.index][placement - 1] == 1:
return False
# if any of the pixel inside the segment is 0
elif 0 in board[bar.axis][bar.index][placement:placement + seg.length]:
return False
# if the next pixel is 1
elif placement + seg.length < len(board[bar.axis][bar.index]) and board[bar.axis][bar.index][
placement + seg.length] == 1:
return False
return True
def mark_flags(board, bar, tmp_placements, flags):
prev = 0
for i in range(len(tmp_placements)):
seg = bar.segs[i]
placement = tmp_placements[i]
# print(seg, placement, placement + seg.length)
for j in range(prev, placement):
flags[j] |= 2
for j in range(placement, placement + seg.length):
flags[j] |= 1
end = len(board[bar.axis][0])
if i != len(tmp_placements) - 1:
end = tmp_placements[i + 1]
for j in range(placement + seg.length, end):
flags[j] |= 2
prev = placement + seg.length
# flag = 1: can be black,
# flag = 2: can be white,
# flag = 3: can be both
def check_bar(board, bar, start=0, iseg=0, tmp_placements=[], flags=[]):
if iseg == len(bar.segs):
last_seg = bar.segs[-1]
if 1 in board[bar.axis][bar.index][tmp_placements[-1] + last_seg.length:]:
return
mark_flags(board, bar, tmp_placements, flags)
else:
seg = bar.segs[iseg]
valid_placements = []
for placement in seg.placements:
# print(validate_placement(board, bar, iseg, placement))
if validate_placement(board, bar, iseg, placement):
valid_placements.append(placement)
seg.placements = valid_placements
for placement in seg.placements:
if placement < start:
continue
if 1 in board[bar.axis][bar.index][start:placement]:
continue
tmp_placements[iseg] = placement
check_bar(board, bar, start=placement + seg.length + 1, iseg=iseg + 1, tmp_placements=tmp_placements,
flags=flags)
(hlens, vlens) = load()
h = len(hlens)
v = len(vlens)
bars = []
for ind in range(len(hlens)):
segs = [Seg(i) for i in hlens[ind]]
bars.append(Bar(0, ind, segs, h))
for ind in range(len(hlens)):
segs = [Seg(i) for i in vlens[ind]]
bars.append(Bar(1, ind, segs, h))
board = [[[None] * v for i in range(h)], [[None] * v for i in range(h)]]
calc_placement(bars)
mark_overlaps(board, bars)
while True:
dirty_bars = [(sum([len(seg.placements) for seg in bar.segs]), bar) for bar in bars if bar.dirty]
if len(dirty_bars) == 0:
break
effort, bar = min(dirty_bars)
flags = [0] * len(board[bar.axis][0])
print("Processing Bar: (" + str(bar.axis) + "," + str(bar.index) + ")")
check_bar(board, bar, tmp_placements=[0] * len(bar.segs), flags=flags)
for i in range(len(flags)):
flag = flags[i]
if flag == 1:
if update_board(board, bar, i, 1):
bars[(1 - bar.axis) * h + i].dirty = True
elif flag == 2:
if update_board(board, bar, i, 0):
bars[(1 - bar.axis) * h + i].dirty = True
bar.dirty = False
print_board(board[0])
print(time.process_time())
# warmup
# 0.03125
# 0.046875
# up
# 0.578125
# 0.625