algorithm
I did not use [BFS] as there are multiple conditions to take care of.
Sorry, I didn't follow the reasoning there.
One could profitably apply either
BFS or
DFS
to this problem.
There is an opportunity to
"$ pip install networkx"
and take advantage of its graph traversal algorithms and data structures.
I understand you're doing this as a learning exercise;
installing a package like NetworkX would let you learn new skills.
Most python projects will eventually come to rely on the code and documentation
of external packages.
main guard
You wrote lots of logic up at module level.
Prefer to bury it within def main():
,
and use the customary guard:
if __name__ == "__main__":
main()
Then the open
cannot raise
at import
time, and we'll have less
coupling
from global variables.
When you get around to writing an
automated unit test,
it will want to be able to safely import
this module
without side effects, something the current code can't offer.
For example if it happens there's no "pro.txt" file we'll raise
FileNotFoundError, so "at import time" is the wrong time to be doing that.
Defer it until run time, using a __main__
guard.
list vs tuple
I really like the U, D, R, L coordinate deltas.
Please make them (dy, dx)
tuples, rather than the [dy, dx]
lists in OP code.
Why? In python we use list
for arbitrary number of "same thing",
e.g. names: list[str] = ["Alice", "Bob"]
.
Position doesn't matter, it doesn't change the meaning of an item.
We use tuple
for fixed number of "different things",
e.g. in delta: tuple(int, int) = (1, 0)
the dy of 1
has an entirely different meaning from the dx of 0
-- they're
distances in very different directions. We might even
name the tuple elements:
Delta = namedtuple("Delta", "x, y")
delta = Delta(1, 0)
comment
I see why you have "inverted coordinate order".
A casual reader might naïvely assume the conventional (dx, dy)
,
so adding a #
comment would be helpful.
Or name those components.
Similarly, spelling out that "Y coordinates are inverted"
from the usual "first quandrant" mathematical conventions wouldn't hurt.
Or consider relying on
numpy
instead of the list-of-lists datastructure.
And on the topic of "backwards", I don't understand this:
"╠":(U,L,D),
U, D? Perfect!
But L? It looks like R, to me.
Consistently doing mirror flip on X-coordinates
results in the "same" problem to be solved.
But there's room to better communicate technical
details to colleagues collaborating with you.
In any event, using those four symbols is a big win
over labeling the ten pieces with a bunch of integers,
so that's well done.
side effects
Yikes, this is a bit terrible:
# Function to check if the coordinates are within bounds of the grid
def check_bounds(index_coord):
while (index_coord[0]<0 or index_coord[0]>29 or
index_coord[1]<0 or index_coord[1]>49):
if visited: ...
The #
comment is nice enough, I suppose,
but please turn it into the function's """docstring""".
It should describe the return value,
or perhaps the signature could do that with something like
def check_bounds(index_coord) -> int:
, or even
def check_bounds(index_coord: tuple[int, int]) -> int:
At first blush this function computes a value to be returned.
But then it turns out we don't merely "check" the input.
No, we "mutate" a pair of module level global variables
which the comment didn't give a hint about at all.
Presumably there's some (unmentioned)
invariant
we're trying to preserve.
The 29
and 49
magic numbers
deserve names.
return 0
return index_coord
Yow! Holy type stability, Batman!
So it turns out the signature is more like
def check_bounds(index_coord) -> tuple[int, int] | int:
,
for reasons I do not yet fathom.
Typically we'll be making things easier for the
caller if a function consistently return
s answers of just one type.
Python is a dynamic language, but refrain from the temptation to get carried away.
Avoid writing tricky code.
Someone will have to debug it, probably you.
If it's unavoidable, then write a helpful docstring, and some unit tests.
predicate helper function
Rather than returning int
, consider adopting this signature:
def backup(direction, backup_coord) -> bool:
It does the same thing.
It just conveys the intent a little more clearly.
And since parameter names are part of the Public API
you're designing, prefer to spell them out.
As a local variable, direct
might be fine,
but not when it's exposed to callers.
meaningful names
def visit_app( ... ):
I was initially parsing that as "application",
before settling on "append".
But it's hard to work "visit append" into a sensible English sentence.
Consider renaming this.
Naming is a challenging, but important task.
Sorry, I do not yet know what the right name for this function is.
This function appears to be working too hard,
parsing inconvenient "pipe" symbols.
Back when you read in the grid configuration,
you could fill in two or three
edges
for each "pipe" node or grid cell.
That happens just once.
And then this function would have an easier time of it,
simply iterating over a given node's edges.
choice of datastructure
def vertical_unsuccessful( ... ): ...
def vertical( ... ): ...
def horizontal_unsuccessful( ... ): ...
def horizontal( ... ): ...
I haven't waded in to find exactly what's going on in there.
But when you see "same code, different direction",
that should make you reconsider your approach,
and maybe choose a datastructure where you can pass in a direction
to change the behavior.
For example, with a numpy
array,
it would be straightforward to work with axis=0
or axis=1
in order to change direction.
automated tests
You have some complex logic and state variables.
Go to the trouble of writing a
unit test
or two. Adding a second caller will help you notice where the documentation
or calling convention could be improved. And tests are always a big help
when you refactor, as they can reveal unexpected changes in behavior.