from random import randint
from time import time
#print()
#print()


FILL_CODES = " 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

NORTH = 32
SOUTH = 128
EAST = 64
WEST = 16
DIRECTIONS = (NORTH, EAST, SOUTH, WEST)
VISITED = 8

mazemap = []
mazework = []
for i in range(256):
    mazemap.append(0)
    mazework.append(0)
#    mazework.append(randint(0, 0))

for i in range(len(mazemap)):
    if i < 16:
        mazemap[i] |= NORTH

    if i > 239:
        mazemap[i] |= SOUTH

    if i % 16 == 0:
        mazemap[i] |= WEST
        mazemap[i+15] |= EAST

"""
mazemap[255] |= EAST + SOUTH
mazemap[136] |= NORTH + WEST + EAST + SOUTH

mazemap[136] = NORTH + WEST + EAST
mazemap[135] = EAST
mazemap[137] = WEST

mazework[136] = 0
"""

target = 165

def printmaze(mazemap):
    """displays the maze to the shell window"""

    global pos

    line1 = ""
    line2 = ""

    for i in range(len(mazemap)):
        line1 += "+"
        
        if i == pos:
            code = "&"
            if direction == 0:
                code = "^"

            elif direction == 1:
                code = ">"

            elif direction == 2:
                code = "V"

            elif direction == 3:
                code = "<"

        else:
            code = FILL_CODES[mazework[i]%32]

        if (mazemap[i] & NORTH) != 0 or ((mazemap[i-16] & SOUTH) != 0 and i > 15):
            line1 += "-"

        else:
            line1 += " "

        if (mazemap[i] & WEST) != 0 or (mazemap[i-1] & EAST) != 0:
            line2 += "|" + code

        else:
            line2 += " " + code

        if (i+1) % 16 == 0 and mazemap[i] & EAST != 0:
            line2 += "|"

        if (i+1) % 16 == 0:
            line1 += "+"
            print(line1)
            print(line2)
            line1, line2 = "", ""

    print("+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+")

# printmaze(mazemap)

# setup.py

pos = 0  # cell number
dig = 0
direction = 0  # 0 = North, 1 = East, 2 = South, 3 = West

def dowall(wall, pos):
    """inserts a wall into the maze in cell pos
wall can be N, W, S, or E"""
    global mazemap
    bit = 0
    othpos = 0
    othbit = 0
    if wall == "W":
        bit = WEST
        othpos = pos - 1
        othbit = EAST
        
    elif wall == "E":
        bit = EAST
        othpos = pos + 1
        othbit = WEST
        
    elif wall == "N":
        bit = NORTH
        othpos = pos - 16
        othbit = SOUTH
        
    elif wall == "S":
        bit = SOUTH
        othpos = pos + 16
        othbit = NORTH
        
    mazemap[pos] |= bit
    if othpos >= 0 and othpos < 256:
        mazemap[othpos] |= othbit  # other pos of the wall
        

def setp(strg):
    global pos
    dig = 0
    for i in range(len(strg)):
        ch = strg[i].upper()  # case doesn't matter
        if ch in ("0123456789"):  # a number sets the robot's position to a certain tile
            if dig == 0:
                pos = int(ch)
                
            else:
                pos = pos * 10 + int(ch)
                
            dig = 1
        
        else:  # otherwise, it's a movement or new wall
            if dig == 1:
                pass  #print(pos)
            dig = 0
            if ch == "U":  # move up
                pos -= 16
                
            elif ch == "D":  # move down
                pos += 16
                
            elif ch == "R":  # move right
                pos += 1
                
            elif ch == "L":  # move left
                pos -= 1
                
            dowall(ch, pos)
            # print(ch,pos)


