# Finding nodes around a given node in a grid

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()

• I see from your docstring that this is a code skeleton. Code Review requires real code. Commented Sep 26, 2017 at 23:08
• Hi ! I am sorry. Can you clarify what you mean by real code ? Because when I say skeleton, I meant the code has been stripped down to do the bare minimum of finding directions, and it does that without a problem. Other functions of storing and traversing in stack have been removed, as I felt it wasn't relevant to the question. Commented Sep 27, 2017 at 6:37

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.

• Hi @J_H, I have added my reply as a post in this thread, as it was too long to be a comment. I did not mark your post as answer because I think I didn't explain my problem statement well enough for you to understand. I have expressed my requirement in code, hoping it will provide me a better opportunity to be understood. Commented Oct 1, 2017 at 3:05

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.

• Is your goal to explore all non-self-intersecting paths through the grid? This rebuttal to @JH's answer just confirms my original belief that the question was unclear due to the omitted code. Your justification for making support_element a tuple instead of two parameters sounds unconvincing. Also, the (0, 0) special case for OFFSET seems nasty. Unfortunately, your simplified code only calls direction() once, so we never get to see what you do with the children, and how its cost and direction elements are used, so it's hard to advise you properly. Commented Oct 1, 2017 at 7:21
• Hi, Sorry I wasted your time. I am not allowed to share the code as my professor might use these questions in future and that might compromise the integrity of the assignment submission. I am new to this so most of my code is very crude, so please bear with me. What exactly do you mean by "non-self-intersecting" because I mentioned I wanted to avoid loops. Commented Oct 1, 2017 at 7:49
• If your goal is to ensure that every path you build contains no loops, then you only need to store the visited coordinates. You don't need to reject 180° turns — that is a redundant check. Commented Oct 1, 2017 at 7:54
• Yes indeed, that OFFSET special case was a nasty construct indeed. I had remove the 180° cases from my initial code, so I had wrongly assumed that I had to account for them here too. Thanks, will try to do a better job of explaining next time. Commented Oct 1, 2017 at 8:04
• If you could edit the question to state the goal of the entire assignment and explain the context in which the val and support_element of direction() are used — even if you don't add any code — then I think I could undo my downvote and upgrade my comment to a proper answer. Commented Oct 1, 2017 at 8:18