123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107 |
- import argparse
- import functools
- from typing import List, NamedTuple, Set, Tuple
- import sys
- 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()]
- def expandMap(board: List[List[int]]) -> List[List[int]]:
- map: List[List[int]] = []
- # build the top 'bar' of the map
- for line in board:
- clone = list(line)
- for repeat in range(0, 4):
- for index in range(0, len(line)):
- curr = clone[index + len(line) * repeat]
- if curr == 9:
- curr = 1
- else:
- curr += 1
- clone.append(curr)
- map.append(clone)
- for repeat in range(0, 4):
- for line_index in range(0, len(board)):
- line = []
- for col in range(0, len(map[0])):
- curr = map[len(board) * repeat + line_index][col]
- if curr == 9:
- curr = 1
- else:
- curr += 1
- line.append(curr)
- map.append(line)
- return map
- def printMap(board: List[List[int]]):
- for line in board:
- print("".join(map(str, line)))
- MAX_VAL = 10000000000000000000
- expanded_map = expandMap(board)
- # expanded_map = board
- max_x_pos = len(expanded_map[0]) - 1
- max_y_pos = len(expanded_map) - 1
- sys.setrecursionlimit(2 * (max_x_pos + max_y_pos + 20))
- class Point(NamedTuple):
- x: int
- y: int
- best_by_pos = [[MAX_VAL for pos in line] for line in expanded_map]
- best_by_pos[0][0] = 0
- traversed = [[False for pos in line] for line in expanded_map]
- CURR_BEST = MAX_VAL
- def lowerNode(costMap: List[List[int]], first: Point, second: Point):
- if costMap[first.y][first.x] < costMap[second.y][second.x]:
- return first
- else:
- return second
- def nodeSearch(untraversedSet: List[Point], currentCostMap: List[List[int]], edgeCosts: List[List[int]]):
- pos = functools.reduce(functools.partial(lowerNode, currentCostMap), untraversedSet[1:], untraversedSet[0])
- untraversedSet.remove(pos)
- if currentCostMap[pos.y][pos.x] == MAX_VAL:
- print("FAILED")
- sys.exit()
- if pos.x == max_x_pos and pos.y == max_y_pos:
- print(currentCostMap[pos.y][pos.x])
- sys.exit(1)
- # for each neighbor, consider costs
- consider = [
- Point(pos.x + 1, pos.y),
- Point(pos.x - 1, pos.y),
- Point(pos.x, pos.y - 1),
- Point(pos.x, pos.y + 1)
- ]
- for other in consider:
- if 0 <= other.x <= max_x_pos and 0 <= other.y <= max_y_pos and not traversed[other.y][other.x]:
- currentCostMap[other.y][other.x] = min(currentCostMap[other.y][other.x], currentCostMap[pos.y][pos.x] + edgeCosts[other.y][other.x])
- if other not in untraversedSet:
- untraversedSet.append(other)
- traversed[pos.y][pos.x] = True
- todo = [Point(0, 0)]
- while len(todo) != 0:
- nodeSearch(todo, best_by_pos, expanded_map)
- for line in traversed:
- print("".join(map(lambda x: "*" if x else " ", line)))
|