Running from Samsquanch - Part 1 [SOLUTION]

Were you able to escape?

Our problem from 8/25/24 was

You’re thinking about doing a backpacking trip through Rainier National Park but there’s one big concern; that’s Samsquanch territory! After thinking it over for a moment you realize you have one big advantage; Samsquanch’s broad shoulders make it more difficult to navigate dense trees while your small, nerdy frame can fit quite easily. In order to make sure you have a chance to escape, you want to make sure the forest you’re hiking through has sufficient tree density.

Let’s model our forest as a 10x10 square. The top will be the entrance and the bottom will be the exit. For simplicity, we will assume the sides are impassable barriers. Each tree will be modeled by a point and Samsquanch will be modeled by a circle of radius 1. Trees will be distributed uniformly in the 10x10 square. Let’s further assume that Samsquanch can’t fit between any two trees that are less than 2R apart. We need to figure out what density the trees need to be in order for you to evade Samsquanch.

But before tackling this rather tricky probability problem, let’s start with a (hopefully) simpler problem:

Given a randomly sampled forest, what’s the most efficient algorithm you can find to determine if Samsquanch can traverse the forest?

Unsurprisingly, we didn’t have any submissions for XPC’s first puzzle. Not to worry though—we’re just getting started. Hopefully you readers will subscribe and submit your solutions :)

I posted my full solution here where I include some simple visualizations. To summarize, we need a way to to determine if Samsquanch can fit through a given forest. If Samsqanch is modeled as a circle of radius 1, then two trees must be at least 2 apart for him to fit through. If not, he has to find a different route. In fact, if there’s a sufficiently dense band of trees going from the left side of the forest to the right, then we know Samsquanch can’t fit. But if there are any gaps, he will be able to get through. With this thinking in mind, I modeled the forest as a graph where two tree nodes were connected if they were closer than 2 apart. If we can find a continuous path on this graph that goes from a tree within 2 of the left side to a tree that’s within 2 of the right side. We know we’ll have found a band that Samsquanch can’t pass. If no such path exists, then we know he can get through. Voila! Once we’ve constructed our graph, all we need to do is implement a simple depth first search to see if such a path exists on the graph.

Overall computing the graph requires O(N*N) and the depth first search is O(S*N) in the worst case where S is the number of starting trees (i.e. trees within 2 of the left side) and N is the total number of trees in the forest. Since S < N, we can say the bounding computation in the solution is the creation of the graph with O(N*N).

If we wanted to get fancy, we could construct the graph with the help of k-d trees with O(N*log(N)) but I didn’t implement such a solution this time around.

I hope you found this problem fun! Feel free to leave comments, thoughts, etc in the comments.