Python 程式解題 (1)

編輯 : Frank
日期 : 2019/08/01
參考網站

題目: Screen Locking Patterns

題目內容

解題觀念:

了解所有移動方式

幫助所有節點去設置所有可滑動方向的路徑，分別有以下組合:
左上,上,右上,左,右,左下,下,右下
左左上,右右上,左左下,右右下
左上上,右上上
(共16筆)

透過 dict 型態來存取節點(key)和可滑動方向路徑(value)

{
‘A’:[左上,右上,….]
‘B’:[左上,右上,….]
……
}

每個節點的可滑動方向路徑順序存取需一致，可解決節點已使用的問題
如若可滑動方向路徑上無節點,宣告為’null’

尋找所有節點的走訪

透過遞迴函數來持續往下進行節點的滑動

若可移動方向節點為’null’,則不做事
若節點已使用過,則根據相同方向探索下一個節點

解題程式碼:

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
#coding:utf-8

# 探討節點的移動方式
def getlink(i,j):

    element_link = [] # 該節點的移動方式
  
    if i-1 >= 0 and j-1 >= 0:
        element_link.append(map[i-1][j-1])
    else:
        element_link.append('null')
    if j-1 >= 0:
        element_link.append(map[i][j-1])
    else:
        element_link.append('null')
    if i+1 < 3 and j-1 >= 0:
        element_link.append(map[i+1][j-1])
    else:
        element_link.append('null')
    if i-1 >= 0:
        element_link.append(map[i-1][j])
    else:
        element_link.append('null')
    if i+1 < 3:
        element_link.append(map[i+1][j])
    else:
        element_link.append('null')
    if i-1 >= 0 and j+1 < 3:
        element_link.append(map[i-1][j+1])
    else:
        element_link.append('null')
    if j+1 < 3:
        element_link.append(map[i][j+1])
    else:
        element_link.append('null')
    if i+1 < 3 and j+1 < 3:
        element_link.append(map[i+1][j+1])
    else:
        element_link.append('null')
    if i-2 >= 0 and j-1 >= 0:
        element_link.append(map[i-2][j-1])
    else:
        element_link.append('null')
    if i+2 < 3 and j-1 >= 0:
        element_link.append(map[i+2][j-1])
    else:
        element_link.append('null')
    if i+2 < 3 and j+1 < 3:
        element_link.append(map[i+2][j+1])
    else:
        element_link.append('null')
    if i-2 >= 0 and j+1 < 3:
        element_link.append(map[i-2][j+1])
    else:
        element_link.append('null')
    if i+1 < 3 and j+2 < 3:
        element_link.append(map[i+1][j+2])
    else:
        element_link.append('null')
    if i+1 < 3 and j-2 >= 0:
        element_link.append(map[i+1][j-2])
    else:
        element_link.append('null')
    if i-1 >= 0 and j-2 >= 0:
        element_link.append(map[i-1][j-2])
    else:
        element_link.append('null')
    if i-1 >= 0 and j+2 < 3:
        element_link.append(map[i-1][j+2])
    else:
        element_link.append('null')
    
    return element_link

map = [['A','B','C'],['D','E','F'],['G','H','I']] # 節點的位置分佈
all_link = {} # 所有節點的移動方式
sum = 0 # 計算路線整體次數

# 探討所有節點的移動方式，並完成all_link的建置
for i in range(3):
    for j in range(3):
        all_link[map[i][j]] = getlink(i,j)

# 遞迴捕捉所有移動方式(移動剩餘次數,移動的節點,未使用的節點,上一個移動路徑,存取節點移動路徑)
# 移動次數:可判斷是否停止移動
# 未使用的節點:可判斷該節點是否被使用
# 上一個移動路徑: 當節點已使用時，透過此路徑可進行節點穿越的動作
# 存取節點的移動路徑:僅供除錯與檢查使用,可以不宣告
def re(count,point,element,i,path):
    global sum
    # 判斷此移動節點是否使用過
    if point in element:
        # 是否可停止移動
        if count == 0:
            # 顯示移動方式
            print path+point
            sum+=1
        else:
            # 移除此節點，代表該節點已被使用
            element = element.replace(point,'')
            # 透過該節點進行下一個節點的移動
            for i in range(16):
                if all_link[point][i] != 'null':
                    re(count-1,all_link[point][i],element,i,path+point)
    else:
        # 根據使用過的移動節點，再次探索同方向的下一個節點
        if all_link[point][i] != 'null':
            re(count,all_link[point][i],element,i,path)
            
