import math def isPrime(number): sqrt = math.ceil(math.sqrt(number)) if number == 1: return False for i in range(2,sqrt + 1): if number % i == 0: return False return True # # prime test # prime numbers 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 # 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 # 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 # primeNumbers = [137 ,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277 ,281,283,293,307,311,313,317,331,337,347, # 349 ,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599, # 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797] # for number in primeNumbers: # if not isPrime(number): # print("error!!!") def maxPath(filePath): file = open(filePath, "r") numbers = [] for line in file: row = line.strip().split() # these numbers are currently stored in strings since we took this data from txt file # cast it to integer # i could do this later but i chose to do it now. row = [int(i) for i in row] numbers.append(row) # result = solver(numbers,0,0) # return result res = solver2(numbers) file.close() pathFinder(res,numbers) print("----------") return res[0][0] def solver2(numbers): sumList = [] for i in range(len(numbers)): dummy = [] for j in range(len(numbers[i])): dummy.append(0) sumList.append(dummy) for i in range(len(numbers)): row = len(numbers) - 1 - i for j in range(len(numbers[row])): number = numbers[row][j] if not isPrime(number): sumList[row][j] = number if row != len(numbers) - 1: if j == 0: sumList[row][j] += max(sumList[row + 1][j], sumList[row + 1][j + 1]) elif j == len(numbers[row]) - 1: sumList[row][j] += max(sumList[row + 1][j - 1], sumList[row + 1][j]) else: sumList[row][j] += max(sumList[row + 1][j - 1], sumList[row + 1][j], sumList[row + 1][j + 1]) return sumList def pathFinder(sumList,numbers): print("path is : ") path = "" if sumList[0][0] != 0: path = path + str(numbers[0][0]) + "-" value = sumList[0][0] - numbers[0][0] for i in range(len(numbers) - 1): ind = sumList[i + 1].index(value) path = path + str(numbers[i + 1][ind]) + "-" value = value - numbers[i + 1][ind] print(path) res = maxPath("big_input.txt") print("sum is : " +str(res)) # res = maxPath("big_input.txt") # print(res)
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question