---
# System prepended metadata

title: 計算機程式設計HW

---

# 計算機程式設計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') 
```

### 山洞找黃金



