Maximum number of squares touched by a line segment

Question

Consider a square grid on the plane, with unit spacing. A line segment of integer length \$L\$ is dropped at an arbitrary position with arbitrary orientation. The segment is said to "touch" a square if it intersects the interior of the square (not just its border).

The challenge

What is the maximum number of squares that the segment can touch, as a function of \$L\$?

Examples

• L=3 \$\ \, \$ The answer is \$7\$, as illustrated by the blue segment in the left-hand side image (click for a larger view). The red and yellow segments only touch \$6\$ and \$4\$ squares respectively. The purple segment touches \$0\$ squares (only the interiors count).

• L=5 \$\ \, \$ The answer is \$9\$. The dark red segment in the right-hand side image touches \$6\$ squares (note that \$5^2 = 3^2+4^2\$), whereas the green one touches \$8\$. The light blue segment touches \$9\$ squares, which is the maximum for this \$L\$.

Additional rules

• The input \$L\$ is a positive integer.
• The algorithm should theoretically work for arbitrarily large \$L\$. In practice it is acceptable if the program is limited by time, memory, or data-type size.
• Input and output are flexible as usual. Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
• Shortest code in bytes wins.

Test cases

Here are the outputs for L = 1, 2, ..., 50 (with L increasing left to right, then down):

 3    5    7    8    9   11   12   14   15   17
18   19   21   22   24   25   27   28   29   31
32   34   35   36   38   39   41   42   43   45
46   48   49   51   52   53   55   56   58   59 
60   62   63   65   66   68   69   70   72   73

Answer 1

Python 2, 27 bytes

lambda L:(2*L*L-2)**.5//1+3

Try it online!

A direct formula:

$$ f(L) = \lfloor \sqrt{2 L^2-2}\rfloor + 3 $$

Derivation

As noted by @Kirill L. and others, the optimal layout uses a near-diagonal line segment whose horizontal and vertical span are at least \$(h,h)\$ or \$(h,h+1)\$. We need the length-\$L\$ to cover at least this much distance using the Pythagorean theorem, plus some extra to reach into squares and hit 3 more.

This gives a result of either:

• \$2h+3\$ where \$h\$ is the greatest positive integer where \$h^2+h^2 < L^2\$, or
• \$2h+4\$ where \$h\$ is the greatest positive integer where \$h^2+(h+1)^2 <L^2\$,

whichever of these is larger. We want to combine these two cases into one.

Let's start by making the two cases look more similar. Note that the second case can be rewritten as

\$2(h+\frac{1}{2})+3\$, where \$2(h+\frac{1}{2})^2 + \frac{1}{2} < L^2\$

or as

\$2h+3\$, where \$2h^2 + \frac{1}{2} < L^2\$

where \$h\$ is a positve integer-and-a-half. The \$2h^2<L^2\$ in the first case can be also be written as \$2h^2 +\frac{1}{2} < L^2\$, which is equivalent because both sides were integers. So, the cases now merge into:

\$2h+3\$ where \$h\$ is the greatest positive integer or half-integer where \$2h^2 +1/2 < L^2\$

Calling \$2h=H\$, this is:

\$H+3\$ where \$H\$ is the greatest positive integer where \$2(H/2)^2 +1/2 < L^2\$.

This inequality is \$H^2 < 2L^2-1\$, and since these are integers, this is the same as \$H^2 \leq 2L^2-2\$. The greatest such positive integer \$H\$ is then \$\lfloor \sqrt{2 L^2-2}\rfloor\$, so the final result is \$ \lfloor \sqrt{2 L^2-2}\rfloor + 3 \$.

Answer 2

R, 79 77 bytes

L=scan();j=1:L;a=j*2^.5;b=Mod(j+j*1i+1i);3+2*sum(L>a)+max(a[L>a],b[L>b])%in%b

Try it online!

Note: as it turned out, this is completely destroyed by xnor's formula, which would be 23 bytes in R:

(2*scan()^2-2)^.5%/%1+3

However, I'm keeping the existing code as a reference to my original solution.

Original explanation

In general case, the most squares will be touched when the line is going close to the diagonal orientation. Specifically, the number of touched squares will be equal to \$2 \times x + 3\$, where \$x\$ is the number of unit square diagonals fully covered by the line. The lengths of square diagonals are stored in a.

However, in some cases a better coverage can be achieved by deviating from the diagonal orientation. To account for this, we also store a vector b containing the lengths of diagonals of "deviated" rectangles of size \$1 \times 2\$ up to \$L \times (L+1)\$ (instead of squares up to \$L \times L\$). It looks like we need to count one additional touch in those cases where the maximal value of b that is still smaller than \$L\$ exceeds the analogous value from a.

