Design a site like this with WordPress.com
Get started

Updates from January, 2022 Toggle Comment Threads | Keyboard Shortcuts

  • Jim Randell 9:43 am on 18 January 2022 Permalink | Reply
    Tags:   

    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 was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). 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, also edited by Victor Bryant and Ronald Postill).

    [teaser901]

     
    • 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

  • Jim Randell 9:45 am on 11 January 2022 Permalink | Reply
    Tags:   

    Brain-Teaser 903: Ding-dong 

    From The Sunday Times, 26th November 1978 [link]

    Today a great celebration will take place on Bells Island, for it is the Feast of Coincidus. On this island there is monastery and a nunnery. At regular intervals (a whole number of minutes) the monastery bell dongs once. The nunnery bell rings at regular intervals too (different from the intervals of the monastery’s bell, but also a whole number of minutes). So the island also regularly reverberates with a ding from the nunnery’s bell. The Feast of Coincidus takes place whenever the monastery’s dong and the nunnery’s ding occur at the same moment, and that is exactly what is due to happen at noon today.

    Between consecutive Feasts the dongs from the monastery and the dings from the nunnery occur alternately and, although the two noises only coincide on Feast days, they do occur a minute apart at some other times.

    When the bells coincided last time (at noon, a prime number of days ago) this whole island indulged in its usual orgy of eating and drinking.

    How many days ago was that?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    After this puzzle was published The Sunday Times was hit by industrial action, and the next issue was not published until 18th November 1979.

    [teaser903]

     
    • Jim Randell 9:47 am on 11 January 2022 Permalink | Reply

      If the shorter interval is i minutes, then, working forwards from the previous feast (= 0) the bell rings at (minutes):

      i, 2i, 3i, 4i, … ni

      And if the shorter interval is (i + x) minutes, then that bell rings at:

      (i + x), 2(i + x), 3(i + x), … (n − 1)(i + x)

      And the last 2 times coincide:

      ni = (n − 1)(i + x)
      i = (n − 1)x
      x = i / (n − 1)

      And there are times where the bells ring only 1 minute apart. As the bells are drifting apart at the beginning and together at the end, and their interval is a whole number of minutes, they must ring 1 minute apart immediately after and immediately before they coincide. i.e. x = 1 and n = i + 1

      So, the number of intervals for the shorter bell is 1 more than than the length of the interval in minutes.

      And in prime p days there are 1440p minutes, so we have:

      1440p = ni = (i + 1)i
      p = i(i + 1) / 1440

      So we need to find two consecutive integers, whose product is the product of a prime and 1440.

      Run: [ @replit ]

      from enigma import irange, inf, div, is_prime, printf
      
      for i in irange(1, inf):
        p = div(i * (i + 1), 1440)
        if p is not None and is_prime(p):
          printf("i={i} p={p}")
          break
      

      Solution: The last feast was 1439 days ago.

      So, almost 4 years ago.

      We have: i = p = 1439.

      Like

    • Hugh+Casement 1:15 pm on 11 January 2022 Permalink | Reply

      The periods are 24 hours for one and 23 hours 59 minutes for the other.

      Like

  • Jim Randell 9:09 am on 6 January 2022 Permalink | Reply
    Tags: by: David Preston   

    Brain-Teaser 896: Handshaking numbers 

    From The Sunday Times, 8th October 1978 [link]

    My wife and I attended a formal dinner at which there were just eight other people, namely the four couples Mr and Mrs Ailsa, Mr and Mrs Blackler, Mr and Mrs Caroline and Mr and Mrs Duncan. Introductions were made, and a certain number of handshakes took place (but, of course, no one shook hands with him/herself, nor with his/her spouse, nor more than once with anyone else). At the end of the evening I asked each other person how many hands they had shaken, and I was surprised to find that all the answers given were different. Also, the total of the number of handshakes made by the other four men was the same as the total of handshakes made by all five women.

    The only woman I shook hands with was my old friend Mrs Ailsa. We had a long chat and then I took her to one side and, being a jealous fellow, I asked her whose hands my wife had shaken. She was unable to tell me, but luckily I was able to work it out later from the above information.

    Whose hands did my wife shake? How many hands did Mrs Ailsa shake?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser896]

     
    • Jim Randell 9:11 am on 6 January 2022 Permalink | Reply

      This one is quite fun to solve manually.

      The largest possible number of handshaking partners is 8 (if you shake hands with everyone except yourself and your spouse).

      So the setter must have got the responses 0 – 8, when he asked the other 9 people their numbers of handshakes.

      Programatically I used a MiniZinc model to construct the handshaking matrix, and then formatted the output using my minizinc.py wrapper.

      The following Python 3 program runs in 207ms.

      from enigma import join, printf
      from minizinc import MiniZinc
      
      # we label the people in pars (1, 2) (3, 4) ... (9, 10)
      people = ["Mr S", "Mrs S", "Mr A", "Mrs A", "Mr B", "Mrs B", "Mr C", "Mrs C", "Mr D", "Mrs D"]
      # map people to integers, and integers to people
      p2i = dict((x, i) for (i, x) in enumerate(people, start=1))
      i2p = dict((v, k) for (k, v) in p2i.items())
      
      ps2is = lambda ps: join((p2i[p] for p in ps), sep=", ", enc="{}")
      MrS = p2i["Mr S"]
      MrABCD = ps2is("Mr " + x for x in "ABCD")
      MrsSABCD = ps2is("Mrs " + x for x in "SABCD")
      
      # construct the MiniZinc model
      model = f"""
      include "globals.mzn";
      
      set of int: People = 1..10;
      
      % boolean handshake matrix
      array [People, People] of var 0..1: x;
      
      % handshakes are reciprocal
      constraint forall (i, j in People) (x[i, j] = x[j, i]);
      
      % no-one shakes hands with themselves
      constraint forall (i in People) (x[i, i] = 0);
      
      % no-one shakes hands with their spouse
      constraint forall (i in People where i mod 2 = 1) (x[i, i + 1] = 0);
      constraint forall (i in People where i mod 2 = 0) (x[i, i - 1] = 0);
      
      % total number of handshakes
      array [People] of var 0..8: t;
      constraint forall (i in People) (t[i] = sum (j in People) (x[i, j]));
      
      % apart from Mr S, everyone had a different total
      constraint all_different([t[i] | i in People where i != {MrS}]);
      
      % total for Mr A, B, C, D = total for Mrs S, A, B, C, D
      constraint sum ([t[i] | i in {MrABCD}]) = sum ([t[i] | i in {MrsSABCD}]);
      
      % Mr S shook hands with Mrs A, but no other wives
      constraint x[{MrS}, {p2i["Mrs A"]}] = 1;
      constraint x[{MrS}, {p2i["Mrs B"]}] = 0;
      constraint x[{MrS}, {p2i["Mrs C"]}] = 0;
      constraint x[{MrS}, {p2i["Mrs D"]}] = 0;
      
      % eliminate duplicates by placing an order on Mr B, C, D
      constraint increasing([t[{p2i["Mr B"]}], t[{p2i["Mr C"]}], t[{p2i["Mr D"]}]]);
      
      solve satisfy;
      """
      
      # solve the model
      for s in MiniZinc(model).solve():
        # output the handshakes
        x = s['x']
        for k in sorted(x.keys()):
          v = list(k_ for k_ in x[k].keys() if x[k][k_] == 1)
          printf("{k} [{n}] = ({v})", k=i2p[k], v=join((i2p[i] for i in v), sep=", "), n=len(v))
        printf()
      

      Solution: The setters wife (Mrs S) shook hands with: Mrs A, Mr B, Mr C, Mr D; Mrs A shook hands with 8 others.


      Manually:

      We have “Mr S” and the other 8 who participated in 0 – 8 handshakes, one value each.

      “0” can’t shake hands with anybody, and “8” can’t shake hands with “0”, so must shake hands with everyone else (and so must be married to “0”).

      Filling in the handshakes we know:

      Mr S: 8, …
      0: none (complete, married to 8)
      1: 8 (complete)
      2: 8, …
      3: 8, …
      4: 8, …
      5: 8, …
      6: 8, …
      7: 8, …
      8: Mr S, 1, 2, 3, 4, 5, 6, 7 (complete, married to 0)

      Now “7”, can’t shake hands with “0”, “1” or “8”, so must shake hands with everyone else (and must be married to “1”). And this completes “7” and “2”. Similarly we complete “6” and “3” (and “6” must be married to “2”), then “5” and “4” (“5” is married to “3”):

      Mr S: 5, 6, 7, 8
      0: none (complete, married to 8)
      1: 8 (complete, married to 7)
      2: 7, 8 (complete, married to 6)
      3: 6, 7, 8 (complete, married to 5)
      4: 5, 6, 7, 8 (complete)
      5: Mr S, 4, 6, 7, 8 (complete, married to 3)
      6: Mr S, 3, 4, 5, 7, 8 (complete, married to 2)
      7: Mr S, 2, 3, 4, 5, 6, 8 (complete, married to 1)
      8: Mr S, 1, 2, 3, 4, 5, 6, 7 (complete, married to 0)

      So “0” – “8” are complete, and hence so is “Mr S”, and he must be married to “4” (“Mrs S”).

      And Mr S shook hands with just one woman (Mrs A), so three of 5, 6, 7, 8 must be men (and the other one is Mrs A).

      We know the sum of the handshakes of the 5 wives must sum to half of sum(0, 1, 2, …, 8) = 36, i.e. 18. And Mrs S is “4”.

      So we need the remaining 4 wives (one each from (0, 8) (1, 7) (2, 6) (3, 5)) to sum to 14.

      The only possibilities are 0 + 7 + 2 + 5 = 14, and 8 + 1 + 2 + 3 = 14.

      The first is ruled out as 5 and 7 can’t both be wives (Mr S only shook hands with one woman).

      So the wives are 1, 2, 3, 8 (and 4). And the corresponding husbands are 7, 6, 5, 0 (and Mr S).

      Hence: “8” = “Mrs A”; “0” = “Mr A”.

      And Mr B, C, D not distinguishable in the puzzle so we can order them by the number of handshakes (the other arrangements will give further solutions), so we can now complete the matrix:

      (4) Mr S: Mr B, Mr C, Mr D, Mrs A
      0 = Mr A: none
      1 = Mrs D: Mrs A
      2 = Mrs C: Mr D, Mrs A
      3 = Mrs B: Mr C, Mr D, Mrs A
      4 = Mrs S: Mr B, Mr C, Mr D, Mrs A
      5 = Mr B: Mr S, Mrs S, Mr C, Mr D, Mrs A
      6 = Mr C: Mr S, Mrs B, Mrs S, Mr B, Mr D, Mrs A
      7 = Mr D: Mr S, Mrs C, Mrs B, Mrs S, Mr B, Mr C, Mrs A
      8= Mrs A: Mr S, Mrs D, Mrs C, Mrs B, Mrs S, Mr B, Mr C, Mr D

      Like

    • NigelR 7:13 pm on 12 January 2022 Permalink | Reply

      I found it very much quicker to solve this puzzle manually than unentangle the code but the program below makes no assumptions about the underlying logic other than the sum of digits 0-8 being 36.
      I am thinking of using the nickname Thor since a big hammer seems to be my weapon of choice!!

      
      from itertools import combinations as comb,permutations as perm
      m=['am','bm','cm','dm'] #list of males not including setter
      f=['af','bf','cf','df','ef'] #list of females
      pairs=[['am','af'],['bm','bf'],['cm','cf'],['dm','df'],['em','ef']] #pairs of spouses
      
      #find combinations of digits where m and f both sum to 18
      def gen():
          for x in comb([0,1,2,3,4,5,6,7,8],4):
              if sum(x)!=18:continue
              y = [y for y in range(0,9) if y not in x]    
              for h in perm(x):
                  for w in perm(y):
                      yield  h+w
      #check allocations of shakes match 0-8 and setter shakes hands with Mrs A: :
      def test1():
          for i in mat:
              if len(mat[i])!=i:return False
          if 'em' not in mat[alloc['af']]: return False   
      #...and Mrs A is only female to shake setter's hand
          count=0
          for i in f:
              if 'em' in mat[alloc[i]]:count+=1
          if count >1:return False
          return True
      
      for seq in gen():    
          mat= {i:[] for i in range(0,9)}  # clear mat entries from previous iteration
          alloc= {i:j for (i,j) in zip(m+f,seq)} # set alloc to access attendees with current shake numbers
          point= {j:i for [i,j] in alloc.items()} #pointer - transpose of alloc to cross reference shake numbers and attendees
          
          for i in range(0,9):
             for j in range(i+1,9):
                  mat[j].append(point[8-i]) #populate mat  
      
          for i in mat:
              pair=[j for j in pairs if point[i] in j]
              mat[i] = [y for y in mat[i] if y not in [item for items in pair for item in items]]
              if len(mat[i])<i:mat[i].append('em')
          if not test1():continue
      #mat now contains valid set of handshakes for each attendee           
          for x in mat:
              print(point[x], 'shakes hand of',mat[x])
          break
      

      Like

  • Jim Randell 10:03 am on 28 December 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 894: Prime consideration 

    From The Sunday Times, 24th September 1978 [link]

    At our local the other night I made the acquaintance of a chap called Michael and his wife Noelle. We talked a good bit about our respective families, our activities and our hobbies. When I happened to mention my interest in mathematical puzzles to Michael he said that he knew one at first hand which might give me some amusement. He proceeded to tell me that although he himself, his parents (who were born in different years), Noelle and their children (featuring no twins, triplets, etc.) had all been born in the nineteen-hundreds and none of them in a leap year, the numerical relationship between their years of birth was nevertheless in two respects a bit unusual.

    “In the first place”, he said, “just one of us has our year of birth precisely equal to the mean of all the others’ years of birth. But more remarkably the difference between my father’s year of birth and that of any one of the rest of us is a prime, and the same is true of that of my mother. And she, like Noelle here, had no child after she had passed her twenties”.

    And then with a grin he concluded, “So now you’ll know about the whole family and even, if you want, be able to figure out just how old Noelle is without having to be rude and ask her!”

    In which year was Noelle born? And how many children does she have?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser894]

     
    • Jim Randell 10:03 am on 28 December 2021 Permalink | Reply

      There are no multiple births for Noelle, but she could manage to have 2 children in a calendar year (by having one early in the year, and one late in the year).

      Also, if she was born at the end of the year (as is suggested by her name), it is possible to squeeze a child (or two) in during the calendar year containing her 30th birthday.

      In order to get a unique solution, we need to assume Michael and Noelle have more than 1 child (justified by his use of “children”).

      This Python program runs in 52ms.

      Run: [ @replit ]

      from collections import defaultdict
      from enigma import irange, Primes, subsets, div, printf
      
      # check for leap years
      is_leap = lambda y: y % 4 == 0 and (y % 100 != 0 or y % 400 == 0)
      
      # primes less than 100
      primes = Primes(100)
      
      # find possible 19xx years
      years = list(y for y in irange(1900, 1978) if not is_leap(y))
      
      # look for viable mother -> children maps
      kids = defaultdict(list)
      for (m, c) in subsets(years, size=2):
        k = c - m
        if 16 < k < 31:
          kids[m].append(c)
      
      # choose a year for M's mother
      for (MM, Ms) in kids.items():
        # all other years must have a prime difference to MM
        ys1 = set(y for y in years if abs(y - MM) in primes)
      
        # find a viable birth year for M
        for M in Ms:
          if not(M in ys1): continue
      
          # and for his father
          for MF in ys1:
            k = M - MF
            if not(k > 15 and k in primes): continue
            # all other years must also have a prime difference to MF
            ys2 = set(y for y in ys1 if abs(y - MF) in primes).difference([M, MF])
      
            # now find a year for N
            for N in ys2:
              ks = sorted(ys2.intersection(kids.get(N, [])))
              if not ks: continue
      
              # no multiple births, so (0, 1, 2) children in each year
              for ns in subsets((0, 1, 2), size=len(ks), select="M"):
                k = sum(ns)
                if k < 2: continue
                # ages
                ages = [MF, MM, M, N]
                for (n, v) in zip(ns, ks):
                  if n: ages.extend([v] * n)
                t = sum(ages)
                # exactly one of the birth years is the mean year
                m = div(t, len(ages))
                if m is None or ages.count(m) != 1: continue
      
                # output solution
                printf("MF={MF} MM={MM} -> M={M}; N={N} -> {k} kids; {ages} -> {m}")
      

      Solution: Noelle was born in 1943. She has 4 children.

      Michael’s father was born in 1900 (which was not a leap year), and his mother in 1902.

      Michael was born in 1931 (prime differences of 31 and 29 to his father and mother), and his mother was 28 or 29 when he was born.

      Noelle was born in 1943 (prime differences of 43 and 41 to Michael’s father and mother), towards the end of the year.

      Her four children were born in 1961 (one towards the beginning of the year, when Noelle was 17, and one towards the end of the year, when she was 17 or 18), and in 1973 (one towards the beginning of the year, when Noelle was 29, and one towards the end of the year, when she was still 29).

      Like

  • Jim Randell 7:30 am on 23 December 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 891: Ups and downs 

    From The Sunday Times, 3rd September 1978 [link]

    An electrician living in a block of flats has played a joke on the tenants by rewiring the lift. The buttons numbered 0 to 9 in the lift should correspond to the ground floor, first floor, etc., but he has rewired them so that although (for his own convenience) the buttons for the ground floor and his own floor work correctly, no other button takes you to its correct floor. Indeed when you get in the lift on the ground floor and go up, three of the buttons take you twice as high as they should, and two buttons take you only half as high as they should.

    The milkman is unaware of the rewiring and so early yesterday morning, rather bleary-eyed, he followed his usual ritual which consists of taking nine pints of milk into the lift, pushing button 9, leaving one pint of milk when the lift stops, pushing button 8, leaving one pint of milk when the lift stops, and so on in decreasing order until, having pushed button and having left his last pint, he usually returns to his van.

    However, yesterday when he tried to follow this procedure all seemed to go well until, having pushed button 1 , when the lift stopped he found a pint of milk already there. So he took the remaining pint back to his van, with the result that just one of the tenants (who lived on one of the floors below the electrician’s) did not get the pint of milk she’d expected.

    The surprising thing was that during the milkman’s ups and downs yesterday he at no time travelled right past the floor which he thought at that time he was heading towards.

    List the floors which received milk, in the order in which the milkman visited them.

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser891]

     
    • Jim Randell 7:32 am on 23 December 2021 Permalink | Reply

      The electrician makes a journey by selecting buttons 9, 8, 7, …, 3, 2, 1, and in the process visits one of the floors twice and one of the floors no times. And the floor that is not visited is a lower number than the electrician’s floor (which is the only button that gives the correct floor).

      I assumed there are exactly 3 buttons that go to floor exactly twice the number on the button, and exactly 2 that go to a floor exactly half the number on the button.

      This Python 3 program chooses the buttons that go to floors twice and half their labelled values, and then fills out the rest of the mapping as it goes along. It runs in 53ms.

      Run: [ @replit ]

      from enigma import irange, update, product, subsets, diff, singleton, trim, map2str, printf
      
      # consider a journey made with buttons <bs>, visiting floors <fs> using map <m> (button -> floor)
      def journey(bs, fs, m):
        # are we done?
        if not bs:
          yield (fs, m)
        else:
          (b, f_) = (bs[0], fs[-1])
          # is the button assigned?
          f = m.get(b, None)
          if f is None:
            (ss, upd) = (irange(0, 9), 1)
          else:
            (ss, upd) = ([f], 0)
          # choose a target floor
          for f in ss:
            # if unassigned: cannot be the right floor, or twice or half
            if upd and (f == b or f == 2 * b or b == 2 * f): continue
            # cannot be a previously visited floor, except for the final floor
            if (f in fs) != (len(bs) == 1): continue
            # journey cannot pass the correct floor
            if not(f_ < b < f or f_ > b > f):
              m_ = (update(m, [(b, f)]) if upd else m)
              yield from journey(bs[1:], fs + [f], m_)
      
      # exactly 3 buttons go to twice the number, exactly 2 buttons go to half the number
      for (ds, hs) in product(subsets([1, 2, 3, 4], size=3), subsets([2, 4, 6, 8], size=2)):
        # remaining floors
        rs = diff(irange(1, 9), ds + hs)
        if len(rs) != 4: continue
      
        # choose the floor for the electrician
        for e in rs:
          if e == 1: continue
      
          # initial map
          m0 = { 0: 0, e: e }
          m0.update((k, 2 * k) for k in ds) # doubles
          m0.update((k, k // 2) for k in hs) # halfs
      
          # consider possible journeys for the milkman
          for (fs, m) in journey([9, 8, 7, 6, 5, 4, 3, 2, 1], [0], m0):
      
            # the unvisited floor is lower than e
            u = singleton(x for x in irange(1, 9) if x not in fs)
            if u is None or not(u < e): continue
      
            # output solution
            printf("{fs} {m}", fs=trim(fs, head=1, tail=1), m=map2str(m, arr='->'))
      

      Solution: The milkman visited floors: 7, 4, 2, 3, 5, 8, 6, 9.

      He then returns to floor 2, and finds he has already visited.

      The rewired map of button → floor is:

      0 → 0
      1 → 2 (twice)
      2 → 9
      3 → 6 (twice)
      4 → 8 (twice)
      5 → 5 (electrician’s floor)
      6 → 3 (half)
      7 → 2
      8 → 4 (half)
      9 → 7

      Like

  • Jim Randell 4:35 pm on 14 December 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 890: Round pond boat race 

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

    In our park is a circular pond exactly 50 metres in diameter, which affords delight to small boys who go down with ships.

    Two such youngsters, Arthur and Boris, took their model motor-cruisers there the other morning, and decided on a race. Each was to start his boat from the extreme North of the pond at the same moment, after which each was to run round the pond to await his boat’s arrival. The moment it touched shore its owner was to grab it by the bows and run with it directly to the South gate of the park, situated exactly 27 metres due South of the Southern edge of the pond. Both boats travelled at the same speed (1 metre in 3 seconds) but both owners, burdened with their respective craft, could manage only 3 metres in 4 seconds over the rough grass.

    When the race started, Arthur’s boat headed due South, but that of Boris headed somewhat East of South and eventually touched shore after travelling 40 metres in a straight line.

    Who arrived first at the gate, and by what time margin (to the nearest second)?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser890]

     
    • Jim Randell 4:36 pm on 14 December 2021 Permalink | Reply

      The boats start at S and travel to A and B, and are then carried to the gate at G. O is the centre of the pond, GX is tangent to the pond.

      For A, the distance travelled by the boat is SA = 50m, and the distance on foot is AG = 27m.

      So the total time taken is: 50 × 3 + 27 × 4/3 = 186 seconds.

      For B, we see that the triangle ABS is inscribed in a semicircle, so has a right angle at B, and the sides SA = 50m, SB = 40m (so AB = 30m), so if θ is the angle ASB we have:

      cos(θ) = 40/50 = 4/5

      We can then calculate the straight line distance BG using the cosine rule on triangle GSB:

      (BG)² = (GS)² + (BS)² − 2(GS)(BS)cos(θ)
      (BG)² = 77² + 40² − 2×77×40×4/5
      (BG)² = 2601
      BG = 51

      For B, the distance travelled by the boat is SB = 40m, and the straight line distance on foot is BG = 51m.

      So the total time taken is: 40 × 3 + 51 × 4/3 = 188 seconds.

      So it looks like A beats B by 2 seconds.

      However looking at the diagram, we note that the line BG actually passes through the pond, and so B would have to run around the circumference of the pool (along the arc BX), until he can make a straight line to G (along XG, a tangent to the circle).

      The straight line distance along the tangent, XG, is:

      (XG)² + 25² = (25 + 27)²
      (XG)² = 2079
      XG = 3√(231)

      We can calculate the angle SOB using the cosine rule:

      (SB)² = (OS)² + (OB)² − 2(OS)(OB)cos(α)
      cos(α) = (2×25² − 40²) / 2×25²
      cos(α) = −7/25

      The amount of arc travelled, φ (the angle BOX), is then given by:

      φ = ψ − (α − π/2)

      Where ψ is the angle OGX, which we can calculate using the right angled triangle OXG:

      cos(ψ) = XG / (OB + BG)
      cos(ψ) = 3√(231)/52

      As expected, the difference made by following the arc instead of the straight line is not enough to change the result (which is given to the nearest second).

      Run: [ @replit ]

      from math import acos
      from enigma import fdiv, sq, sqrt, pi, printf
      
      # boat time
      boat = lambda d: d * 3
      
      # foot time
      foot = lambda d: fdiv(d, 0.75)
      
      # given distances
      R = 25
      SA = 2 * R
      SB = 40
      AG = 27
      
      # exact calculation?
      exact = 1
      
      # calculate time for A
      A = boat(SA) + foot(AG)
      printf("A = {A:.6f} sec")
      
      # calculate time for B
      SG = SA + AG
      cos_theta = fdiv(SB, SA)
      BG = sqrt(sq(SG) + sq(SB) - 2 * SG * SB * cos_theta)
      
      B = boat(40) + foot(BG)
      printf("B = {B:.6f} sec (approx)")
      
      if exact:
        # calculate XG
        XG = sqrt(sq(R + AG) - sq(R))
      
        # alpha is the angle SOB
        cos_alpha = fdiv(2 * sq(R) - sq(SB), 2 * sq(R))
        
        # psi is the angle OGX
        cos_psi = fdiv(XG, R + AG)
      
        # calculate phi (amount of arc)
        psi = acos(cos_psi)
        alpha = acos(cos_alpha)
        phi = psi - (alpha - 0.5 * pi)
      
        # calculate the exact distance for B
        BX = R * phi
        B = boat(40) + foot(BX + XG)
        printf("B = {B:.6f} sec (exact) [extra distance = {xB:.6f} m]", xB=BX + XG - BG)
        
      # calculate the difference
      d = abs(A - B)
      printf("diff = {d:.6f} sec")
      
      

      Solution: Arthur beats Boris by approximately 2 seconds.

      Following the arc is 3.95cm longer than the straight line distance, and adds 53ms to B’s time.

      The actual shortest distance from B to G can be expressed as:

      3\sqrt{231}\; +\; 25\cos ^{-1}\left( \frac{7}{52}\; +\; \frac{18\sqrt{231}}{325} \right)

      which is approximately 51.039494 m, compared to the straight line distance BG of 51 m.

      Like

      • galoisest 4:28 pm on 15 December 2021 Permalink | Reply

        Nice analysis Jim, I completely missed that the straight line goes through the pond.

        The simplest expression I can get for the difference including the arc is:

        100/3*(pi-acos(25/52)-2*acos(3/5)) + 4sqrt(231) – 66

        Like

        • Jim Randell 4:37 pm on 15 December 2021 Permalink | Reply

          It was more obvious in my original diagram (which had the line BG, instead of XG).

          But in this case it doesn’t matter if you spot this or not – the answer is unaffected. (I wonder if the setter intended us to calculate the exact distance, or just work out the length of BG).

          Like

  • Jim Randell 10:00 am on 7 December 2021 Permalink | Reply
    Tags: by: Bryan Thwaites   

    Brain-Teaser 889: Counting the hours 

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

    At school the other day, little Johnny was working with one of those boards with twelve clock-points regularly spaced round a circle against which should be put twelve counters showing the hours.

    He was, in fact, in a bit of a daze about the whole thing and the only hour he was absolutely dead sure of was 12 whose counter he correctly placed. As for the eleven others, if the truth be told, he just put them around at random.

    But Jill, his teacher, spotted some curious things. She first noticed that, however she chose a quartet of counters which formed the corners of a square, their sum was always the same.

    Next, she saw that if she formed numbers by multiplying together the counters at the corners of each square, one of those numbers was more than six times one of the others.

    She also observed that the counters in each quartet were, starting at the lowest, in ascending order of magnitude in the clockwise direction, and that 12 was not the only correct counter.

    In break, she reported all this to her colleague, Mary, adding “If I were to tell you, in addition, how many hours apart from the 12 Johnny had got right, you could tell me which they were”.

    Which were they?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser889]

     
    • Jim Randell 10:01 am on 7 December 2021 Permalink | Reply

      There are three squares that can be constructed, using the numbers in positions (12, 3, 6, 9), (1, 4, 7, 10), (2, 5, 8, 11). These partition the 12 numbers into 3 sets of 4.

      The total sum of the numbers is T(12) = 78, so values for each set must sum to 78/3 = 26.

      The following Python program runs in 48ms.

      Run: [ @replit ]

      from enigma import irange, subsets, diff, ediv, tuples, multiply, product, filter_unique, unpack, printf
      
      # find viable layouts
      def generate():
        ns = list(irange(1, 12))
        T = sum(ns)
        t = ediv(T, 3)
      
        # choose 3 numbers to go with 12 (and they must be in ascending order)
        n12 = 12
        for (n3, n6, n9) in subsets(diff(ns, [n12]), size=3):
          s1 = (n3, n6, n9, n12)
          if sum(s1) != t: continue
          p1 = multiply(s1)
      
          # choose numbers for (1, 4, 7, 10)
          for s2 in subsets(diff(ns, s1), size=4):
            if sum(s2) != t: continue
            p2 = multiply(s2)
      
            # remaining numbers
            s3 = diff(ns, s1 + s2)
            p3 = multiply(s3)
      
            # one of the products must be more than 6 times one of the others
            if not(max(p1, p2, p3) > 6 * min(p1, p2, p3)): continue
      
            # assign s1 to (1, 4, 7, 10) and s2 to (2, 5, 8, 11)
            fn = lambda s: tuples(s, 4, circular=1)
            for ((n1, n4, n7, n10), (n2, n5, n8, n11)) in product(fn(s2), fn(s3)):
              # construct the arrangement
              vs = [n1, n2, n3, n4, n5, n6, n7, n8, n9, n10, n11, n12]
              # find the numbers in the correct positions
              ss = tuple(n for (i, n) in enumerate(vs, start=1) if i == n)
              # there should be more than 1
              if len(ss) > 1:
                yield (vs, ss)
      
      # knowing len(ss) allows you to determine ss
      r = filter_unique(generate(), unpack(lambda vs, ss: len(ss)), unpack(lambda vs, ss: ss))
      
      # output solutions
      for (vs, ss) in r.unique:
        printf("{vs} -> {ss}")
      

      Solution: Johnny also placed 4 and 10 in the correct positions (as well as 12).

      There are two positions that lead to this:

      They both have squares with values (1, 2, 11, 12), (3, 4, 9, 10), (5, 6, 7, 8). But in the second one the (5, 6, 7, 8) square is rotated through 180°.

      The sums of the squares are all 26, and the products are (264, 1080, 1680), and 1680 > 1584 = 6 × 264.


      We find there are 14 possible arrangements that give the situation described.

      10 of them have 12 plus either 5, 7, or 8 in the correct position.

      2 of them have 12 plus (4, 5, 10) or (4, 8, 10) in the correct position.

      And the remaining two are those shown above with 12 plus (4, 10) in the correct position.

      Like

      • Frits 9:22 am on 8 December 2021 Permalink | Reply

        @Jim, you also could have used decompose() to find 4 numbers which sum to “t”.

        Like

    • GeoffR 7:50 pm on 7 December 2021 Permalink | Reply

      # four square group positions are (12,3,6,9), (1,4,7,10), (2,5,8,11)
      # sum of digits (1-12) = 78, so sum of each group is 26
      
      hours = set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11])
      H12 = 12   # set correct counter for Hour 12
      
      from itertools import permutations
      
      # 1st square group positions (12,3,6,9)
      for p1 in permutations(hours, 3):
        # counters for hours H3, H6 and H9
        H3, H6, H9 = p1  
        if H3 + H6 + H9 + H12 != 26:continue
        if not (H3 < H6 < H9 < H12):continue
        q1 = hours.difference([H3, H6, H9])
        
        # 2nd  square group positions (1,4,7,10)
        for p2 in permutations(q1, 4):
          # counters for hours H1, H4, H7, H9
          H1, H4, H7, H10 = p2
          if H1 +  H4 + H7 + H10 != 26:continue
          if not (H1 < H4 < H7 < H10):continue  
          q2 = hours.difference(p1).difference(p2)
          
          # 3rd square group positions (2,5,8,11)
          for p3 in permutations(q2,4):
            # counters for hours H2, H5, H8, H11
            H2, H5, H8, H11 = p3
            if H2 + H5 + H8 + H11 != 26:continue
            if not (H2 < H5 < H8 < H11):continue
            
            # find multiples of the corners of three groups
            m1 = H3 * H6 * H9 * H12
            m2 = H1 * H4 * H7 * H10
            m3 = H2 * H5 * H8 * H11
            m1, m3 = min([m1, m2, m3]), max([m1, m2, m3])
            if m1 < m2 < m3:
              # check one multiple is more than 6X another multiple
              if m2 > 6 * m1 or m3 > 6 * m1:
                print(f" Three products are {m1}, {m2}, and {m3}.")
                print(f" (H1, H2, H3) = ({H1}, {H2}, {H3})")
                print(f" (H4, H5, H6) = ({H4}, {H5}, {H6})")
                print(f" (H7, H8, H9) = ({H7}, {H8}, {H9})")
                print(f" (H10, H11, H12) = ({H10}, {H11}, {H12})")
      
      # Three products are 264, 1080, and 1680.
      # (H1, H2, H3) = (3, 5, 1)
      # (H4, H5, H6) = (4, 6, 2)
      # (H7, H8, H9) = (9, 7, 11)
      # (H10, H11, H12) = (10, 8, 12)
      # Only counters for hours 4, 10 and 12 are in the correct position.
      
      
      
      

      Like

    • GeoffR 9:21 am on 8 December 2021 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      % sum of digits 1..12 = 78, sum of each of three squares = 26
      % counter was correctly placed for 12 o'clock
      int: H12 == 12; 
      
      % Hour values
      var 1..11: H1; var 1..11: H2; var 1..11: H3; var 1..11: H4;
      var 1..11: H5; var 1..11: H6; var 1..11: H7; var 1..11: H8;
      var 1..11: H9; var 1..11: H10; var 1..11: H11; 
      
      constraint all_different ([H1,H2,H3,H4,H5,H6,H7,H8,H9,H10,H11,H12]);
      
      % Corners sum for 1st square  (positions 12,3,6,9)
      constraint H12 + H3 + H6 + H9 == 26;
      constraint H3 < H6 /\ H6 < H9 /\ H9 < H12;
      
      % Corners sum for 2nd square  (positions 1,4,7,10)
      constraint H1 + H4 + H7 + H10 == 26;
      constraint H1 < H4 /\ H4 < H7 /\ H7 < H10;
      
      % Corners sum for 3rd square  (positions 2,5,8,11)
      constraint H2 + H5 + H8 + H11 == 26;
      constraint H2 < H5 /\ H5 < H8 /\ H8 < H11;
      
      % Multiples of corner values - (sum 4 corners = 26, av < 7),
      % LB = 1*2*3*4 = 24, UB approx 7^4 = 2401, say 2400 
      var 24..2400:m1; var 24..2400:m2; var 24..2400:m3; 
      
      constraint m1 == H3 * H6 * H9 * H12;
      constraint m2 == H1 * H4 * H7 * H10;
      constraint m3 == H2 * H5 * H8 * H11;
      
      constraint m1 < m2 /\ m2 < m3;
      % one of the multiples was more than six times one of the others
      constraint m2 > 6 * m1 \/ m3 > 6 * m1;
      
      solve satisfy;
      
      % H12 = 12 << Hour 12 correct - stated value
      
      % H1 = 3;
      % H2 = 5;
      % H3 = 1;
      % H4 = 4;   << Hour 4 correct
      % H5 = 6;
      % H6 = 2;
      % H7 = 9;
      % H8 = 7;
      % H9 = 11;
      % H10 = 10;  << Hour 10 correct
      % H11 = 8;
      % m1 = 264;
      % m2 = 1080;
      % m3 = 1680;
      % % time elapsed: 0.15 s
      % ----------
      % ==========
      % Finished in 182msec
      
      

      Like

  • Jim Randell 9:33 am on 30 November 2021 Permalink | Reply
    Tags:   

    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 was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser888]

     
    • 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 subsets, irange, product, 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
      def rots(p):
        for k in (0, 1, 2, 3):
          yield p
          if k == 3: break
          p = rotate(p)
      
      # 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 product((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 product(l5s, l6s.keys())): continue
      
          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

  • Jim Randell 9:06 am on 23 November 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 887: The valetudinarians 

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

    “We have just been discussing our health”, said Alf, “and we have discovered that between us we share the same five complaints, and the same prescribed tablets for them. Each of us has two complaints, but no two have both the same, and no more than two of us take each sort of tablets. For instance two take red tablets, two blue, and so on. I do not have green ones. I take one lot the same as Ed, but they are not yellow, and I do not take kidney tablets”.

    Bob said: “I do not have green tablets. One heart patient also has tablets for sleeplessness”.

    Cyril said: “I do not have kidney tablets. I take one lot the same as Ed which are not for the heart. I do not take blue ones”.

    Don said: “I do not have heart trouble. My tablets are not yellow. Those who take green tablets do not also take blue ones”.

    Ed said: “I take white tablets which are not for the heart. The ones with nerves do not have indigestion, and nerve tablets are not yellow”.

    What colour were the heart tablets? Who took those for nerves?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser887]

     
    • Jim Randell 9:08 am on 23 November 2021 Permalink | Reply

      I assumed each colour tablet is prescribed for the same condition in each patient.

      This Python program uses the [[ choose() ]] function from enigma.py, which I thought I would use more when I implemented it. It runs in 65ms.

      Run: [ @replit ]

      from enigma import subsets, ordered, choose, intersect, singleton, multiset, join, printf
      
      # tablet colours
      tablets = "BGRWY"
      
      # map complaints to tablets
      for (K, H, N, I, S) in subsets(tablets, size=len, select="P"):
      
        # "white tablets are not for the heart"
        if H == 'W': continue
      
        # "nerve tablets are not yellow"
        if N == 'Y': continue
      
        # there are 2 invalid combinations: nerves + indigestion, green + blue
        invalid = { ordered(N, I), ('B', 'G') }
        values = set(s for s in subsets(tablets, size=2)).difference(invalid)
      
        # choose tablets for each person:
        def fE(Es):
          # E has white
          if 'W' not in Es: return False
          return True
      
        def fA(Es, As):
          # A does not have green or kidney
          if 'G' in As or K in As: return False
          # A has one tablet the same as E, and it isn't yellow
          AE = singleton(intersect([As, Es]))
          if AE is None or AE == 'Y': return False
          return True
      
        def fC(Es, As, Cs):
          # C does not have kidney or blue
          if K in Cs or 'B' in Cs: return False
          # C has one tablet the same as E, and it isn't heart
          CE = singleton(intersect([Cs, Es]))
          if CE is None or CE == H: return False
          return True
      
        def fD(Es, As, Cs, Ds):
          # D does not have heart or yellow
          if H in Ds or 'Y' in Ds: return False
          return True
      
        def fB(Es, As, Cs, Ds, Bs):
          # B does not have green
          if 'G' in Bs: return False
          return True
      
        # make the choices
        for vs in choose(values, [fE, fA, fC, fD, fB], distinct=1):
          # one of them has heart + sleeplessness
          if not(ordered(H, S) in vs): continue
          # each tablet is used by two people
          if not multiset.from_seq(*vs).all_same(2): continue
      
          # output solution
          (Es, As, Cs, Ds, Bs) = (join(v, sep="+") for v in vs)
          printf("A={As} B={Bs} C={Cs} D={Ds} E={Es} [K={K} H={H} N={N} I={I} S={S}]")
      

      Solution: Heart tablets are blue. Cyril and Don took tablets for nerves.

      The complete situation is:

      Alf: blue (heart); yellow (indigestion)
      Bob: red (kidney); yellow (indigestion)
      Cyril: green (nerves); white (sleeplessness)
      Don: green (nerves); red (kidney)
      Ed: blue (heart); white (sleeplessness)

      Like

    • Frits 1:32 pm on 30 November 2021 Permalink | Reply

        
      from itertools import combinations as comb, permutations as perm
      
      # filter on tablet, complaint and shared tablets (with, type, exclusion) 
      def filter(lst, exc_tabl, exc_cmpl=99, shr_with=[], shr_t=0, shr_e={}):
        if shr_with:
          shr_set = {shr_with[0][shr_t], shr_with[1][shr_t]}
          frz_set = {frozenset(), frozenset(shr_e)}
          
        return [(x, y) for x, y in lst if all(e not in {x[i], y[i]} 
               for i, e in enumerate([exc_tabl, exc_cmpl])) and (not shr_with or 
               shr_set.intersection({x[shr_t], y[shr_t]}) not in frz_set)]
      
      guys = ["Alf", "Bob", "Cyril", "Don", "Ed"]
      tablets = ["red", "blue", "green", "white", "yellow"]
      # [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]
      sorted_tablets = [i for i in range(5) for _ in range(2)]
      
      # red    0       indigestion   0
      # blue   1       heart         1
      # green  2       kidney        2
      # white  3       sleeplessness 3 
      # yellow 4       nerves        4
      
      # loop over complaints per tablet
      for p in perm(range(5)):
        # "white tablets are not for the heart"
        # "nerve tablets are not yellow"
        if p[3] == 1 or p[4] == 4: continue
        
        # combine two out of (tablets, complaints) list
        # there are 2 invalid combinations: nerves + indigestion, green + blue
        cmbs = [(x, y) for x, y in comb([(i, z) for i, z in enumerate(p)], 2) 
               if sorted((x[1], y[1])) != [0, 4] and
                  sorted((x[0], y[0])) != [1, 2]]
        
        # one of them has heart + sleeplessness          
        if all(sorted([x[1], y[1]]) != [1, 3] for x, y in cmbs): continue
        
        # E has white
        for E in [(x, y) for x, y in cmbs if 3 in {x[0], y[0]}]:
          notE = set(cmbs).difference({E})
          # A does not have green or kidney
          # A has one tablet the same as E, and it isn't yellow
          for A in filter(notE, 2, 2, E, 0, [4]):
            notAE = set(notE).difference({A})
            # C does not have kidney or blue
            # C has one tablet the same as E, and it isn't heart
            for C in filter(notAE, 1, 2, E, 1, [1]):
              notAEC = set(notAE).difference({C})
              # D does not have heart or yellow
              for D in filter(notAEC, 4, 1):
                notAECD = set(notAEC).difference({D})
                # B does not have green
                for B in filter(notAECD, 2):
                  ABCDE = [A, B, C, D, E]
                  
                  # each tablet is sorted by two people
                  if sorted(z for x, y in ABCDE for z in (x[0], y[0])) != \
                     sorted_tablets: continue
                  
                  # one of them has heart + sleeplessness     
                  if all(sorted([x[1], y[1]]) != [1, 3] for x, y in ABCDE): 
                    continue
                  
                  heart = set(x[0] if x[1] == 1 else y[0] 
                              for x, y in ABCDE if 1 in {x[1], y[1]})
                  if len(heart) != 1: continue 
                  print(f"Heart tablets are {tablets[heart.pop()]}.")
                  
                  nerves = [i for i, (x, y) in enumerate(ABCDE) 
                            if 4 in {x[1], y[1]}]
                  print(f"{guys[nerves[0]]} and {guys[nerves[1]]} "
                        f"took tablets for nerves")
      

      Like

  • Jim Randell 9:09 am on 18 November 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 884: Mice in the works 

    From The Sunday Times, 16th July 1978 [link]

    Recently a hot-drink vending machine was installed in our office. Very nice it is too — completely up to date it was when it was bought. There are five switches, a slot for your money, and a button. The switches are labelled TEA, COFFEE, CHOCOLATE, MILK and SUGAR, and you select the combination you want, put in your money, press the button, and out comes your drink. Why, you can even have coffolatea if you want!

    At least, this is the idea. Unfortunately, during the ten years it has been in store, “awaiting approval”, mice have chewed up the wiring. Mice with soldering irons, I should think. The result is now that no switch affects its “own” ingredient at all, but instead turns on two other ingredients, each ingredient being turned on by two different switches. However, if two switches are set which turn on the same ingredient, then they cancel each other out, and that ingredient doesn’t come out at all.

    The result is somewhat chaotic, though occasionally some of the output is actually drinkable. For instance, when you ask for white sweet coffee, you get unsweetened milky tea; when you ask for sweet milky chocolate, you get sweet chocolate without milk; and when you ask for unsweetened milky tea you get a glorious gooey mocha — i.e. chocolate and coffee with milk and sugar.

    Luckily, pressing the “deliver” button reinstates the original chaos, so that setting the same switches always gives the same results.

    So, what is the easiest way to get white coffee without sugar? (i.e. Name the fewest switches that will deliver just coffee and milk).

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser884]

     
    • Jim Randell 9:12 am on 18 November 2021 Permalink | Reply

      We’ve seen puzzles like this before. See Enigma 91, Puzzle #103 (although this puzzle was published before either of them).

      I reused the code I wrote for Puzzle #103.

      The following Python 3 program runs in 60ms.

      Run: [ @replit ]

      from enigma import multiset, subsets, diff, update, ordered, join, map2str, printf
      
      # buttons
      buttons = 'T Cf Ch M S'.split()
      
      # map each value in <ks> to <n> other values chosen from mutliset <vs>
      # return map d: <ks> -> <n>-tuples from <vs>
      def make_map(ks, vs, n=2, d=dict()):
        # are we done?
        if not ks:
          yield d
        else:
          # choose n values for the next key
          k = ks[0]
          for ss in subsets(diff(vs.keys(), [k]), size=n):
            yield from make_map(ks[1:], vs.difference(ss), n, update(d, [(k, ordered(*ss))]))
      
      # outcome of selecting buttons <bs> using map <d>
      def select(d, bs):
        m = multiset()
        for b in bs:
          m.update_from_seq(d[b])
        return set(k for (k, v) in m.items() if v == 1)
      
      # consider possible maps
      for d in make_map(buttons, multiset.from_seq(buttons, count=2)):
      
        # select M+S+Cf -> M+T
        if not(select(d, ['M', 'S', 'Cf']) == {'M', 'T'}): continue
      
        # select S+M+Ch -> S+Ch
        if not(select(d, ['S', 'M', 'Ch']) == {'S', 'Ch'}): continue
      
        # select M+T -> Ch+Cf+M+S
        if not(select(d, ['M', 'T']) == {'Ch', 'Cf', 'M', 'S'}): continue
      
        # answer, easiest way to get Cf+M?
        for bs in subsets(buttons, min_size=1):
          if select(d, bs) == {'Cf', 'M'}:
            fmt = lambda s: join(sorted(s), sep="+")
            printf("{bs} -> Cf+M {d}", bs=fmt(bs), d=map2str(((k, fmt(v)) for (k, v) in d.items()), arr="->", enc="[]"))
      

      Solution: The easiest way to get coffee and milk is to select “Coffee” and “Milk”.

      There is also a combination of 3 buttons that will give coffee and milk: “Chocolate”, “Tea” and “Sugar”.

      The items delivered by the buttons are:

      Coffee: Chocolate + Milk
      Chocolate: Tea + Sugar
      Milk: Coffee + Chocolate
      Sugar: Coffee + Tea
      Tea: Milk + Sugar

      Like

    • John Crabtree 5:44 pm on 25 November 2021 Permalink | Reply

      Using the same switch twice selects nothing. Using all five switches selects nothing. Call this statement S4
      Using all of the switches in statements S1, S2, S3 and S4 results in: using S gives Cf and T
      S1 reduces to: using Cf and M gives Cf and M
      This is one possible answer, but we do not know that it is the shortest.
      From S1 and S, using M gives Cf
      From S2 and S, using M gives Ch as well as Cf (from above)
      From S1, using Cf gives Ch and M
      From S2, using Ch gives S and T
      From S3, using T gives M and S

      Since no one button gives Coffee with Milk, pressing Coffee and Milk is the simplest way to get Coffee with Milk

      This solution is much simpler that the official one in the book.

      Like

  • Jim Randell 9:11 am on 11 November 2021 Permalink | Reply
    Tags: by: J P Mernagh   

    Brain-Teaser 883: Goals galore 

    From The Sunday Times, 9th July 1978 [link]

    We’ve grown tired of these low-scoring, defensive football matches in our locality, and so it was agreed last March for the annual competition between the five villages, each playing the others once, that no goalkeepers would be allowed, and each game would continue until nine goals had been scored.

    Each village won 2 matches, and scored a different number of goals in each match. In the games, each possible result occurred twice. We had to decide the tournament on the total of goals scored, and happily, all five totals were different.

    Blackton, the eventual champions, lost 2-7 to Appleton. Easton were last with 11 goals fewer than Blackton.

    The Drafton centre-forward remarkably scored a hat-trick in each match, which included a last-second winner against Blackton.

    Caxton scored in every match and could indeed have won the league if they had scored twice more in their match against Blackton. As it was they finished one goal ahead of Drafton in the final totals.

    What was the score between Easton and Appleton; and what was the score between Caxton and Drafton?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser883]

     
    • Jim Randell 9:12 am on 11 November 2021 Permalink | Reply

      I used the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 357ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      # let the matches be:
      #
      #  A vs B = F - G
      #  A vs C = H - I
      #  A vs D = J - K
      #  A vs E = L - M
      #  B vs C = N - P
      #  B vs D = Q - R
      #  B vs E = S - T
      #  C vs D = U - V
      #  C vs E = W - X
      #  D vs E = Y - Z
      
      SubstitutedExpression
      
      # each village scored a different number of goals in each match
      # (and so they also each conceded a different number of goals in each match)
      --distinct="FHJL,GNQS,IPUW,KRVY,MTXZ,GIKM,FPRT,HNVX,JQUZ,LSWY"
      
      # each match goes to 9-goals
      "9 - F = G"
      "9 - I = H"
      "9 - K = J"
      "9 - L = M"
      "9 - P = N"
      "9 - R = Q"
      "9 - T = S"
      "9 - U = V"
      "9 - W = X"
      "9 - Y = Z"
      
      # each team won 2 matches
      "sum([F > 4, H > 4, J > 4, L > 4]) = 2"
      "sum([G > 4, N > 4, Q > 4, S > 4]) = 2"
      "sum([I > 4, P > 4, U > 4, W > 4]) = 2"
      "sum([K > 4, R > 4, V > 4, Y > 4]) = 2"
      "sum([M > 4, T > 4, X > 4, Z > 4]) = 2"
      
      # each result occurred twice
      --code="twice = lambda *ss: multiset.from_seq(ordered(*s) for s in ss).all_same(2)"
      "twice((F, G), (H, I), (J, K), (L, M), (N, P), (Q, R), (S, T), (U, V), (W, X), (Y, Z))"
      
      # each side scored a different number of goals
      "all_different(F + H + J + L, G + N + Q + S, I + P + U + W, K + R + V + Y, M + T + X + Z)"
      
      # A vs B = 7 - 2
      --assign="F,7"
      --assign="G,2"
      
      # D beat B
      --invalid="0-4,R"
      --invalid="5-9,Q"
      
      # D had a hat-trick in each match
      --invalid="0-2,KRVY"
      --invalid="7-9,JQUZ"
      
      # E has 11 goals fewer than B"
      "(G + N + Q + S) - (M + T + X + Z) = 11"
      
      # C finished 1 goal ahead of D
      "(I + P + U + W) - (K + R + V + Y) = 1"
      
      # B were the eventual champions
      "G + N + Q + S > max(F + H + J + L, I + P + U + W)"
      
      # C scored in every match
      --invalid="0,IPUW"
      --invalid="9,HNVX"
      
      # C could have scored 2 more goals against B ...
      --invalid="8-9,P"
      --invalid="0-1,N"
      # ... and been champions
      "I + P + U + W + 2 > max(F + H + J + L, G + N + Q + S - 2, I + P + U + W)"
      
      # [optional] neater output
      --template="F-G H-I J-K L-M; N-P Q-R S-T; U-V W-X; Y-Z"
      --solution=""
      

      Solution: Appleton vs. Easton = 3 – 6; Caxton vs. Grafton = 2 – 7.

      The full results are:

      A vs B = 7 – 2
      A vs C = 0 – 9
      A vs D = 6 – 3
      A vs E = 3 – 6
      B vs C = 8 – 1
      B vs D = 4 – 5
      B vs E = 9 – 0
      C vs D = 2 – 7
      C vs E = 8 – 1
      D vs E = 4 – 5

      B = 23 for; 13 against
      C = 20 for; 16 against
      D = 19 for; 17 against
      A = 16 for; 20 against
      E = 12 for; 24 against

      Like

    • Frits 12:28 pm on 12 November 2021 Permalink | Reply

      Similar but with fewer variables (including the hat-trick requirement).

        
      #!/usr/bin/env python3 -m enigma -r
      
      # let the matches be:
      #
      #  A vs B = F - ..
      #  A vs C = G - ..
      #  A vs D = H - ..
      #  A vs E = I - ..
      #  B vs C = J - ..
      #  B vs D = K - ..
      #  B vs E = L - ..
      #  C vs D = M - ..
      #  C vs E = N - ..
      #  D vs E = O - ..
      SubstitutedExpression
      
      # each village scored a different number of goals in each match
      # (and so they also each conceded a different number of goals in each match)
      --distinct="FGHI, JKL, MN"
      
      "9 - F not in {J, K, L}"
      "all_different(9 - G, 9 - J, M, N)"
      "all_different(9 - H, 9 - K, 9 - M, O)"
      "all_different(9 - I, 9 - L, 9 - N, 9 - O)"
      
      # each team won 2 matches
      "sum([F > 4, G > 4, H > 4, I > 4]) = 2"
      "sum([9 - F > 4, J > 4, K > 4, L > 4]) = 2"
      "sum([9 - G > 4, 9 - J > 4, M > 4, N > 4]) = 2"
      "sum([9 - H > 4, 9 - K > 4, 9 - M > 4, O > 4]) = 2"
      "sum([9 - I > 4, 9 - L > 4, 9 - N > 4, 9 - O > 4]) = 2"
      
      # each result occurred twice
      --code="twice = lambda *y: sorted(sorted(x) for x in y) == \
                      sorted([[0, 9], [1, 8], [2, 7], [3, 6], [4, 5]] * 2)"
      "twice((F, 9-F), (G, 9-G), (H, 9-H), (I, 9-I), (J, 9-J), (9-K, K), 
             (9-L, L), (9-M, M), (N, 9-N), (O, 9-O))"
      
      # each side scored a different number of goals
      "all_different(F + G + H + J, 
                     9 - F + J + K + L, 
                     18 - G - J + M + N, 
                     27 - H - K - M + O, 
                     36 - I - L - N - O)"
      
      # A vs B = 7 - 2
      --assign="F,7"
      
      # D beat B and scored at least 3 goals in each match
      --invalid="5-9,K"
      --invalid="0-2,O"
      --invalid="7-9,HM"
      
      # E has 11 goals fewer than B"
      "11 - (9 - F + J + K + L - (36 - I - L - N)) = O"
      
      # C finished 1 goal ahead of D
      "(18 - J + M + N) - (27 - H - K - M + O) - 1 = G"
      
      # B were the eventual champions
      "9 - F + J + K + L > max(F + G + H + J, 18 - G - J + M + N)"
      
      # C scored in every match
      --invalid="0,MN"
      --invalid="9,GJ"
      
      # C could have scored 2 more goals against B ...
      --invalid="0-1,J"
      # ... and been champions
      "20 - G - J + M + N > max(F + G + H + J, 7 - F + J + K + L)"
      
      # [optional] neater output
      --template="F, G, H, I, J, K, L, M, N, O"
      --solution=""
      

      Like

  • Jim Randell 10:16 am on 28 October 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 905: Prime square 

    From The Sunday Times, 25th November 1979 [link]

    “Here”, said Uncle Henry to the twins, “is a magic square which I’ve started for you”:

    “You must complete it by putting eight different prime numbers in the eight empty squares, so that the [rows], the columns and the diagonals add up to the same total; and it must be the smallest possible total under the conditions.”

    There followed half an hour of comparative peace… after which the twins could bear it no longer.

    “Oh. Uncle”, complained Betty, “It looks so easy and yet it’s much too difficult”. And Brian fervently agreed.

    “All right”, said Uncle Henry, “I’ll tell you a couple more things: there is one such magic square where the number in the middle square is the average of the two numbers directly above and below it; the third largest number is not in the right-hand column; and each square contains one or two digits”.

    After a further ten minutes, the twins managed to produce the right solution.

    Can you complete the magic square?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    It was also included in the book The Sunday Times Book of Brainteasers (1994, edited by Xerxes).

    [teaser905]

     
    • Jim Randell 10:17 am on 28 October 2021 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 64ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      #  AB  CD  EF
      #  GH  IJ  KL
      #  MN  01  PQ
      
      SubstitutedExpression
      
      --distinct=""
      --invalid=""
      
      # missing numbers are different 1 or 2 digit primes
      "is_prime(AB)"
      "is_prime(CD)"
      "is_prime(EF)"
      "is_prime(GH)"
      "is_prime(IJ)"
      "is_prime(KL)"
      "is_prime(MN)"
      "is_prime(PQ)"
      "all_different(AB, CD, EF, GH, IJ, KL, MN, PQ)"
      
      # in an additive magic square the magic constant is 3 times the centre value (= 3 * IJ)
      "2 * IJ - 1 = CD"
      "2 * IJ - AB = PQ"
      "2 * IJ - EF = MN"
      "2 * IJ - GH = KL"
      "3 * IJ - AB - CD = EF"
      "3 * IJ - MN - 1 = PQ"
      "3 * IJ - AB - GH = MN"
      "3 * IJ - EF - KL = PQ"
      
      # third largest number is _not_ in the RH column
      "ordered(1, AB, CD, EF, GH, IJ, KL, MN, PQ)[-3] not in {EF, KL, PQ}"
      
      --template="(AB CD EF) (GH IJ KL) (MN 01 PQ)"
      --solution=""
      

      Solution: Here is a diagram of the completed square:

      Like

      • Mark Valentine 1:21 pm on 28 October 2021 Permalink | Reply

        Third largest number can’t be in right-hand column. Need to flip it.

        Like

        • Mark Valentine 1:23 pm on 28 October 2021 Permalink | Reply

          Apologies. Misread it. Yours is correct.

          Like

      • Frits 3:41 pm on 28 October 2021 Permalink | Reply

        Using “3 * IJ – AB – MN = GH” instead of “3 * IJ – AB – GH = MN” you don’t have to internally loop over G and H.

        Like

      • Jim Randell 12:35 pm on 29 October 2021 Permalink | Reply

        And here is a Python program that can be used to generate magic squares with larger magic constants:

        from enigma import primes, ordered, arg, printf
        
        # the magic square is:
        #
        #  A B C
        #  D E F
        #  G 1 H
        #
        # so the magic constant k = 3E
        
        # generate magic squares
        def generate():
          # consider values for E
          for E in primes.range(3):
            k = 3 * E
            B = k - E - 1
            if B not in primes: continue
        
            # choose a value for A
            for A in primes.range(3, k - E):
              # calculate the remaining values
              H = k - A - E
              if H not in primes: continue
              C = k - A - B
              if C not in primes: continue
              F = k - C - H
              if F not in primes: continue
              G = k - C - E
              if G + 1 + H != k or G not in primes: continue
              D = k - E - F
              if A + D + G != k or D not in primes: continue
              # check conditions
              if len({A, B, C, D, E, F, G, H}) != 8: continue
              ns = ordered(A, B, C, D, E, F, G, 1, H)
              if ns[-3] in {C, F, H}: continue
              # valid layout
              yield (A, B, C, D, E, F, G, H)
        
        N = arg(1, 0, int)
        for (n, (A, B, C, D, E, F, G, H)) in enumerate(generate(), start=1):
          printf("[ {A} {B} {C} | {D} {E} {F} | {G} 1 {H} ] {k}", k=3 * E)
          if n == N: break
        

        Like

    • Hugh Casement 2:47 pm on 28 October 2021 Permalink | Reply

      It’s superfluous information (though perhaps helpful) that the middle column is an arithmetic progression.
      Rather than say “the third largest number is not in the right-hand column” it would have been simpler to tell us that the smallest prime is in the left-hand column (otherwise we find a reflection in the vertical axis).
      Without the 1 we would need at least two 3-digit primes to make a magic square.

      Like

    • GeoffR 4:12 pm on 28 October 2021 Permalink | Reply

      My solution shows that the 3rd highest number must not be in the right hand column is a definite requirement, as shown in the note at the end of the programme output. I initially wrote a programme without this constraint. I am not sure how this constraint would be programmed in MiniZinc.

      % A Solution in MiniZinc
      include "globals.mzn";
      
      %  A  B  C
      %  D  E  F
      %  G  H  I
      
      var 2..97:A; var 2..97:B; var 2..97:C; 
      var 2..97:D; var 2..97:E; var 2..97:F;
      var 2..97:G; var 2..97:I;
      
      int: H == 1;
      constraint all_different([A, B, C, D, E, F, G, H, I]);
      
      predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
      
      % All values of the grid (except H) are primes
      constraint is_prime(A) /\ is_prime(B) /\ is_prime(C)
      /\ is_prime(D) /\ is_prime(E) /\ is_prime(F)
      /\ is_prime(G) /\ is_prime(I);
      
      % All rows, columns and diagonals add to the same total
      constraint A + B + C == D + E + F /\ A + B +  C == G + H + I
      /\  A + B + C == A + D + G /\  A + B + C == B + E + H 
      /\  A + B + C == C + F + I /\  A + B + C == A + E + I
      /\  A + B + C == C + E + G;
      
      % the middle square is the average of the two numbers directly above and below it
      constraint 2 * E == B + H \/ 2 * D == A + G \/ 2 * F == C + I;
      
      %  the smallest possible total
      solve minimize(A + B + C);
      
      output [ "[A,B,C,D,E,F,G,H,I] = " ++ show([A,B,C,D,E,F,G,H,I] ) ];
      
      % [A, B, C, D, E, F, G, H, I] = [31, 73, 7, 13, 37, 61, 67, 1, 43]
      % ----------
      % ==========
      % Analysis of this solution
      % -------------------------
      % the third highest number (61) must not be in the third column
      % it is moved to the left hand column by transposing left and right columns
      % 31  73  7   =>   7  73  31
      % 13  37  61  =>  61  37  13
      % 67   1  43  =>  43   1  67
      
      
      
      

      Like

      • Frits 10:28 am on 29 October 2021 Permalink | Reply

        @GeoffR, you can declare an array, fill it with same elements as the original array and add an “increasing” constraint.

          
        % A Solution in MiniZinc
        include "globals.mzn";
         
        %  A  B  C
        %  D  E  F
        %  G  H  I
         
        var 2..97:A; var 2..97:B; var 2..97:C; 
        var 2..97:D; var 2..97:E; var 2..97:F;
        var 2..97:G; var 2..97:I;
         
        int: H == 1;
        constraint all_different([A, B, C, D, E, F, G, H, I]);
        
        array[1..9] of var 1..97: nbrs = [A, B, C, D, E, F, G, H, I];
        array[1..9] of var 1..97: sorted;
        
        % make sure both arrays contain same elements
        constraint forall(X in nbrs)(
                      exists(i in 1..9) ( X = sorted[i])
        );
        
        % make sure array "sorted" is sorted
        constraint increasing(sorted);
         
        predicate is_prime(var int: x) = x > 1 /\ 
        forall(i in 2..1 + ceil(sqrt(int2float(ub(x))))) ((i < x) -> (x mod i > 0));
         
        % All values of the grid (except H) are primes
        constraint is_prime(A) /\ is_prime(B) /\ is_prime(C)
        /\ is_prime(D) /\ is_prime(E) /\ is_prime(F)
        /\ is_prime(G) /\ is_prime(I);
         
        % All rows, columns and diagonals add to the same total
        constraint A + B + C == D + E + F /\ A + B + C == G + H + I
        /\  A + B + C == A + D + G /\  A + B + C == B + E + H 
        /\  A + B + C == C + F + I /\  A + B + C == A + E + I
        /\  A + B + C == C + E + G;
         
        % the middle square is the average of the two numbers
        % directly above and below it
        constraint 2 * E == B + H;
        
        % third largest number is not in the RH column
        constraint C != sorted[7] /\ F != sorted[7] /\ I != sorted[7];
         
        %  the smallest possible total
        solve minimize(A + B + C);
         
        output [show([A,B,C]) ++ "\n" ++ show([D,E,F]) ++ "\n" ++ show([G, H, I])];
        

        Like

    • GeoffR 11:00 am on 29 October 2021 Permalink | Reply

      @Frits:

      Yes, that is a neat solution to ensure that the third largest number is not in the right-hand column.

      Like

  • Jim Randell 9:07 am on 21 October 2021 Permalink | Reply
    Tags: by: Alfred Moritz   

    Brain-Teaser 882: Another magic class 

    From The Sunday Times, 2nd July 1978 [link]

    This puzzle concerns a class of twenty-five pupils whose first names happen to have different initials (and none begins with X). The teacher makes them sit in alphabetical order in five neat rows of five with Arthur sitting to the left of Barry and in front of Freda.

    When their homework was returned (marked, as usual, out of a maximum of 25 without using fractional marks) they found that each pupil had a different mark and that, surprisingly enough, the total of marks in each row of five, each column of five and each diagonal of five was identical.

    Yvonne came top, followed by Harry and Jane in that order. Ursula scored more marks than Zena, and Richard was beaten by Charles. Victor had twice as many marks as George, and Ivor had four times as many as Freda. Susan beat Michael by the same margin by which Michael beat George (who, incidentally, scored an odd number of marks). This was also the margin by which Walter beat his left-hand neighbour and by which his right-hand neighbour beat him.

    Kenneth beat Olga. By how many marks?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser882]

     
    • Jim Randell 9:08 am on 21 October 2021 Permalink | Reply

      We can use the [[ SubstitutedExpression ]] solver from the enigma.py library to solve this puzzle.

      The following run file executes in 73ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      SubstitutedExpression
      
      # values are 0 to 25, so let's use base 26
      --base=26
      
      # X is the unused value, so: k = (tri(25) - X) / 5, tri(25) = 325
      # so X is a multiple of 5
      "X % 5 == 0"
      
      # each row/column/diagonal sums to the magic constant
      "5 * (A + B + C + D + E) + X == 325"
      "5 * (F + G + H + I + J) + X == 325"
      "5 * (K + L + M + N + O) + X == 325"
      "5 * (P + Q + R + S + T) + X == 325"
      "5 * (U + V + W + Y + Z) + X == 325"
      
      "5 * (A + F + K + P + U) + X == 325"
      "5 * (B + G + L + Q + V) + X == 325"
      "5 * (C + H + M + R + W) + X == 325"
      "5 * (D + I + N + S + Y) + X == 325"
      "5 * (E + J + O + T + Z) + X == 325"
      
      "5 * (A + G + M + S + Z) + X == 325"
      "5 * (E + I + M + Q + U) + X == 325"
      
      # Y is the highest mark
      "(25 if X != 25 else 24) = Y"
      
      # H is the second highest mark
      "(Y - 1 if X != Y - 1 else Y - 2) = H"
      
      # J is the third highest mark
      "(H - 1 if X != H - 1 else H - 2) = J"
      
      # Y beat W by the same margin that W beat V
      "Y - W == W - V"
      
      # and this is the same margin that S beat M and M beat G
      "S - M == Y - W"
      "M - G == Y - W"
      
      # V = 2G, G's score was odd
      "2 * G = V"
      "G % 2 == 1"
      
      # I = 4F
      "4 * F = I"
      
      # U beat Z, C beat R, K beat O
      "U > Z"
      "C > R"
      "K > O"
      
      # [optional]
      --template=""
      --denest
      

      Solution: Kenneth beat Olga by 16 marks.

      The complete layout is:

      [A 21] [B 14] [C  7] [D  0] [E 18]
      [F  2] [G  5] [H 23] [I  8] [J 22]
      [K 20] [L 15] [M 12] [N  9] [O  4]
      [P 11] [Q 16] [R  1] [S 19] [T 13]
      [U  6] [V 10] [W 17] [Y 24] [Z  3]
      [X 25]

      So the marks awarded were 0-24, no-one scored 25.

      Like

    • Frits 12:54 pm on 22 October 2021 Permalink | Reply

       
      # Y + V = 2 * W  \
      # Y = 24 or 25    > V is even so Y is also even
      # V = 2G         /
      #
      # (X, Y, H, J) = (25, 24, 23, 22)
      # W = 17
      #
      # F + G + I = 15 \   G + 5 * F = 15
      # G is odd        >  so G = 5, F = 2, I = 8
      # 4 * F = I      /
      #
      # V = 10 (2 * G)
      # center M = 60 / 12
      # S = 19 (S - M == Y - W)
      #
      # C + H + M + R + W = 60 \  C + R = 8
      #                         >
      # C > R                  /  so only option R = 1, C = 7
      #
      # A + G + M + S + Z = 60 \  A + Z = 24  so Z > 2
      # U > Z                   >
      # U + V + W + Y + Z = 60 /  U + Z = 9 only option Z = 3, U = 6, A = 21
      #
      # D + I + N + S + Y = 60 --> D + N = 9, only options (D, N): (0, 9) or (9, 0)
      #
      # only candidates for 4 are O and T -- > O + T = y + 4  (y is O or T)
      # E + J + O + T + Z = 60 --> E + O + T = 35 --> E + y = 31 --> E > 10
      #
      # B + G + L + Q + V = 60 \  B + L + Q = 45 so B > 6 and also B > 10
      #                         >
      # A + B + C + D + E = 60 /  B + D + E = 32
      #
      # minimal(B + E) = 24 --> D <= 8 --> D = 0 and N = 9
      #
      # E + O + T = 35 \
      #                 > Q = O + T - 1 = y + 3
      # E + Q = 34     /
      #
      # B + E = 32, only options (B, E, Q): (14, 18, 16) or (18, 14, 20)
      # last option implies y = 17 which is not possible
      # so B = 14, E = 18, Q = 16, L = 15
      #
      # A + F + K + P + U = 60 --> K + P = 31
      # only options (K, P): (20, 11) or (11, 20)
      #
      # K + L + M + N + O = 60 --> K + O = 24 with K > O
      # only option (K, O): (20, 4)
      # K = 20, O = 4, T = 13, P = 11 
      

      Like

  • Jim Randell 7:15 am on 14 October 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 879: Seven criminals 

    From The Sunday Times, 11th June 1978 [link]

    The instructor at the police training college spoke to the six constables in his class in these words:

    “You have been studying full-face photographs of seven criminals whom we are calling P, Q, R, S, T, U and V. Now l am going to show you one photograph, taken in profile, of each criminal, and you have to write down their names in the
    order in which I present them.”

    This was done and the constables handed in the following
    six answers:

    1. P Q R S T U V
    2. P Q R U T S V
    3. P S U V R T Q
    4. P S Q U R T V
    5. P U R V T S Q
    6. R P U Q T S V

    “I am pleased to see that each criminal has been correctly identified by at least one of you”, said the instructor. “And I note that you all have a different number of correct answers and so I can give out the prizes”.

    In what order were the photographs presented?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser879]

     
    • Jim Randell 7:16 am on 14 October 2021 Permalink | Reply

      It is straightforward to check all possible arrangements.

      This Python program runs in 87ms.

      Run: [ @replit ]

      from enigma import subsets, seq_all_different, join, printf
      
      # the six answers
      ans = [
        'PQRSTUV',
        'PQRUTSV',
        'PSUVRTQ',
        'PSQURTV',
        'PURVTSQ',
        'RPUQTSV',
      ]
      
      # count number of items in correct position
      correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
      
      # consider possible orderings
      for ss in subsets('PQRSTUV', size=len, select="P"):
        # how many are in the correct position?
        pos = list(correct(xs, ss) for xs in ans)
        if not seq_all_different(pos): continue
        # check each item is correct in one of the answers
        if not all(any(xs[i] == x for xs in ans) for (i, x) in enumerate(ss)): continue
        # output solution
        printf("{ss} -> {pos}", ss=join(ss, sep=" ", enc="()"))
      

      Solution: The photographs were presented in the following order: R, P, U, V, T, S, Q.

      And the number of photographs correctly identified by the constables were: 1, 2, 3, 0, 4, 5.

      There is only a single solution without the condition that each criminal was identified correctly by (at least) one of the constables. But we see that the last constable got Q and V wrong (and the rest right), but the penultimate constable got these two right, so each miscreant was identified correctly by one of the constables.

      Like

    • Frits 10:12 am on 15 October 2021 Permalink | Reply

      Borrowing from above program and the solve() function in Teaser 3080 (One of a kind).
      The program runs in 2ms.

        
      # find members of each set, such that each member is used exactly once
      def solve(ss, ns=[], ds=set()):
        # are we done?
        if not(ss):
          yield ns
        else:
          # choose an element from the next set
          for n in ss[0]:
            if not(ds.intersection(n)):
              yield from solve(ss[1:], ns + [n], ds.union(n))
      
      # count number of items in correct position
      correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
      
      # the six answers
      ans = [
        'PQRSTUV',
        'PQRUTSV',
        'PSUVRTQ',
        'PSQURTV',
        'PURVTSQ',
        'RPUQTSV',
      ]
      
      nr_criminals = len(ans[0])
      nr_answers = len(ans)
      
      # make list of used values
      lst = [set(a[i] for a in ans) for i in range(nr_criminals)]
      
      for ss in solve(lst):
        pos = set(correct(xs, ss) for xs in ans)
        if len(pos) != nr_answers: continue
        
        print(f"{', '.join(ss)} --> {pos}")
      

      Like

      • Jim Randell 2:57 pm on 15 October 2021 Permalink | Reply

        You can use the following to turn a collection of rows into the corresponding collection of columns:

        cols = zip(*rows)
        

        (And [[ unzip() ]] is an alias for this in enigma.py).

        We can also simplify the way the [[ solve() ]] function operates. (I’ve renamed it [[ select() ]]).

        from enigma import unzip, seq_all_different, join, printf
        
        # the six answers
        ans = [
          'PQRSTUV',
          'PQRUTSV',
          'PSUVRTQ',
          'PSQURTV',
          'PURVTSQ',
          'RPUQTSV',
        ]
        
        # select distinct elements from each set in list of sets <ss>
        def select(ss, rs=[]):
          # are we done?
          if not ss:
            yield rs
          else:
            for x in ss[0].difference(rs):
              yield from select(ss[1:], rs + [x])
        
        # count number of items in correct position
        correct = lambda xs, ys: sum(x == y for (x, y) in zip(xs, ys))
        
        # each photograph was identified correctly in at least one answer
        # so the the correct value occurs in each column
        
        # consider possible correct orderings
        for ss in select(list(set(col) for col in unzip(ans))):
          # how many are in the correct position?
          pos = list(correct(xs, ss) for xs in ans)
          if not seq_all_different(pos): continue
          # output solution
          printf("{ss} -> {pos}", ss=join(ss, sep=" ", enc="()"))
        

        I did try a version of [[ select() ]] that chooses from the column with the smallest number of values available, but it is no advantage on a problem of this size.

        Like

  • Jim Randell 9:16 am on 7 October 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 851: Hay fever foiled 

    From The Sunday Times, 6th November 1977 [link]

    Our garden has paths as shown in the plan above. At each junction of paths there is a different variety of plant. The shortest walk (along the paths) from the Marigold to the Sneezewort passes only the Tickseed, and the shortest walk from the Nasturtium to the Quitch passes two plants, one of which is the Lobelia.

    My wife suffers from hay fever and so she never walks past the irritating Rosemary, Sneezewort or Tickseed. We are still able to walk together on the shortest route from the Polyanthus to the Nasturtium (past one other plant), but she has to walk over twice as far as in going from the Orpine to the Marigold.

    List the plants, in order, which my wife passes when taking her shortest route from the Nasturtium to the Marigold.

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser851]

     
    • Jim Randell 9:17 am on 7 October 2021 Permalink | Reply

      This Python program runs in 144ms.

      Run: [ @replit ]

      from enigma import (empty, Accumulator, ordered, tuples, SubstitutedExpression, irange, translate, join, cached, printf)
      
      # adjacency matrix
      adj = [
        [1, 3, 4], # 0
        [0, 2, 5], # 1
        [1, 3, 6], # 2
        [0, 2, 7], # 3
        [0, 5, 7, 8], # 4
        [1, 4, 6, 8], # 5
        [2, 5, 7, 8], # 6
        [3, 4, 6, 8], # 7
        [4, 5, 6, 7], # 8
      ]
      
      # distances for each edge
      dist = {
        (0, 1): 314, (1, 2): 314, (2, 3): 314, (0, 3): 314, # = 100 pi
        (0, 4): 100, (1, 5): 100, (2, 6): 100, (3, 7): 100,
        (4, 5): 157, (5, 6): 157, (6, 7): 157, (4, 7): 157, # = 50 pi
        (4, 8): 100, (5, 8): 100, (6, 8): 100, (7, 8): 100,
      }
      
      # find paths from A to B, avoiding Xs
      def paths(A, B, Xs=empty, s=[]):
        if A == B:
          yield s
        else:
          # move forward from A
          for x in adj[A]:
            if x not in s and x not in Xs:
              yield from paths(x, B, Xs, s + [x])
      
      # find minimal distance paths
      @cached
      def min_path(A, B, Xs=empty):
        r = Accumulator(fn=min, collect=1)
        for s in paths(A, B, Xs, [A]):
          d = sum(dist[ordered(x, y)] for (x, y) in tuples(s, 2))
          r.accumulate_data(d, s)
        return r
      
      # is there a minimal path with n intermediates, that include incs?
      def check(A, B, Xs, n=None, incs=[]):
        incs = set(incs)
        r = min_path(A, B, frozenset(Xs))
        for p in r.data:
          if len(p) == n + 2 and incs.issubset(p): return True
        return False
      
      # check distance avoiding Xs is over twice as far
      def check2(A, B, Xs):
        r1 = min_path(A, B)
        r2 = min_path(A, B, frozenset(Xs))
        return (r2.value > 2 * r1.value)
      
      # make a solver
      p = SubstitutedExpression(
        [
          # M -> S passes only T
          "check(M, S, [], 1, [T])",
          # N -> Q passes L and 1 other
          "check(N, Q, [], 2, [L])",
          # P -> N passes 1 other plant
          "check(P, N, [R, S, T], 1)",
          # but she has to walk over twice as far going from O -> M
          "check2(O, M, [R, S, T])",
        ],
        digits=irange(0, 8),
        env=dict(check=check, check2=check2),
        verbose=0,
      )
      
      # run the solver
      for s in p.solve():
        # map positions to symbols
        m = dict((v, k) for (k, v) in s.items())
        # remove duplicate layouts
        if not (m[1] < m[3] and m[0] < min(m[1], m[2], m[3])): continue
      
        # output solution: (outer) (inner) (centre) -> wife's path from N to M
        printf("{m}", m=translate("({0} {1} {2} {3}) ({4} {5} {6} {7}) ({8})", (lambda x: m[int(x)])))
        r = min_path(s['N'], s['M'], frozenset([s['R'], s['S'], s['T']]))
        for p in r.data:
          printf("-> {p}", p=join((m[x] for x in p), sep=" "))
        printf()
      

      Solution: The plants passed are: Orpine, Polyanthus, Quitch.


      Here is a layout of the plants (reflections/rotations of this layout also work), with the wife’s best route from N to M indicated:

      Like

      • Frits 11:39 am on 7 October 2021 Permalink | Reply

        @Jim, I would say there is no solution as normally “twice as far” would mean twice the distance, not at least twice the distance.

        Like

        • Jim Randell 11:50 am on 7 October 2021 Permalink | Reply

          @Frits: the puzzle text says “she has to walk over twice as far”, so the wife has to travel more than twice the distance of the shortest path.

          Like

  • Jim Randell 10:04 am on 30 September 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 869: New type football 

    From The Sunday Times, 19th March 1978 [link]

    In this puzzle four football teams are going to play each other once during the course of the season. The incomplete table below shows the situation when some of the matches have been played (2 points for a win, 1 for a draw as usual).

    The digits have been replaced by letters and each letter stands for the same digit wherever it appears and different letters stand for different digits.

    The table looks like this:

    List the matches played and the score in each match.

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser869]

     
    • Jim Randell 10:04 am on 30 September 2021 Permalink | Reply

      We know the goals for/against values for A and B, so we can calculate scores for matches involving A or B, which only leaves the score in the C vs D match to be decided, and as the overall goals for C is t, we can calculate potential scores for C in the match. If the match is a draw, then D’s score is the same as C’s. If it is a win for C, then D scored fewer goals. And if it is a win for D, then D scored more goals. I put an upper limit on the number of goals in this last case, but it is not a situation that is reached.

      This Python program uses the [[ Football() ]] helper class from the enigma.py library. It runs in 54ms.

      Run: [ @replit ]

      from enigma import Football, irange
      
      # scoring system
      football = Football(points=dict(w=2, d=1))
      
      # the table
      table = dict(played='x?pk', w='?hx?', l='??h?', d='k?k?', points='??m?')
      (gf, ga) = ('hmt?', 'pm??')
      
      # label the teams
      (A, B, C, D) = (0, 1, 2, 3)
      
      # find match outcomes
      for (ms, d) in football.substituted_table(table):
      
        # calculate scores for games involving A and B
        for ss in football.substituted_table_goals(gf, ga, ms, d=d, teams=[A, B]):
      
          # only the C vs D match is undecided
          sCD = list()
          m = ms[(C, D)]
          if m == 'x':
            sCD = [None]
          else:
            # calculate known goals for/against C
            (f, a) = football.goals([ss[(A, C)], ss[(B, C)]], [1, 1])
            # so the score in the C vs D match is (x, y)
            for x in irange(0, 9 - f):
              t = f + x
              if t in d.values(): continue
              if m == 'd':
                sCD.append((x, x))
              elif m == 'w':
                sCD.extend((x, y) for y in irange(0, x - 1))
              elif m == 'l':
                sCD.extend((x, y) for y in irange(x + 1, 10))  # upper limit on goals scored
      
          for ss[(C, D)] in sCD:
            # output solution
            football.output_matches(ms, ss, teams="ABCD", d=d)
      

      Solution: The played matches are: A vs B = 0-0; A vs C = 0-3; B vs C = 5-5; C vs D = 1-0.

      The A vs D, B vs D matches are not yet played.

      Like

  • Jim Randell 8:11 am on 23 September 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 855: Pity the poor postman 

    From The Sunday Times, 4th December 1977 [link]

    Extract (genuine!) from a national daily, 27th January 1977:

    Pity the poor postman trying to deliver letters along Stonebow Road in the village of Drake’s Broughton, in north-west England. Due to local government confusion the road boasts five houses with the number 1, four others are number 2, three have number 4, and two are numbered 6.

    To add to the postman’s woes there are four families called Davies in Stonebow Road, plus two named Bridges, three named Barker, and two named Webb.

    On the unwarranted supposition that:

    (i) the occupants of the said houses included all of the said families; but
    (ii) the postman’s problem was somewhat alleviated by the fact that no two families of the same name had the same house-number; and
    (iii) the house-numbers of the Webbs totalled to more than did those of the Bridges, while those of all the families with two of the four names totalled the  same as did those of all the families with the other two names.

    What were the house-numbers of the Barkers and Webbs respectively?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser855]

     
    • Jim Randell 8:11 am on 23 September 2021 Permalink | Reply

      This Python program runs in 49ms.

      Run: [ @replit ]

      from enigma import multiset, subsets, partitions, printf
      
      # the pool of house numbers
      ns = multiset.from_pairs([(1, 5), (2, 4), (4, 3), (6, 2)])
      
      # choose 2 house numbers for the Bridges
      for Brs in subsets(ns.keys(), size=2):
        sBrs = sum(Brs)
      
        # choose 2 house number for the Webbs
        ns1 = ns.difference(Brs)
        for Ws in subsets(ns1.keys(), size=2):
          sWs = sum(Ws)
          if not(sWs > sBrs): continue
      
          # choose 4 numbers for the Davies
          ns2 = ns1.difference(Ws)
          for Ds in subsets(ns2.keys(), size=4):
            sDs = sum(Ds)
      
            # choose 3 numbers for the Barkers
            ns3 = ns2.difference(Ds)
            for Bas in subsets(ns3.keys(), size=3):
              sBas = sum(Bas)
      
              # consider partitions of the sums ...
              for (p1, p2) in partitions([sBrs, sWs, sDs, sBas], 2):
                # that give the same total
                if sum(p1) == sum(p2):
                  printf("Bridges = {Brs}; Webbs = {Ws}; Davies = {Ds}; Barkers = {Bas} [{p1}, {p2}]")
      

      Solution: The Barkers are at 1, 4, 6. The Webbs are at 1, 4.

      And the total sum of their numbers is 16.

      The Davies are at 1, 2, 4, 6, and The Bridges are at 1, 2.

      The total sum of their numbers is also 16.

      There are house numbers 1, 2, 2 remaining.

      Like

  • Jim Randell 9:48 am on 9 September 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 859: Sick transit 

    From The Sunday Times, 8th January 1978 [link]

    The State of Inertia, in a last-ditch effort to revive an ailing economy, has decided to go ahead with the controversial innovation of adding two new digits

    POW! (Written ↑)
    WHAM! (Written ↓)

    thus symbolising the stark alternatives facing the nation.

    In a massive referendum on the relative merits, the country came down in favour of POW! carrying the greater weight and accordingly WHAM! is interposed in a lower position than POW! among the ten old digits, the usual order of which is retained.

    Teething troubles from the consequential change to duodecimal-based arithmetic and to the new values of some of the old digits, are minimised by the free provision to everyone of school-age or over of PEST, an appropriate Pocket Electronic Summary Tabulator.

    To enable a check to be made on the correct working of the instruments every PEST comes with the answers to 35 × 64 and 54 × 66, one consisting entirely of the new shapes and the other of neither of them.

    What are the two answers ?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser859]

     
    • Jim Randell 9:49 am on 9 September 2021 Permalink | Reply

      Using P for “POW!” and W for “WHAM!”:

      If we interpret “interposed” to mean that P and W are inserted between 2 existing symbols, then we find a unique solution.

      The following Python program runs in 51ms.

      Run: [ @replit ]

      from enigma import subsets, irange, base2int, int2base, join, printf
      
      # categorise a string
      # 'new' -> entirely composed of new symbols
      # 'old' -> entirely composed of old symbols
      # 'mix' -> a mixture of new and old symbols
      def categorise(s):
        s = set(s)
        assert bool(s)
        if s.issubset('PW'): return 'new'
        if not s.intersection('PW'): return 'old'
        return 'mix'
      
      # make possible base 12 symbol sets
      for (w, p) in subsets(irange(1, 9), size=2):
        syms = list("0123456789")
        syms.insert(p, 'P')
        syms.insert(w, 'W')
      
        # convert between strings and numbers
        s2n = lambda s: base2int(s, base=12, digits=syms)
        n2s = lambda n: int2base(n, base=12, digits=syms)
      
        # calculate: A = '35' * '64', B = '54' * '66'
        A = n2s(s2n('35') * s2n('64'))
        B = n2s(s2n('54') * s2n('66'))
        # one is entirely composed of new symbols and one entirely composed of old
        if set(map(categorise, (A, B))) == {'old', 'new'}:    
          printf("digits 0-11 = {syms}", syms=join(syms))
          printf("  35 * 64 = {A}; 54 * 66 = {B}")
      

      Solution: The two sums are: 35 × 64 = 2445 and 54 × 66 = ↓↑↑↓.

      The digits from 0 to 11 are represented by:

      0 1 2 3 W 4 5 P 6 7 8 9

      So the sums are:

      35 × 64 = 2445 [Inertial base 12]
      36 × 85 = 2556 [standard base 12]
      42 × 101 = 4242 [standard decimal]

      54 × 66 = WPPW [Inertial base 12]
      65 × 88 = 4774 [standard base 12]
      77 × 104 = 8008 [standard decimal]

      However, if we allow W and P to be inserted anywhere (but still with W before P), we find an additional solution using the following digits:

      W 0 1 2 3 P 4 5 6 7 8 9

      And the sums are:

      35 × 64 = 2194 [Inertial base 12]
      47 × 86 = 32B6 [standard base 12]
      55 × 102 = 5610 [standard decimal]

      54 × 66 = PPWW [Inertial base 12]
      76 × 88 = 5500 [standard base 12]
      90 × 104 = 9360 [standard decimal]

      We can see this additional solution by using the following call to [[ subsets() ]] in line 15:

      subsets(irange(0, 10), size=2, select='R')
      

      Like

  • Jim Randell 10:03 am on 2 September 2021 Permalink | Reply
    Tags: by: Gerald Fitzgibbon   

    Brain-Teaser 848: The magic class 

    From The Sunday Times, 16th October 1977 [link]

    The class only had nine pupils.

    Three girls sat in the front row, three boys in the back one, while in the middle rows the sexes sat alternately.

    Altogether, including the teacher, the sexes were equally divided.

    When their home-work was returned marks were compared and the children were surprised to discover that the total marks gained by those in each row were the same, as were also those for each column from front to back and for each diagonal of the square in which they sat. Excitedly they pointed out that fact to the teacher who replied that, when checking their work, which had been marked out of ten, he noticed that every digit had been used once and once only.

    Three was the lowest mark awarded to a girl.

    What was the highest mark given to a boy?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser848]

     
    • Jim Randell 10:05 am on 2 September 2021 Permalink | Reply

      The possible marks are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. For a set of nine of them to use all ten digits requires 10 to be used, which means 0 and 1 cannot be used, so the marks are 2-10.

      These marks sum to 54, so the magic constant is 18, and the central square must be 6.

      The teacher is revealed to be male so the layout must be (front to back): (f f f) (f m f) (m m m).

      The following run file executes in 70ms.

      Run: [ @replit ]

      #! python3 -m enigma -r
      
      #  A B C     m m m <- back
      #  D E F  =  f m f
      #  G H I     f f f <- front
      
      SubstitutedExpression
      
      --base=11
      --digits=2-10
      
      # all rows, columns, diagonals sum to 18
      "A + B + C == 18"
      "D + E + F == 18"
      "G + H + I == 18"
      "A + D + G == 18"
      "B + E + H == 18"
      "C + F + I == 18"
      "A + E + I == 18"
      "C + E + G == 18"
      
      # lowest female mark is 3
      "min(D, F, G, H, I) == 3"
      
      # remove duplicate (left/right) solutions
      "A < C"
      
      # answer is the highest male mark
      --answer="max(A, B, C, E)"
      
      # [optional]
      --template="(A B C) (D E F) (G H I)"
      --solution=""
      

      Solution: 9 was the highest mark awarded to a boy.

      The layout looks like this (or reflected about a vertical axis):

      Like

    • GeoffR 4:08 pm on 2 September 2021 Permalink | Reply

      # Using the same integer (A - I) and m/f references
      
      from itertools import permutations
      for p1 in permutations(range(2, 11)):
        A, B, C, D, E, F, G, H, I = p1
        if (A + B + C == D + E + F == G + H + I
          == A + D + G == B + E + H == C + F + I
          == A + E + I == C + E + G):
          if min(D, F, G, H, I) == 3: #lowest girl mark
            HBM = max(A, B, C, E)  # highest boy mark
            print('All Marks ( A to I): ', A, B, C, D, E, F, G, H, I)
            print('Highest Boy Mark: ', HBM)
      
      # All Marks ( A to I):  7 2 9 8 6 4 3 10 5
      # Highest Boy Mark:  9
      # All Marks ( A to  I):  9 2 7 4 6 8 5 10 3
      # Highest Boy Mark:  9
      
      
      

      Like

    • Frits 4:06 pm on 3 September 2021 Permalink | Reply

      The magic constant is 18, and the central square must be 6.

      All corners can’t be even as using odd marks for all the sides would make odd total marks.
      Only two opposite corners can’t be even as then the other 2 corners would have to be odd.
      To make total even marks we would need odd marks for all the sides as well.
      So all corners must be odd and all sides even.
      As 3 is in a bottom corner 9 must be in a top corner (male).
      The 10 mark must be adjacent to the 3 mark and thus female.

      So we can conclude that the highest mark given to a boy is a 9.

      Like

  • Jim Randell 9:54 am on 26 August 2021 Permalink | Reply
    Tags:   

    Brain-Teaser 840: Cake mix variations 

    From The Sunday Times, 21st August 1977 [link]

    A small party was held to promote a brand of Cake Mix. There were five varieties of cake, five beverages, and five sorts of savouries offered.

    I asked a sample group of five what they had chosen, and learned that each had had a different drink, a different slice of cake and two savouries.

    No one had picked the same two savouries as any other, and no more than two people had the same savoury.

    No one had cake of the same flavour as her beverage (tea being paired with plain sponge in this case).

    Dot told me that she had no coffee in any form, no cheese and no egg, but she did have a sausage roll and one thing with orange flavour.

    Eve had lemon drink, but no egg, and said that the one who had both egg and cheese did not drink coffee, but the tea drinker had cheese nibbles.

    Fran said the one who drank chocolate had lemon cake. Fran had shrimp vol-au-vent, and only one of the shrimp eaters had lemon in either form.

    Gill had a sausage roll and one orange item, and said that the one who had cheese had chocolate cake.

    Helen told me that the one who had coffee cake had a ham sandwich, but no cheese, and no one had stuffed egg as well as shrimp.

    Who had the ham sandwiches ?

    This puzzle was included in the book The Sunday Times Book of Brain-Teasers: Book 1 (1980, edited by Victor Bryant and Ronald Postill). The puzzle text above is taken from the book.

    [teaser840]

     
    • Jim Randell 9:55 am on 26 August 2021 Permalink | Reply

      Here is a solution using the [[ SubstitutedExpression ]] solver from the enigma.py library.

      It runs in 81ms.

      Run: [ @replit ]

      #!/usr/bin/env python3 -m enigma -r
      
      # assign values to the names:
      #   Dot = 1; Eve = 2; Fran = 3; Gill = 4; Helen = 5
      #
      # and then assign these values to the comestibles:
      #   cakes: sponge = A; coffee = B; orange = C; lemon = D; chocolate = E
      #   drinks: tea = F; coffee = G; orange = H; lemon = I; chocolate = J
      #   savouries: cheese = K & L; egg = M & N; s roll = P & Q; shrimp = R & S; ham s = T & U
      
      SubstitutedExpression
      
      --digits="1-5"
      --distinct="ABCDE,FGHIJ,KMPRT,LNQSU,AF,BG,CH,DI,EJ,KL,MN,PQ,RS,TU"
      
      # remove duplicate solutions
      "T < U"
      
      # "Dot has no coffee, no cheese, no egg"
      "B != 1"
      "G != 1"
      "K != 1"
      "L != 1"
      "M != 1"
      "N != 1"
      
      # "Dot has a sausage roll, and something orange"
      "P == 1 or Q == 1"
      "C == 1 or H == 1"
      
      # "Eve had lemon drink"
      "I == 2"
      
      # "Eve had no egg"
      "M != 2"
      "N != 2"
      
      # "someone had egg, cheese and not coffee"
      "((M == K or M == L) and G != M) or ((N == K or N == L) and G != N)"
      
      # "tea drinker had cheese"
      "F == K or F == L"
      
      # "hot chocolate had lemon cake"
      "J == D"
      
      # "Fran had shrimp"
      "R == 3 or S == 3"
      
      # "only one shrimp eater also had lemon"
      "(R == D or R == I) + (S == D or S == I) = 1"
      
      # "Gill had sausage roll and something orange"
      "P == 4 or Q == 4"
      "C == 4 or H == 4"
      
      # "someone had cheese and chocolate cake"
      "(K == E) or (L == E)"
      
      # "coffee cake had a ham sandwich, but no cheese"
      "B == T or B == U"
      "B != K and B != L"
      
      # "no-one had egg and shrimp"
      "not intersect(([M, N], [R, S]))"
      
      # mention A
      "A > 0"
      
      # [optional]
      --template="(A B C D E) (F G H I J) (K L) (M N) (P Q) (R S) (T U)"
      --solution=""
      --denest=1 # for CPython
      

      Solution: Dot and Eve had the ham sandwiches.

      The full solution is:

      D: Sponge cake; orange juice; sausage roll + ham sandwich
      E: Coffee cake; lemon squash; shrimp + ham sandwich
      F: Chocolate cake; tea; cheese + shrimp
      G: Orange cake; coffee; egg + sausage roll
      H: Lemon cake; hot chocolate; cheese + egg

      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
%d bloggers like this: