Finding nodes around a given node in a grid

Question

Even though I have completed this assignment, the direction() function is just irking me. I feel like there is a better way to do it, ideally gaining on execution time or at least aesthetically (cleaner way).

(The stub for my assignment contained code from my professor, but it's generic display_grid and some part of temp().)

Challenge:

Traverse a 10 X 10 grid, to accumulate a cost starting from a location on the grid. The cost and location will be user input. The grid can be traversed in 4 directions(Up, Down, Left, Right) and diagonal movement is not allowed. No location should be added to cost more than once. The direction of traversal should be maintained till the end of the grid or a loop is encountered. In case the direction needs to be changed it must be done clockwise (UP>RIGHT>DOWN>LEFT). If none of the directions are possible from that point, you back track to the previous point and try another direction. For example you are heading RIGHT and at a point it is no longer possible to go right then you try to go DOWN, if that is not possible you try to go LEFT and so on and so forth. If none of these are possible you backtrack you the previous location and try heading DOWN because previously you went RIGHT from this point and the next clockwise option is DOWN. You continue doing this till you accumulate the cost provided by user. Additional Information: Use stack for backtracking.

direction(): Given the list of nodes already seen and the current position, it returns the children of the current position in all direction and the directions they are found ensuring none of them have been previously traversed.

I want to know if I can improve this implementation of direction() which gives me the children of (x,y) and the direction in which they are found.

import sys from random import seed, randrange def display_grid(grid): for i in range(len(grid)): print(' ', ' '.join(str(grid[i][j]) for j in range(len(grid[0])))) def temp(): chain=[] value=0 direction_flag=0 #professor's code starts try: for_seed, bound, x, y, target = [int(x) for x in input('Enter five integers: ').split()] if bound < 1 or x not in range(10) or y not in range(10) or target < 0: raise ValueError except ValueError: print('Incorrect input, giving up.') sys.exit() seed(for_seed) #Creates a grid grid = [[randrange(bound) for _ in range(10)] for _ in range(10)] print('Here is the grid that has been generated:') display_grid(grid) #professor's code ends children = direction((x, y),grid,set(chain),(value,direction_flag)) print(f'Children of ({x},{y}): {children}') def direction(element, grid, chain, support_element): ''' This is a code skeleton, I have removed parts of the code, I thought were not necessary to this code Review In case you feel the need to see the whole thing, please let me know. ''' ''' 1=North 2=South 3=East 4=West ''' #{element} is a location on the grid #{chain} is all the locations previously seen [removed the iteration] #{value} gives the sum of the grid locations seen before arriving at #that point #{direction_flag} gives the direction in which the node was discovered. children = [] direction_flag=support_element[1] if direction_flag == 1: val=element[0] - 1 if element[0] > 0 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 1)] val=element[1] + 1 if element[1] < 9 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 3)] val=element[1] - 1 if element[1] > 0 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 4)] return children elif direction_flag == 2: val=element[0] + 1 if element[0] < 9 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 2)] val=element[1] - 1 if element[1] > 0 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 4)] val= element[1] + 1 if element[1] < 9 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 3)] return children elif direction_flag == 3: val=element[1] + 1 if element[1] < 9 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 3)] val=element[0] + 1 if element[0] < 9 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 2)] val=element[0] - 1 if element[0] > 0 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 1)] return children elif direction_flag == 4: val=element[1] - 1 if element[1] > 0 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 4)] val=element[0] - 1 if element[0] > 0 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 1)] val=element[0] + 1 if element[0] < 9 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 2)] return children else: val = element[0] - 1 if element[0] > 0 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 1)] val = element[1] + 1 if element[1] < 9 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 3)] val = element[1] - 1 if element[1] > 0 and (element[0], val) not in chain: children += [(element[0], val, support_element[0], 4)] val = element[0] + 1 if element[0] < 9 and (val, element[1]) not in chain: children += [(val, element[1], support_element[0], 2)] return children temp() 

Answer 1

Thank you for going to the trouble of abstracting away code not relevant to the question, that was kind of you. Also, kudos for pursuing the assignment to "get it right" even after turning it in.

def temp(): 

Clearly not a good identifier. There's nothing wrong with writing it for a moment to get started, to get code flowing from your fingertips. But after a while the code will tell you what it wants to be, and you should listen, you should rename as needed. Here, init() seems more appropriate.

 chain = [] 

You correctly make this a set() later on. Might as well do that right here.

 value = 0 

Not a good identifier, too vague. Pick a better name, preferably from the problem domain.

 direction_flag = 0 

Also not a good name, as "flag" connotes boolean. Just call it direction.

Your x not in range(10) check uses a magic number. Don't do that. For a square grid, define a constant GRID_SIZE = 10 and use that.

 seed(for_seed) 

A more natural name would have been seed_value, seed_param, seed1, or seed_. But better, simply use import random, so the name seed is still available for your use, like this: random.seed(seed).

1=North 2=South 3=East 4=West 

Thank you for this helpful comment. As above with GRID_SIZE, your comment might be replaced with definitions of four global constants. However, shortly I will suggest viewing direction as an array index.

#{value} gives the sum of the grid locations seen before arriving at #that point 

This suggests that cost would be the appropriate name to use.

The parallel construction between element and support_element is misleading. I don't understand why support_element is a single parameter - it seems like it should be cost, direction instead.

 direction_flag = support_element[1] 

Consider breaking out values with cost, direction = support_element.

if direction_flag == 1: val = element[0] - 1 

OK, now we get to the heart of your complaint, the redundant copy-n-paste code. You have four clauses considering three directions each, for a dozen similar pieces of code. A level of indirection would result in less code.

Also, val above is a poorly chosen identifier, a name with x in it would make more sense here, or y in some other clauses. And x, y = element would let you write clearer code, without the [0] & [1] subscripts.

To summarize what these clauses do: they consider candidate locations near (x, y), perform bounds checks, test chain membership, and conditionally append to children. The neighborhood is defined by small coordinate deltas. Let's put that in an array. You used one-origin, but I will use zero-origin, so 0 denotes "north", and 3 "west":

OFFSET = [ (0, -1), # north (1, 0), # east (0, 1), # south (-1, 0), # west ] 

Now we can conveniently extract coordinate deltas:

 dx, dy = OFFSET[input_direction] 

Let "c" describe a "candidate" location or direction. We need to ensure we do not attempt to go backward -- a simple == test suffices:

 x, y = element children = [] for c_direction in range(len(OFFSET)): dx, dy = OFFSET[c_direction] cx, cy = dx + x, dy + y if (cx, cy) in chain or c_direction == direction: continue if cx not in range(GRID_SIZE) or cy not in range(GRID_SIZE): continue children += [(cx, cy), cost, c_direction] return children 

Now twelve pieces of code are consolidated in one central place.

Answer 2

Thanks a lot @J_H for your suggestion Review by J_H. As I was unable to add such a big comment, I am sorry to write this as a post.

The parallel construction between element and support_element is misleading. I don't understand why support_element is a single parameter - it seems like it should be cost, direction instead.

Actually, I am storing the support_element in a stack as tuple. And each support_element corresponds to an element. And I thought it would be better to pass the data as a single element than to pass it as two different elements(Parameters).

I have a couple of things to apologize for, firstly sorry for not being clear enough with my requirements so I have modified your suggested code to what I wanted, in a hope to give you a better understanding of my problem statement(What cannot be said will be understood through code) and secondly sorry to trouble you but could you suggest any improvement on this implementation. I have made minor logic adjustments to your code and described my needs in comment line, if I make any erroneous judgement kindly forgive me.

def c_direction(element, grid, chain, support_element): """ c_direction(): Given the current position, the grid, the list of nodes already seen and the current cost and direction it returns the children of the current position in all direction, the directions they are found and the cost ensuring none of them have been previously traversed. """ GRID_SIZE = 10 children = [] OFFSET = [ #-J_H- I think you made a mistake in naming/ordering the offsets #I need them to be in this order(Clockwise) (-1, 0), # north ( 0,+1), # east (+1, 0), # south ( 0,-1), # west ( 0, 0) # start #-J_H-First time we need to look in all 4 directions so in #first iteration i pass the value as direction=4 #(0,0) neutralizes finding opposite direction ] cost,c_direction=support_element x, y = element while_loop_counter=0 prev_x,prev_y=OFFSET[c_direction] #Generate Opposite Direction of c_direction prev_x=prev_x*-1 prev_y=prev_y*-1 #-J_H- #I am using while loop because for loop traverses from 0 to 3 # every time. # whereas I want to traverse the current direction first then clockwise # the rest of the directions with the exception of direction I am coming # from. Say the given direction in West, then my final children list # will contain children found in [WEST, NORTH, SOUTH] while while_loop_counter<4: direction=c_direction % 4 dx, dy = OFFSET[direction] cx, cy = dx + x, dy + y while_loop_counter += 1 c_direction += 1 if OFFSET[direction] == (prev_x,prev_y) or (cx, cy) in chain: continue if cx not in range(GRID_SIZE) or cy not in range(GRID_SIZE): continue children += [((cx, cy), cost, direction)] return children 

Thanks again, I wouldn't have made this level of progress without your insights.