2017年4月20日 星期四

Python - 密碼圖(Cipher Map)，學習二維陣列的翻轉以及zip的使用

本題的題目網址：

https://py.checkio.org/mission/cipher-map2/





這題目非常有趣
也花了我好幾天解題

以下是題目的大意

題目將會給兩個4*4的二維陣列

一個陣列顯示了共16位英文字母，做為密碼圖

另一個陣列是格柵板子，與密碼圖疊放之後僅會露出四個格子
依序由上往下、由右往左的方式
就可以拿到密碼

接著，必須再把格柵轉順時針轉90度
一樣依序由上往下、由右往左的方式，拿到第二組密碼

總共必須要轉三次，共四組密碼16位回傳成string即可
由下面題目給的code可知，X代表隔柵的露出位置。

recall_password(
    ('X...',
     '..X.',
     'X..X',
     '....'),
    ('itdf',
     'gdce',
     'aton',
     'qrdi')) == 'icantforgetiddqd'
​
recall_password(
    ('....',
     'X..X',
     '.X..',
     '...X'),
    ('xhwc',
     'rsqx',
     'xqzz',
     'fyzr')) == 'rxqrwsfzxqxzhczy'

基本上
這題需要兩個步驟

1.match兩個二維陣列，找到密碼
2.如何將格柵轉90度


首先要先解決如何match兩個二維陣列
我的想法是

用雙重迴圈控制格柵搜索
搜索方式由上往下，由i迴圈控制
由右往左，由j迴圈控制，蠻直覺，因為一般迴圈都是這樣搜索，沒有特別設定方向
假設遇到 cipher_grillle 的值為'X'，就確定 cipher_password的值是密碼

註：cipher_grillle為二維陣列的格柵；cipher_password為二維陣列的密碼

#cipher_grille為傳進來的二維陣列，代表格柵
for i in range(len(cipher_grille)):
    for j in range(len(cipher_grille[i])):
        if cipher_grille[i][j] == 'X':
            result+=ciphered_password[i][j]

接下來就是要將格柵順時針轉90度
一開始我的想法錯誤，因此卡關卡了很久

但只要畫圖出來就非常容易理解

如下圖

這是還沒原本還未轉矩陣的格柵圖，用數字代表每一格的位置

1234
5678
9101112
13141516

接著順時針轉90度後，我們發現會變成這樣的情況

13951
141062
151173
161284

也就是說以1~4為例，當我們提取：
原本1這個位置 [0][0]，就會放到 [0][3]
原本2這個位置 [0][1]，就會放到 [1][3]
原本3這個位置 [0][2]，就會放到 [2][3]
原本4這個位置 [0][3]，就會放到 [3][3]


但是實作上後來參考了論壇的討論
用另一個方式看
在撰寫上比較直觀

這是原本的格柵

481216
371115
261014
15913

順時針轉90度後變成

1234
5678
9101112
13141516

因為這使得我們要轉置的時，可以用正常的順序放格柵
抓取的方式因而變成下面的樣子
原本1這個位置 [3][0]，就會放到 [0][1]
原本2這個位置 [2][0]，就會放到 [0][2]
原本3這個位置 [1][0]，就會放到 [0][3]
原本4這個位置 [0][0]，就會放到 [0][4]

因此，我們可以另開一個function做為旋轉密碼圖來操作

一邊一樣以跑X的方式雙重迴圈搜索，新的格柵假設是new_grille用正常的方式放入元素
另一邊的拿取則是由 i 為倒序 (先用back做一個倒序串列)，j為正序的方式拿取

def rotation(grille):
    back = [i-1 for i in range(4,0,-1)] #3,2,1,0
        new_grille = ['' * 4 for i in range(4)]  #新格柵 印出會變成 ('','','','')
            for i in range(len(grille)):
               for j in range(len(grille[i])):
                   new_grille[i]+=grille[back[j]][i]
    print (new_grille)

rotation(('XXXX','....','....','....'))
#output: '...X', '...X', '...X', '...X'


綜合了兩者
只要讓抓取密碼的跑四次，並每跑完一次就call rotation函數
即可解決本次題目

但後來完成後
發現有多數人使用 zip 這個函數來完成旋轉

先看一下程式碼

def rotation(grille):
   return list(zip(*grille[::-1]))

rotation(('XXXX','....','....','....'))
#output: '...X', '...X', '...X', '...X'

先來解釋一下zip這個函數
主要拿來對陣列做處理

此網頁對zip的功用做了一些解釋和操作
可以參考
https://puremonkey2010.blogspot.tw/2015/10/python-python-zip.html

簡單來說zip可以幫忙兩個list進行打散重新分配

a = [1,2,3]
b = [4,5,6]

c = zip(a,b)
print (c)
#output (1, 4), (2, 5), (3, 6)

如果a和b長度不一，就只會回傳最短長度的重新分配並回傳tuple的list

而*的使用主要在有二維陣列時的打散分配
例如

k = [[1,2],[3,4]]

print (zip(*k))
#output (1, 3), (2, 4)

那這題可以使用到的原因是
我們發現順時針轉向時
其實也有打散重新分配的味道

舉例來看
1-4原本都在同行
順時針轉後，全部都在不同行上
因此zip可以派上用場

只是轉完之後，會發現這個問題

def rotation(grille):
    return list(zip(*grille))

rotation(('XXXX','....','....','....'))
#output: 'X...', 'X...', 'X...', 'X...'

因此要做倒序放置
回頭來看這個程式碼
list(zip(*grille[ a : b: c])

a代表控制了要把第幾個陣列打散分配

假設我們的二維陣列長('abcd','efgh','ijkl','mnop')

a=2 即是只把 efgh打散分配到四個陣列，變成('e','f','g','h')

b代表控制要打散分配後每一陣列共有幾個元素

b=3 即是把每個一維陣列只要三個元素，並重新分配到四個陣列
變成 ('aei','bfj','cgk','dhl')
由於只要三個元素，因次第四個陣列就被捨棄

最後c是代表正序還是倒序分配

但我目前比較疑惑的是
a:b:c都填的話交互作用，並沒有我想像中的容易理解
因此我上述所提及的控制，皆指單填一個控制變相下的結果

因此有了這個方法
我們可以很輕鬆使用zip函式來完成目的

以下是我最後的程式碼：

def rotate(cipher_grille):
   return list(zip(*cipher_grille[::-1]))

def recall_password(cipher_grille, ciphered_password):
   result = ''
     for k in range(4):
        for i in range(len(cipher_grille)):
            for j in range(len(cipher_grille[i])):
                if cipher_grille[i][j] == 'X':
                    result+=ciphered_password[i][j]
        cipher_grille = rotate(cipher_grille)
   return result

這題解完後
發現原來有函式可以import進來就可以解決

import numpy
裡面有個function 是 rot90
預設是逆時針轉
參數設-1的話可以順時針轉

https://docs.scipy.org/doc/numpy/reference/generated/numpy.rot90.html

以上應該是這次學到的三種二維陣列的轉置方法
於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)