Can You See the Forest for the Trees?

You stand at the origin of an endless grid of trees. Every other point with whole-number coordinates holds a tree, a perfect cylinder of radius $0.25$. Most trees are hidden behind the ones around you. Looking in every direction, how many different trees can you see?

The Fiddler, Zach Wissner-Gross, August 11, 2023(original post)

The official solution appeared in the post of August 18, 2023 and gives $32$ trees for the main puzzle and a longest line of sight of about $9.749$ for the Extra Credit, past the tree at $(9, 4)$. Both agree with the answers below.

Solution

Everything happens in the flat plane at eye level, where each tree is a disc of radius $r = \frac14$.

Which tree does a sight line meet first? A ray from the origin that passes through two trees cuts each of them in a chord, and because the trees do not overlap, neither do the chords. So the ray meets the trees in the order of their chords along it, which is the order of the feet of the perpendiculars from their centres. In particular a tree whose centre is farther away, measured along the ray, is always behind. A tree at distance $d$ from you blocks every direction within an angle $\arcsin(r/d)$ of its centre, and that angle is the tree’s shadow.

Using the symmetry. The grid looks the same after reflection in either axis or either diagonal, so it is enough to look at directions between due east ($0^\circ$) and northeast ($45^\circ$), and count each tree found there as many times as the symmetry copies it. The nearby trees in that range cast these shadows:

The shadows overlap end to end, so every direction from $0^\circ$ to $45^\circ$ meets one of these five trees, and each of them is seen. The tree $(1, 0)$ is the nearest tree of all; $(3, 1)$ is first in the gap from $14.48^\circ$ to $20.15^\circ$ left by $(1, 0)$ and $(2, 1)$; $(2, 1)$ is first around $26.57^\circ$; $(3, 2)$ is first in the narrow gap from $32.98^\circ$ to $34.82^\circ$ between $(2, 1)$ and $(1, 1)$; and $(1, 1)$ is first along the diagonal.

Every other tree is hidden. A tree at distance at least $\sqrt{17}$ lies, along any ray that meets it, at least $\sqrt{17 - r^2} \approx 4.12$ out, while the blocking tree on that ray is at most $\sqrt{13} \approx 3.61$ out, so it is behind. The closer trees not in the table are $(2, 0)$, $(3, 0)$ and $(4, 0)$, whose shadows lie inside that of $(1, 0)$; $(2, 2)$, whose shadow lies inside that of $(1, 1)$; and $(4, 1)$, whose shadow from $10.56^\circ$ to $17.51^\circ$ is covered by $(1, 0)$ and $(3, 1)$, both nearer.

Counting. The trees on the symmetry lines, $(1, 0)$ and $(1, 1)$, each have $4$ copies round the circle. The other three, $(3, 1)$, $(2, 1)$ and $(3, 2)$, each have $8$. So the total is $$\boxed{\ 4 + 4 + 3 \times 8 \;=\; 32 \text{ trees}. \ }$$

The computation

The check sweeps all the way round. It takes every tree within $25$ units and cuts the circle of directions at both edges of every tree’s shadow. Between two neighbouring cuts no tree enters or leaves the line of sight, and since the chords along a ray never cross, the first tree met stays the same. So it is enough to look along the middle of each gap, find the tree met first there by its actual entry distance, and record it. The function also keeps track of the longest line of sight, for the Extra Credit, and checks that no ray escapes the $25$-unit patch.

import numpy as np

def sweep(r, reach=25):
    """Look all round from the origin through a lattice of
    trees of radius r. Returns the trees seen and the longest
    line of sight."""
    pts = np.array([(x, y) for x in range(-reach, reach + 1)
                    for y in range(-reach, reach + 1)
                    if 0 < x*x + y*y <= reach*reach], float)
    d = np.hypot(pts[:, 0], pts[:, 1])
    centre = np.arctan2(pts[:, 1], pts[:, 0])
    half = np.arcsin(r/d)            # half of each shadow
    cuts = np.concatenate([centre - half, centre + half])
    cuts = np.sort(cuts % (2*np.pi))
    cuts = np.append(cuts, cuts[0] + 2*np.pi)

    def entry(i, theta):             # where the ray enters tree i
        off = np.angle(np.exp(1j*(theta - centre[i])))
        s = np.clip(d[i]*np.sin(off), -r, r)
        return d[i]*np.cos(off) - np.sqrt(r*r - s*s)

    seen, longest = set(), 0.0
    for a, b in zip(cuts[:-1], cuts[1:]):
        if b - a < 1e-12:
            continue
        mid = (a + b)/2
        off = np.angle(np.exp(1j*(mid - centre)))
        hit = np.abs(d*np.sin(off)) < r    # trees on the ray,
        hit &= np.cos(off) > 0             # in front of you
        assert hit.any(), "a ray escaped"
        idx = np.flatnonzero(hit)
        first = idx[np.argmin(entry(idx, mid))]
        seen.add(tuple(int(v) for v in pts[first]))
        # the same tree is first across the gap, and the sight
        # line is longest at one end
        ends = entry(first, a + 1e-13), entry(first, b - 1e-13)
        longest = max(longest, *ends)
    assert longest < reach - 1
    return seen, longest

