-
Notifications
You must be signed in to change notification settings - Fork 0
/
L_Shape.py
182 lines (166 loc) · 6.09 KB
/
L_Shape.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
import showit
from typing import NewType
dir = 0 #global variable that decides wheter the first or last available color is chosen in the `colourize()` method
states = []
EXPORT = False #Controls if animation is saved as .gif or displayed via matplotlib
def fillist(n: int, c=0) -> list:
ret = []
for x in range(0,n):
if type(c)==list:ret.append(c.copy())
else: ret.append(c)
return ret
Matrix = NewType('Matrix',list) #for type annotations
class Matrix(list):
'''Matrix class, initialize n x m matrix by `matrix(n,m)`
get i-th row of some matrix m by m[i]
get j-th element of i-th row by m[i][j]
setting works the same way,
len returns amount of elements'''
def __init__(self,m: int,n=0,c=0,mother=0,motherkey=0) -> Matrix:
self.mother = self.motherkey = 0
if n==0:n=m
if c==0:c=fillist(n)
if mother!=0:
self.mother = mother
self.motherkey = motherkey
self.m = m
self.n = n
self.id = fillist(m,c)
def __str__(self) -> str:
ret = ""
for x in self.id:
ret+="|"
for y in x:
ret += " "+str(y)+" "
ret+="|\n"
return ret
def copy(self) -> list:
'''returns list of lists with the values of the matrix, copy of `self.id`'''
new = []
for i in range(len(self.id)):
new.append(self.id[i].copy())
return new
def __getitem__(self,key): #don't touch
'''it works so let's not touch it'''
try:return Matrix(1,c=self.id[key],mother=self,motherkey=key)
except IndexError:
return self.id[0][key]
def __setitem__(self,key,value) -> None: #touch even less
'''it works so let's not touch it (!)'''
if self.mother !=0:
self.mother.id[self.motherkey][key] = value
else:
self.id[key] = value
def __len__(self) -> int:
return self.m*self.n
def filldict(n: int, s: int, thedict={}) -> dict:
'''recursively generates a dictionary that for key i contains all coordinates of
upper left corners of an i*i square in a n*n square'''
thedict[s] = []
for i in range(0,n,s):
for j in range(0,n,s):
thedict[s].append((i,j))
if s==2:
return thedict
else:
return filldict(n,int(s/2),thedict)
def search(x: int, y: int, targets: list, s: int) -> list:
'''finds the coordinates of all fields in the s*s square that contains (x,y)'''
for i in targets: #targets is list of upper left corner fields of s*s squares -> targets comes from the dict generated by `filldict()`
if x not in range(i[0],i[0]+s) or y not in range(i[1],i[1]+s): #prevent useless iterations
continue
gotchas = []
for k in range(0,s):
for j in range(0,s):
gotchas.append((i[0]+j,i[1]+k))
return gotchas
def center(point : tuple, s: int) -> list:
'''gives the 4 center point coordinates of a s sized square that has its upper left edge at point'''
manip = int(s/2)
centerpoints = [
(point[0]+manip-1,point[1]+manip-1),
(point[0]+manip,point[1]+manip-1),
(point[0]+manip-1,point[1]+manip),
(point[0]+manip,point[1]+manip)
]
return centerpoints
def colourize(points: list, mat: Matrix) -> None:
'''Looks at all fields surrounding the three given as list of coordinates
selects an available color for coloring and colors the fields accordingly
if no valid coloring can be found (probably only very rarely) the current
fields are marked brightly and the matrix is displayed '''
global dir
cols = [1,25,50,75,100]
changes = (
(0,1),
(0,-1),
(1,0),
(-1,0),
)
if(len(points)!= 3):
raise ValueError("False len of input")
surround = []
for (x,y) in points:
for (a,b) in changes:
new = (x+a,y+b)
if new not in surround: surround.append(new)
surround = list(filter(lambda x: x[0]>0 and x[0]<len(mat.id) and x[1]>0 and x[1]<len(mat.id[0]),surround )) #filter ivalid coords
for (x,y) in surround:
colFound = mat.id[x][y]
if colFound in cols:
cols.remove(colFound)
try:toColor = cols[0]
except IndexError:
print(len(cols))
for (x,y) in points:
mat[x][y] = 999
states.append(mat.copy())
showit.animo(states,len(mat.id))
dir = 0 if dir <0 else -1 #more change between the selected color
for (x,y) in points:
mat[x][y] = toColor
def fillit(squaredict: dict, coords: tuple, mat: Matrix, n: int) -> Matrix:
'''Main method, recursively fills the given square with L Shapes, kinda bottom up i guess'''
global states
if n==2:
therest = search(coords[0],coords[1],squaredict[n],n)
therest.remove((coords[0],coords[1])) #remove the field that is already marked
colourize(therest,mat) #colorize the 3 fields in therest while making sure there are no color collisions
states.append(mat.copy()) # add current state for visualization
else:
mat = (fillit(squaredict,coords,mat,int(n/2))) #recursion
thepoint = search(coords[0],coords[1],squaredict[n],n)
ctp = center(thepoint[0],n)
for i in ctp:
if(mat[i[0]][i[1]]) !=0:ctp.remove(i)
buoys = []
if len(ctp)>3:
raise ValueError
for i in ctp: #ctp = centerpoints
buoys.append(search(i[0],i[1],squaredict[int(n/2)],int(n/2)))
colourize(ctp,mat)
states.append(mat.copy())
therealG = []
for i in buoys:
for j in i:
if(mat.id[j[0]][j[1]] !=0):
therealG.append(j)
for i in therealG:
mat = fillit(squaredict,i,mat,int(n/2))
return (mat)
def doit(n: int, y: int, x: int) -> None:
'''Prepares variables and starts filling process
works on a n*n square where the initially removed field is at (x,y)'''
global states
coords = (x,y)
mat = Matrix(n) #generates empty (filled with 0) matrix, if only one var is give the matrix will be quadratic
mat[x][y] = 200
states.append(mat.copy()) #add initial state of matrix for visualization
squaredict = filldict(n,n) #dict with beginning coords (upper left) for every possible 2^k with k<=n square that fits inside nxn field, keys are 2^k
mat = fillit(squaredict,coords,mat,n)
showit.animo(states,n,EXPORT) #visualize
if __name__ == '__main__':
n = int(input("give the dimensions (must be a power of 2): \n"))
x = int(input("give an x coordinate, must be an integer and positive: \n"))
y = int(input("give an y coordinate, must be an integer and positive: \n"))
doit(n,x,y)