Python Variable "stuck"?

October 5, 2023 8:29 AM

I'm working on some depth traversal code, and after my 2nd backtrack, the display of the current working node gets stuck on the 2nd to last node of that backtrack (e.g. hit the end and then step back

[2,2] in particular. https://github.com/symbioid/Tetragraphsolver/blob/master/TetraGraphSolver.py

I've been banging my head against this for months in spare time and I have a feeling it's related to either deep vs shallow copying (the first hurdle I had to overcome) or some other quirk of python.

I think my logic is sound, but if anyone can see either a logic flaw or some tips on what python is doing behind the scenes that's preventing this from updating to 2,1 when it steps back the 2nd time from the final (this time) loop).

https://github.com/symbioid/Tetragraphsolver/blob/master/TetraGraphSolver.py

I also tried setting the "current node" after current_path.pop() while backtracking to "current_path[-1]" but it endless loops and overflows the stack. So I think my current code is more correct.

I feel like I'm running into some really difficult confusing reference semantics here, but maybe it's something simpler like a logic bug. Thoughts?

posted by symbioid to Technology (10 answers total)

Response by poster: Sorry link didn't autolink for some reason:
https://github.com/symbioid/Tetragraphsolver/blob/master/TetraGraphSolver.py
posted by symbioid at 8:29 AM on October 5, 2023

Best answer: Can you explain in words/sentences what this code is meant to do? You're not doing something like obviously modifying the thing you're iterating over, and it's hard to spot otherwise just skimming the code. The part where you ran into copy vs deep copy makes me suspect you're modifying something you don't intend to.

Another strategy might be to write a version without the class that doesn't mutate any inputs to a function unless they're returned (i.e. make the functions pure).
posted by hoyland at 9:21 AM on October 5, 2023 [2 favorites]

In the backtrack() method on your walker class, you update the current_node with a copy of prev_node, which is fair enough. But prev_node is only modified when you move. If you hit more than one backtrack in a row, whatever was in prev_node the first time looks like it gets repeatedly copied to the current_node on each subsequent backtrack.

It looks like [2,2] is the prev_node the first time you encounter that situation in this traversal. I'm not familiar with the problem you're trying to solve, but would it make sense to update current_node to the node is at the top of your current_path on backtrack?

Edit: On more careful reading, I see you tried updating from the end of the current_path already. But that seems like it's going in the right direction, so there might be another issue somewhere else.
posted by figurant at 9:36 AM on October 5, 2023 [1 favorite]

Response by poster: OK - background and what I'm trying to do here: http://quardinex.phoningitindustries.com/
My friend helped me make this prototype in JS/React, and to add features like "hints" and difficulty ratings, and valid puzzle generation... etc, I'm trying to write a DFS traverser for this based on the following rules)
-------
n.b. In the python github code starting on [0,0]. the JS Quardinex version is [1,1] Haven't changed yet
1) Node values are on a 3x3 board here.
1a) Board[row][col].value is a "move" value.
2) Current_node = [0,0] (since we're talking my code not the js)
3) Flag current_node.visited = True
4) Append Current Node to Working List
5) Scan targets going clockwise (up = 0.. left = 3)
6) If target Null or Visited, turn right (increment direction)
6a. else: set current node to target[direction]
7) repeat until hitting Left (e.g. = number of polygon sides, 4)
8) If hit 4/Left - backtrack by...

0) Unvisit current node (so future visit from different path can still visit)
1) current_node = prev_node
2) scan... if null or visited, turn right; if direction = 4, backtrack else move.
3) Of course we need the end - as we pop off if the length of current path is 0 we should end (I think I have different conditional IIRC) Maybe I just check to see if Current is Start Node.

Anyways hope this helps what's going on a little more? Or what I'm trying to do?
posted by symbioid at 11:12 AM on October 5, 2023

Best answer: It looks like you're trying to enumerate all the paths your DFS takes. Here are some general tips that may help clarify things, from a guy who has written DFS in various incarnations many, many, many times.

1. Make the input graph immutable (the game board, in your case). Keep the visited set in the Walker instead. Give each node a unique id and use those for the visited set, instead of the Node object itself. You can use the 'ident' field of Node for this, but it needs a delimiter, because str(row) + str(col) is not unique if you have multi-digit rows and columns. E.g., use f"{row},{col}". Don't store direction in the Node, but in the stack (see next point). An immutable game board also makes it easier to write unit tests, which will help your debugging, and obviates the need to muck around with deep copying.