# from Derek Hall's C++ code:
'''bool mazeClass::solvePart(void) {
  byte high;
  bool solved = true;
  for (int i = 0; i < sizeof(mazemap); i++) {
    if (i == target) {
      mazework[i] = 0;
    } else {
      high = 254;
      if (!(mazemap[i].north)) {
        if (mazework[(byte)i - Maze_Width] < high) {
          high = mazework[(byte)i - Maze_Width];
        }
      }

      if (!(mazemap[i].east)) {
        if (mazework[(byte)i + 1] < high) {
          high = mazework[(byte)i + 1];
        }
      }

      if (!(mazemap[i].south)) {
        if (mazework[(byte)i + Maze_Width] < high) {
          high = mazework[(byte)i + Maze_Width];
        }
      }

      if (!(mazemap[i].west)) {
        if (mazework[(byte)i - 1] < high) {
          high = mazework[(byte)i - 1];
        }
      }
      high++;
      if (mazework[(byte)i] != high) {
        mazework[(byte)i] = high;
        solved = false;
      }
    }
  }
  return solved;
}

'''
def solvepart():
    global solved, target
    solved = True
    for i in range(len(mazemap)):
        if i == target:
            mazework[i] = 0
        else:
            high = 254
            if (mazemap[i] & NORTH) == 0:
                if (mazework[i - 16] < high):
                    high = mazework[i - 16]
            if (mazemap[i] & EAST) == 0:
                if (mazework[i + 1] < high):
                    high = mazework[i + 1]
            if (mazemap[i] & SOUTH) == 0:
                if (mazework[i + 16] < high):
                    high = mazework[i + 16]

            if (mazemap[i] & WEST) == 0:
                if (mazework[i - 1] < high):
                    high = mazework[i - 1]

            high += 1
            if (mazework[i] != high):
                mazework[i] = high
                solved = False

def solve2():
    global solved
    solved = False
    count = 0
    while solved == False:
        solvepart()
        count += 1

    # print("Count:", count)
    
        
def checkmaze(mazemap):
    """displays the maze to the shell window"""
    for i in range(len(mazemap)):
        if (mazemap[i] & NORTH) != 0 and (mazemap[i-16] & SOUTH) == 0:
            print(i, "N")

        if (i < 255):
            if (mazemap[i] & EAST) != 0 and (mazemap[i+1] & WEST) == 0:
                print(i, "E")
        if (mazemap[i] & WEST) != 0 and (mazemap[i-1] & EAST) == 0:
            print(i, "W")

        if (i < 240):
            if (mazemap[i] & SOUTH) != 0 and (mazemap[i+16] & NORTH) == 0:
                print(i, "S")            


def dir_to_letter(dir_):
    return "NESW"[dir_]


