Tagged: by: A K Austin Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 9:57 am on 1 March 2022 Permalink | Reply
    Tags: by: A K Austin   

    Brain-Teaser 907: Snakes & ladders 

    From The Sunday Times, 9th December 1979 [link]

    During my recent trip into the jungle, I came across a clearing, at the centre of which was a stone with the following design:

    On closer inspection, I saw that the small squares were numbered from 1 to 10 (left to right along the bottom row), then from 11 to 20 (right to left on the next row up), 21 to 30 (left to right on the third row up), and so on. The lines joined the following pairs of squares:

    13 & 32
    25 & 48
    35 & 54
    45 & 66
    63 & 88
    79 & 94

    My guide explained that it was a very old snakes and ladders board. However, due to the ravages of time, it was not possible to tell which of the six lines were snakes and which were ladders. Fortunately the guide knew a legend concerning the board, and he told it to me.

    Many years ago, the king of that region had a beautiful daughter, and offered her in marriage to the first man who could get from square 1 to square 100 in just one turn. After many young men had tried and failed, a handsome prince from a neighbouring country had his turn, and threw 12 consecutive sixes. As he stood on square 1 to start, the first six took him to square 7. The remaining sixes took him to square 100.

    Which of the lines are snakes?

    This puzzle is included in the book The Sunday Times Book of Brain-Teasers: Book 2 (1981). The puzzle text above is taken from the book.

    It is also included in the book The Sunday Times Book of Brainteasers (1994).

    [teaser914]

     
    • Jim Randell's avatar

      Jim Randell 10:00 am on 1 March 2022 Permalink | Reply

      We start with 6 linked squares, but we don’t know which way they “teleport”.

      This Python program considers each roll of the dice, and progresses the player. If we reach an “unassigned” linked square we try both possible directions of teleportation. It runs in 49ms.

      Run: [ @replit ]

      from enigma import update, delete, printf

# the linked squares
links = [(13, 32), (25, 48), (35, 54), (45, 66), (63, 88), (79, 94)]

# make a dict of potential "teleports"
ps = dict()
for (x, y) in links:
  ps[x] = y
  ps[y] = x

# play the game
# rs = remaining dice rolls
# ps = potential teleports (src -> tgt)
# ts = actual teleports (src -> tgt)
# n = current position
def solve(rs, ps, n=1, ts=dict()):
  # are we done?
  if not rs:
    if n == 100:
      yield (ts, ps)
  else:
    # add in the next roll
    n += rs[0]
    if n > 100: n = 100
    n = ts.get(n, n)
    # is it a potential teleport?
    t = ps.get(n)
    if t is not None:
      ps_ = delete(ps, [n, t])
      # choose to teleport
      yield from solve(rs[1:], ps_, t, update(ts, [(n, t)]))
      # choose not to teleport
      yield from solve(rs[1:], ps_, n, update(ts, [(t, n)]))
    else:
      # move on
      yield from solve(rs[1:], ps, n, ts)

# solve for a finish in 12 throws of 6
for (ts, ps) in solve([6] * 12, ps):
  for (s, t) in sorted(ts.items()):
    printf("{s} -> {t} {x}", x=("snake" if t < s else "ladder"))
  printf("remaining = {ps}")
  printf()

      Solution: The lines (32 → 13) and (66 → 45) are snakes.

      And the rest are ladders.

      So play proceeds:

      (6) 1 → 7
      (6) 7 → 13
      (6) 13 → 19
      (6) 19 → 25 (ladder) → 48
      (6) 48 → 54
      (6) 54 → 60
      (6) 60 → 66 (snake) → 45
      (6) 45 → 51
      (6) 51 → 57
      (6) 57 → 63 (ladder) → 88
      (6) 88 → 94
      (6) 94 → 100

      Like

  • Unknown's avatar

    Jim Randell 9:43 am on 18 January 2022 Permalink | Reply
    Tags: by: A K Austin   

    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]

     
    • Jim Randell's avatar

      Jim Randell 9:44 am on 18 January 2022 Permalink | Reply

      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:

      Like

  • Unknown's avatar

    Jim Randell 9:33 am on 30 November 2021 Permalink | Reply
    Tags: by: A K Austin   

    Brain-Teaser 888: Master pieces 

    From The Sunday Times, 13th August 1978 [link]

    The artist Pussicatto was exhibiting his new painting. It consisted of a 5-by-5 square of small squares with some of the small squares coloured black and the rest of the small squares coloured white.

    The forger Coppicatto sent six of his assistants to make copies of different parts of the painting. They returned with:

    Unfortunately five of the assistants could not remember which way up their  parts should go, and the other assistant, who gave his part the right way up, had copied the colour of one of the small squares wrongly. However the other five parts did cover the whole of the original painting.

    Reproduce the original Pussicatto painting.

    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.

    [teaser888]

     
    • Jim Randell's avatar

      Jim Randell 9:35 am on 30 November 2021 Permalink | Reply

      Considering the 5 pieces that are correct, but of unknown orientation. The entire painting is covered by these 5. In particular each of the corner sub-squares of the painting must correspond to 4 of the pieces (in some orientation), so we can look for those.

      The following Python 3 program runs in 110ms.

      Run: [ @replit ]

      from enigma import (irange, repeat, subsets, cproduct, join, printf)

