quiz_8_solution.py

# Randomly fills a grid of size 10 x 10 with digits between 0
# and bound - 1, with bound provided by the user.
# Given a point P of coordinates (x, y) and an integer "target"
# also all provided by the user, finds a path starting from P,
# moving either horizontally or vertically, in either direction,
# so that the numbers in the visited cells add up to "target".
# The grid is explored in a depth-first manner, first trying to mone north, always trying to keep the current direction,
# and if that does not work turning in a clockwise manner.
#
# Written by Eric Martin for COMP9021


import sys
from random import seed, randrange
from array_stack import *


dim = 10
grid = [[0] * dim for _ in range(dim)]

def display_grid():
    for i in range(dim):
        print('    ', end = '')
        for j in range(dim):
            print(' ', grid[i][j], end = '')
        print()
    print()

def explore_depth_first(x, y, target):
    directions = {'N': (-1, 0),'S': (1, 0), 'E': (0, 1), 'W': (0, -1)}
    next_directions = {'': ('W', 'S', 'E', 'N'),
                       'N': ('W', 'E', 'N'),
                       'S': ('E', 'W', 'S'),
                       'E': ('N', 'S', 'E'),
                       'W': ('S', 'N', 'W')}
    states = ArrayStack()
    states.push(([(x, y)], [grid[x][y]], ''))
    while not states.is_empty():
        path, sums, previous_direction = states.pop()
        if sums[-1] == target:
            return path
        x, y = path[-1][0], path[-1][1]
        for next_direction in next_directions[previous_direction]:
            next_x, next_y = x + directions[next_direction][0],\
                             y + directions[next_direction][1], 
            if next_x not in range(dim) or next_y not in range(dim):
                continue
            if (next_x, next_y) in path:
                continue
            next_sum = sums[-1] + grid[next_x][next_y]
            if next_sum > target:
                continue
            path_copy = list(path)
            path_copy.append((next_x, next_y))
            sums_copy = list(sums)
            sums_copy.append(next_sum) 
            states.push((path_copy, sums_copy, next_direction))
    return None

provided_input = input('Enter five integers: ').split()
if len(provided_input) != 5:
    print('Incorrect input, giving up.')
    sys.exit()    
try:
    seed_arg, bound, x, y, target = [int(x) for x in provided_input]
    if bound < 1 or x < 0 or x > 9 or y < 0 or y > 9 or target < 0:
        raise ValueError
except ValueError:
    print('Incorrect input, giving up.')
    sys.exit()
    
seed(seed_arg)
# We fill the grid with randomly generated digits between 0 and bound - 1.
for i in range(dim):
    for j in range(dim):
        grid[i][j] = randrange(bound)
print('Here is the grid that has been generated:')
display_grid()

path = explore_depth_first(x, y, target)
if not path:
    print('There is no way to get a sum of {} starting '
          'from ({}, {})'.format(target, x, y))
else:
    print('With North as initial direction, and exploring '
          'the space clockwise,\n'
          'the path yielding a sum of {} starting from '
          '({}, {}) is:\n {}'.format(target, x, y, path))