def wn(l, f, r):
    """what should the robot do based on the wall values?"""

    global direction, pos, file
    
    #printmaze(mazemap)
    

    maze_changed = False

    current_cell = mazemap[pos]  # current cell the robot is in

    if f:  # there's a wall in front
        if (not(current_cell & DIRECTIONS[(direction) % 4])):
            dowall(dir_to_letter(direction), pos)
            maze_changed = True

    if l:  # there's a wall to the left
        if (not(current_cell & DIRECTIONS[(direction + 3) % 4])):
            dowall(dir_to_letter((direction + 3) % 4), pos)
            maze_changed = True

    if r:  # there's a wall to the right
        if (not(current_cell & DIRECTIONS[(direction + 1) % 4])):
            dowall(dir_to_letter((direction + 1) % 4), pos)
            maze_changed = True

    if maze_changed and (l, f, r) != (1, 0, 1) or True:
        solve2()  # resolve the maze

    elif maze_changed and (l, f, r) == (1, 0, 1) and direction > 1 or True:
        solve2()

    current_value = mazework[pos]  # value of the cell the robot is in
    current_cell = mazemap[pos]  # current cell the robot is in

    instruction = "s"

    if pos >= 16 and mazework[pos - 16] < current_value and (not (current_cell & NORTH)):  # go up!!!
        if direction == 0:  # already facing up!
            instruction = "+"  # go forward

        elif direction == 1:  # pointing east
            instruction = "<"

        elif direction == 2:  # south
            instruction = "O"  # U-turn

        elif direction == 3:  # west
            instruction = ">"

    elif pos % 16 < 15 and mazework[pos + 1] < current_value and (not (current_cell & EAST)):  # go right!!!
        if direction == 0:  # up!
            instruction = ">"

        elif direction == 1:  # pointing east
            instruction = "+"  # go forward

        elif direction == 2:  # south
            instruction = "<"

        elif direction == 3:  # west
            instruction = "O"  # U-turn

    elif pos < 240 and mazework[pos + 16] < current_value and (not (current_cell & SOUTH)):  # go down!!!
        if direction == 0:  # up!
            instruction = "O"  # U-turn

        elif direction == 1:  # pointing east
            instruction = ">"

        elif direction == 2:  # south
            instruction = "+"  # go forward

        elif direction == 3:  # west
            instruction = "<"

    elif pos % 16 > 0 and mazework[pos - 1] < current_value and (not (current_cell & WEST)):  # go left!!!
        if direction == 0:  # up!
            instruction = "<"

        elif direction == 1:  # pointing east
            instruction = "O"  # U-turn

        elif direction == 2:  # south
            instruction = ">"

        elif direction == 3:  # west
            instruction = "+"  # go forward
            
    # print(instruction)

    if instruction == "+":  # forward
        if direction == 0:
            pos -= 16

        elif direction == 1:
            pos += 1

        elif direction == 2:
            pos += 16

        elif direction == 3:
            pos -= 1

    elif instruction == ">":  # turn right
        direction = (direction + 1) % 4
        if direction == 0:
            pos -= 16

        elif direction == 1:
            pos += 1

        elif direction == 2:
            pos += 16

        elif direction == 3:
            pos -= 1


    elif instruction == "<":  # turn left
        direction = (direction + 3) % 4
        if direction == 0:
            pos -= 16

        elif direction == 1:
            pos += 1

        elif direction == 2:
            pos += 16

        elif direction == 3:
            pos -= 1


    elif instruction == "O":  # U-turn
        direction = (direction + 2) % 4

        if direction == 0:
            pos -= 16

        elif direction == 1:
            pos += 1

        elif direction == 2:
            pos += 16

        elif direction == 3:
            pos -= 1

    elif instruction == "s":
        print("Done!!!")
        
    # line_to_log = str(l) + "," + str(f) + "," + str(r) + "," + instruction + "\n"
    
    #file.write(line_to_log)
    

    return instruction


# modify maze

"""
solve2()
printmaze(mazemap)
"""
fred = "240UUUUUNRNRNRNRNRNEDEDEDEDEDE"
setp(fred)


"""
fred2 = "128nrnrnrnrnrnrnrnrnrnrnrnrnrnrnrn"            
setp(fred2)
print(1)
printmaze(mazemap)
checkmaze(mazemap)

solvepart()
print(2)
printmaze(mazemap)
solvepart()
print(3)
printmaze(mazemap)

print("Calling solve2()")
solve2()

print(4)
printmaze(mazemap)
"""

def human_interface():
    global direction, pos
    instruction = ""

    while instruction != "s":
        printmaze(mazemap)
        print("Direction: " + str(direction))

        values = input("Enter wall values: ").split(" ")
        for v in range(len(values)-1, -1, -1):
            if values[v] == "":
                del values[v]

            else:
                values[v] = int(values[v])
        
        instruction = wn(*values)


def test_with_file(file_name):
    """tests what_now() with a file"""

    pfile = open(file_name)
    
    l = 1
    while l > 0:
        line = pfile.readline()
        l = len(line)
        if (l > 2) and (line[0] == "1" or line[0] == "0"):
            left = int(line[0])
            front = int(line[2])
            right = int(line[4])
            action = str(line[6])
            # print(type(front), "foo")
            ax = wn(left, front, right)
            if (ax != action):
                print("Failed")
                print("Expected: " + action)
                print("Got: " + ax)
                printmaze(mazemap)
                1/0

            else:
                #print("Passed!!!")
                pass
    
    pfile.close()
    #print("end of file")
"""
file = open("runlog2.txt", "w")  # clear the file
file.write("")
file.close()

file = open("runlog2.txt", "a")
"""
setp("240")
solve2()
"""
# human_interface()

# start_time = time_ns()
# sleep(2)

s = time()

test_with_file("runlog1.txt")

print(time() - s)

# end_time = time_ns()
# print(end_time - start_time)
                
file.close()

"""