2. DFS needs a stack. Each stack element needs to remember (a) the current node and (b) the state of iteration over child nodes (your "direction" + visited flag). You can make this stack explicit as a data structure, or you can implicitly use the call stack via recursion*, where local variables of a function call contain (a) and (b). You are mixing implicit and explicit stacks by using recursion but also storing direction in the game board. This will always lead to confusion.

3. If you need to remember paths, use an explicit stack. If you have programmatic access to the stack, you can rebuild the current path by iterating over the stack elements and grabbing current location from each. This is hard to do with recursion, but easy if your stack is explicit. With recursion, you can pass the current path as a parameter to each subsequent recursive call, but this is inefficient. In Python, this will look something like this. Note: no recursion. Also note: not tested :)

all_paths = []
visited = set()
stack = [ [starting_node, 0] ]  # (location, child node iteration)

while stack:
  current_node, child_index = stack[-1]
  
  # TODO test for leaf node status and emit path if this is a leaf, see next comment 

  # assuming each node has a list of adjacent nodes, which includes the parent in the traversal
  if child_index >= len(current_node.adjacent_nodes):
    stack.pop()
    continue
  stack[-1][1] = child_index + 1
  next_node = current_node.adjacent_nodes[child_index]
  if next_node.ident not in visited:
    visited.add(next_node.ident)
    stack.append( [next_node, 0] )

* Recursion in Python is a bad idea if you're traversing large graphs. You'll hit the stack limit.
posted by qxntpqbbbqxl at 11:49 AM on October 5, 2023 [3 favorites]

Best answer: ...and since I wasn't fast enough to abuse the edit window, insert this where the TODO is:

if child_index == 0 and (len(current_node.adjacent_nodes) == 0 or any(node.ident not in visited for node in current_node.adjacent_nodes)):
  all_paths.append([node for node, index in stack])
  stack.pop()
  continue  

posted by qxntpqbbbqxl at 11:58 AM on October 5, 2023 [1 favorite]

I don't know exactly what's wrong with your code, but ipdb is my favorite Python tool for situations like this.

All you have to do (after pip install ipdb) is insert these two lines of code anywhere in your program to set a "breakpoint":

import ipdb
ipdb.set_trace()


Then, when your program gets to those lines, it will stop execution and drop you into an interactive terminal where you can print the value of any variable and/or step through each line of code one by one to see how the values change. Super useful when you need to get to the bottom of WHY your logic is doing something weird.

(One additional thought — it looks like you have a recursive structure where scan() calls backtrack() and then backtrack() calls scan() which isn't ideal as qxntpqbbbqxl pointed out, and also makes it pretty difficult to reason about the logic. Try getting rid of the recursion.)
posted by mekily at 12:04 PM on October 5, 2023 [2 favorites]

Best answer: erm, final correction, the any condition I wrote is backwards :O. Replace it with this:

if child_index == 0 and all(node.ident in visited for node in current_node.adjacent_nodes):

posted by qxntpqbbbqxl at 12:34 PM on October 5, 2023 [2 favorites]

Response by poster: 1. Make the input graph immutable (the game board, in your case). Keep the visited set in the Walker instead. Give each node a unique id and use those for the visited set, instead of the Node object itself. You can use the 'ident' field of Node for this, but it needs a delimiter, because str(row) + str(col) is not unique if you have multi-digit rows and columns. E.g., use f"{row},{col}". Don't store direction in the Node, but in the stack (see next point). An immutable game board also makes it easier to write unit tests, which will help your debugging, and obviates the need to muck around with deep copying.

I'll try for a more functional and immutable approach as noted by you others. I know the code is not near optimal (or myself as a coder LOL)

I'll check out ipdb I'm using VSCode, not sure if that will be helpful there or not, but I can take a look.
posted by symbioid at 1:09 PM on October 5, 2023

I know AskMe doesn't like ChatGPT answers, but I would totally plunk this into ChatGPT 4 with Advanced Data Analysis enabled and see if it can point you in the right direction. Assuming you have access to ChatGPT 4; 3.5 (the free version) however might still be able to provide some helpful insights.
posted by cgg at 2:19 PM on October 5, 2023 [2 favorites]