# 計算機程式設計HW
## 共五題
1. 賓果遊戲
2. 部落旅遊(BFS Application)
3. 理想大學環境
4. 黃金分配
5. 基因序列
### 賓果遊戲
第一行，輸入整數 N、M ( 1 <= M < N×N )。
第二行，輸入 A 的 N×N 個數字，代表 A 的賓果宮格。
第三行，輸入 B 的 N×N 個數字，代表 B 的賓果宮格。
第四行，輸入M 個數字，表示賓果數字。
輸入範例：
3 7
1 2 3 4 5 6 7 8 9
2 3 4 5 1 6 9 7 8
7 2 3 6 9 8 4
輸出範例：
A Win
```python=
def checkBingo(data, store, num, N):
row, col = data.index(num)//N, data.index(num)%N
store[row] += 1
store[col + N] += 1 #從Ｎ開始紀錄col的value
if row == col:
store[N*2] += 1
if row == (N-1-col):
store[N*2+1] += 1
def compute(data, selected, N):
store = [0 for i in range(2*N+2)]#init 連線紀錄
for num in selected:
checkBingo(data, store, num, N)
print(store)
if N in store:return 'Bingo'
return 'sorry'
#print(compute([1,3,5,7,9,2,4,6,8],[1,2,3,5],3))
def compete(dataA, dataB, selected, N, M):
storeA = [0 for i in range(2*N+2)]
storeB = [0 for i in range(2*N+2)]
for num in selected:
checkBingo(dataA, storeA, num, N)
checkBingo(dataB, storeB, num, N)
if N in storeA and N in storeB:
return 'Tie'
elif N in storeA:
return 'A win'
elif N in storeB:
return 'B win'
return 'Tie'
def main():
inputData = input().split()
N, M = int(inputData[0]), int(inputData[1])
dataA = input().split()
dataB = input().split()
selected = input().split()
print(compete(dataA, dataB, selected , N, M))
main()
```
### 部落旅遊
輸入說明：
第一行 N, X, Z, Y，N 是道路數量，X 代表起始點城市，Z 代表終點城市，Y 代表必經城市，
若沒有 Y，則不考慮中途點。
其後 N 行，每一行輸入格式為 A B，代表 A 城市與 B 城市間有道路相連接。
輸出說明：
找出 X 中途經過 Y 城市抵達 Z 的路徑，
若存在，則輸出走過最少通道個數與最短路徑。
若不存在此路徑，輸出 NO。
輸入範例 1：
6 1 3
1 5
7 5
4 5
3 5
2 3
4 3
輸出範例 1：
2
1 5 3
--------------------------------------------------------------------------------------------------------------
輸入範例 2：
6 1 4 3
1 2
1 3
2 4
2 5
3 5
5 4
輸出範例 2：
3
1 3 5 4
```python=
def addAdj(graph, edge, y):#adjacent
Adj = graph[edge] if edge in graph.keys() else []#'1':[2,5] #'1':[]
if y not in Adj: Adj.append(y)#'1':[2,5,3]
graph[edge] = Adj#restored
def addPair(graph, pair):#[1, 3] cuz of undirected graph
addAdj(graph,pair[0],pair[1])
addAdj(graph,pair[1],pair[0])
def BFS(graph, source, target):#graph, 1, 3
visitedNodes = dict() #拜訪過(black)
queue = [[source, 0]] #gray
while True:
if len(queue) == 0: return -1 #此圖空了
currentNode = queue.pop(0)
currentNodeName = currentNode[0]#node = '1'
level = currentNode[1]#level = 0
if currentNodeName == target: #find it
path = findPath(graph, visitedNodes, currentNodeName, level - 1)
return level, path
visitedNodes[currentNodeName] = level #存入至拜訪過的node
for node in graph[currentNodeName]:#visit adj node
if node not in visitedNodes.keys():#if the node haven't visited
queue.append([node, level + 1])
def findPrevNode(graph, visitedNodes:dict, targetNode, level):
nodeCandidate = []
for nodeName, nodeLevel in visitedNodes.items():
if nodeLevel == level:
nodeCandidate.append(nodeName)
for nodeName in nodeCandidate:
if targetNode in graph[nodeName]:
return nodeName
def findPath(graph, visitedNodes:dict, currentNodeName, level):
path = []
while level >= 0:
nodeName = findPrevNode(graph, visitedNodes, currentNodeName, level)
path.append(nodeName)
level = level - 1
currentNodeName = nodeName#將現在的點作為基準點
return path
#top down method
def main():
graph = dict()
#eg.{'1':[3,5,6],
# '3':[1,2,4]
# '4':[3]}
edge = []
par = input().split()#eg.6 1 3 implies 6(edges),1 to 3
#preprocessing
for i in range(int(par[0])):
edge.append(input().split())
for pair in edge:
addPair(graph, pair)
#start
if len(par) == 3:
res = BFS(graph, par[1], par[2])
#print('start')
if res == -1:#level = -1 不存在
print('No')
else:
res[1].reverse()
print(res[0])
print(*res[1], par[2])
elif len(par) == 4:
resFirstHalf = findAdj(graph,par[1],par[3])#前半段
resSecondHalf = findAdj(graph,par[3],par[2])#後半段
if resFirstHalf == -1 or resSecondHalf == -1:
print('NO')
else:
resFirstHalf[1].reverse()
resSecondHalf[1].reverse()
print(resFirstHalf[0]+resSecondHalf[0])
print(*resFirstHalf[1],*resSecondHalf[1],par[2])
main()
```
### 理想大學環境
輸入說明：
第一行，輸入一個正整數 N，代表房屋個數 N ，( 1<= N <=10 )。
其後 N 行，每一行第一項為房屋名稱，接著為其屬性。
房屋名稱最多有 15 個字母，各屬性為 2 個字母。
房屋與屬性資料均為英文字母組成，房屋名稱及各屬性間以 1 個空白分隔。
接下來一行，輸入一個正整數 M，為查詢條件，( 1<= M <=10 )
其後 M 行，每一行有一個查詢。查詢條件為房屋屬性組成，每個房屋屬性為 2 個字元。
用 + 號區格的條件代表"或" 的關係，沒有 + 區隔的條件代表 "且" 的關係。
屬性間及 + 之間有 1 個空白間隔。例如： GF BS + CT RH
代表需找出【有美食且為學區房】或【交通方便且為毛胚屋】的所有房屋名稱。
其格式如下：XX YY + AA BB 意思為屬性條件為: XX 且 YY，或是 AA 且 BB。
最後一 行輸入一個正整數 b，
當 b=0時，代表輸出能符合條件的房屋。
例如：條件 GF BS + CT RH，房屋屬性 PMansion CT BS PS RH ，
則 PMansion 符合條件。
當 b=1，代表輸出符合最多條件的房屋。
例如：條件 GF BS + CT RH，房屋屬性 PMansion CT BS PS RH、 AgoraGarden GF CT BS RH PS，則輸出 AgoraGarden。
輸出說明：
根據每個查詢條件輸出所有符合之房屋名稱。如有 M 個查詢條件，即會有 M 行輸出。
若一個查詢條件中有多個房屋符合，請按照字典序排序各房屋名稱，房屋間以一個空白分隔。
--------------------------------------------------------------------------------------------------------------
輸入範例 1：
5
AgoraGarden GF CT BS RH PS
PMansion CT BS PS RH
JingAnMansion BS NP CT
DaAnPark NP CT SH
SinZhangCity NH BS SH
2
BS RH + CT SH
GF + NM BS + NH SH
0
輸出範例 1：
AgoraGarden DaAnPark PMansion
AgoraGarden SinZhangCity
```python=
def getData():
mapTable = {}
n = int(input())
for i in range(n):
item = input().split()
mapTable[item[0]] = set(item[1:])
return mapTable
def match(requirements, feature, b):
clauses = requirements.split('+')
maxNum = 0
for i in range(len(clauses)):
if b == 0:
if feature.issuperset((set(clauses[i].split()))):#物件的特徵是否超過要求
return -1
if b == 1:
k = len(feature&set(clauses[i].split()))#看多少set重複
if k >= len(clauses[i].split()):maxNum += 1#此物件特徵滿足該clause中所有要求
return maxNum
def compute(requirements, unsortedMapTable, b):
data = {}
#原傳入unsorted
sortedMapTable = {}
for key in sorted(unsortedMapTable):
sortedMapTable[key] = unsortedMapTable[key]
for name, feature in sortedMapTable.items():
data[name] = match(requirements, feature, b)
if b == 0:
for name in data.keys():
if data[name] == -1:
print(name, end = ' ')
if b == 1:
value = max(data.values())
for key, v in data.items():
if v == value:print(key,end=' ')
print()
def main():
mapTable = getData()
n = int(input())
dataList = []
for i in range(n):
dataList.append(input())
b = int(input())
for i in range(n):
compute(dataList[i], mapTable, b)
main()
```
### 黃金分配
N塊黃金，每一塊黃金range1~X公克「平均」分給x,y,z三個人，每人最多不得拿Ｍ塊，有幾種分法
N=5，重=[1, 2, 3, 4, 5]，每人最多拿2塊，6種分法
[A, B, C]={( [1, 4], [2, 3], [5]), ( [1, 4], [5], [2, 3]) , ( [2, 3], [1, 4], [5]), ([2, 3], [5], [1, 4]),( [5],[1, 4], [2, 3])}
輸入範例：
[1, 2, 3, 4, 5],2
輸出範例：
((2, 3), (1, 4), (5,))
((1, 4), (5,), (2, 3))
((5,), (2, 3), (1, 4))
((2, 3), (5,), (1, 4))
((1, 4), (2, 3), (5,))
((5,), (1, 4), (2, 3))
```python=
def check(partition, value, M):
return (sum(partition[0])==value and sum(partition[1]) ==value and sum(partition[2])==value
and len(partition[0])<=M and len(partition[1])<=M and len(partition[2])<=M)
def push(result, answer):#each partition should be ordered then push into the ans
d = (tuple(sorted(answer[0])),tuple(sorted(answer[1])),tuple(sorted(answer[2])))
result.add(d)
def allocateObj(result, array, x, y, z, value, M):
n = len(array)
if n == 0:#base case:已經分完了
if check([x,y,z], value, M):#Is it legal?
push(result,[x, y, z])#add to the ans
return True
t = array[1:]
allocateObj(result, t, x + array[:1] , y, z, value, M)
allocateObj(result, t, x, y+ array[:1], z, value, M)
allocateObj(result, t, x, y, z+ array[:1], value, M)
return True
def main(array, M):
result = set()
x, y, z = [[],[],[]]
value = sum(array)//3
if value*3 == sum(array):#make sure the num is integer
allocateObj(result, array, x, y, z, value, M)
for i in result:
print(i)
main([1, 2, 3, 4, 5],2)
```
### 基因序列
找基因序列
* 若DNA序列由A, C, G, T四個字元組成的字串(string)， 基因(gene)是隱藏於DNA序列中的部分片段(子字串)。給定一DNA序列(長度小於50)，找出在裡面的基因;規則: 1.前面是ATG，後面接TAG、TAA、或TGA;– 例如ATGTTTTAA。
* 2.長度為3的倍數，其中未含有ATG、TAG、TAA或TGA。例如，給定DNA序列，其中包含兩個基因， CCATGTTTTAACCATGCCTAAATGGGGCGTTAGTT:
* 基因TTT前面為ATG，後面接著TAA，長度3，其中未含ATG、 TAG、TAA或TGA。
* 基因GGGCGT前面為ATG，後面接著TAG，長度6，其中未含 ATG、TAG、TAA或TGA。
* 撰寫程式輸入DNA序列，找出該序列中所有基因。
輸入範例：
findAllGen('CCATGTTTTAACCATGCCTAAATGGGGCGTTAGTT')
findAllGen('TAAGATGAATGA')
findAllGen('ATGAAATGA')
findAllGen('ATGTGAATGAAATGA')
findAllGen('TTATGTTAAAAGGATGTTAATGTAAGGGCGTTAGTT')
fin
輸出範例：
==>
TTT
GGGCGT
==>
沒有基因
==>
AAA
==>
AAA
==>
沒有基因
==>
TCA
CCCTTCACC
```python=
def check(gen):
if len(gen)==0: #空的基因
return False
for tag in ['ATG', 'TAG','TAA','TGA']: #不能含有這些tag
if gen.find(tag) > -1:
return False
if len(gen)%3==0: #長度3倍數
return True
return False
def findGen(dna):
startTag, endTags = 'ATG', ['TAG','TAA','TGA']
length = len(dna)
startIndex = dna.find(startTag)+3#基因前面是startTag 'ATG'
endIndex = length+1#初始化結束點
for tag in endTags: #從三個 end tag 找出最小符合基因字串
endTemp = dna.find(tag, startIndex)
if endTemp!=-1 and endTemp < endIndex: #找最小符合的 end tag 的點
endIndex = endTemp
if endIndex==length+1 or startIndex < 3: #找不到前後tag
return 0, 0, 'None'
gen = dna[startIndex:endIndex] #找到基因
if check(gen): #驗證基因
return 1, endIndex+3, gen
return 2, startIndex+3, 'None' #繼續往下找
def findAllGen(dna):
i, count = 0, 0
print('==>')
while True:
dna=dna[i:] #往後找基因
b, i, gen = findGen(dna) #b=1找到, i往後找索引
if (b==1):
print(gen)
count=count+1#找到幾個基因
elif (b==0): #找到最後沒找到
break
if count==0:
print('沒有基因')#完全沒找到
findAllGen('CCATGTTTTAACCATGCCTAAATGGGGCGTTAGTT')
findAllGen('TAAGATGAATGA')
findAllGen('ATGAAATGA')
findAllGen('ATGTGAATGAAATGA')
findAllGen('TTATGTTAAAAGGATGTTAATGTAAGGGCGTTAGTT')
findAllGen('AATAGATGTTTAAGTGATATGGGGATGTCATAGATGCCCTTCACCTAA')
```
### 山洞找黃金
Sign in with Wallet
Connect another wallet