プロジェクト オイラー問題 18は、三角形グリッドの上から下へのルートを最大和で見つけるように求めます。
私のプログラムは、以下に示すように入力を受け取ることができるはずです。最初の行にテスト ケースの数 (2) が表示され、各テスト ケースの行数 (4) と、テスト ケースのデータ (1 行に 1 行) が表示されます。
2
4
3
7 4
2 4 6
8 5 9 3
6
690
650 901
65 774 67
435 248 677 385
878 90 378 191 703
141 296 143 756 938 529
プログラムは、テスト ケースごとに 1 行の出力を生成し、合計が最大のルートを示します。
23
4176
Pythonを使用して実装しようとしました。
コードは以下のとおりです。
def triangle(rows):
PrintingList = list()
for rownum in range (rows ):
PrintingList.append([])
newValues = raw_input().strip().split()
PrintingList[rownum] += newValues
return PrintingList
def routes(rows,current_row=0,start=0):
for i,num in enumerate(rows[current_row]):
if abs(i-start) > 1:
continue
if current_row == len(rows) - 1:
yield [num]
else:
for child in routes(rows,current_row+1,i):
yield [num] + child
testcases = int(raw_input())
for num in range(testcases):
rows= int(raw_input())
triangleinput = triangle(rows)
max_route = max(routes(triangleinput),key=sum)
sum(max_route)
これを入力すると:
1
3
1
2 3
4 5 6
次のエラーが表示されます。
Traceback (most recent call last):
File "Maximum Route.py", line 23, in <module>
max_route = max(routes(triangleinput),key=sum)
TypeError: unsupported operand type(s) for +: 'int' and 'str'
いくつかのガイダンスが必要です..他のエラーがある場合は指摘してください...ありがとう...