# the 6 pieces
pieces = {
  1: (0, 1, 0, 0, 1, 0, 0, 1, 1),
  2: (1, 0, 1, 0, 0, 1, 0, 1, 1),
  3: (0, 1, 0, 1, 0, 0, 1, 1, 1),
  4: (0, 0, 1, 1, 0, 0, 0, 1, 1),
  5: (0, 0, 0, 0, 0, 1, 0, 1, 0),
  6: (1, 0, 0, 1, 1, 1, 0, 0, 1),
}

# rotate a piece
rotate = lambda p: tuple(p[i] for i in (6, 3, 0, 7, 4, 1, 8, 5, 2))

# return all 4 rotations
rots = lambda p: repeat(rotate, p, 3)

# placements for the corners
corners = [(0, 0), (0, 2), (2, 0), (2, 2)]

# place p at (x, y) in the grid
# return a new grid or None
def place(g, p, x, y):
  g_ = dict(g)
  for (j, v) in enumerate(p):
    (dx, dy) = divmod(j, 3)
    k = (x + dx, y + dy)
    v_ = g_.get(k)
    if v_ is None:
      g_[k] = v
    elif v_ != v:
      return None
  return g_

# place pieces <ps> at locations <ls>
def solve(ps, ls, g=dict()):
  # are we done?
  if not ps:
    yield g
  else:
    # place a piece in the next location
    (p, (x, y)) = (ps[0], ls[0])
    # consider possible rotations
    for p in rots(p):
      g_ = place(g, p, x, y)
      if g_ is not None:
        yield from solve(ps[1:], ls[1:], g_)

# locate a piece from ps in grid g
def locate(g, ps):
  for p in ps:
    for (x, y) in cproduct([(0, 1, 2), (0, 1, 2)]):
      if place(g, p, x, y):
        yield (x, y)

# consider possible orderings of pieces
for (p1, p2, p3, p4, p5, p6) in subsets(pieces.keys(), size=6, select="P"):

  # place the first 4 (in some orientation) in the corners
  for g in solve(list(pieces[i] for i in (p1, p2, p3, p4)), corners):

    # check the 5th piece fits in some orientation at some other location
    l5s = set(z for z in locate(g, rots(pieces[p5])) if z not in corners)
    if not l5s: continue

    # and the remaining piece has one square wrong but fits the right way up
    l6s = dict()
    for j in irange(0, 8):
      p = list(pieces[p6])
      p[j] ^= 1
      for z in locate(g, [p]):
        if z not in corners:
          l6s[z] = j
    if not l6s: continue
    if not any(a != b for (a, b) in cproduct([l5s, l6s.keys()])): continue

    # output solution
    printf("corners = [{p1}, {p2}, {p3}, {p4}]; other = {p5} @ {l5s}; wrong = {p6} @ {l6s}\n")
    for x in (0, 1, 2, 3, 4):
      printf("{row}", row=join((g[(x, y)] for y in (0, 1, 2, 3, 4)), sep=" ", enc="[]"))
    printf()

      Solution: The solution is as follows:

      There are 9 possible locations for a 3×3 sub-square of the 5×5 square. The 4 corners, the 4 edges, and the central sub-square.

      The corners consist of pieces 4, 5, 6, 1 (in suitable orientations), and piece 2 corresponds to the left edge sub-square. The central sub-square correspond to piece 3 (the right way up), except the cell marked “x” is the wrong colour.

      Note that each of the pieces 1 – 6 corresponds to a different 3×3 sub-square in the finished painting. If two pieces are allowed to correspond to the same sub-square, then this solution is not unique.

      The program produces 2 solutions corresponding to the same diagram. This is because piece 6 is the same when rotated through 180°.

      Like

    • Frits's avatar

      Frits 1:10 pm on 1 March 2024 Permalink | Reply

      When looking for similar puzzles to the 1994 IMO C1 question I stumbled upon this puzzle.

      @Jim, do you know a more elegant/compact alternative for diff_comb()?

      from enigma import SubstitutedExpression
