Sunday Times Teaser 3187 – Wired Squares

by BRG on October 20, 2023

by Mark Valentine

Published Sunday October 22 2023

Sitting at his study desk one morning, Ted noticed a paperclip poking out of his notebook, unbent to a straight thin wire. Opening it up he found that his granddaughter Jessica had drawn a square grid (less than 14cm [1] side width) on one of the pages, with vertical and horizontal grid lines at 1cm intervals.

Musing this, Ted numbered each cell consecutively from 1, working left to right along each row from top to bottom in turn. Moving the wire over the page, he rested the wire over (or touching the corner of) some cells containing a square number. Placing the wire carefully, he was able to connect as many square-numbered cells as possible in this way. No square grid of less than 14cm [1] side width could have allowed the connection of a larger number of squares.

What squares did he connect?

[1] This was originally 15cm when first published.

From → Uncategorized

2 Comments Leave one →

BRG permalink


from itertools import combinations

# use a power of two here to keep floating point exact
steps = 1

# find the intersection point of two lines in a plane  
# line 1  from p = (x1, y1) to q = (x2, y2)
# line 2  from r = (x3, y3) to s = (x4, y4)
def line_intersection(p, q, r, s):
  pq0, pq1 = p[0] - q[0], p[1] - q[1]
  rs0, rs1 = r[0] - s[0], r[1] - s[1]
  d = pq0 * rs1 - pq1 * rs0
  # if lines can intersect (i.e. they are not parallel)
  if d:
    pr0, pr1 = p[0] - r[0],  p[1] - r[1]
    e = (pr0 * rs1 - pr1 * rs0) / d
    f = (pr0 * pq1 - pr1 * pq0) / d

    if 0 <= e <= 1 and 0 <= f <= 1:
      return [p[0] - e * pq0, p[1] - e * pq1]

# return (x, y) positions on the perimeter of a grid cell 
# with <steps> positions per side 
def steps_around(x, y, steps):
  # start at each corner (x, y) position
  for xx, yy, dx, dy in ((x, y, 1, 0), (x + 1, y, 0, 1),
                 (x + 1, y + 1, -1, 0), (x, y + 1, 0, -1)):
    # step along side
    for s in range(steps):
      yield xx + s * dx / steps, yy + s * dy / steps 

# the number of grid cells in the x and y directions 
for n in range(1, 14):
  # map squares to the co-ordinates of their grid cell
  sq_xy = dict((i * i, divmod(i * i - 1, n)) for i in range(1, n + 1))

  max_sqrs_n = []  
  # consider lines between two squares 
  for (sq1, (x1, y1)), (sq2, (x2, y2)) in combinations(sq_xy.items(), 2):
    max_sqrs = []
    # consider all lines between points on their perimeters
    for p1 in steps_around(x1, y1, steps):
      for p2 in steps_around(x2, y2, steps):
        
        sqrs = {sq1, sq2}
        # now consider all other squares ...
        for sq, (x, y) in sq_xy.items():
          if sq in {sq1, sq2}:
            continue
          cs = ((x, y), (x + 1, y), (x + 1, y + 1), (x, y + 1), (x, y))
          # ... and list those squares that the line touches or traverses
          if any(line_intersection(p1, p2, cs[k], cs[k + 1]) for k in range(4)):
            sqrs.add(sq)
        # keep squares for a line that touches or traverses the most squares 
        if len(sqrs) > len(max_sqrs):
          max_sqrs = sorted(sqrs)
  
    if len(max_sqrs) > len(max_sqrs_n):
      max_sqrs_n = max_sqrs
  
  print(f"grid size = {n:02}, squares = {max_sqrs_n}")

from itertools import combinations

# use a power of two here to keep floating point exact

steps = 1

# find the intersection point of two lines in a plane

# line 1 from p = (x1, y1) to q = (x2, y2)

# line 2 from r = (x3, y3) to s = (x4, y4)

def line_intersection(p, q, r, s):

pq0, pq1 = p[0] - q[0], p[1] - q[1]

rs0, rs1 = r[0] - s[0], r[1] - s[1]

d = pq0 * rs1 - pq1 * rs0

# if lines can intersect (i.e. they are not parallel)

if d:

pr0, pr1 = p[0] - r[0], p[1] - r[1]

e = (pr0 * rs1 - pr1 * rs0) / d

f = (pr0 * pq1 - pr1 * pq0) / d

if 0 <= e <= 1 and 0 <= f <= 1:

return [p[0] - e * pq0, p[1] - e * pq1]

# return (x, y) positions on the perimeter of a grid cell

# with <steps> positions per side

def steps_around(x, y, steps):

# start at each corner (x, y) position

for xx, yy, dx, dy in ((x, y, 1, 0), (x + 1, y, 0, 1),

(x + 1, y + 1, -1, 0), (x, y + 1, 0, -1)):

# step along side

for s in range(steps):

yield xx + s * dx / steps, yy + s * dy / steps

# the number of grid cells in the x and y directions

for n in range(1, 14):

# map squares to the co-ordinates of their grid cell

sq_xy = dict((i * i, divmod(i * i - 1, n)) for i in range(1, n + 1))

max_sqrs_n = []

# consider lines between two squares

for (sq1, (x1, y1)), (sq2, (x2, y2)) in combinations(sq_xy.items(), 2):

max_sqrs = []

# consider all lines between points on their perimeters

for p1 in steps_around(x1, y1, steps):

for p2 in steps_around(x2, y2, steps):

sqrs = {sq1, sq2}

# now consider all other squares ...

for sq, (x, y) in sq_xy.items():

if sq in {sq1, sq2}:

continue

cs = ((x, y), (x + 1, y), (x + 1, y + 1), (x, y + 1), (x, y))

# ... and list those squares that the line touches or traverses

if any(line_intersection(p1, p2, cs[k], cs[k + 1]) for k in range(4)):

sqrs.add(sq)

# keep squares for a line that touches or traverses the most squares

if len(sqrs) > len(max_sqrs):

max_sqrs = sorted(sqrs)

if len(max_sqrs) > len(max_sqrs_n):

max_sqrs_n = max_sqrs

print(f"grid size = {n:02}, squares = {max_sqrs_n}")

Frits permalink

The thin wire length is unknown and thus it may have an effect on the number of connected square-numbered cells.

Reply

Sunday Times Teaser 3187 – Wired Squares

by Mark Valentine

Published Sunday October 22 2023

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta