Solution to Fiddler’s puzzle, Can You See the Forest for the Trees? (August 11, 2023).

You find yourself amidst what appears to be an infinite grid of trees. For the purposes of this puzzle, let’s suppose each tree is a perfect cylinder. You are at the point (0, 0), but there’s a tree with a radius of 0.25 units (and diameter 0.5 units) centered at every other point in the plane with integer coordinates. Of course, you can’t actually see infinitely many trees. Most of them are obscured by the trees immediately around you. As you look around in all directions, how many distinct trees are you able to see?

EXTRA CREDIT: Once again, you are located at (0, 0) amidst an infinite grid of cylindrical trees. But this time, the trees are narrower, each with a radius of 0.1 units (and diameter 0.2 units). When you look due east, your line of sight is 0.9 units, thanks to the tree centered at (1, 0). But if you look in other directions, it’s possible to see farther away. How long is your longest line of sight? Assume you are looking level with the ground, so that this is a two-dimensional puzzle (rather than three-dimensional one).

I will exploit the two-fold symmetry of the grid arrangement and apply the line segment intersection technique outlined here

create_vector_rand <- function(mag) {
  angle <- runif(1, 0, pi / 2)
  random_vector <- tibble(
    x = 0, y = 0,
    xend = mag * cos(angle),
    yend = mag * sin(angle)
  )
}

check_intersection <- function(x1, y1, x2, y2, x3, y3, x4, y4) {
  orientation <- function(xa, ya, xb, yb, xc, yc) {
    val <- (yb - ya) * (xc - xb) - (xb - xa) * (yc - yb)
    if (abs(val) < 1e-10) {
      return(0)
    } # Collinear
    if (val > 0) {
      return(1)
    } # Clockwise
    return(2) # Counterclockwise
  }

  o1 <- orientation(x1, y1, x2, y2, x3, y3)
  o2 <- orientation(x1, y1, x2, y2, x4, y4)
  o3 <- orientation(x3, y3, x4, y4, x1, y1)
  o4 <- orientation(x3, y3, x4, y4, x2, y2)

  # General case: lines intersect if orientations differ
  if (o1 != o2 && o3 != o4) {
    return(TRUE)
  }

  return(FALSE)
}

run_sim <- function(n, r, n_sim, print_sim = FALSE) {
  hash_tree <- list()
  mag <- sqrt(n^2 + n^2) + 2 * r

  segments <- expand_grid(x = 0:n, y = 0:n) |> # sorted output, zero is redundant
    rownames_to_column("pt") |>
    filter(!x + y == 0) |>
    mutate(
      x_l = x - r,
      x_r = x + r,
      y_l = y,
      y_r = y,
      ang = atan2(y, x) * 180 / pi + 90
    ) |>
    group_by(pt) |>
    group_map(
      ~ rotate_2d(
        data = .,
        degrees = .[["ang"]],
        x_col = "x_l",
        y_col = "y_l",
        origin = c(.[["x"]], .[["y"]]),
        keep_original = TRUE
      ),
      .keep = T
    ) |>
    bind_rows() |>
    group_by(pt) |>
    group_map(
      ~ rotate_2d(
        data = .,
        degrees = .[["ang"]],
        x_col = "x_r",
        y_col = "y_r",
        origin = c(.[["x"]], .[["y"]]),
        keep_original = TRUE,
        overwrite = TRUE
      ),
      .keep = T
    ) |>
    bind_rows() |>
    mutate(distance_to_origin = sqrt(x^2 + y^2) |> round(3)) |>
    select(pt,
      x_cartesian = x,
      y_cartesian = y,
      x = x_l_rotated,
      y = y_l_rotated,
      xend = x_r_rotated,
      yend = y_r_rotated,
      distance_to_origin
    )


  for (i in 1:n_sim) {
    random_vector <- create_vector_rand(mag = mag)

    intersections <- segments |>
      rowwise() |>
      mutate(
        intersects = check_intersection(
          x, y, xend, yend,
          random_vector$x, random_vector$y,
          random_vector$xend, random_vector$yend
        )
      ) |>
      ungroup()

    tree_sel <- intersections |>
      filter(intersects) |>
      arrange(distance_to_origin) |>
      head(1)

    if (!tree_sel$pt %in% hash_tree) {
      hash_tree[tree_sel$pt] <- tree_sel$distance_to_origin
    }

    if (print_sim & i == n_sim) {
      p <- segments |>
        ggplot() +
        geom_circle(aes(x0 = x_cartesian, y0 = y_cartesian, r = r), fill = "grey") +
        geom_segment(aes(x = x, y = y, xend = xend, yend = yend), color = "blue") +
        geom_segment(data = random_vector, aes(x = x, y = y, xend = xend, yend = yend), color = "red", arrow = arrow()) +
        scale_y_continuous(breaks = breaks_pretty(n = n)) +
        coord_cartesian(xlim = c(0, n + 1), ylim = c(0, n + 1)) +
        coord_fixed() +
        theme_classic() +
        labs(title = "Example Sim")

      print(p)
    }
  }

  return(hash_tree)
}

Answer

hash_tree <- run_sim(n = 4, r = 0.25, n_sim = 10000, print_sim = TRUE)

str_glue("num trees: ({length(hash_tree)} - 0.5*2)*4 = 32")
## num trees: (9 - 0.5*2)*4 = 32

Bonus:

As the grid size increases, the maximum line of sight converges to the closest distance from point to origin.

hash_tree <- run_sim(n = 25, r = 0.1, n_sim = 1000, print_sim = FALSE)
str_glue("line of sight: {hash_tree |> unlist() |> max() - 0.1}")
## line of sight: 9.749