|
1
|
|
|
# coding: utf8 |
|
2
|
|
|
|
|
3
|
|
|
# Copyright 2013-2015 Vincent Jacques <[email protected]> |
|
4
|
|
|
|
|
5
|
|
|
import collections |
|
6
|
|
|
import fractions |
|
7
|
|
|
import math |
|
8
|
|
|
|
|
9
|
|
|
|
|
10
|
|
|
End = collections.namedtuple("End", "theta, altitude") |
|
11
|
|
|
Segment = collections.namedtuple("Segment", "begin, end") |
|
12
|
|
|
Bridge = collections.namedtuple("Bridge", "before, after, tunnel") |
|
13
|
|
|
Tunnel = collections.namedtuple("Tunnel", "k, before, after") |
|
14
|
|
|
String = collections.namedtuple("String", "k, segments, bridges") |
|
15
|
|
|
|
|
16
|
|
|
|
|
17
|
|
|
class Knot(object): |
|
18
|
|
|
def __init__(self, p, q): |
|
19
|
|
|
self.p = p |
|
20
|
|
|
self.q = q |
|
21
|
|
|
self.d = fractions.gcd(p, q) |
|
22
|
|
|
self._ks = range(self.d) |
|
23
|
|
|
self.p_prime = p // self.d |
|
24
|
|
|
self.q_prime = q // self.d |
|
25
|
|
|
self.__max_theta = 2 * self.p * self.q_prime |
|
26
|
|
|
if self.q == 1: |
|
27
|
|
|
self.strings = [String(0, [Segment(End(0, 0), End(2 * self.p, 0))], [])] |
|
28
|
|
|
else: |
|
29
|
|
|
self.strings = list(self.__make_strings()) |
|
30
|
|
|
|
|
31
|
|
|
def __make_strings(self): |
|
32
|
|
|
intersections = list(self.__find_intersections()) |
|
33
|
|
|
tidied_intersections = self.__tidy_intersections(intersections) |
|
34
|
|
|
ends = list(self.__make_ends(tidied_intersections)) |
|
35
|
|
|
segments = list(self.__make_segments(ends)) |
|
36
|
|
|
bridges = list(self.__make_bridges(tidied_intersections, segments)) |
|
37
|
|
|
for k in self._ks: |
|
38
|
|
|
yield String(k, segments[k], bridges[k]) |
|
39
|
|
|
|
|
40
|
|
|
def __find_intersections(self): |
|
41
|
|
|
found = 0 |
|
42
|
|
|
for m in range(self.d): |
|
43
|
|
|
for n in range(m, self.d): |
|
44
|
|
|
for theta_1, theta_2 in self.__find_strings_intersections(m, n): |
|
45
|
|
|
assert 0 <= theta_1 < self.__max_theta |
|
46
|
|
|
assert 0 <= theta_2 < self.__max_theta |
|
47
|
|
|
assert m != n or theta_1 < theta_2 |
|
48
|
|
|
found += 1 |
|
49
|
|
|
yield m, n, theta_1, theta_2 |
|
50
|
|
|
assert found == self.p * (self.q - 1) |
|
51
|
|
|
|
|
52
|
|
|
def __find_strings_intersections(self, m, n): |
|
53
|
|
|
if m == n: |
|
54
|
|
|
min_a = 1 |
|
55
|
|
|
else: |
|
56
|
|
|
min_a = -self.q_prime + 1 |
|
57
|
|
|
max_a = self.q_prime |
|
58
|
|
|
for a in range(min_a, max_a): |
|
59
|
|
|
min_b = int(math.ceil(float(abs(a) * self.p - m - n) / self.q)) |
|
60
|
|
|
max_b = 2 * self.p_prime - int(math.floor(float(abs(a) * self.p + m + n) / self.q)) |
|
61
|
|
|
for b in range(min_b, max_b): |
|
62
|
|
|
theta_1 = b * self.q - a * self.p + m + n |
|
63
|
|
|
theta_2 = b * self.q + a * self.p + m + n |
|
64
|
|
|
yield theta_1, theta_2 |
|
65
|
|
|
|
|
66
|
|
|
def __tidy_intersections(self, intersections): |
|
67
|
|
|
tidied_intersections = [{} for k in self._ks] |
|
68
|
|
|
for m, n, theta_1, theta_2 in intersections: |
|
69
|
|
|
tidied_intersections[m][theta_1] = (n, theta_2) |
|
70
|
|
|
tidied_intersections[n][theta_2] = (m, theta_1) |
|
71
|
|
|
return tidied_intersections |
|
72
|
|
|
|
|
73
|
|
|
def __make_ends(self, tidied_intersections): |
|
74
|
|
|
ref_ends = list(self.__make_ref_ends(tidied_intersections)) |
|
75
|
|
|
yield ref_ends |
|
76
|
|
|
ref_ends = {e.theta: e for e in ref_ends} |
|
77
|
|
|
for k in range(1, self.d): |
|
78
|
|
|
yield list(self.__make_string_ends(ref_ends, tidied_intersections, k)) |
|
79
|
|
|
|
|
80
|
|
|
def __make_ref_ends(self, tidied_intersections): |
|
81
|
|
|
for (i, theta) in enumerate(sorted(tidied_intersections[0].iterkeys())): |
|
82
|
|
|
yield End(theta, (-1)**i) |
|
83
|
|
|
|
|
84
|
|
|
def __make_string_ends(self, ref_ends, tidied_intersections, k): |
|
85
|
|
|
for theta in tidied_intersections[k].iterkeys(): |
|
86
|
|
|
altitude = ref_ends[(theta - 2 * k) % (self.__max_theta)].altitude |
|
87
|
|
|
yield End(theta, altitude) |
|
88
|
|
|
|
|
89
|
|
|
def __make_segments(self, ends): |
|
90
|
|
|
for string_ends in ends: |
|
91
|
|
|
yield list(self.__make_string_segments(string_ends)) |
|
92
|
|
|
|
|
93
|
|
|
def __make_string_segments(self, string_ends): |
|
94
|
|
|
for begin, end in zip(string_ends, string_ends[1:]): |
|
95
|
|
|
yield Segment(begin, end) |
|
96
|
|
|
yield Segment( |
|
97
|
|
|
string_ends[-1], |
|
98
|
|
|
End(string_ends[0].theta + self.__max_theta, string_ends[0].altitude) |
|
99
|
|
|
) |
|
100
|
|
|
|
|
101
|
|
|
def __make_bridges(self, tidied_intersections, segments): |
|
102
|
|
|
segs_by_begin = [{s.begin.theta: s for s in string_segments} for string_segments in segments] |
|
103
|
|
|
segs_by_end = [{s.end.theta: s for s in string_segments} for string_segments in segments] |
|
104
|
|
|
for k, string_segments in enumerate(segments): |
|
105
|
|
|
yield list(self.__make_string_bridges(tidied_intersections, segs_by_begin, segs_by_end, k, string_segments)) |
|
106
|
|
|
|
|
107
|
|
|
def __make_string_bridges(self, tidied_intersections, segs_by_begin, segs_by_end, k, string_segments): |
|
108
|
|
|
assert len(string_segments) % 2 == 0 |
|
109
|
|
|
it = iter(string_segments) # Inspired by grouper in https://docs.python.org/2/library/itertools.html#recipes |
|
110
|
|
|
if string_segments[0].end.altitude != 1: |
|
111
|
|
|
after = it.next() |
|
112
|
|
|
before = self.__rotate_segment(string_segments[-1]) |
|
113
|
|
|
yield self.__make_bridge(tidied_intersections, segs_by_begin, segs_by_end, k, before, after) |
|
114
|
|
|
for before, after in zip(it, it): |
|
115
|
|
|
yield self.__make_bridge(tidied_intersections, segs_by_begin, segs_by_end, k, before, after) |
|
116
|
|
|
|
|
117
|
|
|
def __rotate_segment(self, segment): |
|
118
|
|
|
return Segment( |
|
119
|
|
|
End(segment.begin.theta - self.__max_theta, segment.begin.altitude), |
|
120
|
|
|
End(segment.end.theta - self.__max_theta, segment.end.altitude), |
|
121
|
|
|
) |
|
122
|
|
|
|
|
123
|
|
|
def __make_bridge(self, tidied_intersections, segs_by_begin, segs_by_end, k, before, after): |
|
124
|
|
|
assert before.end.theta == after.begin.theta |
|
125
|
|
|
assert before.end.altitude == after.begin.altitude == 1 |
|
126
|
|
|
n, theta_2 = tidied_intersections[k][before.end.theta] |
|
127
|
|
|
tunnel = self.__make_tunnel(segs_by_begin, segs_by_end, n, theta_2) |
|
128
|
|
|
bridge = Bridge(before, after, tunnel) |
|
129
|
|
|
if self.p < 3 or self.q < 3: |
|
130
|
|
|
return self.__shorten_bridge(bridge) |
|
131
|
|
|
else: |
|
132
|
|
|
return bridge |
|
133
|
|
|
|
|
134
|
|
|
def __make_tunnel(self, segs_by_begin, segs_by_end, n, theta_2): |
|
135
|
|
|
if theta_2 in segs_by_end[n]: |
|
136
|
|
|
bef_tunnel = segs_by_end[n][theta_2] |
|
137
|
|
|
else: |
|
138
|
|
|
bef_tunnel = self.__rotate_segment(segs_by_end[n][theta_2 + self.__max_theta]) |
|
139
|
|
|
aft_tunnel = segs_by_begin[n][theta_2] |
|
140
|
|
|
return Tunnel(n, bef_tunnel, aft_tunnel) |
|
141
|
|
|
|
|
142
|
|
|
def __shorten_bridge(self, bridge): |
|
143
|
|
|
return Bridge( |
|
144
|
|
|
Segment(End((bridge.before.begin.theta + bridge.before.end.theta) / 2, 0), bridge.before.end), |
|
145
|
|
|
Segment(bridge.after.begin, End((bridge.after.begin.theta + bridge.after.end.theta) / 2, 0)), |
|
146
|
|
|
Tunnel( |
|
147
|
|
|
bridge.tunnel.k, |
|
148
|
|
|
Segment( |
|
149
|
|
|
End((bridge.tunnel.before.begin.theta + bridge.tunnel.before.end.theta) / 2, 0), |
|
150
|
|
|
bridge.tunnel.before.end |
|
151
|
|
|
), |
|
152
|
|
|
Segment( |
|
153
|
|
|
bridge.tunnel.after.begin, |
|
154
|
|
|
End((bridge.tunnel.after.begin.theta + bridge.tunnel.after.end.theta) / 2, 0) |
|
155
|
|
|
), |
|
156
|
|
|
), |
|
157
|
|
|
) |
|
158
|
|
|
|
jacquev6 /
DrawTurksHead
