Programming Enigma Puzzles
From New Scientist #2253, 26th August 2000 [link]
Take a square sheet of paper of side 1 kilometre and divide it into small squares of side 1 centimetre. Colour the small squares so as to give a chessboard pattern of black and white squares.
When we refer to a triangle, we mean a triangle OAB, where O is the bottom left corner of the square of paper, A is on the bottom edge of the paper and B is on the left hand edge of the paper.
Whenever we draw a triangle then we can measure how much of its area is black and how much is white. The score of our triangle is the difference between the black and white areas, in square centimetres. For example if OA = 3 cm and OB = 2 cm then we find the score of the triangle is 1/6 cm².
Question 1. What is the score of the triangle with OA = 87,654 cm and OB = 45,678 cm?
Question 2. What is the score of the triangle with OA = 97,531 cm and OB = 13,579 cm?
Question 3. Is it possible to draw a triangle on the paper with a score greater than 16,666 cm²?
[enigma1097]
 | Frits on Enigma 773: Duodecimal |
 | Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
Enigmatic Code 
A bit of analysis gives us some more general results that can be used to solve the puzzle.
Consider integer values for A and B.
We start with a right angled triangle with vertices (0, 0), (A, 0), (0, B).
By adding a vertex at (A, B) we can make a rectangle, and the diagonal from (A, 0) to (0, B) divides this rectangle into the original triangle and a rotation of the triangle.
If both A and B are even, then the midpoint of the hypotenuse is at an intersection of the grid (see Enigma 1308, Enigma 1110), and so the triangle and its rotation will be identical. So twice the score of the original triangle will be the same as the score of the entire rectangle.
The rectangle has sides that are an even number of squares, so overall it has the same number of black squares and white squares, so its score is 0. Hence:
Solution: Question 1: The score of the first triangle is 0 cm².
If both A and B are odd, then the midpoint of the hypotenuse is in the centre of a grid square, and again, the triangle and its rotation are identical. So the rectangle has twice the score of the original triangle.
The rectangle has sides that are both an odd number of squares, so overall it has one more square of one colour than of the other, so its score is 1. Hence:
Solution: Question 2: The score of the second triangle is 1/2 cm².
Now consider a triangle where A = B and A is odd. The hypotenuse cuts through A squares of the same colour (for the sake of argument let’s say they are black), and the score for the triangle is 1/2 (as both A and B are odd).
The area of the triangle is A²/2 and the score of the triangle is 1/2.
If we now consider the triangle where B = A + 1, then we have a new triangle which contains the old triangle. The overall area of this new triangle is A(A + 1)/2, i.e. its area is A/2 more than the original triangle, and the extra white area is composed of a series of A smaller versions of the new triangle that are completely white.
The dimensions of these triangles is as follows (from largest to smallest):
Summing the areas we get the following extra white area:
The sum of the squares is:
so overall the extra white area is:
and the extra black area is:
So the difference between the black area and the white area in the new triangle is:
Hence:
A 1km × 1km grid of centimetre squares is 100,000 × 100,000 squares. So we can draw a triangle with sides 99,999 cm and 100,000 cm and this has a score of:
Solution: Question 3: Yes, it is possible to draw a triangle with a score that exceeds 16,666 cm².
We note that although A = 99,9999, B = 100,000 is the largest triangle with a score that exceeds 16,666, it is not the only one.
We also have:
And the following result:
gives us another triangle:
My original program to produce a constructive solution was a bit slow, but here’s a version that can solve the problem constructively in 1.74s. In the incarnation below I have included the results from the above analysis to give a program that solves the problem in 46ms.
Run: [ @repl.it ]
#from fractions import Fraction as F from gmpy2 import mpq as F from enigma import divc, gcd, arg, irange, cached, printf # calculate the score (where A >= B) by construction @cached def _score(A, B): (x1, y1, m, r, d) = (0, B, +1, 0, F(B, A)) while x1 < A: (x2, y2) = (x1 + 1, y1 - d) # calculate where the hypotenuse cuts a y line y = divc(y2, 1) x = F((B - y) * A, B) # areas of the triangles above y and below y if x1 < x: above = F((x - x1) * (y1 - y), 2) below = (1 - F((x2 - x) * (y - y2), 2) if y > 0 else 0) else: above = 0 below = F(y1 + y2, 2) - y + 1 # add in the measure for this column if y % 2 == 0: r += m * (above - below + (y > 1)) else: r += m * (below - above) # move to the next column (x1, y1, m) = (x2, y2, -m) return r # calculate the score def score(A, B): if B > A: (A, B) = (B, A) # if A and B are the same parity (pA, pB) = (A % 2, B % 2) if pA == pB: return (F(1, 2) if pA else 0) # if A = B + 1 if A == B + 1: return (F(B + 2, 6) if pB else F(B - 1, 6)) # reducible grids g = gcd(A, B) if g > 1: (A, B) = (A // g, B // g) # compute the value return abs(_score(A, B)) # tests to run args = arg('X123', 0) if 'X' in args: # check the example (A, B) = (3, 2) r = score(A, B) printf("example: score({A}, {B}) = {r}") if '1' in args: # question 1 (A, B) = (87654, 45678) r = score(A, B) printf("question 1: score({A}, {B}) = {r}") if '2' in args: # question 2 (A, B) = (97531, 13579) r = score(A, B) printf("question 2: score({A}, {B}) = {r}") if '3' in args: # question 3 # start with the largest triangle and work downwards M = 100000 for t in irange(2 * M - 1, 2, step=-1): for A in irange(min(M, t - 1), divc(t, 2), step=-1): B = t - A r = score(A, B) delta = r - 16666 if delta > 0: printf("question 3: score({A}, {B}) = {r}, delta = {delta}") exit()I used the [[
gmpy2.mpq()]] class to represent rationals, but if you don’t have that available you can use [[fractions.Fraction()]] by removing line 2 and uncommenting line 1.To run the program without using any analysis, remove lines 35-47 from the [[
score()]] function.Removing the [[
exit()]] statement at line 85 will allow the program to continue and produce the additional triangles given above for question 3 (although this will take longer).from fractions import Fraction as RF def areas(X, Y): # <bk> and <wh> accumulate the areas for black (bottom left) and # white squares; <rv> is 0 or 1 depending on whether the first # square in the current row is black or white bk, wh, rv = 0, 0, 1 # the starting x value on the line below the row being considered xlo = X for y in range(Y): # set rv for this row rv = 1 - rv # callculate the x values on the lines above and below the row xlo, xhi = xlo - RF(X, Y), xlo # find the integer and fractional parts of these values xl, fl = divmod(xlo, 1) xr, fr = divmod(xhi, 1) # add the full squares in the row to the black and white sums if rv: wh += (xl + 1) // 2 bk += xl // 2 else: bk += (xl + 1) // 2 wh += xl // 2 # now consider all partial squares rvv = 1 - rv if xl & 1 else rv # if the line divides a square vertically if xl == xr: if rvv: wh += (fl + fr) / 2 else: bk += (fl + fr) / 2 else: # consder all squares crossed by the line yr = RF(Y * (X - xl), X) - y for xx in range(xl, xr + 1): # calculate the fractional y values on the # lines left and right of the square yl, yr = yr, yr - RF(Y, X) if xx == xl: # the line crosses the top and right sides of the square t = 1 - (1 - fl) * (1 - yr) / 2 elif xx == xr: # the line crosses the left and bottom sides of the square t = fr * yl / 2 else: # the line crosses the left and right sides of the square t = (yl + yr) / 2 # add the result to the appropriate black or white sum if rvv: wh += t else: bk += t # move on to the next square horizontally rvv = 1 - rvv return (wh, bk) if rv else (bk, wh) # Question 1 x, y = 87654, 45678 bk, wh = sorted(areas(x, y)) print(f'Score({x}, {y}) = {wh - bk} cm^2') # Question 2 x, y = 97531, 13579 bk, wh = sorted(areas(x, y)) print(f'Score({x}, {y}) = {wh - bk} cm^2') # Question 3 x, y = 100000, 99999 bk, wh = sorted(areas(x, y)) i, f = divmod(wh - bk, 1) print(f'Score({x}, {y}) = {i} + {f} cm^2')