# Input: grid of # . S (initially facing east) E
# Output: cheapest path from S to E, 1 point per move + 1000 per turn

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)

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:
    print (nodes[node])
    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