Given a 2D array, create a 2D doubly linked list by only using recursion. Every number in the list must have 4 pointers (up, down, right, left) and needs to be linked to every number next to it (If no number, then just 'None')
import numpy as np
class Node:
""" Node class
up
|
left - data - right
|
down
"""
def __init__(self, data):
self.data = data
self.right = None
self.left = None
self.up = None
self.down = None
def constructDoublyLinkedListRecursion(arr):
""" Converts a 2D array into a 2D doubly linked list by calling
the recursee constructDLLRecursiveStep.
input:
arr: 2D array to turn into a 2D DLL
output:
head (top left node) of the 2D DLL of the input arr.
"""
return constructDLLRecursiveStep(arr, 0, 0, None)
def constructDLLRecursiveStep(arr, y, x, curr):
""" Recursively construct the 2D DLL from the given array.
This is the "recursee" of constructDoublyLinkedListRecursion.
input:
arr: The 2D array to construct the 2D DLL from.
y: y-coordinate of the array to get the value from.
x: x-coordinate of the array to get the value from.
curr: The current node to connect the new node from.
output:
new_node: The newly created node which connects to curr node.
"""
return new_node
This is what i did so far:
def constructDLLRecursiveStep(arr, y, x, curr):
arrDim = arr.shape[1]
if(y >= arrDim or x >= arrDim):
return None;
new_node = Node(arr[y,x])
if(x > 0):
new_node.left = curr
else:
new_node.left = None
if(y > 0):
new_node.up = curr
else:
new_node.up = None
new_node.right = constructDLLRecursiveStep(arr, y, x+1, new_node)
new_node.down = constructDLLRecursiveStep(arr, y+1, x, new_node)
return new_node
Display function
def display(dll_ptr):
""" Prints the 2D dll according to their positions similar to
printing a 2D array.
input:
dll_ptr: the head (most upper left node) of a 2D dll.
output:
None
"""
right_ptr = None
down_ptr = dll_ptr
while down_ptr != None:
right_ptr = down_ptr
while right_ptr != None:
msg = f"{right_ptr.data} | "
for i, direction in enumerate([("up", right_ptr.up), ("right", right_ptr.right), ("down", right_ptr.down), ("left", right_ptr.left)]):
direction_str, direction_ptr = direction
if direction_ptr: msg += f"{direction_str}: {direction_ptr.data}"
else: msg += f"{direction_str}: None"
msg += ", "
print(msg)
right_ptr = right_ptr.right
print()
down_ptr = down_ptr.down
I am getting this output which shows that there's an issue with the up-pointer:
"""
Input 2D array:
[[9 4 0 8 6]
[4 3 2 2 7]
[9 7 3 9 2]
[8 7 3 6 2]
[9 4 6 5 3]]
<class 'numpy.ndarray'>
constructDoublyLinkedListRecursion output:
9 4 0 8 6
4 3 2 2 7
9 7 3 9 2
8 7 3 6 2
9 4 6 5 3
constructDoublyLinkedListRecursion output:
9 | up: None, right: 4, down: 4, left: None,
4 | up: None, right: 0, down: 3, left: 9,
0 | up: None, right: 8, down: 2, left: 4,
8 | up: None, right: 6, down: 2, left: 0,
6 | up: None, right: None, down: 7, left: 8,
4 | up: 9, right: 3, down: 9, left: None,
3 | up: 4, right: 2, down: 7, left: 4,
2 | up: 3, right: 2, down: 3, left: 3,
2 | up: 2, right: 7, down: 9, left: 2,
7 | up: 2, right: None, down: 2, left: 2,
9 | up: 4, right: 7, down: 8, left: None,
7 | up: 9, right: 3, down: 7, left: 9,
3 | up: 7, right: 9, down: 3, left: 7,
9 | up: 3, right: 2, down: 6, left: 3,
2 | up: 9, right: None, down: 2, left: 9,
8 | up: 9, right: 7, down: 9, left: None,
7 | up: 8, right: 3, down: 4, left: 8,
3 | up: 7, right: 6, down: 6, left: 7,
6 | up: 3, right: 2, down: 5, left: 3,
2 | up: 6, right: None, down: 3, left: 6,
9 | up: 8, right: 4, down: None, left: None,
4 | up: 9, right: 6, down: None, left: 9,
6 | up: 4, right: 5, down: None, left: 4,
5 | up: 6, right: 3, down: None, left: 6,
3 | up: 5, right: None, down: None, left: 5,
"""
The main issue is that you are recurring almost unconditionally in both directions. That means that the node at index 1, 1 will be created via two different recursion paths: once by first recurring with x + 1 and later on with y + 1, and a second time when y + 1 is being called and there a recursive call is made with x + 1. The total number of recursive calls far exceeds the number of nodes you really need to create, as all possible (zig-zag) paths through the matrix are being made.
One solution is to only make a recursive call with y + 1 when x is zero. That will initiate the process to create the whole row (with the x + 1 recursion). The only thing to take care of is to "nit" those nodes to the corresponding nodes just above them. But this you can achieve by walking from the left side node upwards and then take the node at its right.
Here is the corrected code:
def constructDLLRecursiveStep(arr, y, x, curr):
leny, lenx = arr.shape
if y >= leny or x >= lenx:
return None
new_node = Node(arr[y,x])
if x == 0: # Came from above
new_node.up = curr
else: # Came from the left
new_node.left = curr
if y > 0: # Link to row above, by walking "the block"
curr.up.right.down = new_node
new_node.up = curr.up.right
new_node.right = constructDLLRecursiveStep(arr, y, x + 1, new_node)
if x == 0: # Recur downwards
new_node.down = constructDLLRecursiveStep(arr, y + 1, 0, new_node)
return new_node