From The Sunday Times, 19th October 2025 [link] [link]
George and Martha are keen pop music fans. They recently followed the progress of one record in the charts and noticed that it was in the Top Ten for three weeks in three different positions, the third week’s position being the highest. In practice, a record never zigzags; it reaches a peak and then drops. For example: 5,4,9 or 5,6,9 are possible but 2,5,3 is not.
“That’s interesting!”, commented Martha. “If you add the three positions, you get the day of the month when my father was born; and if you multiply them, you get a number giving the month and last two digits of that year”. “Furthermore”, added George “two of the positions also indicate the last two digits of that year”.
What were the three positions in chronological order, and what was the date of Martha’s father’s birth?
[teaser3291]
With the school inspector scheduled to visit her school, Tina is taking extra care in preparing her lesson plan. The lesson deals with areas, shapes and symmetries. She has produced soft cards on which have been printed a four by four grid, and will ask the pupils to cut the grid into two shapes of equal area, but by only cutting along the lines. She wanted them to create as many different possible shapes in this way, explaining that two shapes are different only if you can’t make one the same as the other by rotating it, turning it over, or both. It turned out that the maximum number of different shapes was the same as the number of pupils in the class.
Alex.T.Sutherland, 
Brian Gladman, and 1 other are discussing. 
Jim Olson are discussing. 
Frits and 
GeoffR, and 
S2T2 
Jim Randell 7:30 am on 9 November 2025 Permalink |
(See also: BrainTwister #29, Enigma 54).
This Python program considers possible dissections of the grid into two connected shapes, and then records a canonical form of the shapes to find the number of different shapes.
It runs in 233ms. (Internal runtime is 154ms).
from enigma import (Accumulator, irange, subsets, grid_adjacency, filter2, repeat, printf) # adjacency matrix for a 4x4 grid adj = grid_adjacency(4, 4) # the pieces (individual cells in the grid) pieces = set(irange(16)) # rotate the grid 90 degrees clockwise rot = [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12] def rotate(ps): return set(rot[p] for p in ps) # mirror the grid vertically mir = [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12] def mirror(ps): return set(mir[p] for p in ps) # slide a shape to the bottom LH corner (Bs, Ls) = ({0, 1, 2, 3}, {0, 4, 8, 12}) def slide(ps): while Bs.isdisjoint(ps): ps = set(p - 4 for p in ps) while Ls.isdisjoint(ps): ps = set(p - 1 for p in ps) return ps # find the canonical form for a shape def canonical(ps): # find the minimal representation r = Accumulator(fn=min) # consider the possible rotations of the shape for ss in repeat(rotate, ps, 3): # also consider reflections for xs in repeat(mirror, ss, 1): # slide to minimal position xs = slide(xs) r.accumulate(tuple(sorted(xs))) # return the minimum value return r.value # are the pieces in <ps> connected? def is_connected(ps, cs=None): if ps and not cs: # move a piece from ps to cs ps = set(ps) cs = {ps.pop()} # move pieces in ps that are connected to cs into cs while ps: # partition ps into those connected to cs and those that aren't (ps, pcs) = filter2((lambda p: cs.isdisjoint(adj[p])), ps) if not pcs: return False cs.update(pcs) return True # collect canonical shapes ss = set() # choose an 8-subset of the pieces for ps in subsets(pieces, size=8, fn=set): # and the remaining pieces rs = pieces.difference(ps) # check both sets are connected if not (is_connected(ps) and is_connected(rs)): continue # collect canonical shapes ss.add(canonical(ps)) # output canonical shapes for (i, ps) in enumerate(sorted(ss), start=1): printf("{i}: {ps}") printf("{n} canonical shapes", n=len(ss))(The internal runtime can easily be reduced to 41ms by noting that each shape must include a corner cell, and a cell adjacent to it, so we only need to look for 6 other cells to go with them).
Solution: There are 19 pupils in the class.
These are the shapes (in grey) that can be generated:
Although these are not necessarily the only ways to cut the shapes out of the grid. (Note that cutting out shape 9 and shape 15 both leave a complementary shape (in orange) that corresponds to shape 18).
LikeLike
Frits 3:58 pm on 9 November 2025 Permalink |
Version 1.
I had a version without itertools.combinations but that was less efficient.
from collections import defaultdict from itertools import combinations N = 4 N2 = N * N H = N2 // 2 def I(i, j, n=N): return i * n + j def rotate(s, n): r = [None] * n * n for i in range(n): for j in range(n): r[I(j, n - i - 1, n)] = s[I(i, j, n)] return tuple(r) def mirror(s, n): r = [None] * n * n for i in range(n): for j in range(n): r[I(j, i, n)] = s[I(i, j, n)] return tuple(r) # is <s> the smallest after rotations/mirrors? def is_canonical(s): z4 = (0, ) * N # go from 4x4 matrix to a 3x3 matrix if all data in SE corner if s[:N] == z4: if tuple(s[i * N] for i in range(N)) == z4: s = tuple(s[i] for i in range(N, N2) if i % N) # dimension of <s> n = int(len(s)**.5) # rotations of the square if (rot1 := rotate(s, n)) < s: return False if (rot2 := rotate(rot1, n)) < s: return False if (rot3 := rotate(rot2, n)) < s: return False # mirrors if (mirror(s, n)) < s: return False if (mirror(rot1, n)) < s: return False if (mirror(rot2, n)) < s: return False if (mirror(rot3, n)) < s: return False return True # adjacent squares d_a = defaultdict(list) for a in range(N): for b in range(N): for i, c in enumerate([a - 1, a, a + 1]): for j, d in enumerate([b - 1, b, b + 1]): if 0 <= c < N and 0 <= d < N and i + j in {1, 3}: d_a[I(a, b)] += [I(c, d)] # are all positive elements in <s> connected with each other def _connected(k, s, adj, curr): global conn_seen if len(conn_seen) == H: yield conn_seen elif k: # add positive adjacent squares conn_seen |= set(x for x in adj[curr] if s[x]) for nxt in adj[curr]: if s[nxt]: yield from _connected(k - 1, s, adj, nxt) def connected(k, s, adj, curr): global conn_seen conn_seen = {curr} # check if all selected squares are connected for conn in _connected(k, s, adj, curr): return True return False sols = [] # check all shapes of <H> squares for cmb in combinations(range(N2), H): s = tuple((1 if i in cmb else 0)for i in range(N2)) if not connected(H - 1, s, d_a, cmb[0]): continue # check if <s> is smallest of all rotations/mirrors if is_canonical(s): oth = tuple(1 - x for x in s) # determine first square not selected f = next(i for i, x in enumerate(oth) if x) if not connected(H - 1, oth, d_a, f): continue sols.append(s) print("answer:", len(sols))LikeLike
Frits 7:18 am on 11 November 2025 Permalink |
When comparing my “connected()” to Brian Gladman’s “is_connected()” I noticed that my version was slow. This one is more efficient. The overall program now also has a decent internal runtime.
# are all positive elements in <s> connected with each other def _connected(s, adj, curr, ss=set()): global conn_seen # add positive adjacent squares conn_seen |= set(x for x in adj[curr] if s[x]) if len(conn_seen) == H: yield conn_seen else: for nxt in adj[curr]: if s[nxt] and nxt not in ss: yield from _connected(s, adj, nxt, ss | {nxt}) def connected(s, adj, curr): global conn_seen conn_seen = {curr} # check if all selected squares are connected for _ in _connected(s, adj, curr, {curr}): return True return FalseLikeLike
Brian Gladman 2:42 pm on 11 November 2025 Permalink |
@Frits
The version on which you comment above was:
# given a set <p> of (x, y) positions for unit squares arranged # on a rectangular grid, return true if the set of squares form # a connected region def is_connected(p): # if two sets of squares in a list of such sets have # any squares that are connected, combine the two sets def combine(s): for s1, s2 in combinations(s, 2): if any(y in adj[x] for x in s1 for y in s2): s[s.index(s1)].update(s2) s.remove(s2) return True return False sets = [set([n]) for n in p] # combine any sets that have connected members while combine(sets): pass # are all squares connected? return len(sets) == 1After thinking about it, I realised it was pretty inefficient so I updated it.
LikeLike
Frits 7:26 am on 10 November 2025 Permalink |
Version 2.
More code (not my priority) but more efficient (my priority).
When cutting from side to side all squares in both shapes have to be connected.
Choosing 4 starting positions for curring is enough to generate all possible shapes.
from collections import defaultdict N = 4 N2 = N * N H = N2 // 2 # direction moving from x to y: Up/Right/Down/Left: 0/1/2/3 dir = lambda x, y: (0 if x[0] > y[0] else 1 if y[1] > x[1] else 2 if x[0] < y[0] else 3) def I(i, j, n=N): return i * n + j def rotate(s, n): r = [None] * n * n for i in range(n): for j in range(n): r[I(j, n - i - 1, n)] = s[I(i, j, n)] return tuple(r) def mirror(s, n): r = [None] * n * n for i in range(n): for j in range(n): r[I(j, i, n)] = s[I(i, j, n)] return tuple(r) # is squaee list <s> the highest after rotations/mirrors? def is_canonical(s): z4 = (0, ) * N # go from N x N matrix to a N-1 x N-1 matrix if all data in NW corner if s[N2 - N:] == z4: if tuple(s[i * N + N - 1] for i in range(N)) == z4: s = tuple(s[i] for i in range(N2 - N) if (i + 1) % N) # dimension of <s> n = int(len(s)**.5) # rotations of the square if (rot1 := rotate(s, n)) > s: return False if (rot2 := rotate(rot1, n)) > s: return False if (rot3 := rotate(rot2, n)) > s: return False # mirrors if (mirror(s, n)) > s: return False if (mirror(rot1, n)) > s: return False if (mirror(rot2, n)) > s: return False if (mirror(rot3, n)) > s: return False return True # check cutting sequence <s> and return list of squares def gen_squares(s): # containers for shape 1 and 2 shape1, shape2 = set(), set() # process the directions of the cuts for x, y in zip(s, s[1:]): match(dir(x, y)): case 0: # U: add square east of it shape1.add(I(y[0], y[1])) shape2.add(I(y[0], y[1] - 1)) case 1: # R: add square south of it shape1.add(I(x[0], y[1] - 1)) shape2.add(I(x[0] - 1, y[1] - 1)) case 2: # D: add square west of it shape1.add(I(x[0], y[1] - 1)) shape2.add(I(x[0], y[1])) case 3: # L: add square north of it shape1.add(I(x[0] - 1, y[1])) shape2.add(I(x[0], y[1])) ns = True # keep coloring adjacent fields of shape 1 with same color while ns: ns = set() for s in shape1: # if adjacent square not in shape2 then add to shape1 ns |= set(a for a in d_a[s] if a not in shape1 and a not in shape2) shape1 |= ns # both shapes must be of the same size if len(shape1) != H: return None return tuple(1 if i in shape1 else 0 for i in range(N2)) # generate a cutting sequence from side to side and return squares def cut(curr, ss=[]): # stop when reaching a side if len(ss) > 1 and not {0, N}.isdisjoint(ss[-1]): # do we have <H> squares per shape? if (sqs := gen_squares(ss)) is not None: yield sqs else: # move the pair of scissors in 4 directions for mv in [(0, -1), (0, 1), (-1, 0), (1, 0)]: new = (curr[0] + mv[0], curr[1] + mv[1]) # if not out of bounds if {-1, N + 1}.isdisjoint(new) and new not in ss: # we must move inside the NxN square after first cut if ss or {0, N}.isdisjoint(new): yield from cut(new, ss + [new]) # adjacent squares d_a = defaultdict(list) for a in range(N): for b in range(N): for i, c in enumerate([a - 1, a, a + 1]): for j, d in enumerate([b - 1, b, b + 1]): if 0 <= c < N and 0 <= d < N and i + j in {1, 3}: d_a[I(a, b)] += [I(c, d)] seen = set() # start cutting near last column for st in [(0, 3), (1, 4), (2, 4), (3, 4)]: # generate squares by performing cuts for s in cut(st, [st]): # check if <s> is highest of all rotations/mirrors if is_canonical(s): seen.add(s) print("answer:", len(seen))LikeLike
Alex.T.Sutherland 2:19 pm on 15 November 2025 Permalink |
I have a pattern that I don’t think is included in the above results.Should the answer be 20?
Am I wrong?
Let me know what you think.
LikeLike
Jim Randell 2:29 pm on 15 November 2025 Permalink |
@Alex: The 0’s are the same as shape 15 in my diagram. And the 1’s are the same as shape 18.
LikeLike
Alex.Sutherland 4:24 pm on 20 November 2025 Permalink |
Thank you for your reply.
My error .I have cleared up the problem.
The following may be of interest.
It is concerned with Teaser 3295 (Always as the Crow flies.)
Quad = abcd; Vertical diagonal = S; Horz diagonal = F;
My answer is based on the equation a^2 + c^2 = b^2 + d^2 simce it is
an orthodiagonal quad .
This is the equation for Pythagorean Trebles (x^2 * y^2 = R^2);
I have a list (from a previous puzzle) of such trebles.
From the list of (x y R) trebles I get a set of possible values
for ‘abcd’.
Choosing at least 2 with equal largest R and with both x and y
<100.
x y R
13 84 85; % Obtained from the list
36 77 85;
40 75 85;
51 68 85;
Choose 2 from the set of 4….(6). eg [a c] = [40 75] ;[b d] = [13 84]
Using each choice iterate S (99->50) to find if F is integer.In
this case
I get 3 answers for ‘abcdSF’.
Choose that whose S is maximum.
The periphery = a+b+c+d.
In my program the answer is a 3 digit number with digits
increasing consectutively.
Diagonal difference = 7 miles.
Run time = 17ms . PC using Pentium processor .Non Python.
As a sideline the locations were found to form a cyclic quad as
well as being
ortho diagonal. ie ac + bd = S*F;
Am I in the right ball park or do I start again?
Regards
A.T.Sutherland.
LikeLike
Jim Randell 2:41 pm on 21 November 2025 Permalink |
@Alex:
I also used the condition a² + c² = b² + d² to find candidate orthodiagonal quadrilaterals (my program is [ here ]).
Although I did not assume that the actual value of the sums must be a perfect square (and so form a Pythagorean triple), as this is not true in general (e.g. 1² + 8² = 4² + 7² = 65, which is not a perfect square), and I wanted to make sure I found all candidate arrangements.
But, if you do assume this, you can still find all 11 possible candidate orthodiagonal quadrilaterals with different 2-digit sides (or 12 if you count a solution that has the same sides as one of the other candidates, but a smaller AS diagonal) that do not have any three of the vertices co-linear. And one of these is the solution to the puzzle.
Four of the 11 candidate quadrilaterals are convex and cyclic as well as orthodiagonal, and for these the intersection of the diagonals cuts each of the diagonals into 2 integer lengths, so they can be composed from 4 Pythagorean triangles.
However, there are candidate solutions where three of the vertices are co-linear, that are not found if you only use Pythagorean triples to construct opposite sides).
I will post some additional notes on my solution on Sunday (on the page for Teaser 3295).
LikeLike