Brain-Teaser 901: Otherwise encaged
From The Sunday Times, 12th November 1978 [link]
Our local pet shop caters especially for people who wish to keep mice in pairs. The shop sells three designs of half-cages and each customer buys two half-cages and joins them together to make a cage for two mice.
Each of the three designs of half-cages, the Astoria, the Dorchester and the Hilton, is based on the plan above and has 3 walls ga, ab, bj together with walls at some of cd, de, ef, gh, hi, ij, dh and ei.
Each customer buys two half-cages of different designs and joins them together such that point g of each coincides with point j of the other. A mouse is then placed in area abfc of each and allowed to run freely except where it is prevented from going by the walls. There may be some parts of the overall cage which cannot be reached by either mouse.
The half-cages have been designed so that in no case can two mice reach each other and such that the following situation occurs: when an Astoria is joined to a Dorchester, the mouse from the Astoria has a larger area to move in than the other mouse; when a Dorchester is joined to a Hilton, the mouse from the Dorchester has a larger area; and when a Hilton is joined to an Astoria, the mouse from the Hilton has a larger area.
When I was last in the shop I noticed that the Astoria was the only cage with a wall at dh, and also that was the only cage with a wall at ef.
Draw a plan of the Dorchester and of the Hilton.
This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980). The puzzle text above is taken from the book.
All puzzles from the The Sunday Times Book of Brain-Teasers: Book 1 (1980) book are now available on the site. I will shortly move on to puzzles from the The Sunday Times Book of Brain-Teasers: Book 2 (1981).
[teaser901]
Hugh+Casement and 
NigelR and 
galoisest are discussing. 
Frits, 
GeoffR, and 1 other are discussing. 
John Crabtree and 
S2T2 
Jim Randell 9:44 am on 18 January 2022 Permalink |
I used the [[
grid_adjacency()]] function from the enigma.py library to provide the transitions between the areas of a cage, and then removed those that are impeded by the inclusion of relevant walls.The following Python program runs in 179ms.
Run: [ @replit ]
from enigma import (subsets, grid_adjacency, cproduct, join, printf) # walls and the passage they impede walls = dict( cd=(0, 3), de=(1, 4), ef=(2, 5), dh=(3, 4), ei=(4, 5), gh=(3, 6), hi=(4, 7), ij=(5, 8), ) # walls that exist in A, and only in A A_walls = {'ef', 'dh'} # walls that may exist in any of A, D, H ADH_walls = set(walls.keys()).difference(A_walls) # possible walls for A (must include 'ef', 'dh') As = list(A_walls.union(s) for s in subsets(ADH_walls)) # possible walls for DH (must not include 'ef', 'dh') DHs = list(subsets(ADH_walls, fn=set)) # adjacency matrix with no walls adj = grid_adjacency(3, 4) # construct a cage from two half-cages def construct(X, Y): # copy the default matrix m = list(set(x) for x in adj) # remove any adjacencies from the top walls for k in X: (x, y) = walls[k] m[x].discard(y) m[y].discard(x) # remove any adjacencies from the bottom walls for k in Y: (x, y) = (11 - j for j in walls[k]) m[x].discard(y) m[y].discard(x) # return the new adjacency matrix return m # find the area of the maze reachable from ns def area(m, ns): xs = set() while ns: n = ns.pop() xs.add(n) ns.update(m[n].difference(xs)) return xs # check an X+Y construction def check(X, Y): m = construct(X, Y) # area reachable from X should be greater than from Y return len(area(m, {0})) > len(area(m, {11})) # choose a set of walls for A and D for (A, D) in cproduct([As, DHs]): # check an A+D construction if not check(A, D): continue # choose a (dfferent) set of walls for H for H in DHs: if H == D: continue # check a D+H and H+A constructions if not (check(D, H) and check(H, A)): continue # output solution fmt = lambda s: join(sorted(s), sep=" ", enc="()") printf("D={D} H={H}; A={A}", D=fmt(D), H=fmt(H), A=fmt(A))Solution: The plans of the Dorchester and Hilton are shown below:
The Astoria can be either of the following 2 diagrams:
(The “walled-orf” area in the second is always inaccessible when A is combined with D or H, so the inclusion of the ij wall doesn’t make any difference).
When combined they produce the following cages:
LikeLike