-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtask_117.py
235 lines (202 loc) · 10.8 KB
/
task_117.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
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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
from typing import Sequence
from arc_tools.grid import Grid, SubGrid, GridRegion, GridPoint, detect_objects, rotate_object
from datetime import datetime
from arc_tools.plot import plot_grids
from arc_tools.squash import squash_grid
show_count = 0
def fit_piece(grid: Grid, piece: Grid, remaining_pieces: Sequence[Grid]) -> Grid:
"""
Try to fit a piece into a grid at the first valid position, trying different rotations.
Prevents creating holes smaller than other pieces.
Args:
grid: The base grid to fit the piece into
piece: The piece to fit
remaining_pieces: List of remaining pieces to check against for hole size
Returns:
Grid: The grid with the piece fitted at the first valid position
"""
# Try all 4 possible rotations
original_piece = piece.copy()
for y in range(len(grid)):
for x in range(len(grid[0])):
# Check if we can place the piece at this position
can_place = True
# First check if the piece would go out of bounds
if y + len(piece) > len(grid) or x + len(piece[0]) > len(grid[0]):
continue
# Then check for overlap with existing pieces
for py in range(len(piece)):
for px in range(len(piece[0])):
if piece[py][px] != grid.background_color:
if grid[y + py][x + px] != grid.background_color:
can_place = False
break
if not can_place:
break
if can_place:
# Create a copy of the grid and place the piece
new_grid = grid.copy()
for py in range(len(piece)):
for px in range(len(piece[0])):
if piece[py][px] != new_grid.background_color:
new_grid[y + py][x + px] = piece[py][px]
if 0:
# Check if this creates any holes smaller than remaining pieces
# Get all objects in the new grid
objects = detect_objects(new_grid, invert=True)
# Get the size of the smallest remaining piece (count non-background values)
min_piece_size = float('inf')
for p in remaining_pieces:
dot_counts = list(p.get_values_count(all=True).values())[0]
if dot_counts < min_piece_size:
min_piece_size = dot_counts
min_piece = p
# Check each object to see if it's a hole (background color)
for obj in objects:
hole_count = obj.get_values_count(all=True)[new_grid.background_color]
if obj.height < min_piece.height or obj.width < min_piece.width or hole_count < min_piece_size:
can_place = False
break
# check if any piece can fit the border with small space
if can_place and remaining_pieces and 0:
# Check if there are any small spaces at the border that could be filled
border_spaces = []
# Check top and bottom borders
for x in range(len(new_grid[0])):
if new_grid[0][x] == new_grid.background_color:
border_spaces.append((0, x))
if new_grid[-1][x] == new_grid.background_color:
border_spaces.append((len(new_grid)-1, x))
# Check left and right borders
for y in range(len(new_grid)):
if new_grid[y][0] == new_grid.background_color:
border_spaces.append((y, 0))
if new_grid[y][-1] == new_grid.background_color:
border_spaces.append((y, len(new_grid[0])-1))
# If there are border spaces, check if any remaining piece can fit
if border_spaces:
for space in border_spaces:
space_filled = False
for p in remaining_pieces:
# Try to fit the piece at this border space
if p.height <= 2 and p.width <= 2: # Only consider small pieces
for py in range(len(p)):
for px in range(len(p[0])):
if p[py][px] != new_grid.background_color:
target_y = space[0] - py
target_x = space[1] - px
if (0 <= target_y < len(new_grid) and
0 <= target_x < len(new_grid[0])):
can_fit = True
for dy in range(len(p)):
for dx in range(len(p[0])):
if p[dy][dx] != new_grid.background_color:
if new_grid[target_y + dy][target_x + dx] != new_grid.background_color:
can_fit = False
break
if not can_fit:
break
if can_fit:
space_filled = True
break
if space_filled:
break
if not space_filled:
can_place = False
break
if can_place:
return new_grid
return grid
def jigsaw_recursive(grid: Grid, pieces: list[SubGrid]) -> Grid | None:
"""
Recursively fit jigsaw puzzle pieces together.
Args:
first_piece: The current base piece to fit other pieces against
remaining_pieces: List of Grid objects representing remaining puzzle pieces
Returns:
Grid: The complete puzzle grid with all pieces fitted together
"""
# Base case: if no remaining pieces, return the current piece
global show_count
if not pieces:
return grid
# Try to fit each remaining piece
pieces.sort(key=lambda x: list(x.get_values_count().values())[0], reverse=True)
for piece in pieces:
grid = grid.copy()
# Store original piece for rotation attempts
original_piece = piece.copy()
# Try all 4 rotations of the piece
for _ in range(4):
# Try to fit the piece
remaining_pieces = [p for p in pieces if p != original_piece]
new_grid = fit_piece(grid, piece, pieces)
if new_grid != grid: # If piece was successfully fitted
show_count += 1
# print(f"show_count: {show_count}")
if show_count and 0:
plot_grids([new_grid, *remaining_pieces], name=f"grid_{show_count}.png", show=0)
# Create new list of remaining pieces, excluding the original piece
# Recursively try to fit remaining pieces
result = jigsaw_recursive(new_grid, remaining_pieces)
if result is not None:
return result
piece = rotate_object(piece)
return None
def jigsaw_puzzle(grid: Grid) -> Grid:
"""
find output grid size by counting the number of objects in the input grid
1. find color map box
2. piece that having the color map box is the first piece without rotation.
3. move the jigsaw puzzle pieces to the correct position (do largest piece first)
4. replace colors of the objects in the output grid with the color map
"""
global show_count
show_count = 0 # Reset show count
start_time = datetime.now()
# find color map box
output_grid_size = int(sum(grid.get_values_count().values())**0.5)
objects = detect_objects(grid)
print(f"Found {len(objects)} objects")
background_color = grid.background_color
key_object = None
first_object = None
for obj in objects:
colors = list(obj.get_values_count().keys())
if len(colors) != 1:
key_object = obj.copy()
objects.remove(obj)
first_object = obj
# plot_grid(key_object, name="key_object.png", show=True)
object_color = colors[0]
key_object.replace_color(object_color, background_color)
key_object = detect_objects(key_object.get_full_grid())[0]
for row in range(key_object.region.y1, key_object.region.y2 + 1):
for col in range(key_object.region.x1, key_object.region.x2 + 1):
obj[row-obj.region.y1][col-obj.region.x1] = object_color
break
if key_object is None:
print("No key object found")
return grid
key_object_colors = [key_object[row][col] for row in range(key_object.height) for col in range(key_object.width)]
key_object_colors = [i for i in key_object_colors if i != background_color]
# Create list of puzzle pieces
# Create empty grid with output_grid_size
empty_grid = Grid([[background_color] * output_grid_size for _ in range(output_grid_size)])
# Try to solve the puzzle starting with the first piece
if first_object is not None:
new_grid = jigsaw_recursive(empty_grid, [first_object])
if not new_grid:
print("No new grid found")
if new_grid is not None:
result = jigsaw_recursive(new_grid, objects)
if result is not None:
for i, color in enumerate(squash_grid(result, background_color)):
result.replace_color(color, key_object_colors[i])
return result
print("No solution found")
print(f"Time taken: {datetime.now() - start_time}")
return grid
if __name__ == "__main__":
import os
os.system("main.py f560132c jigsaw_puzzle")