• API
• FAQ
• Tools
• Archive
daily pastebin goal
25%
SHARE
TWEET

# Untitled

a guest Nov 8th, 2018 76 Never
ENDING IN00days00hours00mins00secs
1. import itertools
2. import time
3.
4.
5. def test():
6.     board = Board(2,
7.                   {"colours": [[1, 1, 1], [1, 1, 2], [2, 2, 3]],
8.                    "trees": {(0, 2)}},
9.                   False)
10.     assert powerset([1, 2, 3]) == {(1,), (2,), (3,), (1, 2), (1, 3), (2, 3)}
11.     assert board.get_neighbours((1, 1)) == {(0, 0), (0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1), (2, 2)}
12.     assert board.get_neighbours((0, 2)) == {(0, 1), (1, 1), (1, 2)}
13.     assert board.row_index((0, 2)) == 0
14.     assert board.column_index((0, 2)) == 2
15.     assert board.row_column_min({(0, 2), (1, 1)}) == (0, 1)
16.     assert board.row_column_max({(0, 2), (1, 1)}) == (1, 2)
17.     assert board.quads == [{(0, 0), (1, 0), (0, 1), (1, 1)},
18.                            {(0, 1), (1, 1), (0, 2), (1, 2)},
19.                            {(1, 0), (2, 0), (1, 1), (2, 1)},
20.                            {(1, 1), (2, 1), (1, 2), (2, 2)}]
21.     assert board.quad_sets[2] == [({(0, 1), (1, 0), (0, 0), (1, 1)}, {(0, 1), (0, 2), (1, 1), (1, 2)}),
22.                                   ({(0, 1), (1, 0), (0, 0), (1, 1)}, {(2, 0), (1, 0), (1, 1), (2, 1)}),
23.                                   ({(0, 1), (1, 0), (0, 0), (1, 1)}, {(1, 2), (1, 1), (2, 1), (2, 2)}),
24.                                   ({(0, 1), (0, 2), (1, 1), (1, 2)}, {(2, 0), (1, 0), (1, 1), (2, 1)}),
25.                                   ({(0, 1), (0, 2), (1, 1), (1, 2)}, {(1, 2), (1, 1), (2, 1), (2, 2)}),
26.                                   ({(2, 0), (1, 0), (1, 1), (2, 1)}, {(1, 2), (1, 1), (2, 1), (2, 2)})]
27.     assert board.identify_sub_regions({(2, 0), (2, 2)}, 2) == ({(2, 0), (1, 0), (1, 1), (2, 1)},
28.                                                                {(1, 2), (1, 1), (2, 1), (2, 2)})
29.     assert board.identify_sub_regions({(2, 0), (2, 2)}, 2) == ({(2, 0), (1, 0), (1, 1), (2, 1)},
30.                                                                {(1, 2), (1, 1), (2, 1), (2, 2)})
31.     assert board.rows == {0: {(0, 0), (0, 1), (0, 2)}, 1: {(1, 0), (1, 1), (1, 2)}, 2: {(2, 0), (2, 1), (2, 2)}}
32.     assert board.columns == {0: {(0, 0), (1, 0), (2, 0)}, 1: {(0, 1), (1, 1), (2, 1)}, 2: {(0, 2), (1, 2), (2, 2)}}
33.     assert board.colour_regions == {1: {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1)},
34.                                     2: {(1, 2), (2, 0), (2, 1)},
35.                                     3: {(2, 2)}}
36.     assert board.count_trees(board.get_neighbours((0, 2))) == 0
37.     assert board.count_trees({(0, 2)}) == 1
38.     assert board.common_neighbours({(0, 0), (1, 1)}) == {(0, 1), (1, 0)}
39.
40.     board1 = Board(1,
41.                    {"colours": [[1, 1, 2, 3, 4],
42.                                 [1, 1, 2, 2, 4],
43.                                 [5, 1, 2, 4, 4],
44.                                 [5, 5, 5, 4, 4],
45.                                 [5, 5, 5, 5, 5]]},
46.                    False)
47.     solution1 = {(0, 3), (1, 0), (2, 2), (3, 4), (4, 1)}
48.     print("Solve board1 ------------------------------------------------------------------------------------")
49.     board1.find_trees()
50.     assert board1.trees == solution1
51.
52.     board2 = Board(1,
53.                    {"colours": [[1, 1, 1, 1, 1],
54.                                 [2, 1, 1, 1, 3],
55.                                 [1, 1, 1, 4, 3],
56.                                 [1, 5, 4, 4, 3],
57.                                 [1, 5, 4, 4, 4]]},
58.                    False)
59.     solution2 = {(0, 2), (1, 0), (2, 4), (3, 1), (4, 3)}
60.     print("Solve board2 -----------------------------------------------------------------------------------")
61.     board2.find_trees()
62.     assert board2.trees == solution2
63.
64.     board3 = Board(1,
65.                    {"colours": [[1, 1, 2, 2, 2],
66.                                 [1, 1, 2, 2, 2],
67.                                 [3, 2, 2, 2, 2],
68.                                 [3, 4, 4, 5, 5],
69.                                 [3, 3, 5, 5, 5]]},
70.                    False)
71.     solution3 = {(0, 1), (1, 3), (2, 0), (3, 2), (4, 4)}
72.     print("Solve board3 ---------------------------------------------------------------------------------")
73.     board3.find_trees()
74.     assert board3.trees == solution3
75.
76.     board14 = Board(1,
77.                     {"colours": [[1, 1, 1, 1, 2, 2, 2],
78.                                  [1, 1, 3, 1, 4, 4, 2],
79.                                  [1, 5, 3, 6, 6, 4, 2],
80.                                  [1, 5, 3, 3, 6, 4, 4],
81.                                  [1, 5, 5, 3, 6, 7, 7],
82.                                  [1, 1, 7, 7, 7, 7, 7],
83.                                  [7, 7, 7, 7, 7, 7, 7]]},
84.                     False)
85.     solution14 = {(0, 6), (1, 2), (2, 5), (3, 1), (4, 4), (5, 0), (6, 3)}
86.     print("Solve board14 ---------------------------------------------------------------------------------")
87.     board14.find_trees()
88.     assert board14.trees == solution14
89.
90.     board39 = Board(2,
91.                     {"colours": [[1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 4, 4],
92.                                  [1, 1, 1, 1, 1, 2, 3, 3, 3, 3, 4, 4],
93.                                  [1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4],
94.                                  [5, 5, 5, 1, 6, 6, 6, 7, 2, 7, 8, 8],
95.                                  [5, 5, 1, 1, 6, 6, 6, 7, 2, 7, 8, 8],
96.                                  [5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 8, 8],
97.                                  [5, 5, 5, 6, 9, 10, 6, 6, 7, 8, 8, 8],
98.                                  [9, 9, 5, 9, 9, 10, 10, 10, 10, 11, 8, 8],
99.                                  [9, 9, 9, 9, 9, 10, 10, 10, 10, 11, 8, 11],
100.                                  [12, 12, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11],
101.                                  [12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11],
102.                                  [12, 12, 12, 12, 12, 12, 11, 11, 11, 11, 11, 11]]},
103.                     False)
104.     solution39 = {(5, 9), (6, 11), (9, 3), (8, 0), (6, 0), (2, 1), (2, 10), (10, 1), (4, 2), (7, 2), (10, 8),
105.                   (4, 4), (5, 7), (8, 10), (11, 3), (3, 8), (1, 5), (0, 11), (7, 4), (3, 6), (1, 7), (0, 9),
106.                   (9, 5), (11, 6)}
107.     print("Solve Board39 --------------------------------------------------------------------------------")
108.     board39.find_trees()
109.     assert board39.trees == solution39
110.
111.     board41 = Board(2,
112.                     {"colours": [[1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3],
113.                                  [1, 1, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4],
114.                                  [1, 1, 2, 2, 2, 5, 3, 3, 3, 4, 4, 4],
115.                                  [1, 1, 2, 2, 2, 5, 3, 3, 4, 4, 4, 4],
116.                                  [1, 1, 2, 2, 2, 5, 5, 4, 4, 4, 4, 4],
117.                                  [1, 6, 6, 7, 7, 7, 7, 7, 4, 8, 4, 4],
118.                                  [6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8],
119.                                  [6, 6, 6, 6, 7, 7, 7, 8, 8, 8, 8, 9],
120.                                  [6, 6, 6, 6, 10, 10, 8, 8, 11, 11, 11, 9],
121.                                  [6, 6, 6, 10, 10, 10, 11, 11, 11, 11, 9, 9],
122.                                  [6, 6, 6, 6, 10, 10, 11, 11, 11, 11, 9, 9],
123.                                  [6, 6, 6, 10, 10, 10, 10, 12, 12, 12, 9, 9]]},
124.                     False)
125.     solution41 = {(0, 4), (0, 6), (1, 0), (1, 2), (2, 5), (2, 10), (3, 0), (3, 2), (4, 6), (4, 8),
126.                   (5, 1), (5, 3), (6, 8), (6, 10), (7, 1), (7, 4), (8, 9), (8, 11), (9, 3), (9, 7),
127.                   (10, 5), (10, 11), (11, 7), (11, 9)}
128.     print("Solve board41 --------------------------------------------------------------------------------")
129.     board41.find_trees()
130.     assert board41.trees == solution41
131.     return "Tests pass"
132.
133.
134. class Board:
135.     """
136.
137.     """
138.
139.     def __init__(self, trees_per_region, cell_data, print_path):
140.         self.colours = cell_data["colours"]
141.         self.colour_regions = self.get_colour_regions(cell_data["colours"])
142.         self.colour_region_combinations = powerset(self.colour_regions.keys())
143.         self.num_rows = len(cell_data["colours"])
144.         self.num_columns = len(cell_data["colours"][0])
145.         self.num_colour_regions = len(self.colour_regions.keys())
146.         self.trees_per_row = trees_per_region
147.         self.trees_per_column = trees_per_region
148.         self.trees_per_colour_region = trees_per_region
149.         self.max_trees_per_region = max(self.trees_per_row, self.trees_per_column, self.trees_per_colour_region)
150.         self.total_trees = self.check_total_trees()
151.         self.trees = set()
152.         self.nos = set()
153.         self.trees = self.mark_trees(cell_data.get("trees", set()))
154.         self.nos = self.mark_no_trees(cell_data.get("nos", set()))
155.         self.rows = {i: set([(i, j) for j in range(self.num_columns)]) for i in range(self.num_rows)}
156.         self.columns = {j: set([(i, j) for i in range(self.num_rows)]) for j in range(self.num_columns)}
157.         self.quads = [{(i, j), (i + 1, j), (i, j + 1), (i + 1, j + 1)}
158.                       for i in range(self.num_rows - 1)
159.                       for j in range(self.num_columns - 1)]
161.                           for r in range(2, self.max_trees_per_region * 2 + 1)}
162.         self.print_path = print_path
163.
164.     def find_trees(self):
165.         start_time = time.time()
166.         print("Finding Trees")
167.         while len(self.trees) < self.total_trees:
168.             found_cells = (set(self.trees), set(self.nos))  # set() functions needed to create proper copies of data
169.             self.run_checks()
170.             if (self.trees, self.nos) == found_cells:
171.                 print("Not all trees found, failing to progress. "
172.                       "Aborted after {0} seconds".format(time.time() - start_time))
173.                 print("Trees found:")
174.                 print(self.trees)
175.                 print("Nos found:")
176.                 print(self.nos)
177.                 return self.trees
178.         print("Solution found after {0} seconds".format(time.time() - start_time))
179.         print(self.trees)
180.         return self.trees
181.
182.     def run_checks(self):
183.         # Check each row, column and colour_region for basic tree total and neighbourhood constraints
184.         for region in self.colour_regions.keys():
185.             self.colour_regions[region] = self.check_region(self.colour_regions[region], self.trees_per_colour_region)
186.             self.check_sub_regions(self.colour_regions[region], self.trees_per_colour_region)
187.         for region in self.rows.keys():
188.             self.rows[region] = self.check_region(self.rows[region], self.trees_per_row)
189.             self.check_sub_regions(self.rows[region], self.trees_per_row)
190.         for region in self.columns.keys():
191.             self.columns[region] = self.check_region(self.columns[region], self.trees_per_column)
192.             self.check_sub_regions(self.columns[region], self.trees_per_column)
193.
194.         for comb in self.colour_region_combinations:
195.             combined_region = set().union(*[self.colour_regions[index] for index in comb])
196.             trees_in_combined_region = len(comb) * self.trees_per_colour_region
197.             self.check_subsets(combined_region, trees_in_combined_region, 3)
198.
199.     def check_region(self, region, n):
200.         """
201.         Return the region excluding any nos after running basic tree total and neighbourhood constraint checks
202.         :param region: A region to be checked against the condition of containing n trees
203.         :param n: The number of trees in total that should exist within the given region
204.         :return: A subset of the input region excluding any nos
205.         """
206.
207.         if self.count_unknowns(region) == 0 and n == 0: return region
208.
209.         if self.print_path: print("Checking region " + str(region) + ", " + str(n))
210.
211.         # Check whether region is over populated and raise error
212.         if self.count_trees(region) > n:
213.             print("Found {0} trees in region but expected {1}".format(self.count_trees(region), n))
214.             print("Trees {0} found in region {1}".format(self.trees & region, region))
215.             raise ValueError("Too many trees found in region")
216.
217.         # Check whether region is under populated and raise error
218.         if n - self.count_trees(region) > self.count_unknowns(region):
219.             print("Found {0} trees in region and {1} unknowns. "
220.                   "Expected {2} trees in total".format(self.count_trees(region), self.count_unknowns(region), n))
221.             print("Trees {0} found in region {1}".format(self.trees & region, region))
222.             raise ValueError("Too few trees found in region")
223.
224.         # Check whether region is already complete with correct number of trees
225.         # and mark all remaining unknown cells as nos
226.         unknowns = self.unknowns_in_region(region)
227.         if unknowns:
228.             if self.count_trees(region) == n:
229.                 print("Region complete, mark remaining to no. Region {0}".format(region))
230.                 self.mark_no_trees(unknowns)
231.
232.         # Check whether the remaining unknown cells are all required for the remaining number of trees
233.         # needed in the region and if so mark them all as trees
234.         unknowns = self.unknowns_in_region(region)
235.         if unknowns:
236.             if n - self.count_trees(region) == self.count_unknowns(region):
237.                 print("All remaining unknowns must be trees in region {0}".format(region))
238.                 self.mark_trees(self.unknowns_in_region(region))
239.
240.         # Check whether any cells are neighbours for all remaining unknown cells in the region and mark them as nos
241.         # If there are any unknown cells then they must contain a tree amongst them, if not they would be marked as nos
242.         # Any cell that neighbours all of these unknown cells must therefore neighbour a tree and so must be a no
243.         unknowns = self.unknowns_in_region(region)
244.         if unknowns:
245.             common_neighbours = self.unknowns_in_region(self.common_neighbours(unknowns))
246.             if common_neighbours:
247.                 print("Remove all common neighbours to unknown cells {}".format(unknowns))
248.                 self.mark_no_trees(common_neighbours)
249.
250.         # If more than one tree is still needed in a region
251.         # then exclude any cells within the region that boarder all other unknown cells
252.         # Identify these cells as being those that are neighbours of the max and min row and column index cells
253.         if n - self.count_trees(region) > 1:
254.             unknowns = self.unknowns_in_region(region)
255.             interior_neighbours = {cell for cell in unknowns
256.                                    if {self.row_column_min(unknowns),
257.                                        self.row_column_max(unknowns)}.issubset(self.get_neighbours(cell))}
258.             if interior_neighbours:
259.                 print("Remove interior neighbours from region {0}".format(region))
260.                 self.mark_no_trees(interior_neighbours)
261.
262.         return region - self.nos_in_region(region)
263.
264.     def check_sub_regions(self, region, n):
265.         """
266.
267.         :param region:
268.         :param n: The number of trees in total that should exist within the given region
269.         :return:
270.         """
271.
272.         if self.print_path: print("Checking sub-regions " + str(region) + ", " + str(n))
273.
274.         num_remaining_trees = n - self.count_trees(region)
275.         sub_regions = self.identify_sub_regions(self.unknowns_in_region(region), num_remaining_trees)
276.         if sub_regions:
277.             for sub_region in sub_regions:
278.                 self.check_region(sub_region & region, 1)
279.         return None
280.
281.     def identify_sub_regions(self, region, num_sub_regions):
282.
283.         # Exit if existence is impossible
284.         if len(region) > 4 * num_sub_regions:
285.             return None
286.
287.         # Exit if only one or no sub_regions needed
288.         if num_sub_regions <= 1:
289.             return None
290.
291.         # Identify a set of num_remaining_trees sub_regions that cover the region
295.                 if self.print_path: print("Sub-regions identified " + str(quad_set))
297.
298.     def check_subsets(self, region, n, iterations):
299.         self.check_subsets_generic(region, n, iterations, "colour-region",
300.                                    self.colour_region, self.colour_regions, self.trees_per_colour_region)
301.         self.check_subsets_generic(region, n, iterations, "row",
302.                                    self.row_index, self.rows, self.trees_per_row)
303.         self.check_subsets_generic(region, n, iterations, "column",
304.                                    self.column_index, self.columns, self.trees_per_column)
305.
306.     def check_subsets_generic(self, region, n, iterations,
307.                               region_type, region_type_index, region_type_dict, trees_per_region_type):
308.
309.         iterations += -1
310.         if iterations < 1: return None
311.         if self.print_path: print("Checking " + region_type + " subsets "
312.                                   + str(iterations) + str(region) + ", " + str(n))
313.
314.         superset_indices = set([region_type_index(cell) for cell in self.unknowns_in_region(region)])
315.         smallest_superset = set().union(*[region_type_dict[i] for i in superset_indices])
316.         trees_in_superset = len(superset_indices) * trees_per_region_type
317.         residual_region = smallest_superset - region
318.         trees_in_residual = trees_in_superset - n + self.count_trees(region - smallest_superset)
319.         if residual_region:
320.             if self.print_path: print("Smallest superset " + str(smallest_superset) + ", " + str(trees_in_superset))
321.             self.check_region(residual_region, trees_in_residual)
322.             self.check_sub_regions(residual_region, trees_in_residual)
323.             self.check_subsets(residual_region, trees_in_residual, iterations)
324.
325.         subset_indices = {i for i in superset_indices
326.                           if self.unknowns_in_region(region_type_dict[i]).issubset(region)}
327.         largest_subset = set().union(*[region_type_dict[i] for i in subset_indices])
328.         trees_in_subset = len(subset_indices) * trees_per_region_type
329.         residual_region = region & smallest_superset - largest_subset
330.         trees_in_residual = n - self.count_trees(region - smallest_superset) - (
331.                 trees_in_subset - self.count_trees(largest_subset - region))
332.         if residual_region:
333.             if self.print_path: print("Largest subset " + str(largest_subset) + ", " + str(trees_in_subset))
334.             self.check_region(residual_region, trees_in_residual)
335.             self.check_sub_regions(residual_region, trees_in_residual)
336.             self.check_subsets(residual_region, trees_in_residual, iterations)
337.
338.         return None
339.
340.     def check_total_trees(self):
341.         total_trees = self.num_rows * self.trees_per_row
342.         if (total_trees == self.num_columns * self.trees_per_column and
343.                 total_trees == self.num_colour_regions * self.trees_per_colour_region):
345.         else:
346.             raise ValueError("Board regions inconsistent")
347.
348.     def check_is_tree(self, cell):
349.         return cell in self.trees
350.
351.     def check_no_tree(self, cell):
352.         return cell in self.nos
353.
354.     def check_unknown_tree(self, cell):
355.         return not self.check_is_tree(cell) and not self.check_no_tree(cell)
356.
357.     def mark_tree(self, cell):
358.         if self.check_no_tree(cell):
359.             raise ValueError("Changed mind no to tree {0}".format(cell))
360.         if self.check_is_tree(cell):
362.         else:
363.             self.trees.update({cell})
364.             print("Set tree {0}".format(cell))
365.         unknown_neighbours = self.unknowns_in_region(self.get_neighbours(cell))
366.         if unknown_neighbours:
367.             print("Set neighbours to no {0}".format(cell))
368.             self.mark_no_trees(unknown_neighbours)
369.
370.     def mark_trees(self, region):
371.         for cell in region:
372.             self.mark_tree(cell)
373.         return self.trees
374.
375.     def mark_no_tree(self, cell):
376.         if self.check_is_tree(cell):
377.             raise ValueError("Changed mind tree to no {0}".format(cell))
378.         if self.check_no_tree(cell):
380.         else:
381.             print("Set no {0}".format(cell))
382.             self.nos.update({cell})
383.
384.     def mark_no_trees(self, region):
385.         for cell in region:
386.             self.mark_no_tree(cell)
387.         return self.nos
388.
389.     def get_colour_regions(self, cell_colours):
390.         colour_regions = {k: set() for k in set().union(*cell_colours)}
391.         for i in range(len(cell_colours)):
392.             for j in range(len(cell_colours[i])):
393.                 colour_regions[cell_colours[i][j]].update({(i, j)})
394.         return colour_regions
395.
396.     def get_neighbours(self, cell):
397.         neighbours = {(i, j) for i in range(max(cell[0] - 1, 0), min(cell[0] + 2, self.num_rows))
398.                       for j in range(max(cell[1] - 1, 0), min(cell[1] + 2, self.num_columns))}
399.         neighbours.remove(cell)
400.         return neighbours
401.
402.     def common_neighbours(self, region):
403.         neighbourhoods = [self.get_neighbours(cell) for cell in region]
404.         return set.intersection(*neighbourhoods)
405.
406.     def colour_region(self, cell):
407.         return self.colours[cell[0]][cell[1]]
408.
409.     def row_index(self, cell):
410.         return cell[0]
411.
412.     def column_index(self, cell):
413.         return cell[1]
414.
415.     def row_column_min(self, region):
416.         """
417.
418.         :param region:
419.         :return: A cell reference (not necessarily lying in the region) which bounds the region at the top, left.
420.         """
421.         return min([cell[0] for cell in region]), min([cell[1] for cell in region])
422.
423.     def row_column_max(self, region):
424.         """
425.
426.         :param region:
427.         :return: A cell reference (not necessarily lying in the region) which bounds the region at the bottom, right.
428.         """
429.         return max([cell[0] for cell in region]), max([cell[1] for cell in region])
430.
431.     def trees_in_region(self, region):
432.         return self.trees & region
433.
434.     def nos_in_region(self, region):
435.         return self.nos & region
436.
437.     def unknowns_in_region(self, region):
438.         return region - (self.trees_in_region(region) | self.nos_in_region(region))
439.
440.     def count_trees(self, region):
441.         return len(self.trees_in_region(region))
442.
443.     def count_nos(self, region):
444.         return len(self.nos_in_region(region))
445.
446.     def count_unknowns(self, region):
447.         return len(self.unknowns_in_region(region))
448.
449.
450. def powerset(iterable):
451.     """
452.     powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)
453.     :param iterable:
454.     :return:
455.     """
456.     s = list(iterable)
457.     return set(itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(1, len(s))))
458.
459.
460. test()
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top