API tools faq
paste
Guest User

Untitled

a guest
Nov 8th, 2018
102
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 22.18 KB | None | 0 0
raw download clone embed print report
  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)]
  160. self.quad_sets = {r: list(itertools.combinations(self.quads, r))
  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
  292. quad_sets = self.quad_sets.get(num_sub_regions, [])
  293. for quad_set in quad_sets:
  294. if region.issubset(set().union(*quad_set)):
  295. if self.print_path: print("Sub-regions identified " + str(quad_set))
  296. return 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):
  344. return total_trees
  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):
  361. print("Already known tree {0}".format(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):
  379. print("Already known no {0}".format(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()
Add Comment
Please, Sign In to add comment
Public Pastes
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.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!