1234567891011121314151617181920212223242526272829303132333435363738394041 |
- import argparse
- import functools
- from typing import List
- parser = argparse.ArgumentParser()
- parser.add_argument("ifile", type=argparse.FileType('r'))
- args = parser.parse_args()
- board = [[int(char) for char in line.strip()] for line in args.ifile.readlines()]
- max_x_pos = len(board[0]) - 1
- max_y_pos = len(board) - 1
- CURR_BEST = 10000000000000000000
- @functools.lru_cache(pow(2, 20))
- def search(posX, posY, currScore):
- global CURR_BEST
- global board
- global max_y_pos
- global max_x_pos
- if currScore > CURR_BEST:
- return CURR_BEST
- if posX == max_x_pos and posY == max_y_pos:
- if currScore < CURR_BEST:
- CURR_BEST = currScore
- return currScore
- possibilities = []
- if posX < max_x_pos:
- possibilities.append(search(posX + 1, posY, currScore + board[posY][posX + 1]))
- if posY < max_y_pos:
- possibilities.append(search(posX, posY + 1, currScore + board[posY + 1][posX]))
- return min(possibilities)
- if __name__ == "__main__":
- print(search(0, 0, 0))
|