def count_patterns_from(firstPoint, length):

    global sum
    # 刷新sum數值
    sum = 0
    # 所有節點元素
    element = 'ABCDEFGHI'   
    # 解決特殊情形
    if length < 1 or length > 9 or firstPoint not in element:
        return 0
    else:
        # 404可隨意設置，第一個節點不會使用到此參數
        re(length-1,firstPoint,element,404,'')
        return sum

另類解法

  1. 提前運算所有答案，並存入陣列備用
    • 優點: 不論count_patterns_from執行多少次，都可快速得知答案
    • 解題技巧: 可將答案分為此三類[ACGI,BDFH,E],不需所有節點都運算
  2. 存取可移動路徑與穿越路徑(無須存取路徑為null的節點)
    • 優點: 無須探索所有方向的移動路徑

Frank_huang 另類解法 2

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
#coding:utf-8


sum = 0 # 計算路線整體次數

DIRECT = {'A':set('BFEHD'), 'B':set('ACFIEGD'), 'C':set('BFHED'), 'D':set('ABCEIHG'),
            'E':set('ABCDFGHI'), 'F':set('ABCEGHI'), 'G':set('DBEFH'), 
            'H':set('GDAECFI'), 'I':set('HDEBF')}
OVER = {'A':{'B':'C', 'E':'I', 'D':'G'}, 'B':{'E':'H'}, 'C':{'B':'A', 'E':'G', 'F':'I'}, 'D':{'E':'F'},
           'F':{'E':'D'}, 'G':{'D':'A', 'E':'C', 'H':'I'}, 'G':{'D':'A', 'E':'C', 'H':'I'},
           'H':{'E':'B'}, 'I':{'H':'G', 'E':'A', 'F':'C'}, 'E':{}}

# 遞迴捕捉所有移動方式(移動剩餘次數,移動的節點,未使用的節點,存取節點移動路徑)
# 移動次數:可判斷是否停止移動
# 未使用的節點:可判斷該節點是否被使用
# 存取節點的移動路徑:僅供除錯與檢查使用,可以不宣告
def re(count,point,element,path):
    global sum
    # 移除此節點，代表該節點已被使用
    element = element.replace(point,'')

    if count == 0:
        # 顯示移動方式
        #print path
        sum+=1
    else:
    # 透過該節點進行下一個節點的移動
        for i in DIRECT[point]:
            if i in element:
                re(count-1,i,element,path+i)
            else:
                if i in OVER[point] and OVER[point][i] in element:
                    re(count-1,OVER[point][i],element,path+point)
                    
def count_patterns_from(firstPoint, length):

    global sum
    # 刷新sum數值
    sum = 0
    # 所有節點元素
    element = 'ABCDEFGHI'   
    # 解決特殊情形
    if length < 1 or length > 9 or firstPoint not in element:
        return 0
    else:
        re(length-1,firstPoint,element,firstPoint)
        return sum
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
for epoch in range(200):

        all_pred = []
        all_target = testY
        sum = 0

        for step, x in enumerate(trainX):
                b_x = x.view(BATCH_SIZE,TIME_STEP,DATA_SIZE)
                b_y = trainY[step].view(BATCH_SIZE,1)

                output = cnnlstm(b_x)
                loss = loss_func(output,b_y)
                optimizer.zero_grad()
                loss.backward()
                optimizer.step()

                for i in range(len(output)):
                        sum = sum + pow((float(output[i]) - float(b_y[i])),2)

        sum = sum/(BATCH_SIZE*STEP_SIZE)
        train_rmse = math.sqrt(sum)

        if epoch % 10 == 0:

                output = cnnlstm(testX)

                sum = 0
                for i in range(len(output)):
                        sum = sum + pow((float(output[i]) - float(testY[i])),2)
                        all_pred.append(round(float(output[i]),6))

                sum = sum / len(output)
                test_rmse = math.sqrt(sum)

                print('Epoch:',epoch)
                print('Target:',all_target)
                print('Pred:',all_pred)
                print('Train_RMSE:',train_rmse)
                print('Test_RMSE:',test_rmse)
                print('Loss:',loss)
                print('==============================================')