from itertools import product

# the 6 pieces
pieces = {
  1: (0, 1, 0, 0, 1, 0, 0, 1, 1),
  2: (1, 0, 1, 0, 0, 1, 0, 1, 1),
  3: (0, 1, 0, 1, 0, 0, 1, 1, 1),
  4: (0, 0, 1, 1, 0, 0, 0, 1, 1),
  5: (0, 0, 0, 0, 0, 1, 0, 1, 0),
  6: (1, 0, 0, 1, 1, 1, 0, 0, 1),
}

# rotate a piece clockwise
rotate = lambda p: tuple(p[x] for x in [3 * i + j for j in range(2, -1, -1)
                                                  for i in range(3)])

# return all 4 rotations
def rotations(p):
  yield p
  for _ in range(3):
    p = rotate(p)
    yield p

# dictionary of 3x3 box usage
d_3x3 = dict()
for k, v in pieces.items():
  for r in rotations(v):
    d_3x3[r] = d_3x3.get(r, set()) | {k}

# placements for the corners
corners = {(0, 0), (0, 2), (2, 0), (2, 2)}

# get the four corner 3x3 boxes
get_corners = lambda m: [topLeft_3x3(m, c) for c in corners]

# check if a corner can be made by one of the pieces
check_corner = lambda r: set() if r not in d_3x3 else d_3x3[r]

# check if a combination with different values exists
def diff_comb(s):
  for p in product(*s):
    if len(set(p)) == len(p):
      return True
  return False

# return the 3x3 box values starting at the top left <tl>
def topLeft_3x3(m, tl):
  (tlx, tly) = tl
  return tuple(m[tlx + x][tly + y]
               for (x, y) in product((0, 1, 2), (0, 1, 2)))

# perform checks for the two remaining pieces
def check_oth(m, cs):
  # nine possible 3x3 boxes minus the four corner 3x3 boxes
  five3x3 = {topLeft_3x3(m, tl) for tl in product((0, 1, 2), (0, 1, 2))
             if tl not in corners}

  # check all combinations of 4 corners
  for p in product(*cs):
    if len(set(p)) != len(p): continue
    # remaining two pieces
    rest = set(range(1, 7)).difference(p)

    found_rotated = []
    found_wrong = []
    for pc in rest:
      # check possible rotation (without the corners)
      for rot in [k for k, v in d_3x3.items() if pc in v]:
        if rot in five3x3:
          found_rotated.append((pc, rot))

      # check if a "right way up" piece has exactly 8 correct squares
      for a in five3x3:
        if sum([x == y for x, y in zip(a, pieces[pc])]) == 8:
         found_wrong.append((pc, a))

    # check options for 2 last pieces
    for (rn, r), (wn, w) in product(found_rotated, found_wrong):
      # different pieces
      if rn == wn: continue
      # both pieces must be at a different spot
      w_spots = {i for i, x in enumerate(five3x3) if x == w}
      r_spots = {i for i, x in enumerate(five3x3) if x == r}
      if len(w_spots | r_spots) < 2: continue
      return True

  return False

A_Y = [chr(x) for x in range(ord("A"), ord("Y") + 1)]

# 5x5 matrix of A-E, F-J, K-O, P-T, U-Y
M = [[A_Y[5 * i + j] for j in range(5)] for i in range(5)]

# all variable names in a 5x5 matrix layout (without quotes)
mat = "((" + "), (".join(','.join(r) for r in M) + "))"

answer = f"{mat}"

exprs = []
# check if every corner can be made from a piece
for i, c in enumerate(get_corners(M), start=1):
  s = "(" + ', '.join(c) + ")"
  exprs.append(f"len(c{i} := check_corner({s})) > 0")

# 4 corners use different pieces
exprs.append("diff_comb([c1, c2, c3, c4])")

# check remaining two pieces
exprs.append(f"check_oth({mat}, [c1, c2, c3, c4])")

# the alphametic puzzle
p = SubstitutedExpression(
  exprs,
  answer=answer,
  distinct="",
  env=dict(check_oth=check_oth,
           check_corner=check_corner,
           diff_comb=diff_comb),
  digits=range(0, 2),
  decl="global c1, c2, c3, c4",
  denest=2,
  reorder=0,    # necessary because of assignment statements
  verbose=0,    # use 256 to see the generated code
)