seen, _ = sweep(0.25)
print("trees seen with radius 0.25:", len(seen))

It prints

trees seen with radius 0.25: 32

Extra Credit

Now the trees are thinner, with radius $0.1$. Looking due east you can see only $0.9$ units, to the tree at $(1, 0)$, but other directions reach farther. How long is your longest line of sight?

Solution

A line of sight ends where it first enters a tree. For a tree at distance $d$ whose centre is a perpendicular distance $h$ from the line, the line enters it at a distance $$e \;=\; \sqrt{d^2 - h^2} \;-\; \sqrt{r^2 - h^2}$$ from you: the foot of the perpendicular, less half the chord. As the direction turns away from the tree’s centre, $h$ grows and $e$ grows with it.

This settles where to look. Cut the directions at the shadow edges of all the trees, as before. Within one gap the same tree is met first, so the sight line is longest at one end of the gap, where the line just grazes the tree that blocks the neighbouring directions. The longest sight lines therefore slip past the edge of one tree to land on another far behind.

The trees are now thin, so the shadows are narrow and the first trees in some directions are a long way off. The most distant tree you can see is the one at $(9, 4)$, at distance $\sqrt{97} \approx 9.849$. It shows through a gap only $0.05^\circ$ wide, between the upper edge of the shadow of $(7, 3)$, at $23.951^\circ$, and the lower edge of the shadow of $(2, 1)$, at $24.002^\circ$.

The lower edge of the shadow of $(2, 1)$ is the line through the origin tangent to that tree on its clockwise side. Its direction is that of $(2, 1)$ turned clockwise by the angle $\alpha$ with $\sin\alpha = r/\sqrt5$ and $\cos\alpha = \sqrt{5 - r^2}/\sqrt5$, which is the unit vector $$u \;=\; \tfrac{1}{\sqrt5}\bigl(2\cos\alpha + \sin\alpha,\; \cos\alpha - 2\sin\alpha\bigr).$$ The perpendicular distance of $(9, 4)$ from this line is the size of the cross product $9u_y - 4u_x = (\cos\alpha - 22\sin\alpha)/\sqrt5$, which is $$h \;=\; \frac{\sqrt{5 - r^2} - 22r}{5} \;=\; \frac{\sqrt{4.99} - 2.2}{5} \;\approx\; 0.00677,$$ well inside the radius $0.1$, so the line does strike the tree at $(9, 4)$. It enters it after $$e \;=\; \sqrt{97 - h^2} - \sqrt{0.01 - h^2} \;\approx\; 9.84886 - 0.09977 \;\approx\; 9.7491 .$$ The other end of the gap, grazing $(7, 3)$, passes $(9, 4)$ with $h \approx 0.00198$ and gives a sight line of $9.7489$, slightly shorter because it strikes nearer the middle of the tree. So $$\boxed{\ \text{the longest line of sight is about } 9.749 \text{ units}. \ }$$ That no other gap does better is a matter of checking them all, which is what the computation below does: across the $192$ trees visible at this radius, the gap that shows $(9, 4)$ gives the longest sight line.

The computation

The sweep above already tracks, gap by gap, the entry distance at both ends of each gap.

seen, longest = sweep(0.1)
far = max(seen, key=lambda p: p[0]**2 + p[1]**2)
print(f"radius 0.1: {len(seen)} trees seen, farthest {far}")
print(f"longest sight {longest:.4f}")

It prints

radius 0.1: 192 trees seen, farthest (4, 9)
longest sight 9.7491

The farthest tree is reported as $(4, 9)$, the mirror image of $(9, 4)$ in the diagonal, which by symmetry gives the same sight line.