Advent of Code - adventofcode.com

You are reading a single comment by @frankenbike and its replies. Click here to read the full conversation.

•

wence
A lot of stacks the past few days...

https://gist.github.com/wence-/500e1bc4633192ac6fee67433aedd974#file-day09-py and so on.

@frankenbike FWIW, your recursive implementation of DFS is not overly idiomatic in imperative languages, the usual approach is:
```
stack = [start]
seen = set()
while stack:
    n = stack.pop()
    for c in neighbours(n):
        if c not in seen:
            stack.append(c)
            # do whatever...
```

•

frankenbike in reply to @wence

I appreciate the advice, I'm considering these interview practice 🙂

Would that not be more like a BFS though? I'm going to visit each neighbour before I visit any neighbours of neighbours right? Suppose you could insert into the stack instead. Not that it matters whether we use BFS/DFS in the problems we've had so far

•

Greenbank in reply to @frankenbike

I didn't use a stack for day 11, I just marked cells that had already flashed that step with a special entry so I could stop it processing a cell more than once per step. That way is was just a relatively simple DFS.

https://gist.github.com/alexgreenbank/7a9123f8bd1aec310d75836f8946596b
•

wence in reply to @frankenbike

Oh yeah, sorry. Here’s a reasonably idiomatic child before parent traversal.

https://github.com/firedrakeproject/tsfc/blob/c9fc62334de20229540be7dc57f6ed91ec26ae3f/gem/node.py#L123

About

Avatar for frankenbike @frankenbike started