# print answers
print("answer:")
for ans in p.answers():
  for x in ans:
    print(f"{x}")
  print()

      Like

      • Jim Randell's avatar

        Jim Randell 8:19 am on 12 June 2024 Permalink | Reply

        @Frits: You could use the [[ disjoint_cproduct() ]] function from Teaser 3220 to implement diff_comb.

        diff_comb(s) → any(disjoint_cproduct(s))

        Like

        • Frits's avatar

          Frits 10:23 am on 12 June 2024 Permalink | Reply

          Thanks, I tested it. I had forgotten I had asked the question.

          Like

  • Unknown's avatar

    Jim Randell 10:08 am on 31 October 2019 Permalink | Reply
    Tags: by: A K Austin   

    Brain-Teaser 507: [Colourful buses] 

    From The Sunday Times, 28th February 1971 [link]

    The Colourful Bus Company serves the five towns of Antwich, Bearton, Catville, Dogchester and Eagleham. The towns are joined by seven roads as shown on the map.

    Each bus of the company is either Red or Blue or Green or Yellow. Each of the seven roads is covered in one direction only and by one colour of bus only.

    I spent three days recently riding round the district on the buses, each day staring at Antwich and finishing at Eagleham. My journeys were on the following buses in order:

    Day 1: Red, Blue, Yellow, Blue, Green, Yellow, ???
    Day 2: Green, Red, Blue, Green, Red, Blue, Red, ???
    Day 3: Green, Yellow, Blue, Yellow, Blue, Red, ???

    I forgot to note the colour of the last bus each day.

    If a bus runs from Antwich to Bearton, what is the direction and colour of the bus between Catville and Dogchester?

    This puzzle was originally published with no title.

    [teaser507]

     
    • Jim Randell's avatar

      Jim Randell 10:10 am on 31 October 2019 Permalink | Reply

      This Python 3 program runs in 77ms.

      Run: [ @repl.it ]

      from enigma import update, join, printf

# the towns, the buses, the roads
towns = (A, B, C, D, E) = list("ABCDE")
buses = "rbgy" 
roads = {
  A: (B, C, D),
  B: (A, C, E),
  C: (A, B, D),
  D: (A, C, E),
  E: (B, D),
}

# follow a journey
# bs = buses remaining to take
# p = current location
# t = target location
# m = current map
# return (map, towns)
def journey(bs, p, t, m, s=None):
  if s is None: s = [p]
  # are we done?
  if not bs:
    # can we reach the target in one hop?
    if t in roads[p]:
      # is the road already on the map
      if (p, t) in m:
        yield (m, s + [t])
      # can we add it to the map?
      elif (t, p) not in m:
        yield (update(m, [(p, t)], ['?']), s + [t])
  else:
    # choose an onward road
    for x in roads[p]:
      # is it already in the map?
      if (p, x) in m:
        # and is it the right colour?
        if m[(p, x)] == bs[0]:
          # solve for the remaining buses
          yield from journey(bs[1:], x, t, m, s + [x])
        elif m[(p, x)] == '?':
          yield from journey(bs[1:], x, t, update(m, [(p, x)], [bs[0]]), s + [x])
      # can we add it to the map?
      elif (x, p) not in m:
        # solve for the remaining buses
        yield from journey(bs[1:], x, t, update(m, [(p, x)], [bs[0]]), s + [x])

# solve for a collection of journeys between s and t
def solve(s, t, js, m={}, ss=[]):
  # are we done?
  if not js:
    yield (m, ss)
  else:
    # solve for the first journey
    for (m1, s1) in journey(js[0], s, t, m):
      # and then for the remaining journeys
      yield from solve(s, t, js[1:], m1, ss + [s1])

# solve the journeys
for (m, ss) in solve(A, E, ["rbybgy", "grbgrbr", "gybybr"], { (A, B): '?' }):
  # output solution
  printf("map: {m}", m=join((join((k[0], '->', k[1], ' = ', v)) for (k, v) in m.items()), sep="; "))
  for (i, s) in enumerate(ss, start=1):
    printf("day {i}: {s}", s=join(s, sep=" -> "))
  printf()

      Solution: The bus that runs from Catville to Dogchester is red.

      The bus routes are as shown in the following diagram:

      The journeys are:

      Day 1: A → B → E → D → A → C → B → E
      Day 2: A → C → D → A → C → D → A → B → E
      Day 3: A → C → B → E → D → A → B → E

      This is the only solution with a bus running from A to B. However if the bus ran from B to A the solution would be:

      A → C = green
      A → D = red
      B → A = blue
      C → B = red
      C → D = yellow
      D → E = blue
      E → B = yellow

      Like

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel
Design a site like this with WordPress.com
Get started