Today was interesting. I inadvertently solved for Part2 first, before realising my bug and subsequently fixing it for Part1 and then undoing my changes to get Part2 answer 😂
Not sure if recursion was a valid choice for this problem but I attempted it and was only able to finish it after looking at your BFS and understanding th. The conditions are actually identical but with slightly different added logic (like a base case) due to call stack stuff etc. Code provided below if anyone is interested. Not sure if this algorithm has an actual name, possibly DFS? (apologies, not a CompSci student) def traverse(grid, r, c, visited: set): if grid[r][c] == 9: # base case: summit found (trail completed) return 1 dir = [(-1, 0), (0, 1), (1, 0), (0, -1)] # directions to check trails summits = 0 # count variable to accumulate
for dr, dc in dir: nr, nc = r + dr, c + dc # new location (in direction) if not (0
solution for part 1 involved grabbing all different summits you could get from any start (by filtering the ones seen already)... and then part 2 was just printing the whole thing without filtering. I actually took a longer time playing around with directionals and structures than solving the thing (I'm playing around with C only primitives and no fancy library functions other than my own), its really funny to see pythonland from that angle Great videos as always!
My solution was interesting: I just did a BFS like you but stored a set of 9s reached for part 1 and returned the length of that set, then for part 2 returned the length of a list (not a set) of nines for a simple modification
haha for my solution on part 2 i just commented out the one condition where i was checking if the position was already in seen or not and it worked. Maybe i got lucky. edit: just finished watching and yeah thats the same thing you did in contest
with BFS i don't need to worry about blowing up the stack and BFS finds the shortest path. DFS doesn't really work unless you have a sufficiently small acyclic graph; this applies here but it's easier to not have to think about the structure lol
I was wondering why everyone uses deque insted of list with pop(0). Then i read the python docs: Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation. Today performance wasnt an issue, so you could shave a few seconds by using a list instead 😅
hmm, that's true. maybe today would've been a good opportunity to show off a trick for replacing a queue with a list; rather than using pop(0) you can sacrifice a bit of memory for speed by just looping through the list. you can append to a list as you loop through it so you can just do "for cr, cc in q" and then append to "q" within the loop
Today was interesting. I inadvertently solved for Part2 first, before realising my bug and subsequently fixing it for Part1 and then undoing my changes to get Part2 answer 😂
Hahaha same
Same
Same
Same
Same 😂
I have reached a point where with every problem I try, I also have to solve the "WHAT AM I DOING WRONG???" part
Not sure if recursion was a valid choice for this problem but I attempted it and was only able to finish it after looking at your BFS and understanding th. The conditions are actually identical but with slightly different added logic (like a base case) due to call stack stuff etc. Code provided below if anyone is interested. Not sure if this algorithm has an actual name, possibly DFS? (apologies, not a CompSci student)
def traverse(grid, r, c, visited: set):
if grid[r][c] == 9: # base case: summit found (trail completed)
return 1
dir = [(-1, 0), (0, 1), (1, 0), (0, -1)] # directions to check trails
summits = 0 # count variable to accumulate
for dr, dc in dir:
nr, nc = r + dr, c + dc # new location (in direction)
if not (0
solution for part 1 involved grabbing all different summits you could get from any start (by filtering the ones seen already)... and then part 2 was just printing the whole thing without filtering.
I actually took a longer time playing around with directionals and structures than solving the thing (I'm playing around with C only primitives and no fancy library functions other than my own), its really funny to see pythonland from that angle
Great videos as always!
My solution was interesting: I just did a BFS like you but stored a set of 9s reached for part 1 and returned the length of that set, then for part 2 returned the length of a list (not a set) of nines for a simple modification
Since each path taken is different, it will guarantee that each way a 9 can be reached is counted exactly once
Pretty much like your alternate solution
did the same, but with DFS
yep, that's how i did it during my initial solve at midnight as well, but instead of changing the set to a list i just changed it to a counter
my answer for part 1 and 2 were exactly as yours "737", "1619" maybe we got the same seed :D
wondering how many unique seeds there are for each task
Got part 1 (with help from your video - thank you!) but part 2 will need to wait until after the day job.
haha for my solution on part 2 i just commented out the one condition where i was checking if the position was already in seen or not and it worked. Maybe i got lucky.
edit: just finished watching and yeah thats the same thing you did in contest
Nice solution!!! I use recursion instead. Why do you prefer BFS (just curiosity)?
Because it shouts for BFS or DFS?
with BFS i don't need to worry about blowing up the stack and BFS finds the shortest path. DFS doesn't really work unless you have a sufficiently small acyclic graph; this applies here but it's easier to not have to think about the structure lol
@@hyper-neutrino For some reason, I don't think you have a problem with 'thinking'. Great video as always.
I was wondering why everyone uses deque insted of list with pop(0). Then i read the python docs:
Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
Today performance wasnt an issue, so you could shave a few seconds by using a list instead 😅
hmm, that's true. maybe today would've been a good opportunity to show off a trick for replacing a queue with a list; rather than using pop(0) you can sacrifice a bit of memory for speed by just looping through the list. you can append to a list as you loop through it so you can just do "for cr, cc in q" and then append to "q" within the loop
@hyper-neutrino cool, didn't know you could alter the list you are looping!
goat