NPAProgComp2019/MainQ4.py at master · printlnHi/NPAProgComp2019 · GitHub

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
from random import randint

n = int(input())

grid = []
for y in range(n):
    grid.append([])
    for x in range(n):
        if y % 2 == 0:
            grid[y] = [1]*n
        elif (y-1) % 4 == 0:
            grid[y] = [0]*n
            grid[y][0] = 1
        else:
            grid[y] = [0]*n
            grid[y][n-1] = 1

ends = [[0,n-1],[n-1,]]

def getZeros(x,y):
    adj=[]
    if y+1 < n:
        if grid[x][y+1] == 0:
            adj.append((x,y+1))
    if y-1 >= 0:
        if grid[x][y-1] == 0:
            adj.append((x,y-1))
    if x+1 < n:
        if grid[x+1][y] == 0:
            adj.append((x+1,y))
    if x-1 >= 0:
        if grid[x-1][y] == 0:
            adj.append((x-1,y))
    return adj

def getAll(x,y):
    adj=[]
    if y+1 < n:
        adj.append((x,y+1))
    if y-1 >= 0:
        adj.append((x,y-1))
    if x+1 < n:
        adj.append((x+1,y))
    if x-1 >= 0:
        adj.append((x-1,y))
    return adj

def getAdj(x,y):
    adj=[]
    if y+1 < n:
        if grid[x][y+1] == 1:
            adj.append((x,y+1))
    if y-1 >= 0:
        if grid[x][y-1] == 1:
            adj.append((x,y-1))
    if x+1 < n:
        if grid[x+1][y] == 1:
            adj.append((x+1,y))
    if x-1 >= 0:
        if grid[x-1][y] == 1:
            adj.append((x-1,y))
    return adj

adj = []
ends = []
for y in range(n):
    adj.append([])
    for x in range(n):
        adj[y].append(len(getAdj(y,x)))
        if(len(getAdj(y,x))) == 1:
            ends.append((y,x))

print("##initial grid\n")
for y in range(n):
    print("".join([str(x) for x in grid[y]]).replace("1","+").replace("0"," "))
print("\n\n")

tail = ends[randint(0,1)]
poss = getZeros(tail[0],tail[1])

print("tail: " + str(tail) + " link: " + str(poss))

testing = 0

while True:
    testing = poss[randint(0,len(poss)-1)]
    if adj[testing[0]][testing[1]] != 3:
        break

for pot in getAll(testing[0],testing[1]):
    adj[pot[0]][pot[1]] += 1

for pot in getAdj(testing[0],testing[1]):
    if adj[pot[0]][pot[1]] != 3:
        continue
    else:
        for padj in getAdj(pot[0],pot[1]):
            if padj != testing:
                #potential break
                seen = set([padj])
                current = 0
                for temp in getAdj(padj[0],padj[1]):
                    if temp != pot:
                        current = temp

                while True:
                    for temp in getAdj(current[0],current[1]):
                        if temp not in seen:
                            seen.add(temp)
                            current = temp
                        if temp == pot:
                            break
                        else:
                            #loop
                            continue