QUIZ_7

# Written by *** for COMP9021
#
# Prompts the user for a ranking of the four horizontal and vertical
# directions, ⬆, ⮕, ⬇ and ⬅, from most preferred to least
# preferred, say d1, d2, d3 and d4.
#
# Determines the path that goes from a given point to another given
# point by following stars in a grid, provided that is possible,
# the path being uniquely defined by the following condition:
# to go from A to B,
# - if it is possible to start taking direction d1,
#   then the path from A to B starts by taking direction d1;
# - otherwise, if it is possible to start taking direction d2,
#   then the path from A to B starts by taking direction d2;
# - otherwise, if it is possible to start taking direction d3,
#   then the path from A to B starts taking direction d3;
# - otherwise, if it is possible to start taking direction d4,
#   then the path from A to B starts by taking direction d4.
#
# The grid and the path, if it exists, are output,
# - the endpoint of the path being represented by a red circle;
# - taking direction North being represented by a yellow square;
# - taking direction East being represented by a brown square;
# - taking direction South being represented by a green square;
# - taking direction West being represented by a purple square;
# - points not on the path being represented by black and white
#   squares depending on whether they are or not occupied by a star.
# (All these characters have been used in quiz 3.)
#
# Also outputs the length of the path, if it exists.

from random import seed, randrange
import sys

dim = 10


# 0 1000000 50
# 0 0
# 1 0
# ⮕⬇⬅⬆
def display_grid():
    print('   ', '-' * (2 * dim + 1))
    for i in range(dim):
        print('   |', ' '.join('*' if grid[i][j] else ' '
                               for j in range(dim)
                               ), end=' |\n'
              )
    print('   ', '-' * (2 * dim + 1))


def connect(start, end):
    if grid[start[0]][start[1]] == 0 or grid[end[0]][end[1]] == 0:
        print('There is no path joining both points.')
        return
    rows = len(grid)
    cols = len(grid[0])
    pre_dict = {(start[0], start[1]): (start[0], start[1])}
    visited = set()
    visit = []
    direction_dict = {'⬆': (-1, 0), '⮕': (0, 1), '⬇': (1, 0), '⬅': (0, -1)}
    symbols = {
        'black_square': 11035,  # Black circle
        'white_square': 11036,  # White square
        'red_circle': 128308,  # Red circle
        'blue_circle': 128309,  # Blue circle
        'orange_square': 128999,  # Orange square
        'yellow_square': 129000,  # Yellow square
        'green_square': 129001,  # Green square
        'purple_square': 129002,  # Purple square
        'brown_square': 129003  # Brown square
    }

    directions_priority_list = [direction_dict[direction_preferences[idx]] for idx in range(4)]

    display_grid = [[chr(symbols['white_square']) for _ in range(cols)] for _ in range(rows)]

    def init_grid():
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    # print(row,col)
                    display_grid[row][col] = chr(symbols['black_square'])

    def display():
        for row in range(rows):
            print('    ', end='')
            for col in range(cols):
                print(display_grid[row][col], end='')
            print()

    def dfs(x, y):
        found = False
        visited.add((x, y))
        visit.append((x, y))
        while found == False and visited:
            v = visit.pop()
            visited.add(v)

            if v == (end[0], end[1]):
                found = True
            else:
                for dx, dy in directions_priority_list[::-1]:
                    cur_x, cur_y = dx + v[0], dy + v[1]
                    if 0 <= cur_x < rows and 0 <= cur_y < cols and grid[cur_x][cur_y] == 1 and (
                            cur_x, cur_y) not in visited:
                        pre_dict[(cur_x, cur_y)] = (v[0], v[1])
                        visit.append((cur_x, cur_y))

        def find_path(start_point, path_reverse):
            path_reverse.append(start_point)
            if start_point == (start[0], start[1]):
                return path_reverse
            return find_path((pre_dict[start_point][0], pre_dict[start_point][1]), path_reverse)

        path_reverse = find_path((end[0], end[1]), path_reverse=[])

        path = path_reverse[::-1]
        path_length = len(path)
        for idx in range(path_length - 1):
            if path[idx + 1][0] - path[idx][0] == 1 and path[idx + 1][1] - path[idx][1] == 0:
                # green_square S
                display_grid[path[idx][0]][path[idx][1]] = chr(symbols['green_square'])
            elif path[idx + 1][0] - path[idx][0] == 0 and path[idx + 1][1] - path[idx][1] == 1:
                # brown_square E
                display_grid[path[idx][0]][path[idx][1]] = chr(symbols['brown_square'])
            elif path[idx + 1][0] - path[idx][0] == -1 and path[idx + 1][1] - path[idx][1] == 0:
                # yellow_square N
                display_grid[path[idx][0]][path[idx][1]] = chr(symbols['yellow_square'])
            elif path[idx + 1][0] - path[idx][0] == 0 and path[idx + 1][1] - path[idx][1] == -1:
                # purple_square W
                display_grid[path[idx][0]][path[idx][1]] = chr(symbols['purple_square'])

        display_grid[end[0]][end[1]] = chr(symbols['red_circle'])
        # if path_length==0:
        #     print('There is no path joining both points.')
        # else:
        print(f'There is a path joining both points, of length {path_length}:')

    init_grid()
    dfs(start[0], start[1])
    display()

    # REPLACE PASS ABOVE WITH YOUR CODE


# ⬆⮕⬇⬅       ⬇⬆⮕⬅
# POSSIBLY DEFINE OTHER FUNCTIONS

try:
    for_seed, density, dim = (int(x)
                              for x in input('Enter three integers, '
                                             'the second and third ones '
                                             'being strictly positive: '
                                             ).split()
                              )
    if density <= 0 or dim <= 0:
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
try:
    start = [int(x) for x in input('Enter coordinates '
                                   'of start point:'
                                   ).split()
             ]
    if len(start) != 2 or not (0 <= start[0] < dim) \
            or not (0 <= start[1] < dim):
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
try:
    end = [int(x) for x in input('Enter coordinates '
                                 'of end point:'
                                 ).split()
           ]
    if len(end) != 2 or not (0 <= end[0] < dim) \
            or not (0 <= end[1] < dim):
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
direction_preferences = input('Input the 4 directions, from most '
                              'preferred to least preferred:'
                              )
if set(direction_preferences) != {'⬆', '⮕', '⬇', '⬅'}:
    print('Incorrect input, giving up.')
    sys.exit()

seed(for_seed)
grid = [[int(randrange(density) != 0) for _ in range(dim)]
        for _ in range(dim)
        ]
print('Here is the grid that has been generated:')
display_grid()
print()
connect(start, end)