# Input: grid of # . S (initially facing east) E
# Output: cheapest path from S to E, 1 point per move + 1000 per turn
#         how many tiles (including S and E) are part of 1+ cheapest paths?

def get_number_adjacent_walls(r, c):
  adjacent_walls = 0
  if grid[r - 1][c] == "#":
    adjacent_walls += 1
  if grid[r + 1][c] == "#":
    adjacent_walls += 1
  if grid[r][c - 1] == "#":
    adjacent_walls += 1
  if grid[r][c + 1] == "#":
    adjacent_walls += 1
  return adjacent_walls

def get_node_key(r, c, dr, dc):
  return str(r) + "," + str(c) + "," + str(dr) + "," + str(dc)

def get_node_values(node):
  return list(map(int, node.split(",")))

def get_cheapest_unvisited_node():
  cheapest_node = None
  cheapest_cost = -1
  for node in unvisited_nodes:
    if nodes[node] >= 0:
      if cheapest_cost == -1 or cheapest_cost > nodes[node]:
        cheapest_node = node
        cheapest_cost = nodes[node]
  return cheapest_node

grid = []

sr, sc, er, ec = -1, -1, -1, -1

r = 0
file = open("16_input.txt", "r")
for line in file:
  line = line.replace("\n", "")
  c = 0
  row = []
  for character in line:
    if character == "S":
      sr, sc = r, c
      character = "."
    if character == "E":
      er, ec = r, c
      character = "."
    row.append(character)
    c += 1
  grid.append(row)
  r += 1

# set of all nodes and their known distance from the start
nodes = {}
for r in range(1, len(grid) - 1):
  for c in range(1, len(grid[0]) - 1):
    if grid[r][c] == ".":
      nodes[get_node_key(r, c, -1, 0)] = -1
      nodes[get_node_key(r, c, 1, 0)] = -1
      nodes[get_node_key(r, c, 0, -1)] = -1
      nodes[get_node_key(r, c, 0, 1)] = -1
nodes[get_node_key(sr, sc, 0, 1)] = 0

unvisited_nodes = []
for node in nodes:
  unvisited_nodes.append(node)

cheapest_path_length = -1
while len(unvisited_nodes) > 0:
  node = get_cheapest_unvisited_node()
  unvisited_nodes.remove(node)
  nv = get_node_values(node)
  if nv[0] == er and nv[1] == ec:
    cheapest_path_length = nodes[node]
    print ("Cheapest path length", cheapest_path_length)
    break
  cr, cc, dr, dc = nv[0], nv[1], nv[2], nv[3]
  # evaluate continuing in current direction
  new_node = get_node_key(cr + dr, cc + dc, dr, dc)
  distance = nodes[node] + 1
  if new_node in nodes and (nodes[new_node] == -1 or nodes[new_node] >= distance):
    nodes[new_node] = distance
  # evaluate turning counterclockwise
  new_node = get_node_key(cr, cc, -dc, dr)
  distance = nodes[node] + 1000
  if new_node in nodes and (nodes[new_node] == -1 or nodes[new_node] >= distance):
    nodes[new_node] = distance
  # evaluate turning clockwise
  new_node = get_node_key(cr, cc, dc, -dr)
  distance = nodes[node] + 1000
  if new_node in nodes and (nodes[new_node] == -1 or nodes[new_node] >= distance):
    nodes[new_node] = distance

paths_to_extend = [[[sr, sc, 0, 1, 0]]] # r, c, dr, dc, cost
complete_paths = []
while len(paths_to_extend) > 0:
  path = paths_to_extend[0]
  paths_to_extend.remove(path)
  r, c, dr, dc, cost = path[-1][0], path[-1][1], path[-1][2], path[-1][3], path[-1][4]
  nk = get_node_key(r, c, dr, dc)
  # if we could have gotten to this point cheaper, then ditch this path
  if nodes[nk] == -1 or nodes[nk] < cost:
    continue
  if r == er and c == ec:
    complete_paths.append(path)
    continue
  # evaluate continuing in current direction
  if grid[r + dr][c + dc] == ".":
    add_new_path = True
    for step in path:
      if step[0] == r + dr and step[1] == c + dc: # would form a loop
        add_new_path = False
        break
    if add_new_path:
      new_path = path.copy()
      new_path.append([r + dr, c + dc, dr, dc, cost + 1])
      paths_to_extend.append(new_path)
  # evaluate turning counterclockwise
  if grid[r - dc][c + dr] == ".":
    add_new_path = True
    for step in path:
      if step[0] == r - dc and step[1] == c + dr:
        add_new_path = False
        break
    if add_new_path:
      new_path = path.copy()
      new_path.append([r - dc, c + dr, -dc, dr, cost + 1001]) # turn and move
      paths_to_extend.append(new_path)
  # evaluate turning clockwise
  if grid[r + dc][c - dr] == ".":
    add_new_path = True
    for step in path:
      if step[0] == r + dc and step[1] == c - dr:
        add_new_path = False
        break
    if add_new_path:
      new_path = path.copy()
      new_path.append([r + dc, c - dr, dc, -dr, cost + 1001])
      paths_to_extend.append(new_path)

tiles = []
for path in complete_paths:
  for step in path:
    tile = [step[0], step[1]]
    if not (tile in tiles):
      tiles.append(tile)
print (len(tiles))