36
\$\begingroup\$

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\$.

enter image description here

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
\$\endgroup\$
5
  • 16
    \$\begingroup\$ No OEIS entry, apparently (maybe soon) \$\endgroup\$
    – Luis Mendo
    Jul 10 at 15:35
  • 2
    \$\begingroup\$ I really liked this one from a problem-solving perspective. \$\endgroup\$
    – Jonah
    Jul 10 at 23:59
  • \$\begingroup\$ My Math.SE question will be interesting to y'all and relevant to this question \$\endgroup\$
    – wasif
    Jul 11 at 9:03
  • \$\begingroup\$ This reminds me of the problem of optimizing beam placement in FTL \$\endgroup\$ Jul 13 at 2:02
  • 1
    \$\begingroup\$ This sequence is now in OEIS: A346232 \$\endgroup\$
    – Luis Mendo
    Jul 15 at 0:02

15 Answers 15

25
\$\begingroup\$

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 \$.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Fantastic. "We want to combine these two cases into one. Let's start by making the two cases look more similar." Did you know somehow this could be done at the outset (if so, how?), or did you just guess it might be possible, and start playing around? \$\endgroup\$
    – Jonah
    Jul 11 at 3:55
  • 2
    \$\begingroup\$ @Jonah It was a guess, but it seemed to me like something like this should be possible because the two types of outputs lie nearly on the same approximate curve. \$\endgroup\$
    – xnor
    Jul 11 at 4:06
  • 2
    \$\begingroup\$ Wonderful! Simpler than the formula I had obtained \$\endgroup\$
    – Luis Mendo
    Jul 11 at 10:41
  • \$\begingroup\$ I intend to submit this sequence to OEIS. Your formula is simpler than the one I had (i+j+3 with i = floor(L/sqrt(2)), j=ceil(sqrt(L^2-i^2))-1, so I'd like to give you credit (in addition to linking this challenge). How can I do that? If you prefer we can go on using e-mail \$\endgroup\$
    – Luis Mendo
    Jul 11 at 15:22
  • \$\begingroup\$ I may also have to write a short paper to support the submission, in particular to justify that the optimal segment orientation is always (h,h) or (h,h+1). Are interested in collaborating on this? Please let me know either way \$\endgroup\$
    – Luis Mendo
    Jul 12 at 8:55
12
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ I tested up to 100 and we get the same results \$\endgroup\$
    – Luis Mendo
    Jul 10 at 21:00
  • \$\begingroup\$ @LuisMendo Thanks for checking, now when I manually counted the first special case of L = 4, I also feel more confident about it \$\endgroup\$
    – Kirill L.
    Jul 10 at 21:40
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice J, and nice correctness argument. \$\endgroup\$
    – Jonah
    Jul 10 at 23:52
  • 1
    \$\begingroup\$ ((>]+&.*:>:)+3+2*])]<.@%%:@2 for 28. \$\endgroup\$
    – Jonah
    Jul 10 at 23:55
  • \$\begingroup\$ 15 using xnor's formula: 3+_2<.@%:@+2**: \$\endgroup\$
    – Jonah
    Jul 11 at 3:46
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 20 bytes

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

Try it online!

Shamelessly copies the idea from xnor's answer

\$\endgroup\$
1
\$\begingroup\$

><>, 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\$

\$\endgroup\$
1
\$\begingroup\$

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

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

Try it online!

Shamelessly translating xnor's Python answer.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Stax, 7 bytes

é╟φQRl:

Run and debug it

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.