Teaser 3044: Building blocks
From The Sunday Times, 24th January 2021 [link] [link]
The kids had used all the blocks each of them owned (fewer than 100 each) to build triangular peaks — one block on the top row, two on the next row, and so on.
“My red one’s nicer!”
“My blue one’s taller!”
“Why don’t you both work together to make one bigger still?” I said.
I could see they could use all these blocks to make another triangle.
This kept them quiet until I heard, “I bet Dad could buy some yellow blocks to build a triangle bigger than either of ours was, or a red and yellow triangle, or a yellow and blue triangle, with no blocks ever left over.”
This kept me quiet, until I worked out that I could.
How many red, blue and yellow blocks would there be?
[teaser3044]
Frits and 
S2T2 
Jim Randell 5:18 pm on 22 January 2021 Permalink |
The following Python program runs in 43ms.
Run: [ @repl.it ]
from enigma import tri, irange, inf, first, subsets, is_triangular, printf # generate triangular numbers from tri(a) to tri(b) tris = lambda a=1, b=inf: (tri(i) for i in irange(a, b)) def solve(): # collect triangular numbers less than 100 ts = first(tris(), (lambda x: x < 100)) # choose (R, B) pairs that sum to another triangular number RBs = list(s for s in subsets(ts, size=2) if is_triangular(sum(s))) # consider values for Y for Y in tris(is_triangular(min(B for (R, B) in RBs)) + 1): # look for R, B pairs that work with Y for (R, B) in RBs: if B < Y and is_triangular(R + Y) and is_triangular(B + Y): yield (R, B, Y) # look for the first solution for (R, B, Y) in solve(): printf("R={R} B={B} Y={Y}") breakSolution: There were 45 red blocks; 91 blue blocks; 990 yellow blocks.
We have:
It makes me wish Python allowed something like a [[
while ...]] clause in list comprehensions, so they could be terminated early:This exact syntax was actually proposed [ PEP 3142 ], but not implemented.
I’ve folded the functionality into the [[
first()]] function in the enigma.py library, so it can take a function and collection of items will stop when the function returns a false value for an item.LikeLike
Frits 11:11 pm on 22 January 2021 Permalink |
@Jim, I can imagine a similar puzzle in 3D. Didn’t we have such a puzzle before?
LikeLike
Jim Randell 10:58 am on 23 January 2021 Permalink |
Here’s an exhaustive version, based on the observation that if Y = tri(y) then R ≥ y + 1, otherwise it will not be possible to complete an additional row of the Y triangle using R blocks.
It still runs in 46ms.
Run: [ @repl.it ]
from enigma import tri, irange, inf, first, subsets, is_triangular, printf # generate triangular numbers from tri(a) to tri(b) tris = lambda a=1, b=inf: (tri(i) for i in irange(a, b)) # collect triangular numbers less than 100 ts = first(tris(), (lambda x: x < 100)) # choose (R, B) pairs that sum to another triangular number for (R, B) in subsets(ts, size=2): if not is_triangular(R + B): continue # consider values for Y for Y in tris(is_triangular(B) + 1, R - 1): if is_triangular(R + Y) and is_triangular(B + Y): printf("R={R} B={B} Y={Y}")This code can also be used to explore larger solutions by increasing the limit at line 7.
There is 1 further solution below 1275:
LikeLike
Frits 10:55 pm on 22 January 2021 Permalink |
Nothing has been implemented regarding upper limits of RE and BL, the program runs fast enough (between 31 ms and 46 ms).
from enigma import SubstitutedExpression # the alphametic puzzle p = SubstitutedExpression( [ # number of reds = RE * (RE + 1)/2 # number of blues = BL * (BL + 1)/2 # number of yellows = YW * (YW + 1)/2 "RE > 0", "BL > 0", # My blue one's taller "BL > RE", # fewer than 100 each "BL * (BL + 1) // 2 < 100", # they could use all these blocks to make another triangle "RE * (RE + 1) // 2 + BL * (BL + 1) // 2 == JK * (JK + 1) // 2", # Dad could buy some yellow blocks to build a triangle bigger # than either of ours was, or a red and yellow triangle, # or a yellow and blue triangle, with no blocks ever left over "YW > BL", "YW * (YW + 1) // 2 + RE * (RE + 1) // 2 == CD * (CD + 1) // 2", "YW * (YW + 1) // 2 + BL * (BL + 1) // 2 == FG * (FG + 1) // 2", ], answer="RE * (RE + 1) // 2, BL * (BL + 1) // 2, YW * (YW + 1) // 2", distinct="", reorder=0, d2i={}, verbose=0) for (_, ans) in p.solve(): print(f"{ans}")LikeLike
Frits 8:52 am on 23 January 2021 Permalink |
Similar.
from enigma import SubstitutedExpression, is_square # the alphametic puzzle p = SubstitutedExpression( [ # If n is the mth triangular number, then n = m*(m+1)/2 # and m = (sqrt(8n+1) - 1) / 2 # number of reds = RE * (RE + 1)/2 # number of blues = BL * (BL + 1)/2 # number of yellows = YW * (YW + 1)/2 "RE > 0", "BL > 0", # My blue one's taller "BL > RE", # fewer than 100 each "BL * (BL + 1) // 2 < 100", # they could use all these blocks to make another triangle "is_square(4 * (BL * (BL + 1) + RE * (RE + 1)) + 1)", # Dad could buy some yellow blocks to build a triangle bigger # than either of ours was, or a red and yellow triangle, # or a yellow and blue triangle, with no blocks ever left over "YW > BL", "is_square(4 * (YW * (YW + 1) + RE * (RE + 1)) + 1)", "is_square(4 * (YW * (YW + 1) + BL * (BL + 1)) + 1)", ], answer="RE * (RE + 1) // 2, BL * (BL + 1) // 2, YW * (YW + 1) // 2", distinct="", reorder=0, d2i={}, verbose=0) for (_, ans) in p.solve(): print(f"{ans}")LikeLike
Frits 10:53 am on 23 January 2021 Permalink |
One (ugly) statement, no imports.
The “is_square” method “n**.5 % 1 == 0” will fail for large numbers of n (like 152415789666209426002111556165263283035677490).
print([(r * (r + 1) // 2, b * (b + 1) // 2, y * (y + 1) // 2) # Triangular root <m> of n = m*(m+1)/2 is (sqrt(8n+1) - 1) / 2 # combinations of red and blue triangular roots and number of blocks < 100 for (r, b) in [(c1, c2) for c1 in range(1, [m for m in range(1, 50) if m * (m + 1)> 198][0] - 1) for c2 in range(c1 + 1, [m for m in range(1, 50) if m * (m + 1)> 198][0]) # they could use all these blocks to make another triangle if (4 * (c1 * (c1 + 1) + c2 * (c2 + 1)) + 1)**.5 % 1 == 0] for y in range(b + 1, 99) # red and yellow triangle, with no blocks ever left over # blue and yellow triangle, with no blocks ever left over if (4 * (r * (r + 1) + y * (y + 1)) + 1)**.5 % 1 == 0 and (4 * (b * (b + 1) + y * (y + 1)) + 1)**.5 % 1 == 0])LikeLike
Frits 12:44 pm on 23 January 2021 Permalink |
can be achieved more efficiently (probably) by:
LikeLike