Teaser 3187: Wired squares
From The Sunday Times, 22nd October 2023 [link] [link]
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 14 cm side width) on one of the pages, with vertical and horizontal grid lines at 1 cm 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 14 cm side width could have allowed the connection of a larger number of squares.
What squares did he connect?
When originally posted on The Sunday Times website the upper limit was “less than 15 cm”, but this was revised down to “less than 14 cm” when the paper was published.
[teaser3187]
GeoffR, 
Hugh Casement, and 
Jim Olson and 
Frits are discussing. 
S2T2 
Jim Randell 8:06 am on 21 October 2023 Permalink |
Initially I drew out the various grids and looked for straight lines that could connect cells. (I am assuming the wire forms a sufficiently long straight line).
This program examines lines that pass through the corners of square-numbered cells (so it may not find all possible lines), but it does better than I did on my manual attempt.
It runs in 664ms.
Run: [ @replit ]
from enigma import (fdiv, inf) # find the slope and intercept of a line defined by points p1, p2 def line_slope_intercept(p1, p2, div=fdiv): ((x1, y1), (x2, y2)) = (p1, p2) if x1 == x2: return (inf, x1) m = div(y2 - y1, x2 - x1) c = y1 - m * x1 return (m, c) from enigma import ( Accumulator, irange, subsets, tuples, line_intersect, catch, uniq, unpack, rdiv, seq2str, printf ) # return the corners of a square corners = lambda x, y: [(x, y), (x + 1, y), (x + 1, y + 1), (x, y + 1)] # solve for an n x n grid # return max hits def solve(n, verbose=1): # calculate the corners of each square cell sqs = dict() pts = set() for i in irange(1, n): k = i * i (y, x) = divmod(k - 1, n) sqs[k] = (x, y) pts.update(corners(x, y)) # find maximal hits ss = Accumulator(fn=max, collect=1) # consider lines that pass through two of the points fn = unpack(lambda p1, p2: line_slope_intercept(p1, p2, div=rdiv)) for (p1, p2) in uniq(subsets(pts, size=2), fn=fn): # which squares are hit hit = set() for (k, (x, y)) in sqs.items(): for (c1, c2) in tuples(corners(x, y), 2, circular=1): r = catch(line_intersect, p1, p2, c1, c2, internal=2, div=rdiv) if r is None: continue hit.add(k) break ss.accumulate_data(len(hit), tuple(sorted(hit))) # output information if verbose: printf("[n={n}]") printf("max hits = {ss.value}") for hit in uniq(ss.data): printf("-> {hit}", hit=seq2str(hit, enc="[]")) printf() # return max hits return ss.value # consider grids up to size 13 r = Accumulator(fn=max, collect=1) for n in irange(1, 13): h = solve(n) r.accumulate_data(h, n) printf("max hits = {r.value} on grids {r.data}")Solution: The connected cells are: 1, 4, 16, 36, 49, 64.
My answer to the originally posted puzzle (with an upper limit of “less than 15 cm”) was the same, and is as follows:
In the revised puzzle, only the 13×13 grid is considered, so this must provide the answer. (Which makes me wonder why the puzzle has all the stuff about straightening the paperclip at all).
The [[
line_slope_intercept()]] function is included in the latest version of enigma.py.LikeLike