Recent Updates Page 12 Toggle Comment Threads | Keyboard Shortcuts

  • Unknown's avatar

    Jim Randell 3:47 am on 6 October 2024 Permalink | Reply
    Tags:   

    Teaser 3237: Oranges and lemons 

    From The Sunday Times, 6th October 2024 [link] [link]

    George and Martha attend a local club where there is a “fruit machine”. There are three dials, each with five “fruits” but here the “fruits” are numbers. On the first dial are the numbers 1-5; on the second there are the numbers 5-9. On the third, 5 appears again but with four two-digit numbers.

    You put £1 in the machine, then pull a handle which spins the dials, and the numbers on the dials appear completely at random. The jackpot payout for three 5s is £52. Otherwise the machine pays £2 if the three displayed numbers sum to a prime total.

    If the machine pays out 80% of its intake on average, what are the lowest possible values for the for the four two-digit numbers?

    Note: Although not explicitly stated, the intention for this puzzle is that the four 2-digit numbers on the third reel are all different.

    [teaser3237]

     
    • Jim Randell's avatar

      Jim Randell 3:58 am on 6 October 2024 Permalink | Reply

      I think the puzzle could be clearer on what constitutes the “lowest possible values”. I went for the values with the smallest sum, but you could go for the smallest maximum value (although in the end both these give the same answer).

      I also assumed that numbers could be repeated on a reel (as the puzzle does not state that they are all different, and it is usual for the reels on a fruit machine to have repeated symbols). However we do get a plausible looking answer with the additional constraint that they are all different.

      (I have opened a discussion topic if you have thoughts on these issues [link]).

      There are 5^3 = 125 possible positions of the reels, each equally likely, so the total take is £125. And if the total payout among all positions is 80% of this, it is £100.

      from enigma import (irange, decompose, primes, cproduct, printf)
      
      primes.expand(113)  # max possible prime
      
      # check a set of reels; return (<total-take>, <total-payout>)
      def check(rs):
        t = w = 0
        for ns in cproduct(rs):
          t += 1
          if ns == (5, 5, 5):
            w += 52
          elif sum(ns) in primes:
            w += 2
        return (t, w)
      
      # the first two reels
      r1 = [1, 2, 3, 4, 5]
      r2 = [5, 6, 7, 8, 9]
      
      # consider total sum of the four 2-digit numbers
      for t in irange(40, 396):
        f = 0
        # construct possible third reels
        for ns in decompose(t, 4, increasing=1, sep=0, min_v=10, max_v=99, fn=list):
          r3 = [5] + ns
          (tot, pay) = check([r1, r2, r3])
          if pay == 100:
            # output solution
            printf("{r3} -> ({tot}, {pay})")
            f += 1
        if f > 0: break
      

      If repeated values are allowed:

      Solution: The 4-digit values with the lowest total are: 14, 14, 14, 14. (total = 56)

      If all values have to be different:

      Solution: The 4-digit values with the lowest total are: 14, 15, 16, 24. (total = 69)

      The second one was the published solution.


      To see the solution to the alternative puzzle where the four 2-digit numbers are all different, you just need to pass [[ sep=1 ]] to [[ decompose() ]] at line 24.

      I think it is likely that this is the answer that the setter was after. [This has now been confirmed].

      Liked by 1 person

    • Frits's avatar

      Frits 4:36 am on 6 October 2024 Permalink | Reply

      from itertools import combinations_with_replacement as cwr, product
      
      # determine suitable primes up to 99+5+9
      P = {3, 5, 7}
      P = {x for x in range(11, 114, 2) if all(x % p for p in P)}
      
      score = lambda seq: 52 if seq == (5, 5, 5) else (2 * (sum(seq) in P))
      
      d1 = range(1, 6)
      d2 = range(5, 10)
      # select four 2-digit numbers for the third dial
      for n4 in cwr(range(10, 100), 4):
        d3 = (5, ) + n4
        # play 5^3 games with every possible outcome
        # it should pay out 4 * 5^2 pounds (80%)
        if sum(score(p) for p in product(d1, d2, d3)) == 100:
          print("answer:", n4)
          exit() # lowest 
      

      Like

    • ruudvanderham's avatar

      ruudvanderham 1:12 pm on 6 October 2024 Permalink | Reply

      The program below finds all two digit numbers that lead to a payout of 100:

      import itertools
      from istr import istr
      
      
      for d3 in range(10, 100):
          payout = 52
          for d1 in range(1, 6):
              for d2 in range(5, 10):
                  if istr.is_prime(d1 + d2 + d3):
                      payout += 4 * 2
                  if istr.is_prime(d1 + d2 + 5):
                      payout += 2
      
          if payout == 100:
              print(d3, end=" ")
      

      If the digits may be the same, we pick four times the lowest value.
      If the digits have to be different, we pick the four lowest values.

      Like

    • Frits's avatar

      Frits 8:39 am on 7 October 2024 Permalink | Reply

      Using a different interpretation of “lowest possible values”.

      from itertools import product
      
      # determine suitable primes up to 99+5+9
      P = {3, 5, 7}
      P = {x for x in range(11, 114, 2) if all(x % p for p in P)}
      
      payout = lambda seq: 52 if seq == (5, 5, 5) else (2 * (sum(seq) in P))
      
      d1 = range(1, 6)
      d2 = range(5, 10)
      
      n_rng = [5] + list(range(10, 100)) 
      
      # payouts per number on the 3rd dial
      pay = {n: sum(payout(p) for p in product(d1, d2, [n])) for n in n_rng}
      # retrieve the lowest number on the 3rd dial for a specific payout
      low = {v: min([k for k in pay.keys() if pay[k] == v]) for v in pay.values()}
      
      todo = 100 - pay[5] # total expected payout is 0.80 * 5^3
      
      # select four 2-digit numbers for the third dial so the combined payout is
      # equal to <todo>
      n4s = [[low[x] for x in p] for p in product(low, repeat=4) if sum(p) == todo]
      
      # assume “lowest possible values" means minimal sum
      mn = min([sum(n4) for n4 in n4s])
      print("answer:", ' or '.join(str(sorted(n4)) for n4 in n4s if sum(n4) == mn)) 
      

      Like

  • Unknown's avatar

    Jim Randell 9:16 am on 3 October 2024 Permalink | Reply
    Tags:   

    Teaser 2599: Removing a card 

    From The Sunday Times, 15th July 2012 [link] [link]

    I have taken a set of cards and written a different digit on each. Overall I have used a set of consecutive digits. Then I have arranged the cards in some order to make one large number. This number is divisible by the digit that is one more than the number of cards.

    Reading from left to right, if any card is removed then the remaining number is divisible by the position of the card removed. For example, if the card in the sixth position is removed and the remaining cards are pushed together to form another number, then that number is divisible by 6.

    What was the original number?

    [teaser2599]

     
    • Jim Randell's avatar

      Jim Randell 9:16 am on 3 October 2024 Permalink | Reply

      Note that the number formed from the cards “is divisible by the digit that is one more than the number of cards”.

      If there are k cards, then (k + 1) must be a single digit, i.e.:

      k + 1 ≤ 9
      ⇒ k ≤ 8

      And the example given involves removing the 6th card and closing up the gap, hence:

      k > 6
      ⇒ k ≥ 7

      So the only possible values for k are 7 or 8.

      This Python program runs in 228ms. (Internal runtime is 142ms).

      from enigma import (irange, tuples, subsets, nconcat, delete, printf)
      
      # solve the puzzle for digits <ds>
      def solve(ds):
        k = len(ds)
        # divisibility by 3 or 9 does not depend on order
        if (k == 2 or k == 8) and sum(ds) % (k + 1) > 0: return
        # choose an ordering for the digits
        for ss in subsets(ds, size=k, select='P'):
          if ss[0] == 0: continue
          n = nconcat(ss)
          # the number is divisible by one more than the number of digits
          if n % (k + 1) > 0: continue
          # if the digit at position i is removed, the number formed from
          # the remaining digits is divisible by i
          if any(nconcat(delete(ss, [i - 1])) % i > 0 for i in irange(2, k)): continue
          # output solution
          printf("k={k}: {ds} -> {ss} -> {n}")
      
      digits = list(irange(0, 9))
      
      # the puzzle implies there between 7 and 8 cards
      for k in irange(7, 8):
        # choose k consecutive digits
        for ds in tuples(digits, k):
          solve(ds)
      

      Solution: The original number was: 2435160.


      If we allow the full range numbers of cards (2 to 9) there are the following solutions:

      k=2: 21, 45, 87
      k=3: 120, 456, 576, 756, 876
      k=5: 14352, 41352, 47658, 74658, 78654, 87654
      k=6: 513240
      k=7: 2435160
      k=9: 143756820, 156473280, 173856420, 176583240, 253716840, 273156480, 453716820, 476513280, 513276840, 516783240, 543176820, 573126840, 573416820, 586713240, 713526480, 716543280, 743516820, 746153280, 753216480, 756183240, 756813240, 873156420, 876513240

      Note that beyond k=2 the numbers are even (as removing the 2nd digit must result in a number divisible by 2, and so the final digit must be even).

      And beyond k=5 the numbers end in 0 (as removing the 5th digit must result in a number divisible by 5, and so the final digit must be 0). And so the only consecutive sequence of digits is 0..(k − 1).

      This means that for k=8 the set of digits is 0..7, but these digits have a sum of 28, which is not divisible by 9, and so none of the arrangements of digits will be. So there is no possible collection of 8 cards.

      We know then, that the number must be formed from 7 cards, using the digits 0..6.

      The following run file uses these restrictions and divisibility rules on the 7-digit number, and has an internal run time of 275µs.

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # k=7: n = ABCDEFG
      --digits="0-6"
      
      # the number is divisible by 8
      "ABCDEFG % 8 = 0"
      
      # removing the digit at position i gives a number divisible by (i + 1)
      "ACDEFG % 2 = 0"
      "ABDEFG % 3 = 0"
      "ABCEFG % 4 = 0"
      "ABCDFG % 5 = 0"
      "ABCDEG % 6 = 0"
      "ABCDEF % 7 = 0"
      
      # additionally ...
      # G must be 0
      --assign="G,0"
      # ABDEFG is divisible by 3 -> C is divisible by 3
      --invalid="1|2|4|5,C"
      # ABCEFG is divisible by 4 -> F is divisible by 2
      --invalid="1|3|5,F"
      
      --answer="ABCDEFG"
      

      Like

  • Unknown's avatar

    Jim Randell 11:18 am on 1 October 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 545: Gold Cup 

    From The Sunday Times, 5th December 1971 [link]

    Although 42 horses (numbered 1 to 42) were originally entered for the Teaser Gold Cup, only 38 took part in the race.

    The number of the horse which came second in the race exceeded the number of the winner by the same number as that by which the number of the third horse exceeded the number of the second.

    When the numbers of the 4 non-runners were placed in numerical order, the difference between each number and the next was the same in every case, and that difference was the same as the difference between the number of the horse which won the race and the number of the horse which came second.

    The sum of the numbers of the highest and lowest of the four non-runners was equal to the sum of the numbers of the horses which came first, second, and third.

    One of the first three horses was numbered 15. Horses numbered 24 and 28 fell at the third fence, and were not remounted.

    What were the numbers of the 4 non-runners?

    [teaser545]

     
    • Jim Randell's avatar

      Jim Randell 11:18 am on 1 October 2024 Permalink | Reply

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

      It runs in 90ms. (Internal runtime of the generated program is 12ms).

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # suppose the first three horses are: A, B, C (ordered by number)
      # and the four non-runners are: W, X, Y, Z (ordered by number)
      
      --base=43
      --digits="1-42"
      --distinct="ABCWXYZ"
      --invalid="24|28,ABCWXYZ"
      
      # A, B, C are ordered by number
      "A < B" "B < C"
      # and form an arithmetic progression (common diff = D)
      "B - A = D"
      "C - B = D"
      # one of them is 15
      "15 in {A, B, C}"
      
      # W, X, Y, Z are ordered by number
      "W < X" "X < Y" "Y < Z"
      # and form an arithmetic progression (common diff = D)
      "X - W = D"
      "Y - X = D"
      "Z - Y = D"
      
      # equal sums
      "W + Z == A + B + C"
      
      --template=""
      

      Solution: The 4 non-runners were: 12, 19, 26, 33.

      Which forms an arithmetic progression with common difference of 7.

      The horses in the first 3 places were: 8, 15, 22.

      Which also form an arithmetic progression with a common difference of 7.

      The sum of the numbers of the first 3 horses is 8 + 15 + 22 = 45, the same as the sum of the highest and lowest numbered non-runners 12 + 33 = 45.

      Like

      • Ruud's avatar

        Ruud 4:36 pm on 1 October 2024 Permalink | Reply

        import itertools
        
        
        for non_runners in itertools.combinations(set(range(1, 43)) - {15, 24, 28}, 4):
            if (diff := non_runners[1] - non_runners[0]) == non_runners[2] - non_runners[1] == non_runners[2] - non_runners[1] == non_runners[3] - non_runners[2]:
                runners123 = set(range(1, 43)) - set(non_runners) - {24, 28}
                for first in runners123:
                    second = first + diff
                    third = second + diff
                    if second in runners123 and third in runners123 and 15 in {first, second, third} and first + second + third == non_runners[0] + non_runners[3]:
                        print(f"{non_runners=} {first=} {second=} {third=}")
        

        , which prints:

        non_runners=(12, 19, 26, 33) first=8 second=15 third=22
        

        Like

    • GeoffR's avatar

      GeoffR 7:23 pm on 1 October 2024 Permalink | Reply

      
      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      var 1..42:NR1; var 1..42:NR2; var 1..42:NR3; var 1..42:NR4;
      var 1..42:W1; var 1..42:W2; var 1..42:W3;
      
      constraint all_different ([NR1, NR2, NR3, NR4, W1, W2, W3]);
      
      constraint W2 - W1 == W3 - W2;
      
      constraint  NR1 < NR2 /\ NR2 < NR3 /\ NR3 < NR4;
      
      constraint NR2 - NR1 == NR3 - NR2 /\ NR3 - NR2 == NR4 - NR3;
      
      constraint NR2 - NR1 == W2 - W1;
      
      constraint NR1 + NR4 == W1 + W2 + W3;
      
      constraint sum ([W1 == 15, W2 == 15, W3 == 15]) == 1;
      
      var set of int: horses = {NR1, NR2, NR3, NR4, W1, W2, W3};
      
      constraint card ({24, 28} intersect horses) == 0;
      
      solve satisfy;
      
      output ["Numbers of non-runners = " ++ show([NR1, NR2, NR3, NR4]) ++
      "\nWinning numbers = " ++ show([W1, W2, W3]) ];
      
      % Numbers of non-runners = [12, 19, 26, 33]
      % Winning numbers = [8, 15, 22]
      % ----------
      % ==========
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 2:14 am on 29 September 2024 Permalink | Reply
    Tags:   

    Teaser 3236: A fair start 

    From The Sunday Times, 29th September 2024 [link] [link]

    We did well selling plants on our charity stall this year: £70 was taken in the first hour. The plants were priced at £1, £2, £3, £4 and £5 but all purchases were made from just three of those categories. All the customers spent different amounts and all bought three items, but no-one bought three items at the same price. Last year the Vicar spent £14 but so far this year no-one has exceeded or even matched that amount. In fact the Vicar was the first customer and spent the average amount in that first hour.

    What, in ascending order, were the prices of the items that the Vicar bought?

    News: I am experimenting with GitHub Discussions to host discussions that are not directly related to the solutions of individual puzzles. Feel free to join in.

    [teaser3236]

     
    • Jim Randell's avatar

      Jim Randell 2:48 am on 29 September 2024 Permalink | Reply

      This Python program runs in 68ms. (Internal runtime is 1.8ms).

      from enigma import (divisors_pairs, subsets, multiset, cproduct, decompose, printf)
      
      # possible denominations
      dss = subsets([1, 2, 3, 4, 5], size=3)
      # possible number of people = n, average spend = a
      nas = ((n, a) for (n, a) in divisors_pairs(70, every=1) if a < 14)
      
      # consider possible (denominations, (people, average)) values
      for (ds, (n, a)) in cproduct([dss, nas]):
      
        # the vicar spent the average amount
        m = multiset.from_seq(ds, count=2)
        for vs in m.express(a, k=3):
      
          # and the rest spent different amounts (less than 14)
          for rs in decompose(70 - a, n - 1, increasing=1, sep=1, min_v=4, max_v=13):
            if a in rs: continue
            # check each amount can be made
            if not m.expressible(rs, k=3): continue
            # output solution
            printf("n={n}: a={a} ds={ds} rs={rs} -> vicar = {vs}", vs=list(vs.sorted()))
      

      Solution: The vicar bought items priced: £2, £3, £5.

      So the vicar spent £10, which is the mean amount among 7 people spending £70.

      The others spent: £7, £8, £9, £11, £12, £13, which brings the total spend to £70.

      We can actually break down each purchase:

      £7 = £2 + £2 + £3
      £8 = £2 + £3 + £3
      £9 = £2 + £2 + £5
      £10 = £2 + £3 + £5 [vicar; mean]
      £11 = £3 + £3 + £5
      £12 = £2 + £5 + £5
      £13 = £3 + £5 + £5
      total = £70

      Like

    • Frits's avatar

      Frits 5:05 am on 30 September 2024 Permalink | Reply

      from itertools import product, combinations
      
      # combinations of three different prices
      prices = list(combinations(range(1, 6), 3))
      # possible price distributions
      dist = set(p for p in product(range(3), repeat=3) if sum(p) == 3)
      
      # choose number of customers
      for n in range(len(dist), 0, -1):
        avg, r = divmod(70, n)
        if avg >= 14: break
        if r: continue
        
        # choose three different prices
        for ps in prices:
          # choose <n> price distributions 
          for ds in combinations(dist, n):
            spent_amnts = {sum(x * y for x, y in zip(ps, d)) for d in ds}
            # sum spent amounts is 70 and the average must be present
            if avg not in spent_amnts or sum(spent_amnts) != 70: continue
            # all different amounts and less than the Vicar spent last year
            if len(spent_amnts) != n or max(spent_amnts) >= 14: continue
            # price distributions of the items that the Vicar bought
            v_dist = [d for d in ds if sum(x * y for x, y in zip(ps, d)) == avg][0]
            v_amnts = [[ps[i]] * v_dist[i] for i in range(3) if v_dist[i]]
            print("answer:", [y for x in v_amnts for y in x])
      

      Like

  • Unknown's avatar

    Jim Randell 9:19 am on 27 September 2024 Permalink | Reply
    Tags:   

    Teaser 2606: Cue for a queue 

    From The Sunday Times, 2nd September 2012 [link] [link]

    Alan, Brian, Colin, Dave and Ed have surnames Smith, Jones, Rogers, Mason and Hall, but not in that order. They form themselves into a queue. Brian is somewhere ahead of Mr Smith who is somewhere ahead of Ed. Similarly, Mr Jones is ahead of Colin who is ahead of Dave who is ahead of Mr Hall. Mr Mason’s two neighbours in the queue are Alan and Mr Rogers.

    If I told you Alan’s surname it would now be possible to work our all their surnames and their positions in the queue.

    What is Alan’s surname and what is his position in the queue?

    [teaser2606]

     
    • Jim Randell's avatar

      Jim Randell 9:20 am on 27 September 2024 Permalink | Reply

      I used the [[ SubstitutedExpression ]] solver from the enigma.py library to assign positions 1-5 in the queue to the forenames and surnames, such that the required conditions are met.

      We can then use the [[ filter_unique() ]] function to select solutions from the viable assignments, such that knowing Alan’s surname gives a single solution for all names.

      The following Python program runs in 89ms. (Internal runtime is 5.8ms).

      from enigma import (SubstitutedExpression, trim, filter_unique, update, peek, join, printf)
      
      # generate possible queues
      def queues():
        # allocate positions 1-5 in the queue to:
        #
        #  Alan = A; Brian = B; Colin = C; Dave = D; Ed = E
        #  Smith = S; Jones = J; Rogers = R; Mason = M; Hall = H
        #
        p = SubstitutedExpression(
          [
            # the surnames are not given in the correct order
            "A != S or B != J or C != R or D != M or E != H",
            # B is ahead of S, who is ahead of E
            "B < S", "S < E",
            # J is ahead of C, who is ahead of D, who is ahead of H
            "J < C", "C < D", "D < H",
            # M's neighbours (on different sides) are A and R
            "abs(A - R) = 2", "abs(A - M) = 1", "abs(R - M) = 1",
          ],
          base=6,
          digits=[1, 2, 3, 4, 5],
          distinct=["ABCDE", "SJRMH"],
        )
      
        # solve the puzzle
        for s in p.solve(verbose=0):
          # assemble the queue
          q = ["??"] * 6
          for k in "ABCDE": q[s[k]] = update(q[s[k]], [0], k)
          for k in "SJRMH": q[s[k]] = update(q[s[k]], [1], k)
          # return the queue
          yield trim(q, head=1)
      
      # knowing A's surname gives a unique solution
      f = (lambda q: peek(x for x in q if x[0] == 'A'))
      for q in filter_unique(queues(), f).unique:
        printf("{q}", q=join(q, sep=" "))
      

      Solution: Alan Smith is second in the queue.

      The queue is as follows:

      1st = Brian Jones
      2nd = Alan Smith
      3rd = Colin Mason
      4th = Dave Rogers
      5th = Ed Hall

      There are 5 candidate solutions:

      BJ, AS, CM, DR, EH
      BJ, CS, ER, DM, AH
      BJ, CS, DR, EM, AH
      AJ, BM, CR, DS, EH
      AJ, CM, BR, DS, EH

      The first of these is unique for AS. The next two both have AH, and the final two have AJ.

      Like

      • ruudvanderham's avatar

        ruudvanderham 5:39 pm on 27 September 2024 Permalink | Reply

        import itertools
        
        for firstnames, lastnames in zip(itertools.repeat("Alan Brian Colin Dave Ed".split()), itertools.permutations("Smith Jones Rogers Mason Hall".split(), r=5)):
            for positions in itertools.permutations(range(1, 6)):
                position = {firstname: position for firstname, position in zip(firstnames, positions)}
                position.update({lastname: position for lastname, position in zip(lastnames, positions)})
                if position["Brian"] < position["Smith"] < position["Ed"]:
                    if position["Jones"] < position["Colin"] < position["Dave"] < position["Hall"]:
                        if {position["Mason"] - position["Alan"], position["Mason"] - position["Rogers"]} == {-1, 1}:
                            if list(lastnames) != "Smith Jones Rogers Mason Hall".split():
                                for firstname, lastname in zip(firstnames, lastnames):
                                    print(f"{firstname+ " "+lastname:12} {position[firstname]}  ", end="")
                                print()
        

        This prints:

        Alan Smith   2  Brian Jones  1  Colin Mason  3  Dave Rogers  4  Ed Hall      5  
        Alan Jones   1  Brian Rogers 3  Colin Mason  2  Dave Smith   4  Ed Hall      5
        Alan Jones   1  Brian Mason  2  Colin Rogers 3  Dave Smith   4  Ed Hall      5
        Alan Hall    5  Brian Jones  1  Colin Smith  2  Dave Rogers  3  Ed Mason     4  
        Alan Hall    5  Brian Jones  1  Colin Smith  2  Dave Mason   4  Ed Rogers    3
        

        So, it has to be Alan Smith (the others are not unique) and he is in second position.

        Like

  • Unknown's avatar

    Jim Randell 10:03 am on 24 September 2024 Permalink | Reply
    Tags:   

    Brain-Teaser 231: Holidays abroad 

    From The Sunday Times, 26th September 1965 [link]

    My old friends Alf, Bert, Charlie, Duggie and Ernie went with their wives for holidays abroad last year, to Andorra, Boulogne, Calais, Dunkirk and Ethiopia. I knew that the names of the five wives were Agnes, Beatrice, Clarissa, Daphne and Ethel, but the only information I had about who was married to whom was that for each pair the names of the husband, the wife and last year’s holiday destination all began with different letters.

    In conversation with the ladies, Beatrice told me that she was not married to Alf, and that she had heard from Ernie that Charlie went to Dunkirk last year.

    Daphne, however, firmly informed me that Charlie went to Ethiopia and that Beatrice went to Dunkirk. “Unlike some people I could mention”, she added darkly, “Alf always tells the truth”.

    Clarissa said that when her husband was asked whether Ethel was married to Charlie, he replied: “No”. She went on to tell me that Duggie went to Boulogne.

    Of each of these married couples one member always told the truth and the other never did.

    Name each man’s wife and holiday resort.

    This puzzle is included in the book Sunday Times Brain Teasers (1974).

    [teaser231]

     
    • Jim Randell's avatar

      Jim Randell 10:03 am on 24 September 2024 Permalink | Reply

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

      I assigned 5 slots (1 – 5), each of which contains one wife, husband, destination and trait (for the wife).

      The following run file fills out the slots. It runs in 77ms. (Internal runtime of the generated code is 631µs).

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # let A = 1, B = 2, C = 3, D = 4, E = 5
      #
      #  slot       : 1 2 3 4 5
      #  wife       : A B C D E
      #  husband    : F G H I J  {Alf, Bert, Charlie, Duggie, Ernie}
      #  destination: K L M N P  {Andorra, Boulogne, Calais, Dunkirk, Ethiopia}
      #  wife trait : V W X Y Z  {0 = false or 1 = true}
      --base=6
      --distinct="FGHIJ,KLMNP,FK,GL,HM,IN,JP"
      --invalid="0,FGHIJKLMNP"
      --invalid="2|3|4|5,VWXYZ"
      --invalid="1,FK"
      --invalid="2,GL"
      --invalid="3,HM"
      --invalid="4,IN"
      --invalid="5,JP"
      
      --macro="@hs = (F, G, H, I, J)"  # husbands
      --macro="@ds = (K, L, M, N, P)"  # destinations
      --macro="@ts = (V, W, X, Y, Z)"  # traits
      
      # find a slot with value v
      --code="slot = lambda vs, v: vs.index(v)"
      
      # check statements truth value "x" says "y"
      --code="check = lambda x, y: bool(x) == bool(y)"
      
      # Beatrice says (Beatrice is not married to Alf)
      "check(W, G != 1)"
      
      # Beatrice says (Ernie says Charlie went to Dunkirk)
      "check(W, check(@ts[slot(@hs, 5)] ^ 1, @ds[slot(@hs, 3)] == 4))"
      
      # Daphne says (Charlie went to Ethiopia)
      "check(Y, @ds[slot(@hs, 3)] == 5)"
      
      # Daphne says (Beatrice went to Dunkirk)
      "check(Y, L == 4)"
      
      # Daphne says (Alf tells the truth)
      "check(Y, @ts[slot(@hs, 1)] == 0)"
      
      # Clarissa says (her husband says (Ethel is not married to Charlie))
      "check(X, check(X ^ 1, J != 3))"
      
      # Clarissa says (Duggie went to Boulogne)
      "check(X, @ds[slot(@hs, 4)] == 2)"
      
      --template="(F G H I J) (K L M N P) (V W X Y Z)"
      --solution=""
      

      And this following Python program formats the output using the appropriate labels:

      from enigma import (SubstitutedExpression, printf)
      
      p = SubstitutedExpression.from_file("teaser231.run",
        # return (<husbands>, <destinations>, <traits>)
        ["--answer=(@hs, @ds, @ts)"],
      )
      
      make_map = lambda vs: dict(enumerate(vs.split(), start=1))
      husbands = make_map("Alf Bert Charlie Duggie Ernie")
      wives = make_map("Agnes Beatrix Clarissa Daphne Ethel")
      destinations = make_map("Andorra Boulogne Calais Dunkirk Ethiopia")
      traits = { 0: 'False', 1: 'True' }
      
      for ans in p.answers(verbose=0):
        # collect the slots [wife, husband, destination, trait]
        d = dict((k, [v]) for (k, v) in wives.items())
        for (vs, labels) in zip(ans, [husbands, destinations, traits]):
          for (k, v) in enumerate(vs, start=1):
            d[k].append(labels[v])
        # output the slots
        for k in sorted(d.keys(), key=(lambda k: d[k][1])):
          (W, H, D, T) = d[k]
          printf("{H} and {W} ({T}) -> {D}")
        printf()
      

      Solution: Alf and Clarissa → Dunkirk; Bert and Daphne → Ethiopia; Charlie and Ethel → Andorra; Duggie and Agnes → Boulogne; Ernie and Beatrix → Calais

      We know:

      Alf and Clarissa → Dunkirk; (Alf = F; Clarissa = T)
      Bert and Daphne → Ethiopia; (Bert = T, Daphne = F)
      Charlie and Ethel → Andorra
      Duggie and Agnes → Boulogne
      Ernie and Beatrix → Calais (Ernie = F, Beatrix = T)

      We cannot determine the traits for Charlie and Ethel or for Duggie and Agnes.

      Like

      • Frits's avatar

        Frits 11:02 am on 24 September 2024 Permalink | Reply

        @Jim,

        I have a different naming convention for storing Python programs.
        One idea might be to use something like (assuming the filename doesn’t contain periods):

        import os
        
        runfile = os.path.basename(__file__).split(".")[0] + ".run"
        p = SubstitutedExpression.from_file(runfile, [
          # return (<husbands>, <destinations>, <traits>)
          "--answer=(@hs, @ds, @ts)",
        ])
        

        Like

        • Jim Randell's avatar

          Jim Randell 3:28 pm on 26 September 2024 Permalink | Reply

          I’ve added a [[ parsepath() ]] function to enigma.py that can be used to extract the following components of a path:

          {path} = the full path name = "{dir}/{file}"
          {stem} = path without extension = "{dir}/{name}"
          {dir}  = directory containing the file
          {file} = the filename = "{name}{ext}"
          {name} = the filename without extension
          {ext}  = the extension
          

          For example:

          {path} = "/users/jim/puzzles/enigma/enigma123.py"
          {stem} = "/users/jim/puzzles/enigma/enigma123"
          {dir}  = "/users/jim/puzzles/enigma"
          {file} = "enigma123.py"
          {name} = "enigma123"
          {ext}  = ".py"
          

          You can then call this to make a new path name from an existing one.

          For example to make a path in the same directory:

          path = parsepath("{dir}/enigma123.run", __file__)
          

          Or to just replace the extension:

          path = parsepath("{dir}/{name}.run", __file__)
          
          path = parsepath("{stem}.run", __file__)
          

          As an added bonus [[ SubstitutedExpression.from_file() ]] will automatically pass the arguments to [[ parsepath() ]] if a non-string is provided as a path, to save you the bother:

          p = SubstitutedExpression.from_file(["{stem}.run", __file__])
          

          Like

  • Unknown's avatar

    Jim Randell 2:00 am on 22 September 2024 Permalink | Reply
    Tags:   

    Teaser 3235: Dromedary lines 

    From The Sunday Times, 22nd September 2024 [link] [link]

    Zayed must cross the Setare desert to move to his summer camp, which lies 240 miles east, and a smaller whole number of miles north of his winter camp. Both camps are on a grid of wells every 5 miles north and east across the desert.

    His camels can only travel 100 miles before needing to stop for water. Being superstitious, he will only travel a whole number of miles, in a straight line, between wells. Subject to this, he attempts to minimise his journey by travelling to the well, in range, closest to the remaining straight-line route. If more than one well is equally close, he stops at the nearest one.

    During his journey he travels a total of 50 miles due east and 5 miles due north and visits 14 wells between his camps (not including the ones at the camps).

    List in order the length of each of the first five stages.

    [teaser3235]

     
    • Jim Randell's avatar

      Jim Randell 2:37 am on 22 September 2024 Permalink | Reply

      This Python program runs in 676ms. (Internal runtime is 570ms).

      from enigma import (
        Accumulator, irange, cproduct, line_distance,
        ihypot, unpack, call, tuples, printf
      )
      
      # calculate the next step of the journey; return ((x, y), dist)
      def step(x0, y0, x1, y1):
        # find the nearest wells to the line joining (x0, y0) to (x1, y1)
        r = Accumulator(fn=min, collect=1)
        for (x, y) in cproduct([irange(x0, x1, step=5), irange(y0, y1, step=5)]):
          # distance travelled should be an integer, less than 100
          d = ihypot(x - x0, y - y0)
          if (not d) or d > 100: continue
          r.accumulate_data(line_distance((x0, y0), (x1, y1), (x, y)), ((x, y), d))
        # find the minimum distance travelled
        return min(r.data, key=unpack(lambda pt, d: d))
      
      # calculate a journey to from p0 to p1; return (points, dists)
      def journey(p1, p0=(0, 0)):
        (pts, ds) = ([p0], [])
        while p0 != p1:
          (p0, d) = call(step, p0 + p1)
          pts.append(p0)
          ds.append(d)
        return (pts, ds)
      
      # consider possible distance north between camps
      for n in irange(5, 235, step=5):
        # look for a journey with 14 intermediate points
        (pts, ds) = journey((240, n))
        if len(pts) != 16: continue
        # accumulate due E and due N distances
        E = N = 0
        for ((x0, y0), (x1, y1)) in tuples(pts, 2):
          if y0 == y1: E += x1 - x0
          if x0 == x1: N += y1 - y0
        if not (E == 50 and N == 5): continue
        # output solution
        printf("n={n}: E={E} N={N} {pts}")
        printf("-> {ds}")
      

      Solution: The distances travelled in the first 5 stages of the journey are: 5, 5, 5, 85, 5 (miles).

      The summer camp is 115 miles north and 240 miles east of the winter camp.

      The full list of distances is:

      5, 5, 5, 85, 5, 85, 5, 5, 5, 25, 5, 25, 5, 5, 5 (miles)
      or:
      1, 1, 1, 17, 1, 17, 1, 1, 1, 5, 1, 5, 1, 1, 1 (units)

      involving the hypotenuses of (8, 15, 17) and (3, 4, 5) triangles.

      And the route looks like this:

      The direct route is shown in green (although only the first stage needs to come closest to this line – the direct line for subsequent steps runs from the current position to the destination).

      Like

    • Frits's avatar

      Frits 1:00 pm on 22 September 2024 Permalink | Reply

      @Jim, right now I come to the same “n” but to a different first five stages (different as of the 2nd stage).

      Having said that, I don’t understand the phrase: “If more than one well is equally close, he stops at the nearest one.”.

      Like

      • Jim Randell's avatar

        Jim Randell 1:20 pm on 22 September 2024 Permalink | Reply

        @Frits: I assumed that meant if there are multiple wells equally close to the direct line, then he chooses the one that is closest to his current position (i.e. the shortest distance to travel).

        Like

        • Frits's avatar

          Frits 1:23 pm on 22 September 2024 Permalink | Reply

          Thx, I will publish after the F1 has finished.

          Like

        • Frits's avatar

          Frits 9:30 pm on 22 September 2024 Permalink | Reply

          I finally understood the puzzle.

          # perpendicular distance from a point (x1, y1) to line ax + by + c = 0
          distance = lambda a, b, c, x1, y1: (abs(a * x1 + b * y1 + c) / 
                                             ((a * a + b * b)**.5))
                                             
          MX = 999999
          d = {n * n: n for n in range(1, 101)}
          
          def is_sqr(x, y):
            return d.get(x * x + y * y, None)
          
          # feasible diagonal routes (don't return z)  
          diags = [(x, y) for x in range(5, 100, 5) for y in range(5, 100, 5) 
                  if (z := is_sqr(x, y)) is not None]
          
          # find a solution that meets the requirements
          def check(journeys, a1, b1):
            a, b, c = a1, b1, 0
            pos = (0, 0)
            stops = []
            # keep adding stops if possible
            while pos[0] <= b1 and pos[1] <= -a1 and pos != (b1, -a1):
              mn = MX
              for j in set(journeys):
                pos2 = (pos[0] + j[0], pos[1] + j[1])       
                if not (pos2[0] <= b1 and pos2[1] <= -a1): continue
                # perpendicular distance to remaining line ax + by + c = 0
                dist = distance(a, b, c, pos2[0], pos2[1])
                if dist <= mn:
                  # if wells are equally close to the line, he stops at the nearest one
                  if dist == mn:
                    if j[0]**2 + j[1]**2 > min_j[0]**2 + min_j[1]**2:
                      continue
                  mn = dist
                  min_j = j
                  
              # set new position 
              pos = (pos[0] + min_j[0], pos[1] + min_j[1])   
          
              # calculate coefficients remaining line
              a, b = pos[1] + a1, b1 - pos[0]
              c = b * a1 - a * b1
              stops.append(min_j)
          
            # double check  
            if pos == (b1, -a1):
              yield stops
          
          E, dueE, dueN = 240, 50, 5
          # check possible north distances
          for N in range(5, E, 5):
            # check if the possible diagonal journeys with (0, 5) and (5, 0) 
            # can be fitted closest to the remaining straight-line route
            for stops in check(diags + [(0, 5), (5, 0)] , -N, E):
              if len(stops) != 15: continue
              if stops.count((0, 5)) != dueN // 5: continue
              if stops.count((5, 0)) != dueE // 5: continue
              print("answer:", [is_sqr(x, y) for x, y in stops[:5]],
                    "for N =", N)
          

          Like

  • Unknown's avatar

    Jim Randell 10:43 am on 17 September 2024 Permalink | Reply
    Tags:   

    Teaser 2604: Foreign friends 

    From The Sunday Times, 19th August 2012 [link] [link]

    The telephone number of my Japanese friend is a ten-digit number written as a group of five two-digit numbers. The phone number does not start with a 0, and no digit is used more than once. The numbers in the group are in increasing order, no two of them have a common factor greater than 1, and one of them is a fourth power. Also, the product of the numbers in the group is divisible by four of the first five primes.

    The telephone number of my Russian friend is also a ten-digit number but it is written as a group of two five-digit numbers. The number and group have the same properties as those stated above. The second digit of the Russian number is double the second digit of the Japanese number.

    What are the two telephone numbers?

    [teaser2604]

     
    • Jim Randell's avatar

      Jim Randell 10:44 am on 17 September 2024 Permalink | Reply

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

      It runs in 772ms. (Internal runtime is 582ms, although this can be reduced to 377ms by splitting out the [[ is_coprime(@jps) ]] check into 10 separate coprime tests (one for each pair)).

      Note: An up-to-date version of enigma.py is required for the multiple argument version of is_coprime().

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # Japanese phone number = AB CD EF GH IJ
      # Russian phone number = KLMNP QRSTU
      --distinct="ABCDEFGHIJ,KLMNPQRSTU"
      --macro="@jps = AB, CD, EF, GH, IJ"
      --macro="@rus = KLMNP, QRSTU"
      
      # neither phone number starts with 0
      --invalid="0,AK"
      
      # in the groups ...
      # the numbers are in increasing order
      "A < C" "C < E" "E < G" "G < I"
      "K < Q"
      
      # the numbers are pairwise co-prime
      "is_coprime(@jps)"
      "is_coprime(@rus)"
      
      # use "at least" or "exactly" for counting?
      --code="count = icount_at_least"  # or: icount_exactly
      
      # one of them is a fourth power
      --code="pow4s = set(i**4 for i in irange(0, 17))"
      --code="pow4 = lambda ns: count(ns, is_in(pow4s), 1)"
      "pow4([@jps])"
      "pow4([@rus])"
      
      # the product is divisible by four of {2, 3, 5, 7, 11}
      --code="_divs = (lambda n, ds, k: count(ds, (lambda d: n % d == 0), k))"
      --code="divs = (lambda ns: _divs(multiply(ns), [2, 3, 5, 7, 11], 4))"
      "divs([@jps])"
      "divs([@rus])"
      
      # 2nd digit of the Russian number is double the 2nd digit of the Japanese number
      "2 * B = L"
      --invalid="5|6|7|8|9,B"  # so, B < 5
      
      --template="(AB CD EF GH IJ) (KLMNP QRSTU)"
      --solution=""
      --denest=-1
      

      Solution: The numbers are: (23 49 50 67 81) and (46970 83521).

      The individual parts factorise as:

      (23 49 50 67 81) = ([23] [7×7] [2×5×5] [67] [3×3×3×3])
      (46970 83521) = ([2×5×7×11×61] [17×17×17×17])

      From which we see in each number there are no prime factors common to any two of the parts, so each is pairwise coprime.

      And the final part in each is the fourth power (of a prime).

      The top number has divisors of: 2, 3, 5, 7 (but not 11).

      The bottom number has divisors of: 2, 5, 7, 11 (but not 3).

      Like

      • Ruud's avatar

        Ruud 12:22 pm on 19 September 2024 Permalink | Reply

        Brute force:

        from istr import istr
        import math
        import functools
        import operator
        
        istr.repr_mode("str")
        solutions = {2: set(), 5: set()}
        
        for s in istr.permutations(istr.range(10)):
            if s[0] != 0:
                for k in (2, 5):
                    numbers = tuple(istr("".join(s[i : i + k])) for i in range(0, len(s), k))
                    if all(number0 < number1 for number0, number1 in zip(numbers, numbers[1:])):
                        if sum((float(number) ** (1 / 4)).is_integer() for number in numbers) == 1:
                            if sum(functools.reduce(operator.mul, numbers) % prime == 0 for prime in (2, 3, 5, 7, 11)) == 4:
                                if all(math.gcd(int(number0), int(number1)) == 1 for number0, number1 in istr.combinations(numbers, 2)):
                                    solutions[k].add(istr(" ").join(numbers))
        for japanese in solutions[2]:
            for russian in solutions[5]:
                if japanese[1] * 2 == russian[1]:
                    print(f"{japanese=} {russian=}")
        

        Like

    • GeoffR's avatar

      GeoffR 4:41 pm on 19 September 2024 Permalink | Reply

      # Japanese telephone number is AB CD EF GH IJ
      # Russian telephone number is KLMNP QRSTU
      
      from itertools import permutations
      from enigma import is_coprime
      
      # max 5 digits for the 4th power
      pow4 = [n * n * n * n for n in range(2, 18)]
      
      dgts = set(range(10))
      
      # Japanese Telephone Number
      for p1 in permutations(dgts, 4):
        jp_found = 0
        A, B, C, D = p1
        if 0 in (A, C): continue
        # Constraint on 2nd digit of 1st Tel No. i.e. L = 2 *  B
        if B == 0 or B > 4: continue
        if not A < C: continue
        AB, CD = 10*A + B, 10*C + D
        if not is_coprime(AB, CD): continue
      
        # Find remaining digits in Japanese Telephone Number
        q1 = dgts.difference({A, B, C, D})
        for p2 in permutations(q1):
          E, F, G, H, I, J = p2
          if 0 in (E, G, I): continue
          if not A < C < E < G < I: continue
          EF, GH, IJ = 10*E + F, 10*G + H, 10*I + J
          
          # check ten co-prime conditions 
          if is_coprime(CD, EF) and is_coprime(EF, GH) and is_coprime(GH, IJ) \
            and is_coprime(AB, EF) and is_coprime(AB, GH) and is_coprime(AB, IJ) \
            and is_coprime(CD, GH ) and is_coprime(CD, IJ) and is_coprime(EF, IJ):
              
            # Check for a fourth power
            if any (x in pow4 for x in (AB, CD, EF, GH, IJ)):
              # Find number of divisors of Japanese Tel. No.
              cnt = 0
              for num in (AB, CD, EF, GH, IJ):
                for p3 in (2, 3, 5, 7, 11):
                  if num % p3 == 0:
                    cnt += 1
                if cnt == 4:
                  print(f"Japanese No. is {AB} {CD} {EF} {GH} {IJ}.")
                  jp_found = 1
      
                # Russian Telephone Number - find first half of Tel. No.
                for p5 in permutations(dgts,5):
                  K, L, M, N, P = p5
                  if K == 0: continue
                  if L != 2 * B: continue
                  KLMNP = 10000*K + 1000*L + 100*M + 10*N + P
                  # Assume 4th power is QRSTU  
                  if KLMNP not in pow4:
                    cnt2 = 0
                    for p5 in (2, 3, 5, 7, 11):
                      if KLMNP % p5 == 0:
                        cnt2 += 1
                  if cnt2 == 4:
                      
                    # Find second half of Russian Tel. No.
                    q6 = dgts.difference({K, L, M, N, P})
                    for p7 in permutations(q6):
                      Q, R, S, T, U = p7
                      QRSTU = 10000*Q + 1000*R + 100*S + 10*T + U
                      if Q == 0: continue
                      if not KLMNP < QRSTU: continue
                      if not is_coprime(KLMNP, QRSTU): continue
                      if QRSTU in pow4 and jp_found == 1:
                        print(f"Russian No. is {KLMNP} {QRSTU}.")
      
      #Japanese No. 23 49 50 67 81
      # Russian No. is 46970 83521
      
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:12 am on 15 September 2024 Permalink | Reply
    Tags:   

    Teaser 3234: An existential threat thwarted 

    From The Sunday Times, 15th September 2024 [link] [link]

    “Merlin, the Saxons are on the rampage. A group of 90 soldiers is advancing towards Mount Badon. We only have 86 knights that we can muster. I think we are doomed”, said the King.

    “Not necessarily, Sire. The strength of an army is proportional to the square of the number of its troops. An army of 100 would defeat an army of 80 yet still have 60 remaining because 100^2 − 80^2 = 60^2. Tell the knights to split into three groups of particular sizes and engage the Saxons in three simultaneous battles. If the Saxons split into three groups of 30, we can prevail.”

    After the conflict there were 32 knights and 24 Saxons remaining.

    What were the sizes of the three groups the knights split into?

    [teaser3234]

     
    • Jim Randell's avatar

      Jim Randell 6:21 am on 15 September 2024 Permalink | Reply

      I am assuming we are looking for battles where there is an integer number of survivors.

      This Python program runs in 68ms. (Internal runtime is 1.4ms).

      from enigma import (decompose, ircs, printf)
      
      # battle <xs> against <ys>, looking for integer advantages
      def battle(xs, ys):
        rx = ry = 0
        for (x, y) in zip(xs, ys):
          if x > y:
            r = ircs(x, -y)
            if r is None: return (None, None)
            rx += r
          elif y > x:
            r = ircs(y, -x)
            if r is None: return (None, None)
            ry += r
        return (rx, ry)
      
      # split the knights into 3 groups
      for ks in decompose(86, 3, increasing=1, sep=0, min_v=1):
        # battle the Knights against the groups of Saxons
        (rK, rS) = battle(ks, (30, 30, 30))
        if rK is None: continue
        # look for scenarios where the Knights prevail
        if not (rK > rS): continue
        # output solution
        printf("{ks} -> {rS} Saxons, {rK} Knights")
      

      Solution: The Knights split into groups of size: 18, 34, 34.

      So we have the following battles:

      30 Saxons vs. 18 Knights → 24 Saxons remaining
      30 Saxons vs. 34 Knights → 16 Knights remaining
      30 Saxons vs. 34 Knights → 16 Knights remaining
      total: 90 Saxons vs. 86 Knights → 24 Saxons, 32 Knights remaining; Knights prevail

      For battles with integer advantages there is one other solution, but in this case the Saxons prevail:

      30 Saxons vs. 18 Knights → 24 Saxons remaining
      30 Saxons vs. 18 Knights → 24 Saxons remaining
      30 Saxons vs. 50 Knights → 40 Knights remaining
      total: 90 Saxons vs. 86 Knights → 48 Saxons, 40 Knights remaining; Saxons prevail

      So we don’t need to know the number of survivors to solve the puzzle.


      Manually:

      There are only 6 possible battles that give an integer number of survivors where one of the sides has 30 participants, and the other side has less than 86:

      (30, 24) → (18, 0)
      (30, 18) → (24, 0)
      (30, 30) → (0, 0)
      (30, 34) → (0, 16)
      (30, 50) → (0, 40)
      (30, 78) → (0, 72)

      And by inspection, the only way for there to be 24 Saxons and 32 Knights remaining in 3 battles is:

      (30, 18) → (24, 0)
      (30, 34) → (0, 16)
      (30, 34) → (0, 16)

      Like

      • Jim Randell's avatar

        Jim Randell 6:08 pm on 15 September 2024 Permalink | Reply

        This is faster (and shorter). Internal runtime is 134µs.

        from enigma import (pythagorean_triples, subsets, printf)
        
        # if A beats B and has C survivors then:
        #   A^2 - B^2 = C^2
        #   B^2 + C^2 = A^2 (i.e. a Pythagorean triple)
        
        # record (<saxons>, <knights>, <remaining-saxons>, <remaining-knights>)
        ss = [(30, 30, 0, 0)]  # draw
        
        # find pythagorean triples involving 30
        for (x, y, z) in pythagorean_triples(84):
          if z == 30:
            ss.extend([(z, y, x, 0), (z, x, y, 0)])
          if y == 30:
            ss.append((y, z, 0, x))
          if x == 30:
            ss.append(((x, z, 0, y)))
        
        # choose 3 battles
        for bs in subsets(ss, size=3, select='R'):
          # calculate initial knights (K) and total survivors (rS, rK)
          (Ss, Ks, rSs, rKs) = zip(*bs)
          (K, rS, rK) = map(sum, (Ks, rSs, rKs))
          if K == 86 and rK > rS:
            printf("Knights = {Ks} -> {rS} Saxons, {rK} Knights [battles = {bs}]")
        

        Like

    • GeoffR's avatar

      GeoffR 5:34 pm on 15 September 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % As the Knights have 32 men left and the Saxons 24 men left after three battles....
      % Assume the Saxons win the 1st battle and the Knights the next 2 battles
      % Also, the Saxons have 30 men in each of the three battles
      
      % K1 knights in 1st battle, K2 knights in 2nd battle and K3 knights in 3rd battle
      var 1..29:K1; var 31..86:K2; var 31..86:K3;
      
      constraint K1 + K2 + K3 == 86; % There are 86 knights in total
      
      predicate is_sq(var int: y) =
        exists(z in 1..ceil(sqrt(int2float(ub(y))))) (
              z*z = y );
              
      % Let the Saxons win the 1st battle
      constraint 30 * 30 - K1 * K1 == 24 * 24; % Saxons have 24 men left after 3 battles
      
      % Let the Knights win 2nd and 3rd battles
      constraint is_sq((K2 * K2 - 30 * 30)) /\ is_sq((K3 * K3 - 30 * 30));
      
      solve satisfy;
      
      output ["The three groups of the knights are " ++ show([K1, K2, K3])];
      
      
      
      
      

      A manual check on K2 and K3 knights showed there were 32 knights left.

      Like

    • Ruud's avatar

      Ruud 10:06 am on 17 September 2024 Permalink | Reply

      This code runs in 57 ms on my M4 iPad Pro.

      import itertools
      import math
      
      for sizes in itertools.product(range(87), repeat=3):
          if sum(sizes) == 86 and sizes == tuple(sorted(sizes)):
              knights = 0
              saxons = 0
              for size in sizes:
                  if (diff := math.sqrt(abs((size**2 - 30**2)))).is_integer():
                      knights += (size > 30) * int(diff)
                      saxons += (size < 30) * int(diff)
                  else:
                      break
              else:
                  if knights > saxons:
                      print(f"{sizes=} {knights=} {saxons=}")
      

      Like

  • Unknown's avatar

    Jim Randell 10:18 am on 11 September 2024 Permalink | Reply
    Tags: ,   

    Brain-Teaser 734: Golden orchard 

    From The Sunday Times, 10th August 1975 [link]

    A farmer grows apples in an orchard divided into plots —three to the East and three to the West of a central path. The apples are of two types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).

    Adjacent plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).

    They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite. Those South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are adjacent. Yellow and orange are of the same type. Orange are North of pleasant and also North of Pearmain. Kingstons are adjacent to golden. Green is South of bitter.

    Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.

    If cider apples taste unpleasant, what are the characteristics of the apples in North East plot? (Name, colour, taste, ripens).

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

    I think the puzzle as published in The Sunday Times and in the book is open to interpretation, and my first attempt using a reasonable interpretation gave two solutions (neither of which are the published solution). After examining the given solution in the book I think the following wording is clearer:

    A farmer grows apples in an orchard divided into plots — three to the East and three to the West of a central track. Adjacent plots are separated by a shared fence. The apples are of two basic types — for eating (Cox, Laxton, Pearmain) and for cider making (Tremlitt, Coppin, Kingston).

    Neighbouring plots contain apples of different basic type. The apples are of six colours (red, green, russet, golden, orange, yellow) and of six tastes (sweet, sour, acid, tart, pleasant, bitter).

    They ripen at different times, either early or late in July, August and September. Those ripening in early or late September are in plots directly opposite each other. Those directly South of Pearmain do not ripen in August. Tart are directly West of the acid variety, which ripens in early August. Yellow apples and those maturing in late September are in adjacent plots. Yellow and orange are of the same basic type. Orange are directly North of Permain, which are pleasant. Kingstons and golden are in adjacent plots. Green is directly South of bitter.

    Cox ripen in early July, and Laxtons ripen early in a different month. Tremlitts are red, and Kingstons mature after Coppins, which are not sour.

    If cider apples are neither pleasant nor sweet, what are the characteristics of the apples in North-East plot?

    [teaser734]

     
    • Jim Randell's avatar

      Jim Randell 10:20 am on 11 September 2024 Permalink | Reply

      When I first tackled this puzzle (using the text from the 1981 book, and what I considered to be the most reasonable interpretation of the text), I found two solutions. And neither of them matched the published solution.

      According to the solution published in The Sunday Times [link] there were:

      A load of wrong answers (and some unacceptable multi-entries) in diffuse permutations brightly offset by an authentic minority including the winner …

      However, I think the wording of the puzzle is too vague to permit a single solution.

      Having looked at the answer in the book, I constructed the alternative wording, which I hope is clearer.


      Using the [[ SubstitutedExpression ]] solver from the enigma.py library, we can assign the characteristics to the plots.

      This run-file executes in 81ms. (Internal runtime of the generated code is 1.2ms).

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # plots are:
      #
      #   1 || 2
      #   --++--
      #   3 || 4
      #   --++--
      #   5 || 6
      #
      # we need to assign each of the six characteristics from each group
      # to a different plot number
      #
      # Eating: A = Cox; B = Laxton; C = Permain
      # Cider: D = Tremlitt; E = Coppin; F = Kingston
      #
      # Colour: G = red; H = green; I = russet; J = golden; K = orange; L = yellow
      #
      # Taste: M = sweet; N = sour; P = acid; Q = tart; R = pleasant; S = bitter
      #
      # Season: T = early Jul; U = late Jul; V = early Aug; W = late Aug; X = early Sep; Y = late Sep
      
      --base=7
      --digits="1-6"
      
      --distinct="ABCDEF,GHIJKL,MNPQRS,TUVWXY"
      
      # row adjacency (W, E)
      --code="row_adj = {(1, 2), (3, 4), (5, 6)}"
      
      # col adjacency (N, S)
      --code="col_adj = {(1, 3), (2, 4), (3, 5), (4, 6)}"
      
      # adjacent plots contain apples of different types
      "{A, B, C} in ({1, 4, 5}, {2, 3, 6})"
      
      # those ripening in early/late September (X, Y) are opposite
      "ordered(X, Y) in row_adj"
      
      # Southerly neighbour of Permain (C) do not ripen in Aug (V, W)
      "C not in {5, 6}"  # implies Permain (C) is not in southernmost row
      "(C, V) not in col_adj"
      "(C, W) not in col_adj"
      
      # tart (Q) are directly West of acid (P)
      "(Q, P) in row_adj"
      
      # acid (P) ripens in early Aug (V)
      "P = V"
      
      # yellow apples (L) and those maturing in late Sep (Y) are adjacent
      "ordered(L, Y) in col_adj"
      
      # yellow (L) and orange (K) are of the same type
      "len(intersect([{L, K}, {A, B, C}])) != 1"
      
      # orange (K) are Northerly neighbours of pleasant (R), and also Northerly neighbours of Permain (C)
      "(K, R) in col_adj"
      "(K, C) in col_adj"
      
      # Kingston (F) are adjacent to golden (J)
      "ordered(F, J) in col_adj"
      
      # green (H) is Southerly neighbour of bitter (S)
      "(S, H) in col_adj"
      
      # Cox (A) ripen in early Jul (T)
      "A = T"
      
      # Laxtons (B) ripen early in [not Jul] (V, X)
      "B in {V, X}"
      
      # Tremlitts (D) are red (G)
      "D = G"
      
      # Kingstons (F) mature after Coppins (E)
      "[T, U, V, W, X, Y].index(F) > [T, U, V, W, X, Y].index(E)"
      
      # Coppins (E) are not sour (N)
      "E != N"
      
      # cider apples do not taste pleasant (R) or sweet (M)
      "R not in {D, E, F}"
      "M not in {D, E, F}"
      
      # make sure all the variables are filled out
      "true(A, B, C, D, E, F, G, H, I, J, K, L, M, N, P, Q, R, S, T, U, V, W, X, Y)"
      
      --template="(A B C D E F) (G H I J K L) (M N P Q R S) (T U V W X Y)"
      --solution=""
      --denest=-1
      

      And the following Python program can be used to make the output more friendly:

      from enigma import (SubstitutedExpression, join, printf)
      
      p = SubstitutedExpression.from_file("teaser734b.run")
      
      # labels for the characteristics
      label = dict(
        # Type:
        A="Cox", B="Laxton", C="Permain", D="Tremlitt", E="Coppin", F="Kingston",
        # Colour:
        G="red", H="green", I="russet", J="golden", K="orange", L="yellow",
        # Taste:
        M="sweet", N="sour", P="acid", Q="tart", R="pleasant", S="bitter",
        # Season:
        T="early Jul", U="late Jul", V="early Aug", W="late Aug", X="early Sep", Y="late Sep",
      )
      
      # solve the puzzle
      for s in p.solve(verbose=0):
        # collect the characteristics for each plot
        d = dict((k, list()) for k in [1, 2, 3, 4, 5, 6])
        for k in sorted(s.keys()):
          d[s[k]].append(label.get(k))
        # output the solution
        for k in sorted(d.keys()):
          printf("{k} -> {v}", v=join(d[k], sep="; "))
        printf()
      

      Solution: The North-East plot contains Cox, russet in colour, sweet in taste, and ripens in early July.

      The full solution is:

      Like

  • Unknown's avatar

    Jim Randell 12:22 am on 8 September 2024 Permalink | Reply
    Tags:   

    Teaser 3233: Not Mrs Perkins’ quilt! 

    From The Sunday Times, 8th September 2024 [link] [link]

    Sue was making a quilt in the shape of an equilateral triangle and she sewed a straight line of stitches from each corner of the quilt to its opposite edge, so as to divide each edge in the ratio 1:2 in a clockwise direction. Sue covered the region enclosed by the lines of stitches with a triangular piece of material of exactly the same size. The area of this piece was 2 square feet.

    Including the triangular quilt and the extra triangular piece, what was the total area of material used?

    Mrs. Perkins’s quilt is a puzzle by Henry Ernest Dudeney from his book “Amusements in Mathematics” (1917).

    [teaser3233]

     
    • Jim Randell's avatar

      Jim Randell 12:41 am on 8 September 2024 Permalink | Reply

      See also: Teaser 2865, Enigma 1076, Enigma 320, Enigma 1313.

      We can solve the puzzle directly using Routh’s Theorem [ @wikipedia ], which I have previously made some notes on here [ rouths-theorem.pdf ]

      In this case we have x = y = z = 2, hence:

      XYZ / ABC = (x − 1)^2 / (x^2 + x + 1)
      XYZ / ABC = 1 / 7

      We are given the area XYZ = 2, hence ABC = 14.

      And the total area of the two triangles is easily calculated.

      from enigma import (rdiv, printf)
      
      # ratio XYZ/ABC in Routh's theorem
      def routh(x, y, z):
        a = x * y * z - 1
        b = (x * y + y + 1) * (y * z + z + 1) * (z * x + x + 1)
        return rdiv(a * a, b)
      
      # compute the ratio r = XYZ / ABC
      r = routh(2, 2, 2)
      
      # calculate the areas of the triangles
      XYZ = 2
      ABC = rdiv(XYZ, r)
      
      # calculate the total area
      T = ABC + XYZ
      printf("total area = {T}")
      

      Solution: The total area of material used is: 16 square feet.

      Note that the result holds even if the triangle is not equilateral.

      Like

    • GeoffR's avatar

      GeoffR 8:07 am on 8 September 2024 Permalink | Reply

      
      % A Solution in MiniZinc
      include "globals.mzn";
      
      int: x == 2;
      int: y == 2;
      int: z == 2;
       
      var 1..35:ABC;
      var 1..5:XYZ; 
      
      % Using Routh's theorem
      constraint XYZ * (x*x + x + 1) == ABC * (x - 1 ) * (x - 1);
      constraint XYZ * 7 == ABC /\ XYZ == 2;
      
      solve satisfy;
      output["Total area = " ++ show(ABC + XYZ) ++ " Sq. Ft."];
      
      

      Like

  • Unknown's avatar

    Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply
    Tags:   

    Brainteaser 1047: Youth opportunities 

    From The Sunday Times, 22nd August 1982 [link]

    Five of the shops in our local High Street sell cakes, electrical goods, greengrocery, hardware and shoes. Each decided recently take on two young assistants, one of each sex, from the Youth Opportunities Scheme.

    These ten lucky youngsters include Hazel and Stephen, who live on either side of my house, and Eric from across the road. He gave me the following information:

    The initials of the assistants’ forenames are all different from the initial of the shop in which they work. Moreover no boy works with a girl whose initial is the same as his own. In addition, Emma does not work with Henry, nor does she work in the shoe shop.

    Henry doesn’t work the in the cake shop, Gordon is not in the hardware shop, Gwen is not in the shoe shop, and  neither Charles nor Sheila work in the greengrocer’s.

    If Carol works in the hardware shop, who sells the electrical goods?

    This puzzle is included in the book The Sunday Times Book of Brainteasers (1994).

    [teaser1047]

     
    • Jim Randell's avatar

      Jim Randell 6:51 pm on 4 September 2024 Permalink | Reply

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

      Most of the conditions can be dealt with using the [[ --distinct ]] and [[ --invalid ]] parameters.

      The following run file executes in 70ms. (Internal runtime of the generated code is just 27µs).

      Run: [ @jdoodle ]

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      # shops: 0 1 2 3 4  (= Cakes, Electricals, Greengrocers, Hardware, Shoes)
      # boys:  Q R S T U  (= Charles, Eric, Gordon, Henry, Steven; in some order)
      # girls: V W X Y Z  (= Carol, Emma, Gwen, Hazel, Shiela; in some order)
      
      --base=5
      # boys and girls have different initials
      # but no-one works with someone with the same initial
      --distinct="QRSTU,VWXYZ,QV,RW,SX,TY,UZ"
      
      # no-one shares an initial with the shop
      # Emma does not work in the shoe shop
      # Gwen does not work in the shoe shop
      # Henry does not work in the cake shop
      # Gordon does not work in the hardware shop
      # neither Charles nor Shiela work in the greengrocers
      --invalid="0,QVS"   # C = 0
      --invalid="1,RWZ"   # E = 1
      --invalid="2,SXZT"  # G = 2
      --invalid="3,TYQ"   # H = 3
      --invalid="4,UZX"   # S = 4
      
      # Carol works in the hardware shop
      --assign="Y,0"
      
      # Henry and Emma do not work together
      "(Q != 3) or (V != 1)" "(S != 3) or (X != 1)"
      
      --answer="((Q, R, S, T, U), (V, W, X, Y, Z))"
      --template="(Q R S T U) (V W X Y Z)"
      --solution=""
      

      We can write additional Python code to format the output nicely:

      from enigma import (SubstitutedExpression, printf)
      
      # label shops and people
      shops = "Cakes Electricals Greengrocers Hardware Shoes".split()
      boys  = "Charles Eric Gordon Henry Steven".split()
      girls = "Carol Emma Gwen Hazel Shiela".split()
      
      # load the puzzle
      p = SubstitutedExpression.from_file("teaser1047.run")
      
      # solve the puzzle, and format solutions
      for (bs, gs) in p.answers(verbose=0):
        for (s, (b, g)) in enumerate(zip(bs, gs)):
          printf("{s} = {b} + {g}", s=shops[s], b=boys[b], g=girls[g])
        printf()
      

      Solution: Henry and Gwen work in the electrical goods shop.

      The full solution is:

      Cakes = Gordon + Shiela
      Electricals = Henry + Gwen
      Greengrocers = Steven + Emma
      Hardware = Eric + Carol
      Shoes = Charles + Hazel

      Like

      • Frits's avatar

        Frits 10:35 am on 5 September 2024 Permalink | Reply

        This is much more intuitive to me:

        #! python3 -m enigma -r
         
        SubstitutedExpression
         
        # shops: 0 1 2 3 4  (= Cakes, Electricals, Greengrocers, Hardware, Shoes)
        # boys:  Q R S T U  (= Charles, Eric, Gordon, Henry, Steven)
        # girls: V W X Y Z  (= Carol, Emma, Gwen, Hazel, Sheila)
         
        --base=5
        # boys and girls have different initials
        # but no-one works with someone with the same initial
        --distinct="QRSTU,VWXYZ,QV,RW,SX,TY,UZ"
         
        # no-one shares an initial with the shop
        # Emma does not work in the shoe shop
        # Gwen does not work in the shoe shop
        # Henry does not work in the cake shop
        # Gordon does not work in the hardware shop
        # neither Charles nor Sheila work in the greengrocers
        --invalid="0,QVT"   # C = 0
        --invalid="1,RW"    # E = 1
        --invalid="2,SXQZ"  # G = 2
        --invalid="3,TYS"   # H = 3
        --invalid="4,UZWX"  # S = 4
         
        # Carol works in the hardware shop
        --assign="V,3"
         
        # Henry and Emma do not work together
        "T != W"
         
        --answer="((Q, R, S, T, U), (V, W, X, Y, Z))"
        --template="(Q R S T U) (V W X Y Z)"
        --solution=""
        

        and

        from enigma import (SubstitutedExpression, printf)
         
        # label shops and people
        shops = "Cakes Electricals Greengrocers Hardware Shoes".split()
        boys  = "Charles Eric Gordon Henry Steven".split()
        girls = "Carol Emma Gwen Hazel Sheila".split()
         
        # load the puzzle
        p = SubstitutedExpression.from_file("teaser/teaser1047.run")
         
        # solve the puzzle, and format solutions
        for (bs, gs) in p.answers(verbose=0):
          for i in range(5):
            b, g = boys[bs.index(i)], girls[gs.index(i)]
            print(shops[i], "=", b, "+", g)
        

        Like

  • Unknown's avatar

    Jim Randell 6:17 am on 1 September 2024 Permalink | Reply
    Tags:   

    Teaser 3232: Digital processing 

    From The Sunday Times, 1st September 2024 [link] [link]

    I divided 1 by 5 in base 7 in the following way. I started with 1, multiplied by the base (7), recorded the result on division by 5 as a digit (1), then used the remainder (2) to repeat the process until the remainder became 0 or the pattern was about to repeat. The result was 0.1254 with those four digits then repeating.

    For some base no more than 20 I also calculated the result of dividing 1 by all numbers from 2 up to the base minus 1. With one of these divisors the result had the “digit” 14 at one point followed immediately by the “digit” 13. Some “digits” never occurred in the fractional part with any of these divisors.

    What “digits” (in increasing order) never occurred?

    [teaser3232]

     
    • Jim Randell's avatar

      Jim Randell 6:36 am on 1 September 2024 Permalink | Reply

      We can use the [[ recurring() ]] function from the enigma.py library to calculate the expansion of a fraction in different bases. (Originally written for Enigma 1247).

      The following Python program runs in 69ms. (Internal runtime is 949µs).

      from enigma import (irange, recurring, int2base, base2int, format_recurring, printf)
      
      # look for digit X followed by digit Y
      (X, Y) = (14, 13)  # {14}:{13} = "ED"
      
      # examine reciprocals in base <b>
      def solve(b, verbose=0):
        # look for subsequence X:Y
        i2b = lambda n: int2base(n, base=b)
        (ss, f) = (i2b(X) + i2b(Y), 0)
        # unused digits
        ds = set(i2b(n) for n in irange(0, b - 1))
        for k in irange(2, b - 1):
          (i, nr, rr) = recurring(1, k, base=b)
          if verbose: printf("[{b}] {k} -> {x}", x=format_recurring((i, nr, rr)))
          if ss in nr + rr + rr[:1]: f += 1
          ds.difference_update(nr, rr)
        if f:
          # output solution (using integer digits)
          ds = list(base2int(d, base=b) for d in ds)
          printf("base={b} -> unused digits = {ds}", ds=sorted(ds))
      
      # consider bases up to 20
      for b in irange(max(X, Y) + 1, 20):
        solve(b)
      

      Solution: The unused digits are: 0, 12, 15, 17.

      In base 18 the reciprocals from 1/2 to 1/17 have the following expansions:

      1/2 = 0.9
      1/3 = 0.6
      1/4 = 0.49
      1/5 = 0.(3AE7)…
      1/6 = 0.3
      1/7 = 0.(2A5)…
      1/8 = 0.249
      1/9 = 0.2
      1/10 = 0.1(E73A)…
      1/11 = 0.(1B834G69ED)… [this contains E followed by D]
      1/12 = 0.19
      1/13 = 0.(16GB)…
      1/14 = 0.1(52A)…
      1/15 = 0.1(3AE7)…
      1/16 = 0.1249
      1/17 = 0.(1)…

      The digits (from 0123456789ABCDEFGH) that do not occur in the fractional parts of these expansions are:

      0
      C = 12
      F = 15
      H = 17

      The puzzle limits us to bases up to 20, but the next solutions don’t occur until bases 58, 86, 142.

      Like

      • Frits's avatar

        Frits 3:00 pm on 2 September 2024 Permalink | Reply

        @Jim, Brian’s counting of the divisors that have the special subsequence is more pure than our approach (as it doesn’t say “With at least one of these divisors”).

        Like

        • Jim Randell's avatar

          Jim Randell 4:11 pm on 2 September 2024 Permalink | Reply

          @Frits: Unless the puzzle is explicit about there being exactly one case, I usually take a relaxed interpretation where the finding of one case is sufficient (a logical existential quantification). In this puzzle we don’t need to use the strict interpretation of “exactly one”.

          However, if you want to use the strict interpretation you can simply change the test at line 18 of my program to [[ if f == 1: ]]. But it doesn’t change the answer to the puzzle.

          Like

    • Frits's avatar

      Frits 10:44 am on 1 September 2024 Permalink | Reply

      # does list <lst2> occur in list <lst1>
      inList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2
                                      for i in range(len(lst1) - len(lst2) + 1))
      
      # return digits in base b in the fraction k / b (where k < b)
      # (not repeating decimals) 
      def divide(b, k):
        r, s, rs = 1, [], set()
        while True:
          (d, r) = divmod(r * b, k)
          s.append(d)
          # break if no remainder or repeating decimals encountered
          if not r or r in rs: break
          rs.add(r)  
        return s 
      
      # consider bases from 15 to 20 (base must be higher than 14)
      for b in range(15, 21):
        found1413, seen = 0, set()
        for k in range(2, b): 
          dgts = divide(b, k)
          # does list [14, 13] occur in <dgts>?
          if inList(dgts, [14, 13]):
            found1413 = 1
          seen |= set(dgts)
          
        if found1413:
          print(f"answer: {sorted(set(range(b)).difference(seen))}")
      

      Like

      • Jim Randell's avatar

        Jim Randell 11:31 am on 2 September 2024 Permalink | Reply

        @Frits: I don’t see how you can differentiate between recurring and non-recurring expansions returned by your [[ divide() ]] routine.

        >>> divide(10, 18)
        [0, 5]
        >>> divide(10, 20)
        [0, 5]
        

        Would your program spot the occurrence of adjacent digits D and 6 in the expansion of 1/15 in base 20?

        1/15 (base 20) = 0.1(6D)… = 0.16D6D6D…

        >>> divide(20, 15)
        [1, 6, 13]
        

        Like

        • Frits's avatar

          Frits 2:48 pm on 2 September 2024 Permalink | Reply

          @Jim, the divide function has been made with the comment “(where k less than b)” so the first question I don’t understand. I don’t think I need to differentiate between recurring and non-recurring except for the valid 2nd point you make (divide(20, 15)).

          Here is the adjustment (assuming we have have to scan for only 2 “digits”):

          # does list <lst2> occur in list <lst1>
          isSubList = lambda lst1, lst2: any(lst1[i:i + len(lst2)] == lst2
                                             for i in range(len(lst1) - len(lst2) + 1))
          
          # return "digits" in base b in the fraction 1 / k (where k < b)
          # (not repeating "decimals") 
          def divide(b, k):
            assert b > k 
            r, s, dct = 1, [], dict()
            while True:
              p = r 
              (d, r) = divmod(r * b, k)
              s.append(d)
              if not r: 
                return s
              # repeating "decimals" encountered?  
              if r in dct: 
                # also suffix first "digit" of repetend as we have to look 
                # for a sequence of two "digits"
                return s if r == p else s + [dct[r]] 
              dct[p] = d
            
          # consider bases from 15 to 20 (base must be higher than 14)
          for b in range(15, 21):
            found1413, seen = 0, set()
            for k in range(2, b): 
              dgts = divide(b, k)
              # does list [14, 13] occur in <dgts>?
              if isSubList(dgts, [14, 13]):
                found1413 = 1
              seen |= set(dgts)
              
            if found1413:
              print(f"answer: {sorted(set(range(b)).difference(seen))}")
          

          Like

          • Jim Randell's avatar

            Jim Randell 4:15 pm on 2 September 2024 Permalink | Reply

            @Frits: It was the same point really. I was trying to show a case where the return value was obviously ambiguous. But I strayed outside the acceptable parameters of your function. I should have used a different example.

            Like

    • GeoffR's avatar

      GeoffR 11:38 am on 2 September 2024 Permalink | Reply

      @Jim:
      Can you please show how the first paragraph works to get an answer of 0.1245 with th same repeating digits? (as the main teaser is the second paragraph)

      Like

      • Jim Randell's avatar

        Jim Randell 12:02 pm on 2 September 2024 Permalink | Reply

        @GeoffR:

        Starting with 1 we perform the following calculations:

        (1 × 7) / 5 = 1 (remainder 2)
        (2 × 7) / 5 = 2 (remainder 4)
        (4 × 7) / 5 = 5 (remainder 3)
        (3 × 7) / 5 = 4 (remainder 1)

        At the end of these 4 steps we have written down 1254 and are about to start the next step with the remainder 1. But this is the same as the value we started with at the beginning, so we will just go through the same steps again.

        So the result is:

        1/5 [base 7] = 0. 1254 1254 1254 …

        >>> recurring(1, 5, base=7)
        Recurring(i='0', nr='', rr='1254')
        

        Like

    • Frits's avatar

      Frits 9:07 pm on 4 September 2024 Permalink | Reply

      Limiting the calls to divide().

      # return "digits" in base b in the fraction 1 / k (where k < b)
      # (not repeating "decimals") 
      def divide(b, k):
        assert b > k 
        r, s, dct = 1, [], dict()
        while True:
          p = r 
          (d, r) = divmod(r * b, k)
          s.append(d)
          if not r: 
            return s
          # repeating "decimals" encountered?  
          if r in dct: 
            # also suffix first "digit" of repetend as we have to look 
            # for a sequence of two "digits"
            return s if r == p else s + [dct[r]] 
          dct[p] = d
        
      seq = [14, 13]
      
      # consider bases to 20
      for b in range(max(seq) + 1, 21):
        for k in range(2, b):   
          # 14 = (r * b) // k
          r1 = (seq[0] * k) // b + 1
          (d2, r2) = divmod(r1 * b, k)  
          if d2 != seq[0]: continue
          (d3, r3) = divmod(r2 * b, k) 
          # seq[0] has to be followed by seq[1]
          if d3 != seq[1]: continue
          
          # check if first specified item is one of the "digits" in the fraction
          dgts = divide(b, k)
          if seq[0] not in dgts: continue
          seen = set(dgts)
          for k2 in range(2, b): 
            if k2 == k: continue
            seen |= set(divide(b, k2))
            
          print(f"answer: {sorted(set(range(b)).difference(seen))}")  
          break
      

      Like

  • Unknown's avatar

    Jim Randell 11:11 am on 29 August 2024 Permalink | Reply
    Tags: by: Simon Massarella   

    Teaser 2592: Inventive inventories 

    From The Sunday Times, 27th May 2012 [link] [link]

    It is known that there is just one 10-digit number that is “self-counting” in the sense that its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it and the tenth digit equalling the number of 0s in it.

    Similarly, a 9-digit number is “self-counting” if its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it (and with the 0s remaining uncounted).

    (a) What is the 10-digit self-counting number?
    (b) What is the highest 9-figure self-counting number?

    [teaser2592]

     
    • Jim Randell's avatar

      Jim Randell 11:12 am on 29 August 2024 Permalink | Reply

      This is puzzle is a variation on autobiographical numbers (or curious numbers), see: Puzzle #16, Enigma 476.

      Except in autobiographical numbers the digits (in order) usually count the number 0’s, then then numbers of 1’s, 2’s, etc.

      The following Python program runs in 386ms. (Internal runtime is 309ms).

      from enigma import (irange, decompose, join, printf)
      
      # generate self counting sequences
      def self_counting(k):
        js = (1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
        assert k == 10 or k in js
        # t of the k digits are counted
        for t in (irange(0, k) if k < 10 else [10]):
          # decompose the t digits into the k counted slots
          for ns in decompose(t, k, increasing=0, sep=0, min_v=0):
            # check the counting works
            if all(ns.count(j) == n for (j, n) in zip(js, ns)):
              yield ns
      
      # find length 10 and 9 self counting numbers
      for k in [10, 9]:
        for ns in self_counting(k):
          if (ns[0] == 0 and len(ns) > 1): continue  # skip leading zeros
          printf("[{k}] {ns}", ns=join(ns))
      

      Solution: (a) 2100010006; (b) 100000000.

      There is an additional self-counting sequence of size 9 and that is (0, 0, 0, 0, 0, 0, 0, 0, 0), but that does not give a viable 9-digit self-counting number (and even if it did we are looking for largest 9-digit self-counting number).

      The full list of self-counting sequences:

      1: 0, 1
      2: 00, 10
      3: 000, 100
      4: 0000, 1000
      5: 00000, 10000
      6: 000000, 100000
      7: 0000000, 1000000
      8: 00000000, 10000000
      9: 000000000, 100000000
      10: 2100010006

      If we bring the 0 to the front of the [[ js ]] array (at line 5), then we get the more usual base 10 autobiographical numbers.

      4: 1210, 2020
      5: 21200
      7: 3211000
      8: 42101000
      9: 521001000
      10: 6210001000

      And we see for the 10-digit self-counting number (where each of the digits is counted) we can calculate the 10-digit autobiographical number and move the leading digit to the end.

      Like

  • Unknown's avatar

    Jim Randell 12:52 am on 25 August 2024 Permalink | Reply
    Tags: ,   

    Teaser 3231: In his prime 

    From The Sunday Times, 25th August 2024 [link] [link]

    Once, on my grandson’s birthday, I asked him the following five questions:

    1. How many days are there in this month?
    2. How many Mondays are there in this month?
    3. How many “prime” days (i.e. 2nd, 3rd, 5th, …) are there in this month?
    4. How many of those prime days are Saturdays?
    5. How many letters are there when you spell the month?

    The total of the five answers was a prime number.

    Then I asked him the same questions the next day. No answer was the same as for the day before, but again the total of the five answers was prime.

    When I first asked the questions what was the month and day of the week?

    As set this puzzle has multiple solutions. However there is a unique answer for the birthday of the grandson (month and day of month).

    [teaser3231]

     
    • Jim Randell's avatar

      Jim Randell 1:30 am on 25 August 2024 Permalink | Reply

      Assuming the grandson answers each of the questions correctly, if the answer to each question must be different from that of the previous day, then the next day must be in a different month to the birthday.

      This Python program works backwards, considering the answers for pairs of adjacent months, until it finds the most recent viable solution. (Assuming the system locale is set to find appropriate day and month names).

      It runs in 68ms. (Internal runtime is 2.8ms).

      from datetime import (date, timedelta)
      from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, printf)
      
      # increment of 1 day
      day1 = timedelta(days=1)
      # function to check the weekday of a date
      weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)
      
      # answer the questions
      def results(y, m):
        # days in the month
        ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
        # 1. number of days in the month
        r1 = len(ds)
        # 2. number of Mondays
        r2 = icount(ds, weekday_is(1))
        # 3. number of prime days
        pds = list(d for d in ds if d.day in primes)
        r3 = len(pds)
        # 4. number of prime Saturdays
        r4 = icount(pds, weekday_is(6))
        # 5. number of letters in the month name
        r5 = len(ds[0].strftime('%B'))
        return (r1, r2, r3, r4, r5)
      
      # generate result values going back in time
      def generate(y, m):
        prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
        for (y, m) in repeat(prev_month, (y, m)):
          if y < 1753: break
          rs = results(y, m)
          t = sum(rs)
          yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))
      
      # consider adjacent months for (next-day, birthday)
      for (d1, d2) in tuples(generate(2024, 8), 2):
        # both totals are prime and no answers are the same
        if d1.tprime and d2.tprime and not any(x == y for (x, y) in zip(d1.rs, d2.rs)):
          # output solution
          nd = date(d1.y, d1.m, 1)
          bd = nd - day1
          printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))
          break  # only need the most recent solution
      

      Solution: The first time the questions were asked was on a Monday in February.

      Actually on Monday, 29th February 2016.

      The answers to the questions are: (29, 5, 10, 1, 8) giving a total of 53.

      The next day is Tuesday, 1st March 2016.

      And the answers to the questions are: (31, 4, 11, 2, 5) also giving a total of 53.

      If we go further back the dates: Friday, 29th February 2008 and Saturday, 1st March 2008 also work.

      And in fact all viable dates are Monday/Friday 29th February, and Tuesday/Saturday 1st March. So there are two possible answers to the puzzle.


      The published solution is: “February, Monday or Friday (apologies for the multiple answers)”.

      Like

      • Jim Randell's avatar

        Jim Randell 10:27 am on 25 August 2024 Permalink | Reply

        > [Frits suggests that solutions earlier than the most recent give the same answer]

        @Frits: Are you sure?

        Like

      • Jim Randell's avatar

        Jim Randell 7:26 am on 26 August 2024 Permalink | Reply

        I interpreted the condition “no answer was the same as for the day before” to mean that each answer given on the second day was different from the answer given to the same question on the previous day (and I think this is the most reasonable interpretation).

        However, if we take this condition to mean that there were no values given as answers on the second day that had also been given as answers on the first day, then we do find a unique solution to the puzzle.

        Here is my program adapted for this interpretation. (The condition at line 38 is changed).

        from datetime import (date, timedelta)
        from enigma import (Record, repeat, inc, first, icount, primes, unpack, tuples, intersect, printf)
        
        # increment of 1 day
        day1 = timedelta(days=1)
        # function to check the weekday of a date
        weekday_is = lambda n: (lambda d, n=n: d.isoweekday() == n)
        
        # answer the questions
        def results(y, m):
          # days in the month
          ds = first(repeat(inc(day1), date(y, m, 1)), count=(lambda d, m=m: d.month == m))
          # 1. number of days in the month
          r1 = len(ds)
          # 2. number of Mondays
          r2 = icount(ds, weekday_is(1))
          # 3. number of prime days
          pds = list(d for d in ds if d.day in primes)
          r3 = len(pds)
          # 4. number of prime Saturdays
          r4 = icount(pds, weekday_is(6))
          # 5. number of letters in the month name
          r5 = len(ds[0].strftime('%B'))
          return (r1, r2, r3, r4, r5)
        
        # generate result values going back in time
        def generate(y, m):
          prev_month = unpack(lambda y, m: (y, m - 1) if m > 1 else (y - 1, 12))
          for (y, m) in repeat(prev_month, (y, m)):
            if y < 1753: break
            rs = results(y, m)
            t = sum(rs)
            yield Record(y=y, m=m, rs=rs, t=t, tprime=(t in primes))
        
        # consider adjacent months for (next-day, birthday)
        for (d1, d2) in tuples(generate(2024, 8), 2):
          # both totals are prime and no answers are the same
          if d1.tprime and d2.tprime and not intersect([d1.rs, d2.rs]):
            # output solution
            nd = date(d1.y, d1.m, 1)
            bd = nd - day1
            printf("birthday = {bd} ({dow}) {d2.rs}; next day = {nd} {d1.rs}", dow=bd.strftime('%A'))
        

        Note: Apparently this is not the interpretation intended by the setter. They just didn’t realise that there were multiple solutions to the puzzle.

        Like

        • Ruud's avatar

          Ruud 5:05 pm on 26 August 2024 Permalink | Reply

          That’s an interesting interpretation that indeed leads to a unique solution.
          In my code just change
          if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
          into
          if set(counts1) & set(counts2) == set():
          to get the unique result.

          Like

      • Frits's avatar

        Frits 12:02 pm on 28 August 2024 Permalink | Reply

        @Jim, please add a comment to explain the hardcoded 1753 value

        Like

    • Ruud's avatar

      Ruud 1:13 pm on 25 August 2024 Permalink | Reply

      It is obvious that the birthday must be at the end of a month to make the answer to the month name different. So we can just search by year/month. As the grandchild still has a living grandfather, I assume that the grandchild must be born after 1939. So I just check for all years between 1940 and 2024 and all months.

      It turns out that there are 6 possible solutions in this timeframe. And the month is unique, but the day of the week is ambiguous (there are two possibilities).

      import calendar
      
      
      def is_prime(n):
          if n < 2:
              return False
          if n == 2:
              return True
          if not n & 1:
              return False
      
          for x in range(3, int(n**0.5) + 1, 2):
              if n % x == 0:
                  return False
          return True
      
      
      def counts(year, month):
          number_of_days = calendar.monthrange(year, month)[1]
          number_of_mondays = 0
          number_of_prime_days = 0
          number_of_prime_saturdays = 0
          weekday = calendar.weekday(year, month, 1)
          for day in range(1, number_of_days + 1):
              number_of_mondays += weekday == 0
              number_of_prime_days += is_prime(day)
              number_of_prime_saturdays += weekday == 5 and is_prime(day)
              weekday = (weekday + 1) % 7
          number_of_letters = len(calendar.month_name[month])
          return [number_of_days, number_of_mondays, number_of_prime_days, number_of_prime_saturdays, number_of_letters]
      
      
      for year in range(2024, 1940, -1):
          for month in range(1, 13):
              counts1 = counts(year, month)
              if is_prime(sum(counts1)):
                  next_month = (month % 12) + 1
                  next_year = year + (month == 12)
                  counts2 = counts(next_year, next_month)
                  if is_prime(sum(counts2)):
                      if all(answer1 != answer2 for answer1, answer2 in zip(counts1, counts2)):
                          day = calendar.monthrange(year, month)[1]
                          print(f"{calendar.month_name[month]:10} {calendar.day_name[calendar.weekday(year,month,day)]} ({year:4}-{month:02}-{day:02})")
      

      Like

  • Unknown's avatar

    Jim Randell 10:18 am on 22 August 2024 Permalink | Reply
    Tags: by: L Poulter   

    Brain-Teaser 777: Feeler gauges 

    From The Sunday Times, 6th June 1976 [link]

    I have half-a-dozen feeler gauges on a ring like keys on a key ring. They are attached in a certain order and by selecting a single gauge or combinations of adjacent gauges it is possible to measure from 1 thou to 31 thous of an inch in steps of 1 thou.

    If I remove two adjacent gauges, replace them with a single gauge and rearrange the five on the ring I can now measure from 1 thou to 21 thous in steps of 1 thou with these five gauges by again selecting a single gauge or combinations of adjacent gauges.

    What are the thicknesses of the gauges and the order of arrangement on the ring in each case? (Start with gauge of unit thickness and then its thinner neighbour for each of the sets).

    [teaser777]

     
    • Jim Randell's avatar

      Jim Randell 10:20 am on 22 August 2024 Permalink | Reply

      This is another puzzle involving magic circles (see: Teaser 1986Enigma 985Puzzle #171, Teaser: Circular Tour).

      This Python program uses the routines for generating magic circles of a specified size that I’ve previously developed for the other puzzles.

      It runs in 72ms. (Internal runtime is 4.2ms).

      from magic_circles import magic_circle
      from enigma import (cproduct, printf)
      
      # make magic circles of size 5 and 6
      (m5s, m6s) = (list(magic_circle(n)) for n in (5, 6))
      
      # choose the circles
      for (m5, m6) in cproduct([m5s, m6s]):
      
        # find the difference between the circles
        ds = set(m6).difference(m5)
        # there should be 2 adjacent items
        if not (len(ds) == 2): continue
        (d1, d2) = (m6.index(d) for d in ds)
        if not ((d1 - d2) % 6 in {1, 5}): continue
      
        # output solution
        printf("6 set = {m6}; 5 set = {m5}")
      

      Solution: The 6-set is: (1, 3, 2, 7, 8, 10). The 5-set is: (1, 3, 10, 2, 5).


      There is only one magic circle of size 5:

      (1, 3, 10, 2, 5)

      There are 5 magic circles of size 6:

      (1, 3, 6, 2, 5, 14) [*]
      (1, 3, 2, 7, 8, 10) [*]
      (1, 2, 5, 4, 6, 13)
      (1, 7, 3, 2, 4, 14)
      (1, 2, 7, 4, 12, 5)

      Only the ones marked [*] have 4 values in common with the size 5 magic circle, and only the second one has the two values to be removed in adjacent positions.

      Like

      • Frits's avatar

        Frits 10:28 am on 23 August 2024 Permalink | Reply

        @Jim, do you assume that all the gauges are of different widths? If not then the “2 adjacent items” code doesn’t seem to be accurate.

        Like

        • Jim Randell's avatar

          Jim Randell 10:39 am on 23 August 2024 Permalink | Reply

          @Frits: With k gauges we can use them all together (1 way) or we can start with any of the k gauges and use between 1 and k − 1 of the gauges (going clockwise say).

          This gives a total of:

          n(k) = 1 + k(k − 1) = k^2 − k + 1

          possible selections.

          For k = 6 we get n(6) = 31 selections.

          So if we can measure all values between 1 and 31 all the selections must give different total values, in particular all the single gauges must give different values, and so they must all be different.

          Similarly for k = 5 we get n(5) = 21 selections.

          Like

    • Frits's avatar

      Frits 4:53 pm on 22 August 2024 Permalink | Reply

      I discovered I already had some code stored on my PC for this puzzle.

      Arthur Vause has made a blog entry on this Brain Teaser:

      [https://arthurvause.blogspot.com/2014/06/feeler-gauges-and-magic-circles.html]

      Like

  • Unknown's avatar

    Jim Randell 11:18 am on 20 August 2024 Permalink | Reply
    Tags:   

    Brain Teaser: Circular tour 

    From Sunday Times Brain Teasers 1974 [link]

    Arley, Barley, Carley, Darley, Earley and Farley are six villages connected, in that order, by a circular bus service. A passenger is allowed to board at any village and alight at any other or complete the whole circuit. The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.

    Arley to Barley is 1 mile. The distance from Farley to Arley is greater than that from Barley to Carley but less than that from Earley to Farley.

    What is the distance from Earley to Farley?

    This puzzle is taken from the book Sunday Times Brain Teasers (1974), but it is not a puzzle that originally appeared in The Sunday Times.

    [teaser-book-1974-p95]

     
    • Jim Randell's avatar

      Jim Randell 11:20 am on 20 August 2024 Permalink | Reply

      We have encountered puzzles involving magic circles before (see: Teaser 1986, Enigma 985, Puzzle #171), and developed tools for generating them

      This Python program considers magic circles of size 6, and then looks for ones that meet the specified requirements.

      It runs in 75ms. (Internal runtime is 4.1ms).

      from magic_circles import magic_circle
      from enigma import printf
      
      # look for a size 6 magic circle (including reflections)
      for ds in magic_circle(6, refl=1):
        # distance AB = 1
        assert ds[0] == 1
        # distance EF > distance FA > distance BC
        if not (ds[4] > ds[5] > ds[1]): continue
        # output solution
        printf("distance EF = {ds[4]} [ds = {ds}]")
      

      Solution: The distance from Earley to Farley is 12 miles.

      And we have the following distances around the circle:

      A→B = 1
      B→C = 2
      C→D = 7
      D→E = 4
      E→F = 12
      F→A = 5

      Like

      • Ruud's avatar

        Ruud 2:09 pm on 21 August 2024 Permalink | Reply

        A bit verbose and certainly very brute force:

        import itertools
        
        ab = 1
        for bc, cd, de, ef, fa in itertools.permutations(range(2, 20), 5):
            ac = ab + bc
            ad = ac + cd
            ae = ad + de
            af = ae + ef
            bd = bc + cd
            be = bd + de
            bf = be + ef
            ba = bf + fa
            ce = cd + de
            cf = ce + ef
            ca = cf + fa
            cb = ca + ab
            df = de + ef
            da = df + fa
            db = da + ab
            dc = db + bc
            ea = ef + fa
            eb = ea + ab
            ec = eb + bc
            ed = ec + cd
            fb = fa + ab
            fc = fb + bc
            fd = fc + cd
            fe = fd + de
        
            if ef > fa > bc and af+fa == 31:
                if {ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe} == set(range(1, 31)):
                    print(ab, ac, ad, ae, af, bc, bd, be, bf, ba, cd, ce, cf, ca, cb, de, df, da, db, dc, ef, ea, eb, ec, ed, fa, fb, fc, fd, fe)
                    print(ef)
        

        Like

    • Lise Andreasen's avatar

      Lise Andreasen 10:27 pm on 20 August 2024 Permalink | Reply

      So… The bus travels 31 miles on 1 circuit. And there’s also 2 villages, 31 miles apart on the circuit. Is this the distance from a village to itself?

      Like

      • Jim Randell's avatar

        Jim Randell 8:14 am on 21 August 2024 Permalink | Reply

        That’s right. A complete circuit is 31 miles, but we can also travel all the distances between 1 and 30 miles.

        A→B = 1; B→A = 30
        B→C = 2; C→B = 29
        A→C = 3; C→A = 28
        D→E = 4; E→D = 27
        F→A = 5; A→F = 26
        F→B = 6; B→F = 25
        C→D = 7; D→C = 24
        F→C = 8; C→F = 23
        B→D = 9; D→B = 22
        A→D = 10; D→A = 21
        C→E = 11; E→C = 20
        E→F = 12; F→E = 19
        B→E = 13; E→B = 18
        A→E = 14; E→A = 17
        F→D = 15; D→F = 16

        Like

        • Lise Andreasen's avatar

          Lise Andreasen 6:29 pm on 21 August 2024 Permalink | Reply

          Just an odd way to describe the 31 miles “distance”.

          “The distances from any village to any other village on the route are all different and all an exact number of miles, consisting of every possible whole number from 1 mile up to the distance for the whole circuit.”

          Like

    • GeoffR's avatar

      GeoffR 9:48 am on 21 August 2024 Permalink | Reply

      There are 6 single trips between villages and 6 trips for each of 2,3,4 and 5 bus stops between villages e.g. AB, BC, CD, DE, EF, FA for single stops between villages. There is only 1 circular bus trip visiting all 6 villages i.e. AB + BC + CD + DE + EF + FA.
      In total, therefore, there are 5 X 6 + 1 = 31 total bus trips.
      This MiniZinc solution enumerates all possible bus trips.

      % A Solution in MiniZinc
      include "globals.mzn";
       
      % Villages are A,B,C,D,E,F
      
      % Assumed upper bounds of six distances between villages
      var 1..15:AB; var 1..15:BC; var 1..15:CD; var 1..15:DE; var 1..15:EF; var 1..15:FA;
      
      constraint all_different ([AB, BC, CD, DE, EF, FA]);
      
      constraint FA > BC /\ FA < EF;
      constraint AB == 1; 
      
      % There are 31 possible distances between villages, as shown below:
      var set of int: soln_nums == {AB, BC, CD, DE, EF, FA,  % 1 stop
      AB+BC, BC+CD, CD+DE, DE+EF, EF+FA, FA+AB,              % 2 stops
      AB+BC+CD, BC+CD+DE, CD+DE+EF, DE+EF+FA, EF+FA+AB, FA+AB+BC,  % 3 stops
      AB+BC+CD+DE, BC+CD+DE+EF, CD+DE+EF+FA, DE+EF+FA+AB, EF+FA+AB+BC, FA+AB+BC+CD, % 4 stops
      AB+BC+CD+DE+EF, BC+CD+DE+EF+FA, CD+DE+EF+FA+AB, DE+EF+FA+AB+BC, % 5 stops
      EF+FA+AB+BC+CD, FA+AB+BC+CD+DE, 
      AB+BC+CD+DE+EF+FA};  % 6 stops
      
      set of int: req_nums = 1..31;
       
      constraint soln_nums == req_nums;
      
      constraint card(soln_nums) == AB + BC + CD + DE + EF + FA;
      
      solve satisfy;
      
      output["[AB, BC, CD, DE, EF, FA] = " ++ show( [AB, BC, CD, DE, EF, FA] )
      ++"\n" ++ "Distance from Earley to Farley =  "  ++ show(EF) ++ " miles."];
      
      % [AB, BC, CD, DE, EF, FA] = [1, 2, 7, 4, 12, 5]
      % Distance from Earley to Farley =  12 miles.
      % ----------
      % ==========
      
      
      

      Like

    • Ruud's avatar

      Ruud 11:24 am on 22 August 2024 Permalink | Reply

      A bit less verbose:

      import itertools
      
      succ = dict(zip("abcdef", "bcdefa"))
      
      for x5 in itertools.permutations(range(2, 20), 5):
          dist = dict(zip("ab bc cd de ef fa".split(), [1, *x5]))
          for d in "abcdef":
              d1 = succ[d]
              for _ in range(4):
                  dist[d + succ[d1]] = dist[d + d1] + dist[d1 + succ[d1]]
                  d1 = succ[d1]
          if dist["ef"] > dist["fa"] > dist["ac"] and set(dist.values()) == set(range(1, 31)):
              print(dist["ef"])
      

      Like

    • Frits's avatar

      Frits 4:10 pm on 22 August 2024 Permalink | Reply

      Using my Puzzle #171 code but now using decomposition.

           
      from itertools import permutations
      
      # for a list with n numbers check if the set of sums of 1...n-1 adjacent items
      # (also circular) is complete (with n.(n-1) different sums)
      def allOccurOnce(s, ln):                                         
        sms = set(s)
        for i in range(ln):
          for j in range(2, ln):
            if (sm := sum((s * 2)[i:i + j])) in sms: 
              return False
            sms.add(sm)
        return True  
      
      # decompose <t> into <k> increasing numbers from <ns>
      def decompose(t, k, ns, s=[]):
        if k == 1:
          if t in ns:
            yield s + [t]
        else:
          for i, n in enumerate(ns):
            # make sure we don't overshoot
            if 2 * t < (2 * n + k - 1) * k: break
            yield from decompose(t - n, k - 1, ns[i + 1:], s + [n])
      
      N = 6
      T = N**2 - N + 1
      H = int(T // 2)
      
      # for a magic circle with N numbers and total sum T
      # the highest possible circle number is T - N(N-1)/2 which equals H + 1
      
      # exclude mandatory numbers 1 and 2 from the decomposition
      for dc in decompose(T - 3, N - 2, range(3, H + 2)):
        # weave in the number 2
        for p in permutations([2] + dc):
          p1 = (1, ) + p
          
          # distance EF > distance FA > distance BC
          if not (p1[4] > p1[5] > p1[1]): continue
          # can we make N.(N - 1) different sums?
          if not allOccurOnce(p1, N): continue
          print(f"answer: {p1[4]} miles")
      

      Like

  • Unknown's avatar

    Jim Randell 5:35 am on 18 August 2024 Permalink | Reply
    Tags:   

    Teaser 3230: Polytunnel 

    From The Sunday Times, 18th August 2024 [link] [link]

    I have extended my market garden by the addition of a polytunnel. The polyethylene cover is supported at intervals by identical sets of three vertical pillars supporting metal arcs, of negligible thickness, resting on the level ground on both sides. In each set, the highest pillar is in the middle of the cross-section, at the highest point of the tunnel. The other two pillars are of equal height, being three quarters of the height of the central pillar. These shorter pillars are positioned on each side, 2/11 of the ground-level width of the tunnel from each edge.

    Each metal arc is part of a circle (less than a semicircle), and the highest point is exactly 3m above the ground.

    What is the ground-level width of the polytunnel in cm?

    [teaser3230]

     
    • Jim Randell's avatar

      Jim Randell 5:36 am on 18 August 2024 Permalink | Reply

      By considering two right-angled triangles we can derive a linear equation for the depth of the centre of the arc below ground level (x), from which the width of the polytunnel (2w) can be determined.

      The triangles are indicated in the following diagram:

      This Python program (appropriately enough) uses the [[ Polynomial() ]] class from the enigma.py library to perform the calculations.

      It runs in 76ms. (Internal runtime is 139µs).

      from enigma import (Rational, Polynomial, sq, sqrt, printf)
      
      Q = Rational()
      
      # suppose the polytunnel has ground-level semi-width w
      # and the centre of the circle is a distance x below ground
      # we have:
      #
      #  r = x + 300
      #  r^2 = w^2 + x^2
      #  r^2 = (7w/11)^2 + (225 + x)^2
      
      fx = Polynomial('x')  # depth of origin
      fr = fx + 300  # radius of arc
      
      f1 = sq(fr) - sq(fx)  # = w^2
      f2 = sq(fr) - sq(fx + 225)  # = (7w/11)^2
      
      f = sq(Q(7, 11)) * f1 - f2  # equate values of w^2
      
      # solve f(x) = 0 for positive real x
      for x in f.roots(domain='F', include='0+'):
        # calculate width
        W = sqrt(f1(x)) * 2
        printf("polytunnel width = {W:g} cm [x = {x:g}]")
      

      Solution: The width of the polytunnel at ground level is 660 cm.

      The polynomial to determine the depth of the centre of the circular arc simplifies to:

      f(x) = 2x − 63

      From which we easily find the depth of the centre and the radius of the circle:

      x = 31.5
      r = 331.5

      And from these we calculate the semi-width of the polytunnel:

      w^2 = r^2 − x^2 = (r + x)(r − x)
      w^2 = 363 × 300 = 108900
      ⇒ w = 330

      So the total width of the polytunnel is 660 cm.

      Like

    • Frits's avatar

      Frits 11:24 am on 18 August 2024 Permalink | Reply

      I made my narrowing down routine from scratch.
      Of course there are more efficient ways to do this (I don’t know them by heart).

      from sys import float_info
      eps = float_info.epsilon
      
      # r = x + 300    # the centre of the circle is a distance x below ground
      # 49.w^2 - 117600.x - 17_640_000 = 0
      # 49.w^2 -  72600.x - 19_057_500 = 0
      
      f1 = lambda x: 17_640_000 + 117_600 * x
      f2 = lambda x: 19_057_500 +  72_600 * x
      
      mode = ""
      x = 100         # choose an arbitrarily starting value
      delta = 5       # increment/decrement value for variable x
      
      # find a value for "x" where both f1(x) and f2(x) are (almost) the same
      while True:
        v1, v2 = f1(x), f2(x)
        # do we have an solution where both values are (almost) the same?
        if abs(v2 - v1) <= eps:
          w = (2_400 * x + 360_000)**.5
          print(f"answer:  ground-level width = {round(w, 2)} cm")
          break
        
        if v1 < v2:
          if mode == "more": 
            delta /= 2
          x += delta
          mode = "less"
        else:
          if mode == "less": 
            delta /= 2
          x -= delta
          mode = "more"     
      

      Like

      • Frits's avatar

        Frits 11:34 am on 18 August 2024 Permalink | Reply

        The program was only made if you don’t want to analyse the problem till a solution is found.

        Like

    • GeoffR's avatar

      GeoffR 6:23 pm on 18 August 2024 Permalink | Reply

      % A Solution in MiniZinc
      include "globals.mzn";
      
      % X = half tunnel width, Y =  depth below ground, R = circle radius
      % All dustances in mm.
      
      % Assumed UB's for variables
      var 1..4500:R;  var 1..4000:X; var 1..1500:Y; 
      
      constraint R == 3000 + Y;  
      
      constraint X * X  + Y * Y == R * R;
       
      % (2250 + Y)^2 + (7/11 * X)^2 = R * R
      constraint 121 * R * R == 121 * ((2250 + Y) * (2250 + Y)) + (49 * X * X);
      
      solve satisfy;
      
      
      

      Like

  • Unknown's avatar

    Jim Randell 10:46 am on 15 August 2024 Permalink | Reply
    Tags:   

    Teaser 2623: Latecomer 

    From The Sunday Times, 30th December 2012 [link] [link]

    Imogen is having a New Year party tomorrow night and she has invited Madeline, hoping not to have a repeat of last year’s episode which completely spoilt the celebrations. Last New Year’s Eve Madeline had been due at a certain whole number of minutes past an hour but she was late, the number of minutes late being that same aforementioned “certain number of minutes” but with the digits in the reverse order. Madeline pointed out that at least the angle between the hands of the clock at the moment of her arrival was the same as it would have been when she was due.

    At what time was she due to arrive?

    [teaser2623]

     
    • Jim Randell's avatar

      Jim Randell 10:46 am on 15 August 2024 Permalink | Reply

      Madeline was expected to arrive at a time of xy minutes past a specified hour, but she was late, and arrived yx minutes later than her expected time. So yx (and xy) cannot be 00 (as then she would not be late).

      This Python program finds both possible solutions to the puzzle.

      It runs in 74ms. (Internal runtime is 3.6ms).

      from enigma import (Rational, irange, cproduct, nrev, printf)
      
      Q = Rational()
      
      # calculate angle between hands at time h:m
      # angles are between 0 (coincident) and 1 (opposite)
      def angle(h, m):
        (x, m) = divmod(m, 60)
        h = (h + x) % 12
        ah = Q(h + Q(m, 60), 6)
        am = Q(m, 30)
        a = abs(ah - am)
        return (2 - a if a > 1 else a)
      
      # consider possible scheduled arrival times
      for (h, m) in cproduct([irange(0, 11), irange(1, 59)]):
        a1 = angle(h, m)
        # calculate angle at actual arrival time
        a2 = angle(h, m + nrev(m, 2))
        # are angles the same?
        if a1 == a2:
          # output solution
          printf("expected arrival = {h:02d}:{m:02d} [angle = {a:.2f} min]", a=float(a1 * 30))
      

      There are two possible answers:

      Expected time = 11:43; Actual time = 11:43 + 34 minutes = 12:17
      Expected time = 5:43; Actual time = 5:43 + 34 minutes = 6:17

      Both of which are illustrated below, with the same shape indicating the identical angles between the hands:

      As the party in question is a New Years Eve party, presumably the setter intends us to choose the solution where Madeline was expected to arrive before midnight, but actually arrived after midnight (although this could easily have been specified in the problem text).

      Solution: Madeline was due to arrive at 11:43 pm.

      Like

  • Unknown's avatar

    Jim Randell 8:21 am on 13 August 2024 Permalink | Reply
    Tags:   

    Teaser 2586: Powerful dice 

    From The Sunday Times, 15th April 2012 [link] [link]

    George and Martha threw a die, noted the number of spots on the uppermost face, and entered that number in one of the boxes of a 3-by-3 grid of nine squares. They repeated the exercise eight more times resulting in a digit in each box.

    Then George looked at the three 3-digit numbers read across the rows and commented that each was a square or a cube. Martha looked at the three 3-digit numbers read down the columns and said the same was true for her numbers. Furthermore, their two sets of three numbers had only one in common.

    What (in increasing order) were the five different 3-digit numbers?

    [teaser2586]

     
    • Jim Randell's avatar

      Jim Randell 8:22 am on 13 August 2024 Permalink | Reply

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

      The following run file executes in 76ms. (Internal runtime of the generated program is 2.5ms).

      #! python3 -m enigma -rr
      
      SubstitutedExpression
      
      #  A B C
      #  D E F
      #  G H I
      
      --digits="1-6"
      --distinct=""
      
      --code="check = cached(lambda n: is_square(n) or is_cube(n))"
      
      # check rows and columns
      "check(ABC)"
      "check(DEF)"
      "check(GHI)"
      "check(ADG)"
      "check(BEH)"
      "check(CFI)"
      
      # there is exactly one number shared between the rows and columns
      "len(intersect([{ABC, DEF, GHI}, {ADG, BEH, CFI}])) = 1"
      
      # and there are five different numbers in total
      "len({ABC, DEF, GHI, ADG, BEH, CFI}) = 5"
      
      --answer="call(ordered, {ABC, DEF, GHI, ADG, BEH, CFI})"
      --template="rows = [ ABC DEF GHI ]; cols = [ ADG BEH CFI ]"
      --solution=""
      --verbose="1-H"
      

      Solution: The numbers entered in the box were: 121, 125, 216, 256, 512.

      We have:

      121 = 11^2
      125 = 5^3
      216 = 6^3
      256 = 16^2
      512 = 8^3

      512 appears as both a row and a column.

      The most likely scenario is:

      Then George’s rows would consist of both squares and cubes, and Martha could say the same about her columns even though they are actually all cubes.

      Swapping the rows and columns yields a second viable layout, but it seems unlikely George would note that his each of his rows was a square or a cube, when they are in fact all cubes.

      Like

      • ruudvanderham's avatar

        ruudvanderham 11:50 am on 13 August 2024 Permalink | Reply

        from istr import istr
        istr.repr_mode('int')
        squares=[i*i for i in range(10,32)]
        cubes=[i*i*i for i in range (5,10)]
        squares_cubes=istr(squares+cubes)
        
        solutions=set()
        for abc in squares_cubes:
            for def_ in squares_cubes:
                for ghi in squares_cubes:
                    horizontals={abc,def_,ghi}
                    verticals={abc[i]|def_[i]|ghi[i] for i in range(3)}
                    if all(vertical in squares_cubes for vertical in verticals):
                        horizontals_verticals= horizontals | verticals
                        if len(horizontals_verticals)==5:
                            solutions.add(tuple(sorted(horizontals_verticals)))
        print(solutions)
        

        Like

        • Ruud's avatar

          Ruud 7:07 pm on 13 August 2024 Permalink | Reply

          I forgot to test whether all digits were between 1 and 6.
          Here’s an improved version (same output):

          from istr import istr
          
          istr.repr_mode("int")
          squares = [i * i for i in range(10, 32)]
          cubes = [i * i * i for i in range(5, 10)]
          squares_cubes = [i for i in istr(squares + cubes) if all(j in range(1, 7) for j in i)]
          
          solutions = set()
          for abc in squares_cubes:
              for def_ in squares_cubes:
                  for ghi in squares_cubes:
                      horizontals = {abc, def_, ghi}
                      verticals = {abc[i] | def_[i] | ghi[i] for i in range(3)}
                      if all(vertical in squares_cubes for vertical in verticals):
                          horizontals_verticals = horizontals | verticals
                          if len(horizontals_verticals) == 5:
                              solutions.add(tuple(sorted(horizontals_verticals)))
          print(solutions)
          

          Like

          • Jim Randell's avatar

            Jim Randell 5:54 pm on 14 August 2024 Permalink | Reply

            @Ruud: I think you also need to add a test for “their two sets of three numbers had only one in common”. Your code would allow a repeated row or a repeated column.

            Like

            • Ruud's avatar

              Ruud 7:07 pm on 14 August 2024 Permalink | Reply

              @Jim
              Thanks for pointing this out. You are right.
              My updated code:

              from istr import istr
              
              istr.repr_mode("int")
              squares = [i * i for i in range(10, 32)]
              cubes = [i * i * i for i in range(5, 10)]
              squares_cubes = [i for i in istr(squares + cubes) if all(j in range(1,7) for j in i)]
              
              solutions = set()
              for abc in squares_cubes:
                  for def_ in squares_cubes:
                      for ghi in squares_cubes:
                          horizontals = {abc, def_, ghi}
                          verticals = {abc[i] | def_[i] | ghi[i] for i in range(3)}
                          if all(vertical in squares_cubes for vertical in verticals):
                              if len(horizontals & verticals) == 1:
                                  solutions.add(tuple(sorted(horizontals | verticals)))
              print(solutions)
              

              Like

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