For example, the first few diagonals are of length:

 1x1       2x2       3x3       4x4
 1.414214  2.828427  4.242641  5.656854 ...

We can see that after going from \$L = 3\$ to \$L = 4\$ we have still covered only the 2nd term (\$2 \times 2\$ diagonal), it's not enough to reach the edge of the 3rd square, so we are not gaining any more touches. But if we switch to the "deviated" rectangles:

 1x2       2x3       3x4       4x5
 2.236068  3.605551  5.000000  6.403124 ...
 

Here \$L = 4\$ now encompasses a larger value of 3.60..., which corresponds to (\$2 \times 3\$) rectangle. In this orientation we gain an extra touched square compared to the diagonal.

Answer 3

J, 28 bytes

-1 thanks to Jonah!

The optimal is always either the diagonal L, L with 3+2*L tiles crossed as noted by @Kirill L. or L, L+1, in which case an extra tile is crossed.

((>]+&.*:>:)+3+2*])[<.@%%:@2

Try it online!

• [<.@%%:@2 calculate L by dividing n by sqrt(2), then flooring
• 3+2*] 3+2*L
• ]+&.*:>: calculate length to L, L+1
• > … + if n is larger than this length, add 1

Because the lines have rational length n, and the diagonals irrational length L, we can always find an epsilon \$L - n > 0\$ to slide the line top-left to touch the 3 extra tiles, which justifies the 3+2*L.

L, L+2 will always be further away then the next diagonal L+1, L+1, as \$L^2 + (L+2)^2 = 2L^2 + 4L + 4 > 2L^2 + 4n + 2 = (L+1)^2 + (L+1)^2\$, so checking L, L+1 is enough.

Answer 4

Vyxal, 7 bytes

*d⇩√3+⌊

Try it Online!

Shameless port of xnor's answer

*       # Square
 d      # Double
  ⇩     # Subtract 2
   √    # Square root
    3+  # Add 3
      ⌊ # Floor

Answer 5

Jelly,  18 17  8 bytes

-9 using xnor's mathematical simplification of the same method as the 17, below.

²Ḥ_2ƽ+3

A monadic Link that accepts a positive integer, \$L\$ and yields the maximal squares touched.

Try it online! Or see the test-suite.

How?

²Ḥ_2ƽ+3 - Link: positive integer, L
²        - square -> L²
 Ḥ       - double -> 2L²
  _2     - subtract 2 -> 2L²-2
    ƽ   - integer square-root -> ⌊√(2L²-2)⌋
      +3 - add three

---

17:

²H½Ḟð‘Ḥ‘++²ḤƊ‘½<ʋ

Try it online!

How?

First finds the longest \$(a,a)\$ or \$(a,a+1)\$ diagonal that \$L\$ can cover with some to spare, then places the line along this diagonal, poking out at both ends, and shifts it in the \$x\$ direction to cover \$2a+3+X\$ squares where \$X=1\$ if the diagonal is \$(a,a+1)\$, otherwise \$X=0\$.

²H½Ḟð‘Ḥ‘++²ḤƊ‘½<ʋ - Link: positive integer, L
²                 - square -> L²
 H                - halve -> L²/2
  ½               - square-root -> side of square with diagonal L
   Ḟ              - floor -> a
    ð             - new dyadic chain, f(a,L)...
     ‘            - increment -> a+1
      Ḥ           - double -> 2a+2
       ‘          - increment -> 2a+3
                ʋ - last four links as a dyad, f(a, L):
            Ɗ     -   last three links as a monad, f(a):
          ²       -     square -> a²
         +        -     (a) add (that) -> a+a²
           Ḥ      -     double -> 2(a+a²)
             ‘    -   increment -> 2(a+a²)+1 = a²+(a+1)²
              ½   -   square-root -> diagonal length of (a,a+1)
               <  -   less than (L)? -> 1 or 0 -> X
        +         - (2a+3) add (X)

Answer 6

Perl 5, 73 bytes

for$d(0,1){$w=0;1while$w**2+($d+$w++)**2<$_**2;$m+=2*$w-1+$d}$_=int$m/2+1

Try it online!

Took @Kirill L.'s explanation and ran with it. Does two passes, without and with "deviation" in $d. The int$m/2+1 outputs the average (rounded up if .5) of those two passes, which will be the max of those two results. Reads the wanted length from stdin and prints max number of squares for that length. The following bash command outputs max number of squares touched for all lengths 1 to 50:

