KenMercusLai /
checkio
| Total Complexity | 27 |
| Total Lines | 186 |
| Duplicated Lines | 17.2 % |
| Changes | 0 | ||
Duplicate code is one of the most pungent code smells. A rule that is often used is to re-structure code once it is duplicated in three or more places.
Common duplication problems, and corresponding solutions are:
| 1 | import heapq |
||
| 2 | from collections import defaultdict |
||
| 3 | |||
| 4 | |||
| 5 | View Code Duplication | def shortestPath(graph, start, end): |
|
|
Duplication
introduced
by
|
|||
| 6 | queue = [(0, start, [])] |
||
| 7 | seen = set() |
||
| 8 | while True: |
||
| 9 | (cost, v, path) = heapq.heappop(queue) |
||
| 10 | if v not in seen: |
||
| 11 | path = path + [v] |
||
| 12 | seen.add(v) |
||
| 13 | if v == end: |
||
| 14 | return cost, path |
||
| 15 | for (next, c) in graph[v].items(): |
||
| 16 | heapq.heappush(queue, (cost + c, next, path)) |
||
| 17 | return queue |
||
| 18 | |||
| 19 | |||
| 20 | def checkio(maze_map): |
||
| 21 | connect_map = defaultdict(dict) |
||
| 22 | for row in range(len(maze_map)): |
||
| 23 | for col in range(len(maze_map[0])): |
||
| 24 | # only collect states of path cells |
||
| 25 | if maze_map[row][col] == 0: |
||
| 26 | # N |
||
| 27 | if row - 1 > 0 and maze_map[row - 1][col] == 0: |
||
| 28 | connect_map[(row, col)][(row - 1, col)] = 1 |
||
| 29 | connect_map[(row - 1, col)][(row, col)] = 1 |
||
| 30 | # S |
||
| 31 | if row + 1 < len(maze_map) and maze_map[row + 1][col] == 0: |
||
| 32 | connect_map[(row, col)][(row + 1, col)] = 1 |
||
| 33 | connect_map[(row + 1, col)][(row, col)] = 1 |
||
| 34 | # E |
||
| 35 | if col + 1 < len(maze_map[row]) and maze_map[row][col + 1] == 0: |
||
| 36 | connect_map[(row, col)][(row, col + 1)] = 1 |
||
| 37 | connect_map[(row, col + 1)][(row, col)] = 1 |
||
| 38 | # W |
||
| 39 | if col - 1 > 0 and maze_map[row][col - 1] == 0: |
||
| 40 | connect_map[(row, col)][(row, col - 1)] = 1 |
||
| 41 | connect_map[(row, col - 1)][(row, col)] = 1 |
||
| 42 | |||
| 43 | steps, path = shortestPath(connect_map, (1, 1), (10, 10)) |
||
| 44 | path.append((10, 10)) |
||
| 45 | steps += 1 |
||
| 46 | directions = [] |
||
| 47 | for i in range(1, steps): |
||
| 48 | previous_step, current_step = path[i - 1], path[i] |
||
| 49 | if current_step[0] > previous_step[0]: |
||
| 50 | directions.append('S') |
||
| 51 | elif current_step[0] < previous_step[0]: |
||
| 52 | directions.append('N') |
||
| 53 | elif current_step[1] > previous_step[1]: |
||
| 54 | directions.append('E') |
||
| 55 | elif current_step[1] < previous_step[1]: |
||
| 56 | directions.append('W') |
||
| 57 | return ''.join(directions) |
||
| 58 | |||
| 59 | |||
| 60 | if __name__ == '__main__': # pragma: no cover |
||
| 61 | # This code using only for self-checking and not necessary for auto-testing |
||
| 62 | View Code Duplication | def check_route(func, labyrinth): |
|
| 63 | MOVE = {"S": (1, 0), "N": (-1, 0), "W": (0, -1), "E": (0, 1)} |
||
| 64 | # copy maze |
||
| 65 | route = func([row[:] for row in labyrinth]) |
||
| 66 | pos = (1, 1) |
||
| 67 | goal = (10, 10) |
||
| 68 | for i, d in enumerate(route): |
||
| 69 | move = MOVE.get(d, None) |
||
| 70 | if not move: |
||
| 71 | print("Wrong symbol in route") |
||
| 72 | return False |
||
| 73 | pos = pos[0] + move[0], pos[1] + move[1] |
||
| 74 | if pos == goal: |
||
| 75 | return True |
||
| 76 | if labyrinth[pos[0]][pos[1]] == 1: |
||
| 77 | print("Player in the pit") |
||
| 78 | return False |
||
| 79 | print("Player did not reach exit") |
||
| 80 | return False |
||
| 81 | |||
| 82 | # These assert are using only for self-testing as examples. |
||
| 83 | assert check_route( |
||
| 84 | checkio, |
||
| 85 | [ |
||
| 86 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 87 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 88 | [1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1], |
||
| 89 | [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 90 | [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1], |
||
| 91 | [1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1], |
||
| 92 | [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1], |
||
| 93 | [1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1], |
||
| 94 | [1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1], |
||
| 95 | [1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1], |
||
| 96 | [1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1], |
||
| 97 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 98 | ], |
||
| 99 | ), "First maze" |
||
| 100 | assert check_route( |
||
| 101 | checkio, |
||
| 102 | [ |
||
| 103 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 104 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 105 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 106 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 107 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 108 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 109 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 110 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 111 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 112 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 113 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 114 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 115 | ], |
||
| 116 | ), "Empty maze" |
||
| 117 | assert check_route( |
||
| 118 | checkio, |
||
| 119 | [ |
||
| 120 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 121 | [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1], |
||
| 122 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1], |
||
| 123 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], |
||
| 124 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], |
||
| 125 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], |
||
| 126 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1], |
||
| 127 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], |
||
| 128 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], |
||
| 129 | [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1], |
||
| 130 | [1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1], |
||
| 131 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 132 | ], |
||
| 133 | ), "Up and down maze" |
||
| 134 | assert check_route( |
||
| 135 | checkio, |
||
| 136 | [ |
||
| 137 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 138 | [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], |
||
| 139 | [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], |
||
| 140 | [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], |
||
| 141 | [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], |
||
| 142 | [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], |
||
| 143 | [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], |
||
| 144 | [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], |
||
| 145 | [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1], |
||
| 146 | [1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1], |
||
| 147 | [1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1], |
||
| 148 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 149 | ], |
||
| 150 | ), "Dotted maze" |
||
| 151 | assert check_route( |
||
| 152 | checkio, |
||
| 153 | [ |
||
| 154 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 155 | [1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1], |
||
| 156 | [1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1], |
||
| 157 | [1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1], |
||
| 158 | [1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1], |
||
| 159 | [1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1], |
||
| 160 | [1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1], |
||
| 161 | [1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 162 | [1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1], |
||
| 163 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1], |
||
| 164 | [1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1], |
||
| 165 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 166 | ], |
||
| 167 | ), "Need left maze" |
||
| 168 | assert check_route( |
||
| 169 | checkio, |
||
| 170 | [ |
||
| 171 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 172 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 173 | [1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1], |
||
| 174 | [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 175 | [1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1], |
||
| 176 | [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1], |
||
| 177 | [1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1], |
||
| 178 | [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1], |
||
| 179 | [1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1], |
||
| 180 | [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1], |
||
| 181 | [1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1], |
||
| 182 | [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], |
||
| 183 | ], |
||
| 184 | ), "The big dead end." |
||
| 185 | print("The local tests are done.") |
||
| 186 |
Loading history...