Skip to main content
Stack Overflow
  1. About
  3. For Teams

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Required fields*

Python: Functions where a variable with the same name of the input is generated

Apologies for any possible confusion about the title. I will try my best to illustrate my question.

Context:

I just finished working on an interesting coding problem on CodeWars where I was asked to write a function to simplify a list of directions.

The input will look like ["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

The 'SOUTH' 'NORTH' and 'EAST' 'WEST' that are next to each other shall both be deleted since it makes little sense to go north and then immediately south. And the list shall be simplified until it can't be simplified anymore.

For instance:

["NORTH", "SOUTH", "SOUTH", "EAST", "WEST", "NORTH", "WEST"]

shall be simplified to

['WEST']

Dummy OP wrote a clunky function that does it. But my question is about a really clever answer posted by someone else.

Code:

def dirReduc(arr):
 dir = " ".join(arr)
 dir2 = dir.replace("NORTH SOUTH",'').replace("SOUTH NORTH",'').replace("EAST WEST",'').replace("WEST EAST",'')
 dir3 = dir2.split()
 return dirReduc(dir3) if len(dir3) < len(arr) else dir3

I played with it and see that it works but just couldn't wrap my head around how.

I see that in the return statement, it shall run again unless the result has the same length as input, which is understandable. But the code uses dirReduc(dir3) which seems wrong to me.

If I run dirReduc(dir3) then my input will be dir3, but then inside the frame of the function, another dir3 is created. So now when the function goes to the final return statement it shall be return dirReduc(dir3) if len(dir3) < len(dir3) else dir3. And since len(dir3) == len(dir3)', it will just returndir3`.

In my understanding, the function will be run twice, max with each input, which is not the truth. So which part of my understanding is wrong?

Sorry for the sheer volume of words, I think after all this is a simple problem. There must be a very fundamental thing that I'm getting wrong.

Answer*

Draft saved
Draft discarded
Cancel
11
  • I would argue that the second problem is in fact less interesting. Its optimal solution runs in Ө(n) time and Ө(log n) auxiliary space. However, the given solution to the original problem requires Ο(n^2) time, albeit only Ө(1) space (assuming tail-call optimization, which à propos is not the case with Python, so it's in fact Ο(n) space). An alternative solution would require Ө(n) time and Ο(n) space (to maintain a stack of counters, one for each N/S or E/W level). Commented Dec 9, 2018 at 1:19
  • Yes, but why would you only want a partially compressed path, instead of the shortest possible path? That's what I meant by "more interesting". Commented Dec 9, 2018 at 15:50
  • Imagine you are at coordinate (0,0). You need to go 2 units to the east -- to (0,2), but there is an obstacle at (0,1). So you cannot just "compress" N-E-E-S to E-E because you would run into the obstacle. Imagine the input directions describe a walk in a directed graph (en.wikipedia.org/wiki/Glossary_of_graph_theory_terms#walk); what you want to do is make it into a simple path (en.wikipedia.org/wiki/Simple_path). Commented Dec 9, 2018 at 16:31
  • Ok, that's a good point. I was thinking of a fully connected space. Commented Dec 9, 2018 at 17:23
  • Thanks. I forgot about the basic concept of stack frame. Please lemme know if I'm understanding correctly. After the first iteration, when the function is going to run dirReduc(dir3), this dir3 is established in the first stack frame, and in the run of dirReduc(dir3), the return statement will be dirReduc(dir3(2nd stack frame) if len(dir3(2nd stack frame)) < len(dir3(first stack frame). Did I get it right? Thanks again. Commented Dec 10, 2018 at 15:10

lang-py

AltStyle によって変換されたページ (->オリジナル) /