|
1
|
|
|
from collections import defaultdict |
|
2
|
|
|
from math import hypot |
|
3
|
|
|
from random import choice |
|
4
|
|
|
|
|
5
|
|
|
|
|
6
|
|
|
possible_positions = [(i, j) for i in range(10) for j in range(10)] |
|
7
|
|
|
|
|
8
|
|
|
|
|
9
|
|
|
def distance(point_1, point_2): |
|
10
|
|
|
return hypot(point_2[0] - point_1[0], point_2[1] - point_1[1]) |
|
11
|
|
|
|
|
12
|
|
|
|
|
13
|
|
|
def checkio(steps): |
|
14
|
|
|
global possible_positions |
|
15
|
|
|
previous_distance = defaultdict(int) |
|
16
|
|
|
|
|
17
|
|
|
if len(steps) == 1: |
|
18
|
|
|
possible_positions = [(i, j) for i in range(10) for j in range(10)] |
|
19
|
|
|
possible_positions.remove(tuple(steps[0][:2])) |
|
20
|
|
|
for i in possible_positions: |
|
21
|
|
|
previous_distance[i] = distance(tuple(steps[0][:2]), i) |
|
22
|
|
|
max_distance = max(previous_distance.values()) |
|
23
|
|
|
candidates = [ |
|
24
|
|
|
cell for cell, value in previous_distance.items() if value == max_distance |
|
25
|
|
|
] |
|
26
|
|
|
next_step = choice(candidates) |
|
27
|
|
|
possible_positions.remove(next_step) |
|
28
|
|
|
return next_step |
|
29
|
|
|
|
|
30
|
|
|
last_step = tuple(steps[-1][:2]) |
|
31
|
|
|
last_feedback = steps[-1][-1] |
|
32
|
|
|
disqualified = [] |
|
33
|
|
|
for i in possible_positions: |
|
34
|
|
|
last_distance = distance(tuple(steps[-2][:2]), i) |
|
35
|
|
|
current_distance = distance(last_step, i) |
|
36
|
|
|
if last_feedback == -1 and last_distance >= current_distance: |
|
37
|
|
|
disqualified.append(i) |
|
38
|
|
|
elif last_feedback == 0 and last_distance != current_distance: |
|
39
|
|
|
disqualified.append(i) |
|
40
|
|
|
elif last_feedback == 1 and last_distance <= current_distance: |
|
41
|
|
|
disqualified.append(i) |
|
42
|
|
|
for i in disqualified: |
|
43
|
|
|
possible_positions.remove(i) |
|
44
|
|
|
next_step = choice(possible_positions) |
|
45
|
|
|
possible_positions.remove(next_step) |
|
46
|
|
|
return next_step |
|
47
|
|
|
|
|
48
|
|
|
|
|
49
|
|
|
if __name__ == '__main__': |
|
50
|
|
|
# This part is using only for self-checking and not necessary for |
|
51
|
|
|
# auto-testing |
|
52
|
|
|
MAX_STEP = 12 |
|
53
|
|
|
|
|
54
|
|
View Code Duplication |
def check_solution(func, goal, start): |
|
|
|
|
|
|
55
|
|
|
prev_steps = [start] |
|
56
|
|
|
for step in range(MAX_STEP): |
|
57
|
|
|
row, col = func([s[:] for s in prev_steps]) |
|
58
|
|
|
if [row, col] == goal: |
|
59
|
|
|
return True |
|
60
|
|
|
if 10 <= row or 0 > row or 10 <= col or 0 > col: |
|
61
|
|
|
print("You gave wrong coordinates.") |
|
62
|
|
|
return False |
|
63
|
|
|
prev_distance = hypot( |
|
64
|
|
|
prev_steps[-1][0] - goal[0], prev_steps[-1][1] - goal[1] |
|
65
|
|
|
) |
|
66
|
|
|
distance = hypot(row - goal[0], col - goal[1]) |
|
67
|
|
|
alteration = ( |
|
68
|
|
|
0 |
|
69
|
|
|
if prev_distance == distance |
|
70
|
|
|
else (1 if prev_distance > distance else -1) |
|
71
|
|
|
) |
|
72
|
|
|
prev_steps.append([row, col, alteration]) |
|
73
|
|
|
print("Too many steps") |
|
74
|
|
|
return False |
|
75
|
|
|
|
|
76
|
|
|
assert check_solution(checkio, [7, 7], [5, 5, 0]), "1st example" |
|
77
|
|
|
assert check_solution(checkio, [5, 6], [0, 0, 0]), "2nd example" |
|
78
|
|
|
|
KenMercusLai /
checkio
Loading history...