for l in {1..50}; do
  echo $l | perl -pe \
  'for$d(0,1){$w=0;1while$w**2+($d+$w++)**2<$_**2;$m+=2*$w-1+$d}$_=int$m/2+1';
  echo -n " ";
done

3 5 7 8 9 11 12 14 15 17 18 19 21 22 24 25 27 28 29 31 32 34 35 36 38 39 41 42 43
45 46 48 49 51 52 53 55 56 58 59 60 62 63 65 66 68 69 70 72 73

Answer 7

Japt, 10 bytes

Ò2nU²Ñ ¬ÄÄ

Try it

Ò2nU²Ñ ¬ÄÄ     :Implicit input of integer U
Ò              :Negate the bitwise NOT of (i.e., floor and increment)
 2n            :  Subtract 2 from
   U²          :    U squared
     Ñ         :    Times 2
       ¬       :  Square root
        ÄÄ     :Add one twice

Answer 8

JavaScript (Node.js), 20 bytes

n=>(2*n*n-2)**.5+3|0

Try it online!

Shamelessly copies the idea from xnor's answer

Answer 9

><>, 27 bytes

:*2*2-0v
:})?v1+>::*{
;n+2<

Try it online!

Xnor's formula, but in a language with neither square root nor rounding operations. Instead, it does the equivalent thing of finding the least square number larger than \$2L^2 - 2\$

Answer 10

Wolfram Language (Mathematica), 20 bytes (14 characters)

⌊√(2#^2-2)⌋+3&

Try it online!

Shamelessly translating xnor's Python answer.

Answer 11

Java (JDK), 28 bytes

L->L+=Math.sqrt(2*L*L-2)+3-L

Try it online!

Same as everyone, I guess, cheers to xnor!

Same length as:

L->(int)Math.sqrt(2*L*L-2)+3

Try it online!

Answer 12

Retina, 43 29 bytes

.+
**2*
(^_|\1__)*__+
__$#1*

Try it online! Link is to test suite that generates the results from 1 to the input. Explanation: Now using @xnor's formula.

.+
**2*

Double the square of L and convert it to unary.

(^_|\1__)*__+
__$#1*

Subtract 2 and take the integer square root. This is based on @MartinEnder's comment to my Retina answer to It's Hip to be Square but without the leading ^ anchor as the subtraction of 2 guarantees a single match.

Add a final 1 and convert to decimal.

Previous 43-byte solution based on @KirillL.'s answer:

.+
**
((^(_)|\2__)*)\1(\2_(_))?.+
__$2$3$5

Try it online! Link is to test suite that generates the results from 1 to the input. Explanation:

.+
**

Square L and convert it to unary.

((^(_)|\2__)*)\1(\2_(_))?.+

Find the largest n where 2n²<L², thereby dividing L by √2. Additionally, try to match a further 2n+1 (\2 contains 2n-1), because a rectangle of dimensions n by n+1 has diagonal √(2n²+2n+1). Match at least a further 1 so that the inequality is strict, but also because it guarantees a single match.

__$2$3$5

Calculate 2+2n, plus add another 1 for the rectangular case. Note that $2$3 is used because \2 doesn't actually contain 2n-1 when n=0, but $2$3 is always 2n.

Add a final 1 and convert to decimal.

Answer 13

Stax, 7 bytes

é╟φQRl:

Run and debug it

Answer 14

05AB1E, 7 bytes

n·Ít3+ï

Port of @xnor's Python answer, so using the same formula:

$$f(L) = \lfloor\sqrt{L^2+2}+3\rfloor$$

Try it online or verify the first 50 test cases.

Explanation:

n        # Square the (implicit) input-integer
 ·       # Double it
  Í      # Subtract it by 2
   t     # Take the square-root of that
    3+   # Increase it by 3
      ï  # Truncate/floor it to an integer
         # (after which the result is output implicitly)

Answer 15

MathGolf, 7 bytes

²∞⌡√3+i

Port of @xnor's Python answer, so using the same formula:

$$f(L) = \lfloor\sqrt{L^2+2}+3\rfloor$$

Try it online.

Explanation:

²        # Square the (implicit) input-integer
 ∞       # Double it
  ⌡      # Subtract it by 2
   √     # Take the square-root of that
    3+   # Increment it by 3
      i  # Convert it to an integer
         # (after which the entire stack is output implicitly as result)